\documentstyle[psfig, 11pt]{article}

\textwidth=6.0in
\textheight=8.0in

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

\begin{document}

\section{Run-time based HPF compilation}

The HPF compiler is embeded in a compiler construction framework
showed in the figure system overview. Currently it has already handled
different HPF language features. In the following, we give an
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 \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 from 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, 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 has been autoconfigured and tested on different platforms,
including: IBM AIX, SUN OS/Solaris, DEC OSF, HP HP-UX, SGI IRIX and PC
Linux.

\subsection{Compiler implementation}

The implementation of the compiler is 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 range, 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 equal in the
  same dimension.

\end{itemize}

The communication pattern will determine two importand aspects in 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, a
data used in the computation is allocated according to HPF
\texttt{TEMPLATE} size distributed on each processor. 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 shift. Then whenever
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 memory management need to take
care of two levels of address translation: 1) The global address and
local address. 2) The node program use linearized array index to
facilitate procedure call with array varibale 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. Different kinds of communication may happen as we
described previously. The difference among them are: 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 send
data to or from the root processor.

Particularly, linearization of array index and the DAD handler
provided 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 nor callee are
necessary.

\subsubsection{Examples}

We use an example to illustrate the actual transform needed in node
program. Suppose we have the following program header:

\small
\begin{verbatim}
      PROGRAM MAIN
      REAL X(1:205), Y(-12:161)
!HPF$ PROCESSORS P(2)
!HPF$ TEMPLATE TX(-2:205),TY(-17:190)
!HPF$ DISTRIBUTE TX(BLOCK) ONTO P
!HPF$ DISTRIBUTE TY(BLOCK) ONTO P
!HPF$ ALIGN X(i) WITH TX(1*i+0)
!HPF$ ALIGN Y(i) WITH TY(1*i-14)
\end{verbatim}
\normalsize

The communication detection will find a FORALL statement like:

\small
\begin{verbatim}
      FORALL (i=8:112:1) X(i) = Y(1*i-1)
\end{verbatim}
\normalsize

does not need communication, so the corresponding node program for the
FORALL statement will be:

\small
\begin{verbatim}
      pcrc_irg0 = pcrc_new_range_loop (8,112,1,1,0,pcrc_range (pcrc_dad_&
     &X,1))
      call pcrc_loop_bounds (pcrc_irg0,pcrc_lil_i,pcrc_liu_i,pcrc_lis_i)
      pcrc_sdd0 = pcrc_new_array_section (1,pcrc_dad_X)
      call pcrc_set_array_triplet (pcrc_sdd0,1,8,112,1,pcrc_dad_X,1)
      call pcrc_coef (pcrc_dad_X,1,8,112,1,1,0,0,pcrc_u00,pcrc_v00)
      call pcrc_coef (pcrc_dad_Y,1,8,112,1,1,(-1),0,pcrc_u10,pcrc_v10)
      if (pcrc_on (pcrc_group (pcrc_sdd0))) then
         do  i=0,(pcrc_liu_i-pcrc_lil_i)/pcrc_lis_i,1
            pcrc_sdx1 = pcrc_v10+pcrc_u10*i
            pcrc_sdx0 = pcrc_v00+pcrc_u00*i
            X(pcrc_sdx0) = Y(pcrc_sdx1)
         enddo
      endif
      call pcrc_delete_array (pcrc_sdd0)
      call pcrc_delete_range (pcrc_irg0)
\end{verbatim}
\normalsize

In the program segment, \texttt{pcrc\_new\_range\_loop} is used for
caculating local loop bounds, \texttt{pcrc\_coef} for address
translation. The actual compuation is guarded by an IF statement to
make sure it owns the \emph{LHS} array.

If we change the alignment a little, as: 

\small
\begin{verbatim}
!HPF$ ALIGN Y(i) WITH TY(1*i-12)
\end{verbatim}
\normalsize

A shift communication is needed. The node program will do the
following thing more before the computation:

\small
\begin{verbatim}
      pcrc_gtl_Y(1) = 0
      pcrc_gtu_Y(1) = 2
      call pcrc_write_halo (pcrc_dad_Y,pcrc_gtl_Y,pcrc_gtu_Y)
\end{verbatim}
\normalsize

and caculate the address for the \emph{RHS} array \texttt{Y} with:

\small
\begin{verbatim}
      call pcrc_coef (pcrc_dad_Y,1,8,112,1,1,(-1),2,pcrc_u10,pcrc_v10)
\end{verbatim}
\normalsize

The \texttt{Y} should be 2 emlement larger than the one in the
previous case. The \texttt{pcrc\_write\_halo} will send the edge data
to the accurate position in the next processor.

If we further change the distribution of the array,

\small
\begin{verbatim}
!HPF$ DISTRIBUTE TY(CYCLIC) ONTO P 
\end{verbatim}
\normalsize

a remap is needed. The node program will be:

\small
\begin{verbatim}
      pcrc_irg0 = pcrc_new_range_loop (8,112,1,1,0,pcrc_range (pcrc_dad_&
     &X,1))
      call pcrc_loop_bounds (pcrc_irg0,pcrc_lil_i,pcrc_liu_i,pcrc_lis_i)
      pcrc_sdd0 = pcrc_new_array_section (1,pcrc_dad_X)
      call pcrc_set_array_triplet (pcrc_sdd0,1,8,112,1,pcrc_dad_X,1)
      call pcrc_coef (pcrc_dad_X,1,8,112,1,1,0,0,pcrc_u00,pcrc_v00)
      pcrc_sdd1 = pcrc_new_array_section (1,pcrc_dad_Y)
      call pcrc_set_array_triplet (pcrc_sdd1,1,7,111,1,pcrc_dad_Y,1)
      pcrc_tdd1 = pcrc_new_array_section (1,pcrc_dad_X)
      call pcrc_set_array_triplet (pcrc_tdd1,1,8,112,1,pcrc_dad_X,1)
      pcrc_tbs1 = pcrc_real_alloc (pcrc_size (pcrc_tdd1))
      call pcrc_reset_array_base (pcrc_tdd1,pcrc_real_stack(pcrc_tbs1))
      call pcrc_remap (pcrc_tdd1,pcrc_sdd1)
      if (pcrc_on (pcrc_group (pcrc_sdd0))) then
         do  i=0,(pcrc_liu_i-pcrc_lil_i)/pcrc_lis_i,1
            pcrc_sdx0 = pcrc_v00+pcrc_u00*i
            X(pcrc_sdx0) = pcrc_real_stack(pcrc_tbs1+pcrc_sdx0)
         enddo
      endif
      call pcrc_real_free (pcrc_tbs1)
      call pcrc_delete_array (pcrc_tdd1)
      call pcrc_delete_array (pcrc_sdd1)
      call pcrc_delete_array (pcrc_sdd0)
      call pcrc_delete_range (pcrc_irg0)
\end{verbatim}
\normalsize

This time, a temporary array is allocated from \texttt{pcrc\_stack},
starting from \texttt{pcrc\_tbs1}. \texttt{pcrc\_remap} is used to
copy original \texttt{Y} to the new position, so the computation can
be carried on.

\end{document}
