

\begin{slide}{Title}

\begin{center}
{\Large PCRC-based HPF Compilation} \\ \vspace{0.25in}
Guansong Zhang, Bryan Carpenter, Geoffrey Fox, Xiaoming Li,
Xinying Li, Yuhong Wen \\
\em Northeast Parallel Architectures Centre, \\
\em Syracuse University, \\
\em Syracuse, New York
\end{center}

\end{slide}

\begin{slide}{PCRC}

\begin{center}
\bf PCRC Project
\end{center}

\small

\begin{itemize}
\item
DARPA supported.
\item
Develop a public domain common runtime infrastructure
supporting parallel compiler/interpreter development.
\item
Common library should be shared by different languages and
programming models.
\item
Partners: NPAC, Rice, Maryland, Austin, Indiana, CSC, Rochester, Harvard.
\end{itemize}

\end{slide}

\begin{slide}{System}

\begin{center}
\bf Overview of NPAC HPF translation system
\end{center}

\small

The translation system has three components
\begin{itemize}
\item
{\bf HPFfe}.  A compiler front end for HPF 1.0.
Complete coverage of HPF syntax and most static semantic checks.
Generates IR extended from Sage++.
\item
{\bf Transformation modules.} Transformations on IR and code generation.
\item
{\bf PCRC runtime.} Provides functions for distribute array management,
data movement, and computational functions corresponding to HPF intrinsics.
\end{itemize}

\end{slide}

\begin{slide}{System}

\centerline{\psfig{figure=../structure.eps,width=6in}}

\end{slide}

\begin{slide}{System}

\begin{center}
\bf Key Technologies
\end{center}

\small

\begin{enumerate}
\item
Distributed Array Descriptor (DAD).
\item
Kernel Runtime.
\item
Communication Detection and Classification.
\end{enumerate}

\end{slide}

\begin{slide}{DAD}

\begin{center}
\bf Distributed Array Descriptor
\end{center}

\small

Designing an effective DAD for HPF is non-trivial.  Support many
distribution formats (block-cyclic, collapsed, replicated, \ldots) and
alignments and embeddings, {\em and} describe sections constructed with
arbitrary combinations of scalar and triplet subscripts.

NPAC DAD includes
\begin{itemize}
\item
Type and rank information.
\item
Description of process subgroup to which array is mapped
\item
For each dimension, distribution format and alignment information.
\item
For each dimension, local memory stride.
\end{itemize}

\end{slide}

\begin{slide}{Table}

\begin{center}
\bf Tabular representation of DAD
\end{center}
\vspace{0.5in}

\centerline{\psfig{figure=../dad-10.11.eps,width=2.5in}}

\end{slide}

\begin{slide}{Components}

\begin{center}
\bf Hierarchical representation of DAD
\end{center}
\vspace{0.5in}

\centerline{\psfig{figure=6comp.eps,width=3in}}

\end{slide}

\begin{slide}{Groups}

\begin{center}
\bf Embedding groups handled by DAD
\end{center}
\vspace{0.5in}

\centerline{\psfig{figure=embedding.eps,width=3in}}

\end{slide}

\begin{slide}{Kernel}

\begin{center}
\bf Kernel Runtime
\end{center}

\small

Kernel of NPAC library is a C++ class library.  Descended from runtime
of {\em shpf} system, with influences from F90D, CHAOS/PARTI.
Based on MPI.
\begin{itemize}
\item
Object oriented, {\em but efficient}.  Eg, use inline functions extensively.
\item
All collective operations work with general DAD.
\item
Array-array copying supported by {\tt pcrc\_remap} operation.
\item
Shift-style communication supported by {\tt pcrc\_write\_halo}.
\item
General gather/scatter operations.
\item
General reductions and other F90 array arithmetic.
\item
Most collective operations based on reusable {\em schedule objects}.
\end{itemize}

\end{slide}

\begin{slide}{Runtime}

\begin{center}
\bf Runtime Architecture
\end{center}
\vspace{0.3in}

\centerline{\psfig{figure=../architecture.eps,width=6.5in}}

\end{slide}

\begin{slide}{Remap}

\begin{center}
\bf Remap Schedule
\end{center}

\small

Distribution of source array:
\vspace{0.2in}
\centerline{\psfig{figure=src.eps,width=3in}}
Block send operations:
\vspace{0.2in}
\centerline{\psfig{figure=send.eps,width=3in}}

\end{slide}

\begin{slide}{Sum}

\begin{center}
\bf Reduction Schedules
\end{center}

\small

\begin{verbatim}
template<class T>
class Sum : public Reduce_<T, T> {
public :
  Sum(const Frame* _src) : Reduce_<T, T>(_src) {}

private :
  void opCombine(void* buf) {
    *res += *((T*) buf) ;
  }

  void opZero() {
    *res = 0 ;
  }

  void opReduce(const int srcOffset) {
    blockSum(res, srcBase + srcOffset, steps, exts, rank) ;
  }
} ;
\end{verbatim}

\end{slide}

\begin{slide}{Detection}

\begin{center}
\bf Communication Detection and Classification
\end{center}

\small

For a regular array assignment or equivalent term in a forall,
recognize three different communication strategies:
\begin{itemize}
\item
{\bf No communication.}  Required elements are aligned with destination.
\item
{\bf Shift communication.}  A shift along the source array's template
is sufficient.
\item
{\bf Remap communication.}  A general array remapping operation is required.
\end{itemize}

\end{slide}

\begin{slide}{Homomorphism}

\begin{center}
\bf Shift Homomorphism
\end{center}

\small

Classification based on {\em shift-homomorphism}.
\tiny
\begin{tabbing}
{\tt  !HPF\$ } \= {\tt PROCESSORS P(}$p${\tt )} \\
{\tt  !HPF\$ } \> {\tt TEMPLATE TX(}$t_x${\tt), TY(}$t_y${\tt)} \\
{\tt  !HPF\$ } \> {\tt DISTRIBUTE TX(BLOCK) ONTO P} \\
{\tt  !HPF\$ } \> {\tt DISTRIBUTE TY(BLOCK) ONTO P} \\
\\
{\tt  !HPF\$ } \> {\tt DIMENSION X(M), Y(N)} \\
{\tt  !HPF\$ } \> {\tt ALIGN X(I) WITH TX(}$a_x${\tt * I + }$b_x${\tt )} \\
{\tt  !HPF\$ } \> {\tt ALIGN Y(I) WITH TY(}$a_y${\tt * I + }$b_y${\tt )} \\
               \> {\tt ...} \\
               \> {\tt X(}$x_l${\tt :}$x_u${\tt :}$x_s${\tt) =
                       Y(}$y_l${\tt :}$y_u${\tt :}$y_s${\tt)} \\
\end{tabbing}
\small
$t_x$ and $t_y$ are normalized to be multiples of $p$.
Array sections shift-homomorphic if have the same extent and
\begin{displaymath}
\frac{a_x . x_s}{a_y . y_s} = \frac{t_x}{t_y}
\end{displaymath}
(different definition applies for cyclic distribution).

\end{slide}


\begin{slide}{Framework}

\begin{center}
\bf Compiler Construction Framework
\end{center}

\small

The \emph{frontEnd} system is an extensible software package for
constructing programming language processing tools.

Package is divided into
\begin{itemize}
\item \textbf{Language parsers.} Used to
  convert program source code to IR.  IR suitable for multiple
  programming languages.

\item \textbf{Package tools.} Used for displaying the IR.

\item \textbf{C++ class library.} Class library extended
  from the Sage++ class library.

\item \textbf{Test suite.} Extensive test suite for
  parsers.  Eg, package includes a ``first order'' exhaustive syntax
  test, in which each BNF syntax rule is used at least once.
\end{itemize}
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{slide}


\begin{slide}{Transformation}

\begin{center}
\bf Program Transformation
\end{center}

\small

Transformation goes in two phases:
\begin{enumerate}
\item
{\bf Format transformation.}
Components of source program are changed, making them suitable for
being further processed.  Eg, simple array assignments can be trivially
converted to forall statements.
\item
{\bf Program generation.}
Carries out the actual translation work and generates the node program.
\end{enumerate}

\end{slide}



\begin{slide}{Generation}

\begin{center}
\bf DAD Generation
\end{center}

\small

Consider the HPF fragment
\begin{verbatim}
      REAL X(1:205)
!HPF$ PROCESSORS P(2)
!HPF$ TEMPLATE TX(-2:205)
!HPF$ DISTRIBUTE TX(BLOCK) ONTO P
!HPF$ ALIGN X(i) WITH TX(1*i+0)

      ...
\end{verbatim}
\small
Translation involves
\begin{itemize}
\item
For each processor array create a {\em grp} value.
\item
For each template dimension, create a {\em rng} value.
\item
For each partitioned array, create a {\em dad} value.
\end{itemize}

\end{slide}

\begin{slide}{Generation}

\begin{center}
\bf DAD Generation
\end{center}

\small

Generated code is
\tiny
\begin{verbatim}
      pcrc_shp_P(1) = 2
      pcrc_grp_P = pcrc_new_group_grid (1,pcrc_shp_P)
      pcrc_rng_TX(1) = pcrc_new_range_distribute ((-2),205,1,pcrc_grp_P,&
     &1)
      pcrc_dad_X = pcrc_new_array_data (X,pcrc_real,pcrc_size_real,1,pcr&
     &c_grp_P)
      call pcrc_set_array_align (pcrc_dad_X,1,1,205,1,0,0,0,pcrc_rng_TX(&
     &1))

      ...

      call pcrc_delete_array (pcrc_dad_X)
      call pcrc_delete_range (pcrc_rng_TX(1))
      call pcrc_delete_group (pcrc_grp_P)
\end{verbatim}

\end{slide}


\begin{slide}{Assignments}

\begin{center}
\bf Assignments
\end{center}

\small

Now add
\tiny
\begin{verbatim}
      REAL Y(-12:161)
!HPF$ TY(-17:190)
!HPF$ DISTRIBUTE TY(BLOCK) ONTO P
!HPF$ ALIGN Y(i) WITH TY(1*i-12)
      ...
      FORALL (i=8:112:1) X(i) = Y(1*i-1)
\end{verbatim}
\small
Note
\begin{itemize}
\item
A shift communication is needed.  Local {\tt Y} segment
extended 2 elements to include ghost area.
\item
\texttt{pcrc\_write\_halo} communicates edge data.
\item
Local loop bounds calculated from forall index range and DAD of {\em lhs}.
\item
{\tt pcrc\_coef} gives address coefficients for each array dimension.
\end{itemize}

\end{slide}

\begin{slide}{Assignments}

\begin{center}
\bf Assignments
\end{center}

\small

Generated code is
\tiny
\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)
      pcrc_gtl_Y(1) = 0
      pcrc_gtu_Y(1) = 2
      call pcrc_write_halo (pcrc_dad_Y,pcrc_gtl_Y,pcrc_gtu_Y)
      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),2,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}

\end{slide}

\begin{slide}{Benchmarks}

\begin{center}
\bf Preliminary Benchmarks
\end{center}

\small

Compared the new NPAC compiler with 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.

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.

\end{slide}

\begin{slide}{Runtime}

\begin{center}
\bf Laplace Update
\end{center}
\vspace{0.3in}

\centerline{\psfig{figure=../laplace.ps,width=6in}}

\end{slide}

\begin{slide}{Availability}

\begin{center}
\bf Software Availability
\end{center}

\small

\begin{itemize}
\item
HPF front end (not full translator) is available through
\begin{verbatim}
http://www.npac.syr.edu/projects/pcrc/
\end{verbatim}
\item
Runtime kernel is being documented, for release later this summer.
\end{itemize}

\end{slide}

