
\documentstyle[psfig, 11pt]{article}

\textwidth=6.0in
\textheight=8.0in

\voffset=-0.5in
\hoffset=-0.5in

\begin{document}

\section{Run-time based HPF compilation}

\subsection{Compiler implementation}

The implementation of the compiler based on our classification for the
communication pattern needed in each computation.

\subsubsection{Communication detection}

We use FORALL statement as example and use \emph{LHS} to denote array
reference in the left-hand-side of the FORALL assignment, \emph{RHS}
for the right-hand-side. And we use ``owner computes'' rule to
partition the computation, then the communication pattern will be
decided by the FORALL index, index referrence in \emph{LHS},
\emph{RHS}, and the data mapping directives for the \emph{LHS},
\emph{RHS}.

A comprehensive detect-communication algrithom is used in our
compiler, possible communication patterns include:

\begin{itemize}
\item No communication: The corresponding \emph{LHS} and \emph{RHS}
  array elements needed to do calculation are located on the same
  machine.

\item Shift communication: The \emph{RHS} data need to move in
  parallel with same distance along one or more dimensions. The
  communication detection algorithom is also used to caculate the
  actual shift amount.

\item Remap communication: The \emph{RHS} data movement is among
  different dimension of the array or the distance is not unified in
  the same dimension.

\end{itemize}

The communication classification will determine two importand aspects of the
generated node program: 1) memory allocation and 2) execution control
for computation/communication.

\subsubsection{Memory management}

There are two memory allocation strategy used in our compiler: 1)
dynimicaly allocate temproray array. 2) allocate ``ghost area'' along
the \emph{RHS} array which need a small amount of shift on the
processor grid.

The first method is useful to handle remap communication. Usually,
data used in the computation is allocated according to HPF
\texttt{TEMPLATE} size distributed on each node. When remap is needed,
a temprary array will be allocated with the same alignment and
distribution as the \emph{LHS} array. The \emph{RHS} need
communication will be copied to the temporary array from its old
distribution, so the compuation can be carried on.

The second method is used to efficently handle shift communication. As
compiler can detect the shift amount for each \emph{RHS} array, a
``ghost area'' will be set along each array need to shift. When
required by the computation, only ``edge'' elements of the array need
to be sent to the neighbor processor. This will save memory copy time
compared with the remap case.

In addition to allocation method, the node program need to take care
of two level of memory address translation: 1) The global address and
local address. 2) The node program use linearized array index to
facilitate procedure call with array varible as argument.

\subsubsection{Execution control}

The execution control in node program have to deal with DAD
initialization, expressions and assignment, execution control in
source program, input/output and procedure call.

Given PCRC-runtime Fortran interface, DAD initialization is
strightforward. The execution control need to be remained in the node
program. The rest three items can be considered as ``computation'' in
the source program. Communication may happen as we described
previously. The difference is: in procedure call the dummy argument
will be treated as the \emph{LHS} and actual argument as \emph{RHS};
in I/O statement, remap is always used to scatter and gather the data
from root processor.

Particularly, linearization of array index and the DAD handle provide
in runtime library will help to implement the transcriptive features
of HPF procedure, such as \texttt{INHERIT} derictive, effectively.
Copy-in and copy-out in neither caller or callee are necessary.
The HPF compiler is embeded in a compiler construction framework
showed in the figure. Currently it has already handled different HPF
language features, including data mapping derictives, expressions and
assignment, program execution control, input/output and procedures. In
the following, we first give a breif introduction of the compiler
construction framework, then discuss the major issues considered in
the compiler implementation.

\begin{figure}
\centerline{\psfig{figure=structure.eps}}
\caption{System overview}
\label{System overview}
\end{figure}

\subsection{Compiler construction framework}

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

We can see the structure of the package frome the following
components:
\begin{itemize}
\item \textbf{Language parsers} The language parsers are used to
  convert program source code to intermediate representation (IR). The
  IR is designed to be suitable for multipule programming language. We
  already have an HPF language parser (including a semantics checking
  module to check all constrains in language definition) and a Java
  language parser. A C++ parser is being developed. So the usage of
  the package will certainly beyond the HPF compiler itself as more
  compilation work is involved.

\item \textbf{Package tools} These tools are used for displaying the
  itermediate representation.  Two of them are available now. One is
  to unparse the IR back to different language source code for which
  the parse tree is generated.  The other one is to dump IR in plain
  text or HTML format for debugging purpose.

\item \textbf{C++ class library} A C++ class library was extended from
  Sage++ class library. In the library, the supported language
  component is mapped to different C++ class (and inherit classes),
  with corresponding member functions provided to perform standard
  transformation, such as insert or delete a statement on the syntax
  tree.

\item \textbf{Testsuite} An extensive testsuite is designed for
  different language parsers. For example, the package include 1) a
  ``first order'' exhaustive syntax test, in which each syntax rule
  are used at least once. 2) all example programs from ``Migrating to
  Fortran 90'' and ``HPF handbook''. as test program 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.


\end{document}

