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

\talk{{\em Adlib}: A Distributed Array Library to Support HPF Translation}
\speaker{Dr Bryan Carpenter}

\address{HPC Centre\\
University of Southampton\\
Southampton SO9 5NH\\
United Kingdom}

\user{dbc}

\meeting{5th Workshop on Compilers for Parallel Computers}
\prepared{dbc@ecs.soton.ac.uk}
\when{June 26, 1995}

\maketitle  % Builds frame and slide-0


\begin{slide}{History}

Precursors at Southampton
\begin{itemize}
\item
{\em ADLIB}---run-time library of {\em ADAPT} system.
\item
{\em ACL}---``Array Communication Library''.
\end{itemize}
Developed in Esprit PUMA project.

\end{slide}

\begin{slide}{Adlib}

The current {\em Adlib} is a component of the Southampton HPF translation
system.  It combines ideas from the ADAPT system, ACL, and HPF
\begin{itemize}
\item
ACL-like framework---abstract data types used to describe process
arrays, distributed data, distributed control, and collective
communication in an integrated way.
\item
Communication functionality enhanced to a superset of that in the
original ADLIB, to fully support translation of distributed Fortran.
\item
Data distribution formats enhanced to support full HPF.
\end{itemize}
Adlib is implemented as a C++ class library.  There is a reduced
interface to Fortran.

\end{slide}

\begin{slide}{Process Arrays}

The HPF declaration
\begin{verbatim}
  !HPF$ PROCESSORS P (4, 4)
\end{verbatim}
introduces a 4 by 4 arrangment of virtual processors, over which
program data can be distributed.  The Adlib declaration
\begin{verbatim}
  Procs2 p(4, 4) ;
\end{verbatim}
creates a 4 by 4 {\em process array} over which data (and control) can
be distributed.  Individual {\em process dimensions} of class
\verb$Dimension$ are extracted from \verb$p$ by the \verb$dim$ member
function.

\end{slide}

\begin{slide}{Ranges}

A {\em range} is a one-dimensional index space.  A range of extent $n$
has associated values $0 \ldots n - 1$, and defines a mapping from this
interval into a process dimension.

A {\em primitive range} is distributed over a process dimension,
according to one of the HPF distribution formats.
\begin{verbatim}
  Range x(100, p.dim(1), BLK) ;
  Range y(200, p.dim(2), CYC, 10) ;
  Range z(50) ;
\end{verbatim}
An Adlib primitive range is analogous to a single dimension of
an HPF template.

\end{slide}

\begin{slide}{Derived ranges}

A {\em derived range} is a range linearly aligned to some primitive range.
\begin{verbatim}
  Range i(20, 0, 5, x) ;
  Range j(100, 10, 1, y) ;
  Range k(50, 74, -1, j) ;
\end{verbatim}
Arguments to constructor are extent of derived range, base and stride
for alignment to a parent range, and the parent range.

An {\em embedding} is similar, but is ``scalar''.
It is aligned with a single element of some range.
\begin{verbatim}
  Embed e(60, x) ;
  Embed f(20, k) ;
\end{verbatim}

\end{slide}

\begin{slide}{Process groups}

A {\em process group} is a process array, or a slice of an array
constructed by restricting one or more dimensions to a single
coordinate value.  The coordinate and dimension is specified
implicitly by an embedding.
The operator \verb$/$ is overloaded to construct a new process group
(class \verb$ProcessGroup$) from an existing one and an embedding.
\begin{verbatim}
  ProcessGroup q(p / e) ;
  ProcessGroup r(q / f) ;
  ProcessGroup s(p / e / f) ;
\end{verbatim}
The {\em active process group} is the process group sharing the
local thread of control.

\end{slide}

\begin{slide}{Process groups}

\centerline{\psfig{figure=procgroup.eps,height=5in}}

\end{slide}

\begin{slide}{Arrays}

An {\em array} is distributed over a particular process group.
Shape and mapping of an array of rank $r$ defined by list of $r$
ranges distributed over distinct dimensions in the process
group, or collapsed.
\begin{verbatim}
  Array2<float> a(p, x, y) ;
  Array1<int> b(q, k) ;
  Array1<float> c(z) ;
\end{verbatim}
If the process group argument is omitted, the array is distributed over
the active process group.

\end{slide}

\begin{slide}{Subscripts}

The \verb$Subscript$ class is a common base class of \verb$Embed$ and
\verb$Range$.

Simple subscripting is by means of \verb$()$.  It returns a reference
to an array element
\begin{verbatim}
  b(f) = 17 ;
  a(e, f) = 2 * b(f) ;
\end{verbatim}
It is illegal to perform this operation on a process which doesn't
hold the selected element.

Can also take a {\em section} of an array using the section constructor
\begin{verbatim}
  Section1<float> d(a, sect(e, k)) ;
\end{verbatim}

Arrays and sections have identical interfaces and a common base class,
\verb$Frame$.

\end{slide}

\begin{slide}{Embedding control: {\em on}}

The library provides three operations which can be used to change the
active process group---{\em on}, {\em at} and {\em where}.

The {\em on} construct is used to change the active process group
\begin{verbatim}
  if(q.on()) {
    ...
  } q.no() ;
\end{verbatim}
After the call to \verb$q.on()$ the active process array is \verb$q$.
\verb$q.on()$ returns a truth value which specifies whether any virtual
process in \verb$q$ is held on the local physical process.
\verb$q.no()$ returns the active process group to its earlier value.

\end{slide}

\begin{slide}{Embedding control: {\em at}}

The {\em at} construct is used to embed control within a dimension
of the active process array (it can be regarded as a special case of
{\em on}).  If the active process group is currently \verb$p$\ldots
\begin{verbatim}
  if(e.at()) {
    if(f.at()) {
      b(f) = 17 ;
      a(e, f) = 2 * b(f) ;
    } f.ta() ;
  } e.ta() ;
\end{verbatim}
Between the calls to \verb$e.at()$ and \verb$e.ta()$ the active process
array is \verb$p / e$.  \verb$e.at()$ returns a truth value which
specifies whether any virtual process in the new active process group
is held by the local physical process.

\end{slide}

\begin{slide}{Distributing control: {\em where}}

{\em at} is like a conditional; {\em where} is like a loop.
It is parametrised by a range.  Suppose the active process group
is \verb$q$, then
\begin{verbatim}
  for(k.where() ; k.test() ; k.next()) {
    b(k) = k() ;
  } k.erewh() ;
\end{verbatim}
Between \verb$k.where()$ and \verb$k.erewh()$ the active process group
is reduced by restricting the process dimension associated with
\verb$k$ to the locally held coordinate.  The loop body executes once
for every index value of \verb$k$ held on the local process.

If a range activated as an iterator is used as a subscript
it behaves like an embedding in the range at the location associated
with the current iteration.  The \verb$()$ operator returns the
loop index for the current iteration.

\end{slide}


\begin{slide}{Communication: the {\em remap} family}

The \verb$remap$ operation copies an array to another array of the
same shape.  Its interface is
\begin{verbatim}
  void remap(Frame& dst, Frame& src) ;
\end{verbatim}
The mappings of the source and destination arrays are arbitrary.


The {\em remap} family potentially contains other operations which can
be expressed in terms of \verb$remap$, but may be more efficiently
implemented directly.  These include broadcasts, shifts and matrix
transpose.

\end{slide}

\begin{slide}{Simple nearest neighbour update in HPF.}

{\Large

\begin{verbatim}
  real u(10)

  !hpf$ distribute u (block) onto p
  !hpf$ processors p (4)

  integer i, n

  do i = 1, 10
    if(i .eq. 1 .or. i .eq. 10) then
      u(i) = 1.0
    else
      u(i) = 0.0
    endif
  enddo

  do n = 1, 5
    u(2 : 9) = 0.5 * (u(1 : 8) + u(3 : 10))
  enddo
\end{verbatim}

}

\end{slide}

\begin{slide}{Simple nearest neighbour update in Adlib.}

{\large

\begin{verbatim}
  Procs1 p(4) ;

  if(p.on()) {
    Range x(10, p.dim(1), BLK) ;
    Array1<float> u(x) ;

    for(x.where() ; x.test() ; x.next()) {
      if(x() == 0 || x() == 9)
        u(x) = 1.0 ;
      else
        u(x) = 0.0 ;
    } x.erewh() ;

    Range l(8, 0, 1, x), r(8, 2, 1, x), c(8, 1, 1, x) ;

    Section1<float> u_l(u, sect(l)), u_r(u, sect(r)) ;
    Array1<float> tmp1(c), tmp2(c) ;

    for(int n = 1 ; n <= 5 ; n++) {
      remap(tmp1, u_l) ;
      remap(tmp2, u_r) ;

      for(c.where() ; c.test() ; c.next()) {
        u(c) = 0.5 * (tmp1(c) + tmp2(c)) ;
      } c.erewh() ;
    }
  } p.no() ;
\end{verbatim}

}

\end{slide}

\begin{slide}{Communication: the {\em gather-scatter} family}

The general \verb$gather$ operations have interfaces
\begin{verbatim}
  void gather(Frame& b, Frame& a, Frame* i_1, ...) ;
\end{verbatim}
\verb$b$ is the {\em gathered data}; \verb$a$ is the {\em
scattered data}.  These are followed by subscript arrays---integer
arrays with the same shape and mapping as the gathered data.
The number of subscripts equals the rank of the scattered
data.

Restricted forms are provide for translating Fortran vector subscripts
\begin{verbatim}
  void vecGather(Frame& b, Frame& a, Frame* i_1, ...) ;
\end{verbatim}
where \verb$a$ and \verb$b$ have the same rank, and the subscripts
are rank-1 arrays.

\verb$scatter$ primitives have identical interfaces.

\end{slide}


\begin{slide}{Communication: the reduction family}

The simplest reduction primitive is
\begin{verbatim}
  void reduce(const int typeLen, char* res, Frame* src,
              void (*opZero)(void*),
              void (*opAccum)(void*, void*)) ;
\end{verbatim}
The result, cast to a character vector of length \verb$typeLen$,
is replicated over the active process group.  \verb$src$
holds the input data.  The accumulation operation is defined by the
function \verb$opAccum$, and the function \verb$opZero$ sets data to
the zero of \verb$opAccum$.

Variants do reductions on pairs of arrays (scalar product and masked
reductions) and reductions in single array dimensions, where the result
is an array with rank reduced by one.

\end{slide}

\begin{slide}{Lower level interfaces}

The interface described is at too high a level to be very
suitable as a target of compilation.  An optimising compiler would
in-line the implementations of the less efficient operations, in terms
lower level interfaces.

Example: the implementation given for the {\em where} construct
is inefficient.  Iterator functions are quite complex; they and
subscript member functions are called in every iteration---wasteful,
when, typically, data pointers are simply being incremented in most
iterations.

Lower level iterator functions are provided which just enumerate the
set of contiguous index blocks held on the local physical process.
Lower level inquiry functions on arrays provide direct access to the
data layout---base addresses and strides.

\end{slide}

\begin{slide}{Fortran interface}

Current Fortran interface to Adlib quite restrictive---essentially
only access to the communication functions.

Fortran arrays representing local segments of distributed arrays passed
in with dope vectors describing the data mapping.  Interface code
constructs Adlib class objects from this parametrisation, and
dispatches relevant C++ communication procedures.

The Fortran interface provides functions which directly implement all
the Fortran 90 intrinsic functions on arrays.

\end{slide}

\begin{slide}{Implementation status}

Adlib is part of the distribution of the Southamption High Performance
Fortran, version 0.1, currently in Beta testing.

Written in C++, layered on MPI.

The released version of Adlib is a prototype, offering full
functionality, but poor performance.  Major optimisations are in
progress (a new version of \verb$remap$ is up to an order
of magnitude faster on some platforms).

\end{slide}

\end{document}

