\documentstyle[snarcslide]{article}
\newcommand{\ignore}[1]{}  % Useful when hacking existing text
\begin{document}

\talk{HPF Translation Project}
\speaker{Dr Bryan Carpenter}

\address{High-Performance Computing Centre\\
University of Southampton\\
Southampton SO9 5NH\\
United Kingdom}

\user{dbc}

\meeting{HPF project review}
\prepared{dbc}
\when{October 18, 1994}

\maketitle  % Builds frame and slide-0


\begin{slide}{1 Why HPF?}

Some extant HPC architectures:

\begin{itemize}
  \item Single processor vector
  \item Single instruction stream, distributed data (SIMD)
  \item Multiple processor (MIMD)
  \begin{itemize}
    \item Message-passing
    \item ``Remote memory access''
    \item Shared memory
  \end{itemize}
\end{itemize}

Standardisation efforts within some subclasses (eg MPI), but still
great diversity.

Parallelisation of sequential languages difficult/intractable.

HPF generalises SIMD dialects of Fortran---less baggage than
message-passing or general shared memory.
``Bulk-synchronous, parallel random access'' model.
Adds some of the flexibility of MIMD model.

Can be compiled to any of the above architectures\dots

\end{slide}

\begin{slide}{The High Performance Fortran Forum}

Started meeting March 1992.  Participation of 40+ organisations,
including designers of Fortran D, Vienna Fortran, and manufacturers of
parallel computers (Cray, DEC, Fujitsu, HP, IBM, Intel, Maspar, Meiko,
nCube, Sun, Thinking Machines\ldots).

Language is a development of SIMD Fortran dialects such as Connection
Machine Fortran, and distributed memory dialects such as Fortran D and
Vienna Fortran.

Standard distributed in May '93, published in September.

Still no ``full Subset'' implementations available.

\end{slide}

\begin{slide}{2. HPF Overview}

HPF extends Fortran in two main ways:

\begin{itemize}
  \item It adds constructs which specify parallel execution of computations.
  \item It adds directives which specify how program data is ``aligned''
        and distributed across multiple memories.
\end{itemize}

\end{slide}

\begin{slide}{Array Syntax}

Examples of Fortran 90 syntax:
\begin{verbatim}
  REAL X (10), Y (10), LEN (10)

  LEN = SQRT(X**2 + Y**2)
\end{verbatim}
All 10 lengths can be computed in parallel.
\begin{verbatim}
  REAL A (10, 10), B (10, 10), C (10, 10)

  DO I = 1, 10
    DO J = 1, 10
      A (I, J) = DOT_PRODUCT (B (I, :), C (:, J))
    END DO
  END DO
\end{verbatim}
The intrinsic {\bf DOT\_PRODUCT} can be computed by a parallel algorithm
(but {\bf DO} loops remain sequential).  Note syntax for ``array
sections''.

\end{slide}


\begin{slide}{\bf{FORALL}}

By combining the F90 array intrinsics with section subscripts (and
``masking''), possible to express many parallel algorithms.

{\em But}, array syntax rapidly becomes clumsy for writing practical
parallel programs.  Can use {\bf FORALL} instead
\begin{verbatim}
  FORALL (I = 1 : N, J = 1 : N)
    U (I, J) = (U (I, J - 1) + U (I, J + 1) +
                U (I - 1, J) + U (I + 1, J)) / 4
  END FORALL
\end{verbatim}
(a parallel iterative solver).
\begin{verbatim}
  FORALL (I = 1 : N, J = 1 : N)
    A (I, J) = DOT_PRODUCT (B (I, :), C (:, J))
  END FORALL
\end{verbatim}
(fully parallel version of earlier example).

\end{slide}


\begin{slide}{2.2 Distributed Data}

In practise programmer has to take some responsibility for how the
program is divided across the parallel computer.

Done in HPF by specifying how program data is distributed across local
memories.

From these clues compiler can (hopefully) choose sensible places to
perform individual computations.

\begin{figure}[hbtp]
\centerline{
\begin{picture}(280, 60)(0, 0)
\put(0, 5){\small Memory areas}
\put(0, 45){\small Processors}
\multiput(80, 0)(40, 0){5}{\put(10,50){\circle{20}}
\multiput(0, 0)( 0, 20){2}{\line(1, 0){20}}
\multiput(0, 0)(20,  0){2}{\line(0, 1){20}}
\thicklines
\put(10,20){\line(0, 1){20}}
}
\end{picture}
}
\caption{\label{parallel-computer}Idealised picture of a distributed memory
parallel computer}
\end{figure}

\end{slide}

\begin{slide}{Bad Placements}

\begin{verbatim}
         FORALL (I = 1 : 3)  C (I) = A (I) + B (I)
\end{verbatim}

\begin{figure}[hbtp]
\centerline{\psfig{figure=nonlocal.ps,height=1.5in}}
\caption{\label{non-local}A data distribution leading to
excessive communication}
\end{figure}

\begin{figure}[hbtp]
\centerline{\psfig{figure=unbalanced.ps,height=1.5in}}
\caption{\label{unbalanced}A data distribution leading to poor load balancing}
\end{figure}

\end{slide}

\begin{slide}{Good Placement}

\begin{figure}[hbtp]
\centerline{\psfig{figure=ideal.ps,height=1.5in}}
\caption{\label{ideal}An ideal data distribution}
\end{figure}

Could be achieved by following the declarations of {\bf A}, {\bf B},
{\bf C} with the directives
\begin{verbatim}
            !HPF PROCESSORS P (3)
            !HPF DISTRIBUTE C (BLOCK) ONTO P
            !HPF ALIGN A (I) WITH C (I)
            !HPF ALIGN B (I) WITH C (I)
\end{verbatim}

\end{slide}

\begin{slide}{More Complex Distributions}

\begin{verbatim}
          PROCESSORS P (3, 3)
          REAL A (6, 6)
          !HPF DISTRIBUTE A (BLOCK, BLOCK) ONTO P
\end{verbatim}

\begin{figure}[hbtp]
\centerline{\psfig{figure=block.ps,height=2.5in}}
\caption{Block distribution}
\end{figure}

\end{slide}

\begin{slide}{Cyclic distribution}

\begin{verbatim}
          !HPF DISTRIBUTE A (CYCLIC, CYCLIC) ONTO P
\end{verbatim}

\begin{figure}[hbtp]
\centerline{\psfig{figure=cyclic.ps,height=2.5in}}
\caption{Cyclic distribution}
\end{figure}

\end{slide}

\begin{slide}{Templates}

\begin{figure}[hbtp]
\centerline{\psfig{figure=mapping.eps,height=3.5in}}
%\caption{The stages of data mapping in HPF.}
\end{figure}
 
\end{slide}


\begin{slide}{3. Southampton HPF Project}

\section*{PUMA: ADAPT, ADLIB, ACL}   % !!! Get a better font !!!

Since 1989, ECS has been involved in research and development
on {\em ADAPT} (``Array Distribution Automatic Parallelisation
Tool'').

Tool for automatically transforming Fortran~90 +
data-distribution-declarations to code for message-passing computers.

Work started in Esprit PUMA project.  Initiated by John Merlin.
Predates HPF by several years.

F90 converted to F77 + calls to run-time library: {\em ADLIB}.

ACL was an occam-based collective communication library, also developed
in the PUMA project.

\end{slide}

\begin{slide}{JISC NTI and SERC projects}

This year SUCS received 1MY JISC funding, to generalise ADAPT/ADLIB
system to Subset HPF.  Output will be a public domain translation
system.

Subsequently ECS granted 2MY SERC funding to work on optimisation
issues.  NAG are ``heavy uncle''.

\end{slide}



\begin{slide}{Overview of Translation System}

\begin{figure}[hbtp]
\centerline{\psfig{figure=translation.eps,height=1.2in}}
\end{figure}

\begin{itemize}
\item
{\em front end}---syntactic and static semantic analysis of the input
HPF.

\item
{\em mapper}---``expression mapping''.

\item
{\em code generator}---convert AST to Adhoc-based intermediate form
with explicit communication and distributed loops, then target
language.

\item
{\em Adhoc}---a high-level target language, close to C++.

\item
{\em Mini-Adlib}---C++ interface to a minimal RTL.
\end{itemize}

\end{slide}


\begin{slide}{Adhoc}
\begin{verbatim}
      REAL A (10, 10), B (10)
!HPF$ DISTRIBUTE A (BLOCK, BLOCK)
!HPF$ ALIGN B WITH A ( : , *)

      FORALL (I = 1 : 10, J = 1 : 10)
        A (I, J) = B (I) + FUN (J)
      END FORALL
\end{verbatim}
could be translated as
\begin{verbatim}
  range i_a(10 #blk p_1), j_a(10 #blk p_2) ;
  array float a(i_a, j_a) ;
  array float b(i_a) ;

  where(i_a)
    where(j_a)
      a = b + fun(j_a) ;
\end{verbatim}
\end{slide}


\begin{slide}{Communication in Adhoc}

\begin{verbatim}
      REAL U (12)
!HPF$ DISTRIBUTE U (BLOCK)

      FORALL (I = 2 : 11)
        U (I) = (U (I - 1) + U (I + 1)) / 2
      END FORALL
\end{verbatim}
could translate to
\begin{verbatim}
  range i_u(12 # p_1) ;
  array float u [i_u] ;
  range i_interior(10 : base 1 : i_u) ;
  array float n [i_interior], p [i_interior] ;

  remap(n, u [10 : base 0]) ; remap(p, u [10 : base 2]) ;
  where(i_interior)
    u = (n + p) / 2 ;
\end{verbatim}

\end{slide}


\begin{slide}{Adhoc Communication Primitives}
{\em remap} copies data between two arrays of the same shape---they
can have {\em any} legitimate HPF (or Adhoc) mapping.

Also provides {\em gather} and {\em scatter} primitives to handle
communications implied by non-linear subscripts.

A couple of communication primitives are needed for IO, and some extra
support is needed to implement F90 array intrinsics.
\end{slide}


\begin{slide}{Mini-Adlib}
Minimal ``Run-time library'' for Adhoc.

{\em Mini-Adlib} provides classes for ``process arrays'' and ranges,
and template classes for arrays.  Range objects have built in
``iterator'' functionality, implementing the distributed loops of
Adhoc.

Free use made of operator overloading (eg, function application
``operator'' used for array subscripting).

(Less elegant) Fortran 90 interfaces will also be provided.

Run-time support for Fortran IO will be lifted from existing
sequential Fortran translators.
\end{slide}

\begin{slide}{Transcription of Adhoc to C++}
\begin{verbatim}
  range i_a(10 #blk p_1), j_a(10 #blk p_2) ;
  array float a(i_a, j_a) ;
  array float b(i_a) ;

  where(i_a)
    where(j_a)
      a = b + fun(j_a) ;
\end{verbatim}
translates to
\begin{verbatim}
  Range i_a(10, p_1, blk), j_a(10, p_2, blk) ;
  Array<2, float> a(i_a, j_a) ;
  Array<1, float> b(i_a) ;

  for(i_a.first() ; i_a ; i_a++)
    for(j_a.first() ; j_a ; j_a++)
      a(i_a, j_a) = b(i_a) + fun(j_a()) ;
\end{verbatim}

\end{slide}

\begin{slide}{The Mapping Problem}
A central problem in HPF translation is mapping of intermediate
results, ie, subexpressions.  Especially difficult in FORALL.

Are developing schemes applicable to general FORALL statements, with no
reliance on ``Owner-Computes'' type rules.  Mapping scheme specified in
Prolog.

Example:
\begin{verbatim}
  REAL B (N)
  REAL A (N, N)

  FORALL (I = 1 : N, J = 1 : N)
    a (I, J) = FUN1 (I) + (b (J) + FUN2 (J))
  ENDFORALL
\end{verbatim}
\end{slide}

\begin{slide}{Mapping of Example}
Possible Adhoc translation\ldots
\begin{verbatim}
  array float b [i_b] ;
  array float a [i_a, j_a] ;

  array float temp1 [i_b] ;
  where(i_b)
    temp1 = b + fun2(i_b) ;  // temp1 [j] = b [j] + fun2(j)

  array float temp2 [j_a] ;
  remap(temp2, temp1) ;      // communication !

  where(i_a) {
    float temp3 = fun1(i_a) ;
    where(i_b)
      a = temp3 + temp2 ;    // a [i, j] = fun1(i) + temp2 [j]
  }
\end{verbatim}
\end{slide}

\begin{slide}{JISC work completed January-September 1994}
Major tasks have been
\begin{itemize}
\item
Investigation of ``expression mapping'' strategies.
\item
Requirements analysis for HPF run-time library.
\item
Definition of Adhoc.
\item
Definition of Mini-Adlib.
\end{itemize}
Implementation work on Adlib in progress.  First MPI version
expected by December 1994.
\end{slide}

\begin{slide}{Translator: EPSRC project.}

JISC project closely related to EPSRC project ``Efficient translation
of High Performance Fortran for distributed memory systems'',
currently supporting John Merlin.

Latter project emphasises {\em translation}, and will provide the HPF
translator---JISC manpower mainly focussed on issues of run-time support
(target ``abstract machine'').

First translator (available end of this year) will adopt a simplified
mapping strategy.  Next year, JISC work on expression mapping will be
further developped and integrated into more advanced translator.  Also,
code generation will be improved.

\end{slide}

\end{document}

