
\documentstyle[psfig,12 pt]{article}

\textwidth=6.5in
\textheight=8.5in
\voffset=-0.5in
\hoffset=-0.5in


\begin{document}

\title{PCRC Runtime Library and HPF Compiler, \\
       \em Extended abstract}

\author{Bryan Carpenter, Geoffrey Fox, Xiaoming Li, \\
        Xinying Li, Yuhong Wen and Guansong Zhang \\
        \em Northeast Parallel Architectures Centre, \\
        \em Syracuse University, \\
        \em 111 College Place, \\
        \em Syracuse, New York 13244-410\\
        \{dbc,gcf,lxm,xli,wen,zgs\}@npac.syr.edu}

\maketitle

\section{Introduction}

The Web and Java have stolen some of the limelight over the past few
years, but the role of parallel processing in the drive to ultimate
computer performance remains unquestioned.  National programs like
Petaflops and ASCI attest continuing support for research and
development in basic parallel processing technologies.  While
arguments will persist over what proportion of applications can benefit
economically from parallel execution, we remain convinced that lack of
good system software and tools is the main technical reason for the
limited deployment of large scale parallel processing systems.
Sponsored by ARPA, PCRC (Parallel Compiler Runtime Consortium) is
an effort to establish a common base for parallel compiler development.
This common base is a {\em runtime library}, which is supposed
to be available to the compilers.  It is linked to the generated
``node program''.

The basic idea is not new. Almost every compiler targetting a parallel
architecture is supported by some sort of runtime, which resolves
issues impossible to handle at compile-time.  Those runtimes are
usually designed at a low level in the hope of squeezing out the
maximum performance.  According to this mindset, low-level {\tt send()}
and {\tt receive()} operations are encouraged in the node program.  A
consequence of this approach is that an {\em operational} parallel
compiler is very difficult to construct---the compiler has too many
details to take care of, and often ends up resorting to naive
strategies.  The result is that performance is much lower than it
should be---promised global optimization by thin runtimes is hard to
exploit.  Our philosophy in PCRC is to
build a relatively high level runtime library.  We believe this
approach will greatly facilitate compiler construction and deliver
comparable or better performance for typical applications.  An
important aspect of PCRC runtime is that it is supposed to be a common
base for different compilers.  This demands a flexible design, and an
implementation that adopts sound engineering practices.

PCRC is a joint effort among 10 organizations. This paper reports the
work carried out at Syracuse University, in NPAC.  In particular,
section 2 introduces the architecture, functionality, and
implementation of core PCRC runtime library (which will shortly be made
public domain).  Three groups of functions: data management, data
movement, and computational routines, are described.  Section 3
introduces an HPF compiler that uses this runtime.  The compiler serves as an
exemplar for the use of the runtime.  This section also describes an
infrastructure that has been developed in parallel with compiler
construction.  The algorithm for communication detection and the
approaches employed for procedure interface processing and memory
management are illustrated through segments of a node program generated
by the compiler.  Section 4 is a performance study. We compared
performance of our compiler with a leading commercial HPF compiler on a
Laplace solver and some test programs. The data suggest that our compiler
produces higher performance and more consistent code than the
commercial ones.

\section{The NPAC run-time library}

The kernel of NPAC library is a C++ class library.  It is most directly
descended from the run-time library of an earlier research
implementation of HPF\footnote{Southampton HPF}, with influences from the
Fortran 90D run-time and the CHAOS/PARTI libraries.  The kernel
is currently implemented on top of MPI\footnote{Because of the modular
design of the library we anticipate that porting to other
message-passing platforms would be relatively straightforward.  The
modules of the library that directly access the message-passing layer
only contain around 10\% of the total code.  The only particularly
MPI-specific feature used is MPI-style non-blocking communication.}.
The library design is solidly object-oriented, but efficiency is
maintained as a primary goal.  Inlining is used extensively, and
dynamic memory allocation, unnecessary copying, true procedure calls,
virtual functions and other forms of indirection are generally avoided unless
they have clear organizational or efficiency advantages.

The overall architecture of the library is illustrated in figure
\ref{PCRCArchitecture}.  At the top level there are several
compiler-specific interfaces to a common run-time kernel.  
The four interfaces shown in the figure are illustrative.
They include two different Fortran interfaces (used by different HPF
compilers), a user-level C++ interface called ad++\footnote{ad++ is
currently implemented as a set of header files defining distributed
arrays as type-secure container class templates, function templates for
collective array operations, and macros for distributed control
constructs.}, and a proposed Java interface\footnote{We also intend to
produce a METACHAOS interface.}.  The development of several top-level
interfaces has produced a robust kernel interface, on which we
anticipate other language- and compiler- specific interfaces can be
constructed relatively straightforwardly.

The largest part of the kernel is concerned with global communication
and arithmetic operations on distributed arrays.  These are represented on
the right-hand side of figure \ref{PCRCArchitecture}.  
The communication operations supported include HPF/F90 array intrinsic
operations such as {\tt CSHIFT}, the function {\tt writeHalo}, which
updates ghost areas of a distributed array, the function {\tt remap},
which is equivalent to a Fortran 90 array assignment between a
conforming pair of sections of two arbitrarily distributed HPF arrays,
and various gather- and scatter- type operations allowing irregular patterns
of data access.  Arithmetic operations supported include all F95
array reduction and matrix arithmetic operations, and HPF
combining scatter.  A complete set of HPF standard library functions
is under development.

Nearly all these operations (including many of the arithmetic operations)
are based on reusable schedules, in the PARTI/CHAOS mold.  As well as
supporting the inspector-executor compilation strategy, this
organization is convenient in an object-oriented setting---a
communication pattern becomes an object.  As an illustration, consider
the reduction operations.  All reductions from a distributed
array to a global result are described by an abstract base class using
virtual functions for local block reductions.  Specific instances such
as {\tt SUM} or {\tt PRODUCT} are created by deriving concrete classes
that instantiate the arithmetic virtual functions.  This is a cleaner
and more type-secure (hence, potentially, more efficiently compilable)
alternative to passing function pointers to a generic reduction
function.

For regular data movement operations a schedule consists of lists of
source and destination blocks for local copies or send or receive
operations.  A block is defined as a multi-dimensional local array
section parametrized by an offset and two short vectors of extents and
strides.  Where blocks are non-contiguous due to striding, or several
blocks need to be communicated between the same pair of processors to
execute a schedule, data is agglomerated by copying from user space to
a buffer before sending, and copied back after receiving.  Very long
messages are split to avoid allocation of very large buffers by the
library.  Where a single contiguous block is to be sent between a pair
of processes, no unnecessary copying is introduced.  When local block copies
involve contiguous data, a system operation such as {\tt memcpy} is
used.

All the data movement schedules are dependent on the infra-structure on the
left-hand side of the figure \ref{PCRCArchitecture}.  This provides the
distributed array descriptor, and basic support for traversing
distributed data (``distributed control'').  Important substructures
in the array descriptor are the {\em range} object, which describes
the distribution of an array global index over a process
dimension, and the {\em group} object, which describes the embedding
of an array in the active processor set.

At the time of writing the kernel is fully functional and quite mature,
two of the four interfaces illustrated are complete, and others are
in progress.


\section{Run-time based HPF compilation}

The NPAC compiler is implemented as a translator from HPF to Fortran 77.
It focusses on exploitation of explicit forall parallelism in
the source HPF program.  The translation scheme for forall assignments
with linear subscripts is based on classification of the
communication pattern needed in the construct.
The ``owner computes'' rule is used to partition the computation, then
the communication pattern is determined from the form of subscript
expressions for arrays appearing on the right-hand side of the
assignment.  A compile-time {\em detect-communication} function
recognizes three patterns:
\begin{itemize}
\item
No communication: Corresponding array elements on the left-hand and
right-hand sides of the assignment are located on the same processor.
\item
Shift communication: The right-hand side data need to be moved in
parallel a constant distance along one or more dimensions.  The {\em
detect-communication} function returns that actual shift amount.
\item
Remap communication: The data movement is between different dimensions
of the array, or the distance is not uniform along dimension.
\end{itemize}
The communication classification determines two aspects of the
generated node program: memory allocation and execution control
for computation and communication.

There are two memory allocation strategies used in our compiler:
dynamically allocate a temporary for each RHS term, or allocate a
``ghost area'' for arrays that appear in RHS contexts where they need a
small shift along the processor grid.  The first method is used to
handle ``remap'' communication.  When a call to {\tt pcrc\_remap} is
needed, a temporary array is allocated with the same alignment and
distribution as the LHS target array and the RHS term is copied to the
temporary array.
The second method is used to efficently handle ``shift'' communication.
If the compiler detects the need for a shift
a ``ghost area'' is added to the RHS array.
``Edge'' elements are transferred using {\tt pcrc\_write\_halo}.
This saves the cost of copying a whole array.

The compiler must generate code and initialize the distributed array
descriptors (DADs) passed to run-time functions and sub-programs.
Using the PCRC-runtime Fortran interface, DAD initialization is
straightforward.

As well as memory allocation, the node program must
deal with translation between global array subscripts and local (node)
subscripts.  The run-time provides various functions to help with this
translation\footnote{But these functions are never called from within
the inner DO loops generated by translation of a forall.}.  The node
program linearizes subscript computations for multi-dimensional
arrays.  Linearization of array segments, in conjunction with use of DAD
inquiry functions provided in the runtime library, is important for
implementing transcriptive features of HPF procedure, such as the
\texttt{INHERIT} directive.  Unnecessary copy-in and copy-out in caller
or callee are generally avoided.

The HPF compiler is embedded in a compiler construction framework
illustrated in the figure \ref{infrastructure}.  Currently it handles
various HPF language features, including data mapping directives,
expressions and assignment, program execution control, I/O, and
procedures.

The compiler construction framework, called the \emph{frontEnd} system,
is an extensible software package for constructing programming
language processing tools.  The system analyzes the input source
language and converts it to a uniform intermediate representation
(IR) which can later be manipulated by a set of functions provided in
a C++ class library.

The package is divided into the following components:
\begin{itemize}
\item \textbf{Language parsers} The language parsers are used to
  convert program source code to IR.  The IR is designed to be suitable
  for multiple programming languages.  We already have an HPF language
  parser (including a semantics checking module to check all constraints
  in the language definition) and a Java language parser.  A C++ parser is
  being developed.

\item \textbf{Package tools} These tools are used for displaying the
  intermediate representation.  Two of them are available now.  One
  tool unparses the IR back to the language source code for which
  the parse tree was generated.  The other dumps the IR in plain
  text or HTML format for debugging purpose.

\item \textbf{C++ class library} A C++ class library has been extended
  from the Sage++ class library.  In the library, the nodes of the
  syntax tree are mapped to different C++ classes, with associated
  member functions provided to perform standard transformations, such
  as inserting or deleting statements from the tree.

\item \textbf{Test suite} An extensive test suite is designed for
  different language parsers.  For example, the package includes a
  ``first order'' exhaustive syntax test, in which each BNF syntax rule
  is used at least once.  It also includes all example programs from
  ``Migrating to Fortran 90'' and the ``HPF handbook'' as test cases
  for the HPF parser.

\end{itemize}

The package is autoconfigured and tested on different platforms,
including: IBM AIX, SUN OS/Solaris, DEC OSF, HP HP-UX, SGI IRIX and PC
Linux.

\section{Preliminary Benchmark Results}

Figures \ref{bench1} and \ref{bench2} display select results of a
benchmark comparision between the new NPAC compiler the PGI HPF
compiler, version 2.0.  The programs were run on the IBM SP2 at NPAC.
The Laplace benchmark performs Jacobi relaxation on $256 \times 256$,
$512 \times 512$ and $1024 \times 1024$ arrays, distributed blockwise
over various numbers of processor.  Both compilers achieve about the
same performance on a single node, but generally our compiler exhibits
better speedup on multiple processors, presumably due to more effective
handling of communication.  The synthetic benchmark involves no
communication---it is a forall assignment involving large arrays.  It
illustrates that (unlike the PGI compiler) we deal with address
translation efficiently, even for cyclic distribution format.  (Speedup
is relative to an equivalent sequential program compiled with the IBM
Fortran compiler.)

While these examples are necessarily select, in general we find that
(on code that both compilers can successfully compile) the NPAC compiler
compares very favourably with the commercial compiler.

\newpage

\begin{figure}[ptb]
\centerline{\psfig{figure=architecture.eps,height=6in}}
\caption{\label{PCRCArchitecture}Architecture of the run-time.}
\end{figure}

\begin{figure}
\centerline{\psfig{figure=structure.eps}}
\caption{Compilation system overview}
\label{infrastructure}
\end{figure}

\begin{figure}
\centerline{\psfig{figure=laplace.ps}}
\caption{Laplace update.}
\label{bench1}
\end{figure}

\begin{figure}
\centerline{\psfig{figure=generator.spd.ps}}
\caption{Synthetic benchmark involving cyclic distribution format.}
\label{bench2}
\end{figure}

\end{document}

