\input epsf
\input{psadobe}
\documentstyle[]{art-nocolon}
\include{psfig}

\textheight = 9in
\textwidth = 6.5in              % assume output has this much centered
%\voffset = -.5 in
%\hoffset = -1.0in
%
%
\oddsidemargin   0in
\evensidemargin  0in
\topmargin = -.5 in

\renewcommand{\floatpagefraction}{1}
\renewcommand{\topfraction}{1}
\renewcommand{\bottomfraction}{1}
\renewcommand{\textfraction}{0}
%\renewcommand{\baselinestretch}{1}

\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newcommand{\ignore}[1]{}

\begin{document}
\title{Task Parallel Programming in Fx}
\author{ Jaspal Subhlok \\
School of Computer Science\\
Carnegie Mellon University\\
Pittsburgh, PA 15213\\
{\em (WORKING PAPER)}
}
\thispagestyle{empty}
\maketitle
\bibliographystyle{alpha}

{\em Abstract:}{This paper presents a set of extensions to Fortran which
can be used to build task parallel programs for private memory 
parallel machines, or for sets of different computers over a high
speed network. The framework is designed for exploiting task and data 
parallelism together. The changes that a user has to make to his 
program are at a high level and minor, and management of parallelism
and generation of commmunication is completely handled by the compiler.
This approach to task parallelism is taken in the Fx compiler at
Carnegie Mellon, and the results are presented in detail in related
publications\cite{SSOG93,SOGD94}. In this paper, we describe the
programming model and
the set of Fortran extensions for task parallelism,
 and discuss the basis for the design decisions.
}

\section{Introduction}
In the past few years, compilation of  programs for 
private memory parallel computers has received considerable attention.
High Performance Fortran (HPF) has emerged as a standard extension of 
Fortran for parallel computing, which is
a very encouraging development. HPF can be used to write and compile
data parallel programs for a variety of architectures, but is not 
suitable for a heterogeneous, or {\em task parallel} computing. 
Heterogeneity can be introduced in two different ways:

\begin{itemize}
\item Applications:
An application is often composed of a set of different modules,
with data parallelism inside modules and task parallelism between them.

\item Computing environments:
Use of different computers over a high speed network is an
increasingly popular way of parallel computing.
Individual computers can themselves be parallel computers, and can
vary from workstations to supercomputers.
\end{itemize}

It is important that support for task parallelism 
be provided alongside a compilation and execution environment
for data parallel programs. Our 
design of task parallelism is in the context of a data parallel
compiler, and our implementation is integrated with a prototype
High Performance Fortran compiler. Task parallelism is expressed
using additional directives. In this paper we present a programming
model and a compiler for task parallel computing. We discuss the 
main issues in compilation, illustrate how they are addressed
in the compiler, and present examples. Our current implementation
is for task and data parallel programs on an iWarp processor array,
and is being extended to other parallel machines and high speed networks.

\section{Programming Model} 
We describe the basic programming model. A program consists of
a set of (possibly) data parallel  {\em task-subroutines}
in a language similar to HPF. Task-subroutines have well defined
side effects, and calls to task-subroutines are followed by
directives that specify the side
effects of the subroutines with respect to the variables they reference
as  parameters.
A program begins execution as a single (data parallel or sequential)
thread on one machine. New  tasks are created by calls to
task-subroutines. Since the data 
relationship of the calling program
to the task-subroutines is well defined, the compiler can
map the tasks on different sets of processors, and generate communication
to maintain data consistency. The basic paradigm is that the results
obtained should be consistent with those obtained with sequential 
execution.

The mapping of task-subroutine onto processors, that is which 
set of processors executes a particular call to a task
subroutine, is a critical factor in obtaining good performance,
although it does not effect correctness. The mapping of task-subroutines
to sets of processors is many to many. Multiple task-subroutines can
be mapped to the same set of processors. Also one (or a set of) 
task-subroutine can be {\em replicated} and mapped to multiple sets
of processors. When a task-subroutine is replicated, successive
calls to the task-subroutine are executed on different instances
of the task-subroutine on different sets of processors, in round 
robin fashion.

The programmer can control the 
mapping using  directives. We are also developing
tools to automatically choose a good mapping and to  help the
programmer choose an efficient mapping~\cite{Subh93b}. In this paper,
we assume that the mapping process is driven by explicit
directives which may be provided by the programmer, or
automatically generated by another tool.
The compiler currently supports  mappings that are fixed at 
compile time, since that is simpler and requires minimal
support from the data parallel compiler and the runtime system.
Support for a dynamic implementation is also discussed.

The main characteristics of the programming model can be abbreviated as
follows:

\begin{itemize}
\item No new language constructs, only special compiler directives.
\item Common name space for shared data.
\item Data parallel subroutines with well defined side effects 
      are units for task parallelism.   
\item Communication between tasks is generated and
      managed by the compiler.
\item Sequential consistency, determinism, and freedom 
      from deadlock  guaranteed by the compiler.
\end{itemize}

\section{Compiler Directives}
Some directives are required by the compiler for generating
a parallel program, while others are used to guide the compiler
in making decisions about program mapping, which influence the 
perfomance significantly, but not the correctness.
We state and explain the directives that are used to express task
parallelism, and illustrate them with an example.
Later in the paper, we will discuss the potential for making the directives
more powerful, and adding new directives.

\subsection{Parallel section}
Calls to task-subroutines are permitted only in special 
code regions called {\em parallel sections}.
The code inside a parallel
section can only contain loops and subroutine calls.
There can be other directives in a parallel section
that specify the input/output
behavior 
and resource requirements of task-subroutines.
A parallel section corresponds to a mapping of task-subroutines
to processors and other resources.
On exit from a parallel section, the program reverts
to the mapping prior to the beginning of the parallel section.
Subsequent parallel sections may have different mappings.

As stated above, task parallel subroutine calls can be made
only inside a parallel section, and parallel sections can 
contain only a fixed set of constructs. These restrictions are
necessary to make it possible to manage shared data and shared
resources (including processors) efficiently at compile time.

A {\tt begin  parallel}...{\tt end parallel}
pair specifies a parallel section.
Statements inside 
a parallel section must be task-subroutine calls,
loop headers, or loop delimiters.

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

\subsection{Input and  output parameters}
Calls to task-subroutines have {\tt input} and
{\tt output} directives that precisely determine the data space
that the subroutine accesses and modifies. Every variable in the 
calling program, whose value at the call site may be potentially
used by the called subprogram, must 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, must 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. 

\begin{verbatim}
C$   begin parallel
       .
       .
     call foo(a,b,i)
C$   input a(:,:), i
C$   output b(:,1)
       .
       .
C$   end parallel
\end{verbatim}


\subsection{Directives for mapping programs}
The programmer controls the placement of task-subroutines onto
sets of processors and machines with directives. For
mapping onto a homogeneous processor array, the size and location
of a subarray is sufficient information to map a task-subroutine.
In an environment with multiple machines, additional machine 
information is also needed.
Different task-subroutines can be mapped together or separately.
Multiple locations can be given for a single task-subroutine,
which will generate replicated instances of the task-subroutine
that
execute the calls to
the task-subroutine at different locations, in round robin fashion.

We currently support two directives. The {\tt processors}
directive states how many processors should be assigned to
the task-subroutine. The {\tt origin} directive states the
location(s) for the task-subroutine in the processor array.
In the implementation, only rectangular subarrays can be
assigned to task-subroutines and the processor array is
in two dimensional space. Hence,  both directives have a pair
of integers as argument.

\begin{verbatim}
C$   begin parallel
       .
       .
     call foo(a,b,i)
C$   processor (4,4)
C$   origin (0,0)
       .
       .
C$   end parallel
\end{verbatim}


\subsection{An example program}
We will use the program in Figure~\ref{fig:tasks} to
show how the directives discussed above are used to write a task
parallel program and guide it's mapping. Th program contains a 
{\em src} routine that supplies data to routines {\em p1} and {\em p2}
for processing, and the final results are collected in a {\em sink}
routine.
\begin{figure}[htb]
%\hspace{.1in}
\begin{minipage}[t]{3.0in}
\tt
\begin{tabbing}
ttttt\=ttt\=ttt\= ttt\=ttt\= \kill
C\$ \>{\bf begin parallel} \\
\>     do i = 1,10 \\
\>\>     call src(A,B)\\
C\$\>\>  {\bf output} (A,B)\\
C\$\>\>  {\bf processor} (2,4)\\
C\$\>\>  {\bf origin} (0,0)\\
\>\>     call p1(A)\\
C\$\>\>  {\bf input} (A),  {\bf output} (A)\\
C\$\>\>  {\bf processor} (2,4)\\
C\$\>\>  {\bf origin} (0,0)\\
\>\>     call p2(B)\\
C\$\>\>  {\bf input} (B),  {\bf output} (B)\\
C\$\>\>  {\bf processor} (2,2)\\
C\$\>\>  {\bf origin} (2,0), (2,2)\\
\>\>     call sink(A,B)\\
C\$\>\>  {\bf input:} (A,B)\\
C\$\>\>  {\bf processor} (2,2)\\
C\$\>\>  {\bf origin} (2,0), (2,2)\\
\>     enddo\\
C\$\>   {\bf end parallel}
\end{tabbing}
\rm
\normalsize
\end{minipage} \
\begin{minipage}[t]{3.5in}
\vspace{.3in}
\psadobenomag{task.eps}
\end{minipage}
%\epsfbox{task.eps}
\caption{Compilation of task parallelism}
\label{fig:tasks}
\end{figure}

The task-subroutine {\em src} has variables {\em A} and {\em B} as output
parameters, task-subroutines {\em p1} and {\em p2} have {\em A} and {\em B} 
as there input-output parameters, respectively, and task-subroutine
{\em sink} has both {\em A} and {\em B} as input parameters. Using 
sequential execution as the basis to match inputs and outputs of 
subroutines, the compiler constructs the task dependence graph shown in the
figure. Task-subroutines {\em src} and {\em p1} are mapped to the same
module (M1) since they have identical {\em origin} directive, and 
similarly for task-subroutines {\em p2} and {\em sink} (M2). Based
on the {\em procesor} and  {origin} directives, the modules are mapped
as shown in the figure. Since the task-subroutines in M2 have two
arguments to the {\em origins} directive,
 the module is {\em replicated}. Succesive invocations
of the corresponding task-subroutines are executed alternately on the
two different instances of the module.

The details of the compiler analysis and options are discussed in the
next section, and more discussion of the directives is presented in a
later section.


\section{Compilation of task parallelism} 
The compiler has to perform a set of steps to support task parallelism:
\begin{enumerate}
\item Identify the task structure of the program and determine
the placement of task-subroutines (mapping).
\item Determine the communication links between the task subroutines and 
      identify the data  to be transferred.
\item  Generate  and schedule 
       inter-task communication.
\item Generate a final program along with variable declarations to
       manage the shared address space.
\end{enumerate}

One of the primary goals of our selection of a language
for expressing task parallelism is that it should be
easy to compile to efficient parallel programs.
In the rest of  this section, we discuss some parts of the compilation 
process to illustrate how the choice of directives has led
to a fairly simple compilation scheme. 

\subsection{Mapping programs}
The mapping of a program consists of a sequence of steps. First, the 
task-subroutines are partitioned into modules. All task-subroutines in
the same module are mapped to the same set of processors. Second, the
modules may be {\em replicated} to form multiple instances of modules.
Different module instances execute on different sets of processors, and
the compiler uses a round-robin schedule to determine which module 
instance excutes a particular task-subroutine call. Finally, 
a set of machine processors is assigned to each module instance.

The set of legal mappings is detrmined by resource constraints,
and selecting a good mapping is important for performance. However, the
selection of a mapping is not a part of the core compiler, which 
assumes that the mapping information is provided by the user
or another tool.
The program characteristics that influence
the choice of a mapping are discussed in~\cite{SOGD94}.

\subsection{Array section analysis}
The compiler has to precisely determine the communication 
between task-subroutines. The input and output directives
determine the variables that a task-subroutine call defines
and uses.
Since conditional statements are not permitted inside a parallel
section, there is a unique definition that reaches a use, and this
can be detrmined using data flow analysis. The main complexity comes 
from the fact that definitions and uses can be of array sections
also, not just variables, hence data flow analysis must handle
array sections.

Because of the constraints on the input and output directives,
only constant rectangular array sections can be specified
as parameters. The compiler has to be able to perform
union and subtraction of array sections for data flow analysis,
but these are straightforward for rectangular sections.
In future, we plan to relax some of the constraints, and use 
more sophisticated analysis. However, some constraints are
necessary for compile time analysis of data movement between
task-subroutines.

\subsection{Communication generation and scheduling} 
Once the compiler has determined the task-structure and mapping
of the program, and the data that needs to be transferred between
task-subroutines, the actual communication has to be generated.
The compiler also determines the  data distribution of  
array parameters inside task-subroutines, so that parameters
that are sent from other modules are distributed correctly.
The actual communication code is external to the task-subroutines
and ensures that the subroutines get data in the expected
distribution on entry.

The communication primitives used obviously depend on the
primitives that are available, but the compiler may
have to make some important choices. In our implementation,
two different schemes are possible, the first based on systolic
communication and the second on message passing communication.
In the first scheme, all
processors in a module are connected
in a ring, and the data is routed systolically over a single
channel.
This scheme provides extremely low latency, low overhead 
communication with no buffereing. Another advantage of
this scheme is that the sending module needs no knowledge
of the receiveing module, and simply puts the data on a 
channel in a canonical order.
In the second scheme, the sending module computes the processor 
number and address for each data element that has to be sent,
and sends it using a message passing library. 
This method can use  parallelism in communication, although
it has a somewhat higher overhead than systolic communication.
The compiler selects one of the communication schemes for
each communication step based on the granularity of communication.
Alternately, the user can explicitly select one scheme
using a compiler flag.

The compiler also has to find a global communication 
schedule that guarantees freedom from deadlock.
When a task-subroutine has
to send data to multiple tasks corresponding to multiple
task-subroutine calls, the data is sent in the order in which
those subroutine calls would have executed in the original
sequential program. A similar
   ordering scheme is used for receiving data. It is easy to see that
this guarantees deadlock freedom, since when no task is executing,
the unexecuted task corresponding to the earliest execution in the
sequential program must be ready to execute.

\section{Discussion}
The  approach that we have taken towards task parallelism in a
data parallel evironment is characterised by the following
features:
\begin{itemize}
\item Task parallelism is expressed by specifying task parallel
      subroutines and their side effects. There are no explicit
      communication statements in the user's program.

\item The compiler does most of the management of task parallelism,
      and the runtime overhead is minimal. To achieve this, it is
      necessary to place certain restrictions on the computations
      that can be expressed in our model.

\item No new programming constructs are added to the language.
      The directives are 
      critical to the performance, but do not effect the semantics.
\end{itemize}

Our basic goal is to provide support for task parallelism in a way that
would require minimal change in the user program (which may be
sequential or data parallel), and can be implemented efficiently
with relatively simple compiler technology. In this respect, our
approach is similar to that taken in HPF. We now discuss
and justify the main design decisions that we have made in
the context of alternatives that were available.

\subsection{User or compiler generated communication}
We have taken the view
that all communication for  task parallelism
should be generated by the compiler. This is analogous to the 
approach to data parallelism taken in High Performance Fortran. 
An alternate approach is taken in Fortran M~\cite{Foch92}, where
the programmer uses a portable
message passing interface  for communication between task parallel
components. 

Compiler generation of communication has several advantages. 
The most obvious and important   is that the user does not have to
actually write the communication between tasks. Only a high
level definition and use information is needed. In particular,
this implies that, except for compiler directives, identical
programs can be used for
sequential, purely data parallel, and various
task parallel implementations of a program. 

Portability is another important and desirable property. When
using explicit communication, portability can be achieved
by using a portable communication layer. This approach can
also be used when the compiler is generating the communication,
i.e the compiler can generate calls to a portable communication
library. In addition, the compiler can also use any other 
communication mechanisms that may be available. The compiler
can also perform optimizations relating to choosing communication
primitives and scheduling communication because of global
knowledge of data movement.

To make it possible for a compiler to generate efficient
communication with minimal analysis, we have imposed some 
restrictions on how task parallelism is expressed. For
instance, data transfer is permitted only on entry and exit
from a task-subroutines. Also input and output parameters must be 
variables, whole arrays or simple array sections, but arbitrary
array sections are not allowed. While some of these restrictions
can be relaxed if more sophisticated analysis was used, it is
clear that some restrictions are necessary. This implies that the
user does not have fine control over parallel execution, as he
or she would with explicit message passing. We believe that 
this price has to be paid for using a high level model
for task parallel computations.

\subsection{Static and Dynamic scheduling}
In our compiler, placement and scheduling of tasks is done at
compile time. It is possible to postpone some or all of these
decisions to runtime. For example, in Jade~\cite{LaRi91}
task scheduling is done completely at runtime.

Management of tasks at compile time has several advantages.
The overhead of parallel execution is minimized and only 
a simple runtime system is needed. The individual data parallel
subroutines can be compiled more easily and efficiently if the number
of processors they are to execute on is fixed at compile time.

It is clear that there are many applications that would benefit from 
dynamic scheduling of tasks.
The basic programming model can support a dynamic implementation,
and the reason for a static approach is partially simplicity.
In future we plan to extend the directives and the compiler
to be able to support more dynamic programs, and also learn from the 
experience of other researchers. 

However, the research is directed towards programs whose
main components are data parallel, but task parallelism
is also needed for good performance. We do not
expect to efficiently support programs that create and
destroy tasks dynamically as the basic mechanism
of creating parallelism.

\subsection{Language constructs and Compiler Directives}
We do not introduce any new language constructs, and instead
use compiler directives to specify and manage parallelism.
We feel that this property is vary important for building
task and data parallel programs from data parallel or sequential
programs.
In particular, the task parallelism directives can be ignored
to compile the program as a data parallel or sequential program.


While there is less freedom in choosing how to express task
parallelism without defining new language constructs, we do
not think it is a handicap for our objectives, which is to
make it possible to exploit task parallelism in a data 
parallel environment. The situation is similar to HPF where 
(almost) all the parallelism  related information is expressed
as directives without changing the language.

\section{Extension and standardization of task parallelism}
Use of subroutines (or any program components) with well
defined side effects is a powerful paradigm for heterogeneous
task parallelism.
We believe that the set of directives described in this paper,
or some variation of them, would be a valuable addition to a language
like HPF. There are several ways in which the directives can be
extended, making the language more powerful
(and some of them are discussed later in this section),
but it is extremely important that the directives lead
to a simple, portable compilation scheme that would generate
efficient parallel programs. 

Making the directives more general can make it more difficult
for the compiler to generate efficient parallel programs and/or
make it necessary to postpone some analysis to runtime. We 
discuss some of the extensions that we are considering, and comment
on their importance and impact on implementation.


\subsubsection*{Less restrictions on input and output directives}
We currently permit array sections in input and output directives,
but each dimension and the step size must be a known constant, or
"colon" implying all elements in that dimension. It will certainly
be useful to relax some of these restrictions.

Allowing ranges in dimensions (rather than a single constant) 
would be useful and relativel easy to implement. Allowing
varibles in array specifications would also be useful, but will
have a significant impact on the compiler. The compiler will
not be able to statically determine which
task-subroutines communicate, and what data is to be
communicated. We plan to allow some loop index expressions,
but not arbitrary expressions in array section specifications.
The objective is to allow more general array section specifications,
while ensuring that the compiler  is able to 
generate efficient communication code.

\subsubsection*{Nested task parallelism}
We do not permit nested task parallelism. In our experience,
nested task parallelism is less important when
data parallelism is also available. However, more experience
with task parallel applications is needed before the importance
of nested parallelism is well understood.

\subsubsection*{General directives for resource management}
We support directives to allocate processors to task-subroutines
and decide their placement. In general, the compiler will need
more information to map programs, particularly in a heterogeneous
environment. For example, the compiler will need to know what 
kind of computing and I/O resources have to be made available to
different task-subroutines. The specific information
that is needed will be dependent on the environment.

We plan to allow a general directive that would  list
all the resources that are needed by a task-subroutine. 
The system will provide the compiler with a default list of
available resources, which may be modified by a user. 
The entries that are permitted in this directive, and the
effect they would have, may be dependent on the execution
environment.

\subsubsection*{Using Fortran~90 Module and Interface features}


\section{Conclusions}
We have presented a set of compiler directives which can be
combined with a data parallel language like High Performance
Fortran to write task and data parallel programs for a 
private memory parallel machine, or a heterogeneous computing
environment based on a high speed network. We discuss 
the compilation issues and describe a compiler for the iWarp
distributed memory parallel machine. We argue that the approach
is a simple and portable way of writing efficient task and data 
parallel programs.

\bibliography{/afs/cs/project/iwarp/member/jass/bib/all}
\end{document}