
\begin{document}

\title{Task Parallelism in Fortran 90}
\author{\bf DRAFT}
\date{}
\maketitle
\thispagestyle{empty}

\section{Need for procedure level specifications}
Fortran 90 is designed to have the ability to specify fine grain parallelism.
A parallelizing compiler
can easily exploit this parallelism - the exact approach taken would 
 depend on the machine architecture. However the
high level computation structure, that may not be a simple data parallel
model can be difficult to infer from a program. In a large 
class of applications it is important to identify the coarse
grain parallelism available as different subroutines that can execute 
in parallel. 
     
Some of the situations where it is profitable to allocate processors
to different parts of the program, instead of purely relying on 
data parallelism, are as follows:

\begin{enumerate}

\item Real time applications where the problem size is relatively small
but new input data has to be processed and output has to be generated
in real time. Thus a large number of relatively small problems have to
be solved repeatedly.

\item When the processor array size is so large that it is not
profitable to use all the processors on a single module in the program
at any given time. The additional compute power can potentially 
be used for parallel execution between different modules.

\end {enumerate}
\section{Requirements of parallelism  description}
We use the following guidelines to ensure that description of
subprogram level parallelism can be expressed and implemented
with ease and does not inhibit portability of programs written
in standard Fortran 90.


\begin{itemize}
\item
The programs would be legal Fortran 90 programs. Thus all procedure
level parallelism description will be in the form of special comments.
(also referred to as directives)
\item
Each node for higher level parallelism would be a subprogram,
that is a subroutine or a function. Since a subprogram is the unit of
code that can be conveniently assigned to a set of processors,
it is natural and simple to do program partitioning at subprogram
level.

\item 
Determinism: Every syntactically correct program description must
be deterministic. However, incorrect directives might lead to
incorrect answers which will differ from the answers obtained
by running the program by ignoring the directives.  

\item
Deadlock: It is entirely possible that a faulty parallelism description
could lead to a program that would deadlock, where the original
sequential program is deadlock free. The compiler would catch most
of the potential deadlock conditions.

\item
All procedures that are units of parallelism must have explicit 
input and output parameters and be side effect free otherwise.
This restriction allows us to exploit available parallelism
without analysis of dependence between subroutines. Since precise
dependence analysis between procedure calls is complex and 
intractable in general, we consider such a restriction necessary.
The input and output parameters can be array sections in Fortran
90 style.
\end{itemize}

\section{Compiler Directives}

\subsection{Overview}

All parallelism is expressed as {\em parallel blocks}.
A section of code starting with {\tt begin parallel} and ending with
{\tt end parallel} directives constititutes a parallel block.
 A parallel block
can contain  loops with constant bounds and subprogram\footnote{subroutine 
or a function}  calls, and nothing else.

Every subprogram inside a  parallel block has an
{\tt input} and an {\tt output} parameter list  attached to it.
The subprogram  must be side effect free and its relationship to the
calling program should be limited to
reading from input parameters and writing to output
parameters.

An {\tt input} or {\tt output} directive has a list of
parameters. Each parameter can be a scalar variable,
array, or an  array section. The array sections should be completely
determined by constants
and induction variables of loops that are nesting the statement inside
the parallel block.

Additionally  statements inside a parallel block can have {\tt blocksize},
 {\tt weight}, and 
 {\tt processors} directives attached to them. These do not affect the
semantics of the program but help the compiler with distibuting the
subprograms over the processor array.

\subsection{Parallel blocks}
A {\tt begin  parallel}...{\tt end parallel}
pair specifies a parallel block
over which every subprogram is to be treated as an independent
module that shares data only through parameters. Statements inside such 
a parallel block must be subprogram calls, loop headers or loop delimiter
statements. All loops must have constant bounds\footnote{This can be extended
to variables, that can be determined to be constants by compiler constant
propagation, but a static number is necessary for efficient partitioning and
scheduling}.

\begin{verbatim}
C$   begin parallel
       .
       .
     body consisting of subprogram
     calls, loops and other directives
       .
       .
C$   end parallel
\end{verbatim}

\subsection{Input and  output parameters}
Subprograms inside the scope of a parallel block have {\tt input} and
{\tt output} directives that precisely determine the interaction between
the calling program and the called subprogram. Every variable in the 
calling program, whose value at the call site may be potentially
used by the called subprogram, should be added to the input parameter
list. Similarly, every variable in the calling program, whose value
may be modified as a result of the called subprogram, should be included
in the output parameter list.

A variable in the input or output parameter list can be a scalar, an array,
or an array section. An array section must be a legal Fortran90 array
section, with the additional restriction that all the bounds and step
sizes must be constant or a function of the loop induction variables
of loops inside the parallel block. 

To enable the compiler to do subprogram
level parallelization effectively, every subroutine should have an {\tt input}
and an {\tt output} directive. If there are no input or output
parameters, the list of parameters should be left empty, but the directive
should still be included.
If an input or
output directive is missing, the compiler will analyze
the routines and
determine the parameters conservatively.\footnote{This feature will not
be supported by the compiler in the beginning, potentially leading to
significantly reduced exploitation of
parallelism, if any input or output parameter list is missing}.
A future version of the compiler would warn the user if the compiler
analysis arrived at a set of input or output parameters, which are different
from those specified by the programmer.

\subsection{Directives for modeling execution behavior}
We provide three   directives, {\tt blocksize}, {\tt weight} and
{\tt processors}, to allow the programmer to provide
information about the execution profile of a program section in
a parallel block,
and to direct processor allocation. All these directives are optional
and do not change the semantics of the program, but they can effect the
way the compiler implements parallelism and hence performance.

The {\tt blocksize} directive is used to form groups of execution
instances of subprograms that should be treated as a single module
for execution. The blocksize directive has an integer argument that
specifies the number of execution instances of the subprogram that
should be treated as a single unit for ditributing across the processor array.
When a blocksize directive is used after a loop header statement, it 
applies to every subprogram in the loop, unless there is another
directive after the particular subprogram call. This information is not
propagated in any way to loops nested inside. 

The {\tt weight} directive is used to specify an estimate of the relative
execution time of a subprogram in relation to the execution time of the
parallel block. The weight directive has an integer or a real argument.
If a weight directive follows a loop header, the estimate is taken as
relating to the execution time of the complete loop.

The {\tt processors} directive is used to specify how many processors
should be allocated to a subprogram. The directive relates to {\em all}
invocations of that subprogram. This directive should follow only a
subprogram and not a loop statement. 


\section{Using directives to guide parallelization}

To ensure that the results of executing a program in parallel are the
same as those obtained by sequential execution, the programmer must
ensure that the directives are used correctly. To obtain good 
performance, the programmer must ensure that the directives are placed
at appropriate places in the program. Also directives that control
load balancing and  assignment
of processors can be used to give explicit information useful for
parallelization process to the compiler.

\subsection{Specifying parallel execution}

A section of code inside a parallel block must satisfy the following
conditions:

\begin{enumerate}
\item All statements must be subroutine calls, loop header, or loop
      delimiter statements.

\item A subroutine may expect input only from parameters specified in
      the input statement, and leave output only in the parameters
      specified by output statements.

\item Loop bounds for all the loops must be constants.

\item The step size and range specifiers of any array section
       in the list of input and output parameters must be simple expressions
      in terms of constants and induction variables of enclosing loops.

\end {enumerate}

Note that for specifying a parallel block correctly, the user does not have
to think about parallel execution. The main criterion is that user must
specify input and ouput parameters correctly.


Any parallel block that follows these simple 
rules is  a legal parallel block. But the 
main purpose of using parallel blocks is to help the compiler make
decisions about the implementation of function level parallelism.
Hence, it is extremely important that only appropriate
parts of the program be  included in  parallel blocks

Every instance of a subprogram inside a parallel block is a unit
that the compiler can treat as an independent module. Each module 
is placed on a subset of processors, and there can be data parllelism
inside the modules. Different modules can execute in parallel subject 
to scheduling constraints imposed by the input and ouput parameters.
The compiler generates communication code to ensure that input/output
data is correctly transferred between modules.

Thus a parallel block should be specified around a sequence of procedure
calls only when the programmer thinks that it would be profitable to
distribute different functions to different processors, rather than solely
exploiting data parallelism by running one processor over the whole
array at one time.

\subsection{Controlling processor allocation}
Given a set of modules, and a set of processor, the compiler has to
decide how to map the available processors to the modules. We explained the
meaning of these directives in the last section. Here we discuss how they
can be used to help the compiler generate an efficient program module.

\begin{itemize}

\item[blocksize] This directive can be used to ensure that the compiler
does not do too fine a distribution of the program. It can be used to 
define multiple instances of a subprogram that must be together when
partitioning and scheduling the program.
 
\item[weight] The weight directive is used to give the compiler an idea of
how much computation is involved in a subprogram. The compiler would use this
information in deciding how many processors should be assigned to each module.
This directive is very important since the compiler does not
have a simple way to estimate this information with accuracy. The weights
used are relative, so all subprograms in a parallel block should be assigned 
weights to make it meaningful.

\item[processors] The programmer can specifically request the compiler to
assign a certain number of processors to a particular subprogram. While
this gives very precise control over load balancing to the programmer, the
directives would normally have to be changed when the program is to
run on a different processor array configuration. Thus, we recommend that
relative weights be the preferred mode of controlling load balancing.

\end{itemize}

\section{Examples}

\subsection{Pipe}
In Figure~\ref{fig:pipe} we show how a pipelined loop can be expressed
using a parallel block construct. The original sequential program
consists of a loop in which the subroutine {\tt getdata()} reads from input,
subroutines {\tt proc1} and {\tt proc2} do the processing, and finally
subroutine {\tt putdata} writes to the output.

\begin{figure}[htb]
\begin{center}
\centering
\fbox{
\psfig{figure=pipe.eps}
}

\tt
\begin{tabbing}
tttttttt\=ttt\=ttt\=ttt\=ttt\= \kill
C\$   \>{\bf parallel} \\
\>     do i = 1,10 \\
\>\>     call getdata(a)\\
C\$\>\>     {\bf input: i/o}\\
C\$\>\>     {\bf output: a}\\
\>\>       call proc1(a, b)\\
C\$\>\>     {\bf input: a}\\
C\$\>\>     {\bf output: b}\\
\>\>       call proc2(b, c)\\
C\$\>\>     {\bf input: b}\\
C\$\>\>     {\bf output: c}\\
\>\>       call putdata(c)\\
C\$\>\>     {\bf input: c}\\
C\$\>\>     {\bf output: i/o}\\
\>     endo\\
C\$\>   end parallel\\ 
\end{tabbing}
\rm
\caption{Pipeline}
\label{fig:pipe}
\end{center}
\end{figure}

Constructing a parallel block around this code implies that all of the
subroutine invocations can be potentially scheduled in parallel subject
to dependences due to input and output parameters. Analysis of dependences
shows that there are dependences that force sequentiality in each loop
iteration but no data dependences across loop iterations. However, the 
iterations of procedures {\tt getdata} and {\tt putdata} must be executed
in sequential order since they are involved in input and output respectively.
Thus multiple iterations of the loop can execute in parallel, but they
must start off in sequential order. 

The compiler has several options for implementing the model. In the
simplest scenario, each subroutine is assigned a set of processors, and they
execute asynchronously. Parameters are passed through explicit communication.
Alternately, the compiler can treat a set of iterations of a subroutine
as a module and have a large number (upto 40) modules to schedule.

The decision phase of the compiler is driven by analysis and explicit
directives.
\subsection{Fan}
\begin{figure}[htb]
\begin{center}
\centering
\fbox{
\psfig{figure=fan.eps}
}
\tt
\begin{tabbing}
tttttttt\=ttt\=ttt\=ttt\=ttt\= \kill
C\$ \>   {\bf parallel} \\
\>     do i = 1,10\\
\>\>       call getdata(a)\\
C\$\>\>   	{\bf input: i/o}\\
C\$\>\> 	{\bf output: a}\\
\>\>	do j = 1,4\\
\>\>\>	   call proc(a, j)\\
C\$\>\>\>	   {\bf input: a(j,:)}\\
C\$\>\>\>	   {\bf output: a(j,:)}\\
\>\>	endo\\
\>\>	call putdata(a)\\
C\$\>\>	{\bf input: a}\\
C\$\>\>	{\bf output: i/o}\\
\>      end   do\\
C\$\>   {\bf end parallel}\\
\end{tabbing}
\rm
\caption{Fan}
\label{fig:fan}
\end{center}
\end{figure}


\subsection{Pipelined Fans}
\begin{figure}[htb]
\begin{center}
\centering
\fbox{
\psfig{figure=abi.eps}
}

\tt
\begin{tabbing}
tttttttt\=ttt\=ttt\=ttt\=ttt\= \kill
C\$\>   {\bf parallel}\\
\>     do i = 1,10\\
\>\>        call getdata(a)\\
C\$\>\>        {\bf input: i/o}\\
C\$\>\>        {\bf output: a}\\
C\$\>\>        do j = 1,4\\
\>\>\>           call proc(a, j)\\
C\$\>\>\>           {\bf input: a(j,:)}\\
C\$\>\>\>           {\bf output: a(j,:)}\\
C\$\>\>        endo\\
\>\>        call trans(a)\\
C\$\>\>        {\bf input: a}\\
C\$\>\>        {\bf output: a}\\
\>\>        do j = 1,4\\
\>\>\>           call proc(a, j)\\
C\$\>\>\>           {\bf input: a(j,:)}\\
C\$\>\>\>           {\bf output: a(j,:)}\\
\>\>        endo        	\\
\>\>        call putdata(a)\\
C\$\>\>	{\bf input: a}\\
C\$\>\>	{\bf output: i/o}\\
\>    enddo\\
C\$\>   {\bf end parallel}\\
\end{tabbing}

\caption{Pipelined fans}
\label{fig:abi}
\end{center}
\end{figure}

\subsection{Filter Bank}
\begin{figure}[htb]
\begin{center}
\centering
\fbox{
\psfig{figure=bank.eps}
}

\tt
\begin{tabbing}
tttttttt\=ttt\=ttt\=ttt\=ttt\= \kill
C\$\>   {\bf parallel}\\
\>     do i = 1,10\\
\>\>        call getdata(a)\\
C\$\>\>        {\bf input: i/o}\\
C\$\>\>        {\bf output: a}\\
\>\>        call dsamp1(a)\\
C\$\>\>	{\bf input: a}\\
C\$\>\>        {\bf output: a}\\
\>\>	call fir1(a,a1)\\
C\$\>\>	{\bf input: a}\\
C\$\>\>	{\bf output: a1}\\
\>\>	call fft(a1,a2)\\
C\$\>\>	{\bf input: a1}\\
C\$\>\>	{\bf output: a2}\\
\>\> call fir2(b,b1)\\
C\$\>\>      {\bf input: b}\\
C\$\>\>        {\bf output: b1}\\
\>\>        call fft(b1,b2)\\
C\$\>\>        {\bf input: b1}\\
C\$\>\>        {\bf output: b2}\\
\>\>	call putdata(a2,b2)\\
C\$\>\>	{\bf input: a2, b2}\\
C\$\>\>	{\bf output: i/o}\\
\>     enddo\\
C\$\>   {\bf end parallel}\\
\end{tabbing}
\rm
\caption{Filter bank}
\label{fig:bank}
\end{center}
\end{figure}

%\section {}
%
%(The directives are designed to help the compiler (or a parallelizing tool)
%generate an efficient parallel program that runs on an array of cells.
%While part of the purpose of the directives is to advise the compiler on
%how to partition a program among arrays of cells, they are also used to
%inform the  compiler about data relations between modules that 
%are needed for scheduling and generating communication. Thus directives
%are not purely for optimization, and we need to have precise semantics for
%the directives to ensure correctness)

\end{document}
