Subject: hpff-doc: Expanded section/chapter on task parallelism

From: [email-masked]
Date: Tue, 23 Jul 96 16:33:30 EDT

---------------------------------------------------------------------------
[email-masked] is a mailing list for HPF 2.0 language specification
authors and editors.  Instructions for adding or deleting yourself from this
list appear at the bottom of this message.
---------------------------------------------------------------------------
Chuck, Rob and others:

I am appending the expanded section on task parallelism. It is formatted
as a chapter. Chuck - could you integrate it into the full chapter on
parallelism extensions, perhaps after you are done revising the ON. Also
I am counting on you or Rob to fill in the bnf (search for "CHUCK" for 
the location). 

jas

ps: It appears that there is a lot of macros described in the README
file (e.g. MAKE-HPF-CHAPTER) that I could not find at the ftp site.
This caused me a lot of confusion.

--------------------------------------------------------

% File: parallel-ext.tex

% Contents:
% Approved Extensions for data-parallel computation for HPF 2.0
% document, including
%	ON
%	TASK
%	RESIDENT

% Revision history:
% May-10-96	Created by Charles Koelbel, Rice University
%		(from HPF 2.0 proposals)

\chapter{Approved Extensions for Data and Task Parallelism}
\label{ch-parallel-ext}

{\em
Comments on this chapter should be directed to 
Chuck Koelbel ({\tt [email-masked]}),
Jaspal Subhlok ({\tt [email-masked]}),
and {\tt [email-masked]}.
Please use ``{\tt Comments on Extended Parallelism}'' as the {\tt Subject:}
line.
\par
}

\section{The TASK\_REGION Directive}
\label{sec-tasking}

Task parallelism is expressed implicitly in HPF by mapping data 
objects onto subsets of processors and adding assertions that
allow concurrent execution of different  code blocks on different
processor subsets. A data objects is mapped to a processor subset
by distribution onto a 
subsection of a processor arrangement.
Execution on a subset of processors is specified by using an 
{\tt ON} directive. This section introduces a {\tt TASK\_REGION}
directive that allows the user to implicitly specify that
disjoint processor subsets can execute blocks of code concurrently.
  
A {\tt TASK\_REGION} construct is used to assert that a block of code 
satisfies the following set of constraints.
 All lexically outermost {\tt ON} blocks
inside a task region must have a {\tt RESIDENT} attribute
implying that all  data accessed inside them is mapped to the
corresponding processor subset. Further,
the code inside two such {\tt ON} blocks must not have interfering
I/O. Under these constraints, two such {\tt ON} blocks  
 can safely execute concurrently if they execute on disjoint
processor subsets.

\subsection{Syntax of the TASK\_REGION Directive}

[CHUCK : Could  you replace this with a BNF - I suspect
 it will take  you 5 mins and will take me much longer]

A task region is a single entry region delimited by:
\CODE
!HPF$ TASK REGION
  ......
!HPF$ END TASK REGION
\EDOC

\subsection{Semantics of the TASK\_REGION Directive}

The task region directive is a way for the programmer to assert
that a section of code satisfies a set of conditions. The compiler
is expected to use these assertions to generate task parallel code.
We will refer to a block of code enclosed by a 
{\tt TASK\_REGION ... END TASK\_REGION} pair as a ``task region''.

A task region can contain blocks of code that are directed to execute {\tt ON} 
processor subsets.  All other code executes on a subset that 
contains all executing processors.  Every {\tt ON} block at the outermost
nesting level (i.e.  not inside another {\tt ON} block or another task 
region) inside a 
task region is defined as a ``lexical task''.  Every execution instance of 
a lexical task is defined as an ``execution task'' and will also be
referred to
as just ``task'' when the distinction is clear from the context.

The following restrictions must hold  inside a task region:  
\begin{itemize}
\item Every {\tt ON} block corresponding to a lexical task must
have the {\tt RESIDENT} attribute.
This means that, for  reading a variable inside an execution task,
the executing processor subset for the task 
(also referred to as {\em active processors}) 
must own at least one copy of the variable, and for writing, they must own 
all copies of that variable.

\item An I/O operation inside an
execution task may interfere with an I/O operation inside
another execution task if and only if the two tasks execute on
identical subsets of  processors. Note that  two execution tasks
can be  instances of the same or different lexical tasks.
In general, two I/O operations interfere if they access the same
file or unit. The conditions for interference of I/O operations are
detailed in Section~\ref{sub-independent} in the context of the
{\tt INDEPENDENT} directive.

\end{itemize}

\subsection{Execution Model and Usage}

A task region does not introduce a fundamentally new execution model.  
However, the asssertions implicit in a task region imply that only
the specified executing processors of an execution task need to
participate in its execution, and that other processors can skip its
execution.  A processor executing a task 
region participates in the execution of all tasks
executing on a processor subset that it belongs to and
does not participate in the  execution of tasks executing 
on processor subsets that it does not belong to. 
Code outside lexical tasks is 
executed as normal data parallel code by all processors.  The access 
restrictions for a task region guarantee that the results obtained
by this execution paradigm will be consistent with pure data
parallel execution of a task region.

A task region presents a simple yet powerful model to write integrated
task and data parallel programs. We illustrate three basic computation
structures in which task parallelism can be effectively exploited
with this model.

\begin{enumerate}

\item {\em Parallel sections:} 
A task region can be used to divide the available processors into 
disjoint sets for performing independent computations, simulating
what is often referred to as {\em parallel sections}. This form of
task parallelism is relatively straightforward and useful in many
application scenarios, an example being multiblock applications.
The task region simply contains
a sequence of {\tt RESIDENT ON} blocks on disjoint processor subsets. 
Note that the division of processors among subsets can be dynamic,
that is, it can be in terms of other variables computed during execution.

\item {\em Nested parallelism:}
Task regions can be nested, and in particular, a subroutine call made
from an execution task can further subdivide the executing (or active)
processors using another task region directive. This allows the exploitation
of nested parallelism. An example is the implementation of
dynamic tree structured divide and conquer computations. As a 
specific example,
{\em quicksort} can be implemented by  recursively 
partitioning the input array of keys 
around a pivot and  assigning proportionate number of processors
to the two new arrays obtained as a result of partitioning.

\item {\em  Data parallel pipelines:}
Task regions can be used to implement 
pipelined data parallel computations. We will
illustrate this with a 2 dimensional fast Fourier transform (2D FFT)
computation. The first stage of a 2D FFT reads a two dimensional matrix
and performs a 1 dimensional FFT on each row of the matrix. The second
stage performs a 1 dimensional FFT on each column of the matrix and generates
the final output. In a pipelined data parallel implementation of this
form of 2D FFT, the two stages are mapped on to disjoint subsets of processors.
Task and data parallel code for a 2D FFT, along with a brief
description, is included in Section~\ref{sec:2DFFT}.

\end{enumerate}

\subsection{Implementation}
A task region is simply an assertion about a code block and the
exploitation of task parallelism is at least partially dependent
on the compilation scheme. While the specifics of how task parallelism
is exploited will be strongly dependent on the parallel system
architecture, the compiler, and the  underlying communication 
model, we will point out some  important considerations and
illustrate task parallel code generation with an example. We primarily
address distributed memory machines using a  message passing 
communication and synchronization model, but will point out
some of the important issues relating to shared memory implementations.

\subsubsection{Localized computation and communication}
It is of central importance that computation and communication
inside an executing task should not  involve any processors
other than those directed to execute the task in the
relevant {\tt ON} clause.

On entry to a lexical task, the compiler has to insert checks so
that the processors not in the relevant subset jump to the code
following the task. Since an execution task cannot access data
outside of the active executing processor subset, no communication
needs to be generated between the relevant executing processors
and other processors. In a message passing model, a communication
generation algorithm that only generates necessary messages will
naturally achieve the desired results. However, some communication
schemes can involve generation of empty messages between processors
that do not communicate and it is important to ensure that empty
messages are not generated between active processors of an executing
task and other processors.

A communication model that uses barriers for synchronization (in
shared or distributed memory machines) must ensure that all barriers
inside an executing task are subset barriers that only span the 
active processors. An implementations may also need to include a
subset barrier on entry and exit to an executing task for consistency
of data accesses inside and outside an executing task. In general,
the compilation framework has to ensure the consistency of data
accesses inside and and outside an executing tasks and this can be done
in the context of  virtually any synchronization scheme in a shared
or distributed memory environment.

\subsubsection{Replicated computations}
All computations exclusively involving replicated variables should be 
replicated on all executing processors.
A simple alternative is that  one processor performs the
computation and broadcasts the results to all processors. While such
replication
is generally profitable in HPF anyway, it has additional importance
in a task region since the communication generated by a broadcast can
cause additional synchronization that may interfere with
task parallelism.

\subsubsection{Implications for I/O}
In some parallel system implementations, I/O is performed through
a single node of the system. Task parallelism in the presence of 
I/O assumes that all nodes can perform I/O independently and this
paradigm has to be supported, although it is not necessary that 
each node be able to physically perform all I/O operations independently.
One simple solution is to have a single
designated I/O processor that performs
all I/O but is not considered an executing processor and hence does 
not have any execution related dependences.

\subsubsection{SPMD or MIMD code generation}
Another issue for the compiler is whether or not the same code image
should execute on all processors. Since different processor groups 
may need different variables, a naive SPMD implementation is likely
to be wasteful of memory since it must allocate all variables on
all processors. This can be addressed by dynamic memory allocation,
but at the cost of added complexity. Using different code images for
different processor subsets is another solution which leads to
significant added complexity.

\subsection{Example: 2-D FFT}
\label{sec:2DFFT}

This sections shows the use of task parallelism to build
a pipelined data-parallel 2-dimensional FFT and illustrates 
the compilation of task parallelism by  showing
SPMD code generated from the HPF program.

The basic  sequential 2DFFT code is as follows:
\CODE
      REAL, DIMENSION(n,n) :: a1, a2

      DO WHILE(.true.)
          READ (unit = 1, end = 100) a1
          CALL rowffts(a1)
          a2 = a1
          CALL colffts(a2)
          WRITE (unit = 2) a2
          CYCLE
100       CONTINUE
          EXIT
      ENDDO
\EDOC

To write a pipelined task and data parallel 2D FFT
in HPF, the code is slightly modified and several HPF
directives are added.
First,  variables {\tt a1} and {\tt a2} are distributed onto disjoint
subsets of processors, and then a task region is used to create two
lexical tasks to do {\tt rowffts}  and {\tt colffts} on different
subsets of processors. The assignment {\tt a2 = a1} in the task region
specifies transfer of data between the tasks. A new variable {\tt done1}
is introduced to store the termination condition.
The modified code is as follows:

\CODE
        REAL DIMENSION(n,n) :: a1,a2
        LOGICAL done1
!HPF$   PROCESSORS procs(8) 

!HPF$   DISTRIBUTE a1(block,*) ONTO procs(1:4)
!HPF$   DISTRIBUTE a2(*,block) ONTO procs(5:8)

!HPF$   TEMPLATE, DIMENSION(4), DISTRIBUTE(BLOCK) ONTO procs(1:4) :: td1
!HPF$   ALIGN WITH td1(*) :: done1
                 
!HPF$   TASK REGION
        done1 = .false.
        DO WHILE (.true.)
!HPF$       ON HOME(procs(1:4)) BEGIN, RESIDENT
              READ (unit = iu,end=100) a1
              CALL rowffts(a1)
              GOTO 101
    100       done1 = .true.
    101       CONTINUE
!HPF$       END ON
            
            IF (done1) EXIT
            a2 = a1

!HPF$       ON HOME(procs(5:8)) BEGIN, RESIDENT
               CALL colffts(a2)
               WRITE(unit = ou) a2
!HPF$       END ON
        ENDDO
!HPF$   END TASK REGION
\EDOC

Finally, we show simplified SPMD code generated
for each processor. We assume
a  message passing model where sends are asynchronous and nonblocking
and receives block until the data is available. We use a simple memory
model where variable declarations are identical across
all processors even though some variables will be referenced only on
subsets of the processors.
A shadow variable {\tt done1\_copy} is created by the compiler to
transfer information from processor subset 1 to processor subset 2
about termination of processing. The code is as follows:

\CODE
        REAL DIMENSION(n/4,n) :: a1, a2
        BOOLEAN done1

C       Following are compiler generated variables       
        BOOLEAN done1_copy
        BOOLEAN inset1, inset2

C     
C       Following magic compiler function call is to set the variables
C       inset1 and  inset2 to .true. for subset1 and subset 2 processors
C       respectively, and .false. otherwise.
C
        CALL intialize_tasksets(inset1,inset2)

C       Code for processor subset 1
        IF (inset1)
           done1 = .false.
           DO WHILE (.true.)
              READ (unit = 1,end=100) a1
              CALL rowffts(a1)
              GOTO 101
    100       done1 = .true.
    101       CONTINUE
              _send(done1,procs(5:8))
              IF (done1) EXIT
              _send(a1,proces(5:8))
           ENDDO
         ENDIF

C       Code for processor subset 2
        IF (inset2)       
           DO WHILE(.true.)
              _receive(done1_copy,procs(1:4))
              IF (local_done1) EXIT
              _receive(a2,procs(1:4))
              CALL colffts(a2)
              WRITE (unit = 2) a2
           ENDDO
        ENDIF
\EDOC

{\tt \_send} and {\tt \_receive} are  communication calls to
transfer variables between subsets of processors. Program execution
until the end of input is as follows.
Subset 1 processors repeatedly read input, compute
{\tt rowffts}, and send the computed output as well as {\tt done1} flag
(which is not set) to subset 2 processors. The subset 2 processors
receive the flag and the data set, compute
{\tt colffts} and write the results to the output. When the end of input is
reached, subset 1 processors set the flag {\tt done1} , send it and terminate
execution. Subset 2 processors receive the flag, recognise that the end of
input has been reached, and terminate execution.

---------------------------------------------------------------------------
To (un)subscribe to this list, send mail to [email-masked].
Leave the subject line blank, and in the body put the line
(un)subscribe <email-address>
---------------------------------------------------------------------------