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

\talk{High Performance Fortran Translator}
\speaker{Dr Bryan Carpenter}

\address{Southampton University Computing Services\\
University of Southampton\\
Southampton SO9 5NH\\
United Kingdom}

\user{dbc}

\meeting{HPC open day}
\prepared{dbc}
\when{April 22, 1994}

\maketitle  % Builds frame and slide-0


\begin{slide}{Contents}
\begin{itemize}
  \item Background
  \begin{itemize}
    \item Why HPF?
    \item HPFF
  \end{itemize}
  \item HPF overview
  \begin{itemize}
    \item Parallel computation
    \item Distributed data
  \end{itemize}
  \item Southampton work
  \begin{itemize}
    \item PUMA: ADAPT and ADLIB
    \item JISC and SERC projects
    \item Mapping of computation
    \item Run-time library
  \end{itemize}
  \item{Conclusion}
\end{itemize}
\end{slide}

\begin{slide}{1.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\ ;-).

\end{slide}

\begin{slide}{1.2 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 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}

\section*{2.1 Parallel Computation}   % !!! Get a better font !!!

HPF includes all the ``array syntax'' and ``array intrinsics'' of
Fortran 90.  It adds a {\bf FORALL} construct.

\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 (A (I, :), B (:, 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 (A (I, :), B (:, J))
  END FORALL
\end{verbatim}
(fully parallel version of earlier example).

\end{slide}

\begin{slide}{Example: LU Decomposition}

\begin{verbatim}
  REAL A (N, N), B (N, N)
  REAL L_COL (N), U_ROW (N)

  DO R = 1, N - 1
    R1 = R + 1
    FORALL (I = R : N)
      L_COL (I) = A (I, R)
    END FORALL
    FORALL (J = R1 : N)
      U_ROW (J) = A (R, J) / L_COL (R)
      A (R, J)  = U_ROW (J)
    END FORALL
    FORALL (I = R1 : N, J = R1 : N)
      A (I, J) = A (I, J) - L_COL (I) * U_ROW (J)
    END FORALL
  END DO
\end{verbatim}

\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 para
llel 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}{More Complex Alignments}

\begin{verbatim}
            REAL A (4, 4)
            REAL L_COL (4), U_ROW (4)

            !HPF ALIGN L_COL (I) WITH A (I, *)
            !HPF ALIGN U_ROW (J) WITH A (*, J)
\end{verbatim}

\begin{figure}[hbtp]
\centerline{\psfig{figure=replicated-example.ps,height=2.5in}}
\caption{Alignment of the arrays for LU decomposition example}
\end{figure}

\end{slide}

\begin{slide}{Templates}

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


\begin{slide}{3. Southampton Work}

\section*{3.1 PUMA: ADAPT and ADLIB}   % !!! 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}.

\end{slide}

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

This year Computing Services 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}{3.3 Mapping of Computation}

A central problem in HPF translation is mapping of intermediate
results, ie, subexpressions.  Equivalent to mapping computations
to processors.  Especially difficult in {\bf FORALL}.

Are developing schemes applicable to rather general {\bf FORALL}
statements.  Attempt to distribute any index {\em whose range doesn't
depend on other indices}.

Intermediates mapped to templates derived from templates of named
program variables.

No reliance on ``Owner-Computes'' type rules---assignment not treated
specially.

Mapping scheme specified in Prolog.

\end{slide}

\begin{slide}{Example Mapping of Intermediate Results}

Input code\ldots
\begin{verbatim}
  DIMENSION B (n), A (n, n)

  FORALL (I = 1 : N, J = 1 : N)
    A (I, J) = FUN1 (I) + (B (J) + FUN2 (J))
  ENDFORALL
\end{verbatim}
``Translation''\ldots
\begin{verbatim}
  ALIGN TEMP1 (I) WITH A (I, *)
  ALIGN TEMP2 (J) WITH B (J)
  ALIGN TEMP3 (J) WITH A (*, J)
 
  FORALL (I = 1 : N)  TEMP1 (I) = FUN1 (I)
  FORALL (J = 1 : N)  TEMP2 (J) = B (J) + FUN2 (J)
  TEMP3 = TEMP2                             ! remapping
  A     = TEMP1 + TEMP3
\end{verbatim}

\end{slide}

\begin{slide}{Run-time Library}

Schematic form of principal calls\ldots

Remapping can occur at either variable reference or function
reference nodes.
\begin{verbatim}
    remap(result_data, target_mapping, input_data).
\end{verbatim}
{\bf target\_mapping} is any legitimate HPF mapping for the input data.
Optimised entry points for shifts, transposes etc.

At variable reference nodes also have
\begin{verbatim}
          gather(result_data, hpf_array,
                 subscript_1, subscript_2, ...)
\end{verbatim}
Optimised entry points for taking array sections, etc.  Simiarly,
{\bf scatter}.

\end{slide}

\begin{slide}{4. Conclusion}

Plan to make prototype version of HPF translation system available
by the end of this year, under the JISC HPF translation project
(B. Carpenter).

Results of concurrent and subsequent research on optimisation
strategies, funded by SERC project (J. Merlin) will be incorporated
later.

\end{slide}

\end{document}

