\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}