\documentstyle{article}

\input{psfig} 

\begin{document}

\sloppy

\pagestyle{empty}

%\title{Adhoc}
\title{{\em Adlib}: A Distributed Array Library to Support HPF Translation}

\author{D.B. Carpenter \vspace{0.25in} \\ 
        \em High Performance Computing Centre, \\
        \em University of Southampton, \\
        \em Southampton, S09 5NH} 

\date{DRAFT}

\maketitle

\begin{abstract}
{\em Adlib} is a class library implementing the HPF distributed
data model.  Its native interface is in C++.  A Fortran interface
provides a subset of the Adlib functionality.  This paper
mainly discusses the C++ interface and implementation.
\end{abstract}

\section{Introduction}

The {\em Adlib} communication library is a component of the Southampton HPF
translation system.  It combines ideas from the ADAPT system for
translation of Distributed Fortran 90, and from earlier collective
communication libraries developed at Southampton.  Its features include
\begin{itemize}
\item
Extensive use of abstract data types used to describe process
arrays, distributed data, distributed control, and collective
communication in an integrated way.
\item
A communication functionality adequate to fully support translation of
distributed Fortran.
\item
Data distribution formats to support full HPF.
\end{itemize}
Adlib is implemented as a C++ class library.  There is a reduced
interface to Fortran.


\section{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.  In Adlib the role of the HPF
processor arrangement is taken by the {\em process array}.
A rank 2 process array, equivalent to \verb$P$, is declared by
\begin{verbatim}
  Procs2 p(4, 4) ;
\end{verbatim}
An Adlib process array has a set of {\em process dimensions} of
class \verb$Dimension$.  The individual dimensions of a process array are
accessed by the member function \verb$dim$, illustrated in the next section.

A \verb$Procs$ array describes {\em virtual processes}, which are
mapped (somehow) into the available set of physical processes.  In the
remainder of this paper we will occasionally be cavalier about the
distinction between virtual and physical processes; if the library in
used as intended the distinction should not be significant.

A process array is a particular case of a {\em process group}.  Adlib
has a more general idea of a process group, to be described in section
\ref{groups}.

\section{Ranges}

A central idea in Adlib is the {\em range}.  There is no
completely analogous object in HPF.  A range is a one-dimensional index
space.  A range of extent $n$ has the values $0 \ldots n - 1$
associated with it.  The range 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.  The statements
\begin{verbatim}
  Range x(100, p.dim(1), BLK) ;
  Range y(200, p.dim(2), CYC, 10) ;
  Range z(50) ;
\end{verbatim}
declare that \verb$x$ has extent $100$, and is distributed block-wise
over the first dimension of \verb$p$; \verb$y$ has extent $200$ and is
distributed block-cyclically over the second dimension of \verb$p$.
\verb$z$ is a ``collapsed'' range of extent 50.
An Adlib primitive range is directly analogous to a single dimension of
an HPF template.

A {\em derived range} is a range linearly aligned to some primitive range.
The statements
\begin{verbatim}
  Range i(20, 0, 5, x) ;
  Range j(100, 10, 1, y) ;
  Range k(50, 74, -1, j) ;
\end{verbatim}
declare that \verb$i$ has extent $20$; it is aligned to \verb$x$ starting
at position 0 in \verb$x$, with stride $5$---that is, element $0$ of
\verb$i$ has the some process mapping as element $0$ of \verb$x$, element
$1$ of \verb$i$ has the same mapping as element $5$ of \verb$x$, etc.
\verb$j$ has extent $100$; it is aligned to \verb$y$ starting at postion
$10$ with stride $1$.  \verb$k$ has extent $50$; it is aligned to \verb$y$
starting at position $84$ with stride $-1$ (the immediate parent of
\verb$k$ is \verb$j$ but the two alignments are composed to yield the
mapping to the primitive range---two derived ranges are equivalent if
they have to same extent and the same alignment to equivalent primitive
ranges, however they are derived).

The extent of a range can be determined by the member function \verb$size$.
Its interface is
\begin{verbatim}
  int Range :: size() ;
\end{verbatim}


\section{\label{arrays}Arrays}

An {\em array} is distributed over a particular process group.  The
shape and mapping of an array of rank $r$ are defined by list of $r$
ranges.  Each of these ranges must be distributed over a dimension of
the array's process group,
or it must be collapsed; no two of them may be
distributed over the same dimension.
\begin{verbatim}
  Array2<float> a(p, x, y) ;
  Array1<float> c(z) ;
\end{verbatim}
The (optional) first argument of the constructor is the process group
over which the array is distributed.  If it is omitted, as in the
declaration of \verb$c$, the array is distributed over the active
process group (see section \ref{groups}).

According to these declarations \verb$a$ is a rank 2 array of floats,
shape \verb$(100, 200)$, distributed over the process
array \verb$p$.  \verb$c$ has a collapsed range and is replicated over
the active process group.  If no range of an array is distributed over
an effective dimension of its process group, the array is replicated
over that dimension.  \verb$c$ has no distributed ranges so it must be
replicated over all dimensions of the active process group.

Creation of an array is a collective operation---all members of the
active process group must cooperate in the construction.

\section{Local subscripts} 

Adlib arrays can be subscripted by objects from the \verb$Subscript$
class.  This is as an abstraction of the local subscripts for
distributed array access.  A typical implementation would incorporate a
representation of a coordinate within a process array, and a local
array subscript.

A \verb$Range$ object functions as a map between an integer global
array subscript and the \verb$Subscript$ class.  So, for example
\begin{verbatim}
  Subscript s(x(30)) ;
\end{verbatim}
declares \verb$s$ as a local subscript assocated with element 30 of the
distributed range \verb$x$. 
The expression is ill-defined if and the process which evaluates it
does not hold a copy of this element of the distributed array.

Elements of array may be accessed by passing appropriate
\verb$Subscript$ arguments to the (overloaded) function
application operator on the array.  So
\begin{verbatim}
  a(x(30), y(50))
\end{verbatim}
returns a reference to element \verb$(30, 50)$ of \verb$a$.

It is not required that a range used to construct
a subscript is identical to the corresponding range of the array,
but it should be {\em derived} from that range.
Because of the alignment between \verb$i$, \verb$j$ and \verb$x$, \verb$y$
the subscript \verb$u$ defined by
\begin{verbatim}
  Subscript u(i(6)) ;
\end{verbatim}
is equivalent to \verb$s$ and
\begin{verbatim}
  a(i(6), j(40))
\end{verbatim}
selects the same array element as the earlier expression.

\section{\label{at} Embedding control: {\em on} and {\em at}}

As explained in the last section an array element may only be
referenced by a process which holds a copy of the element.
The library provides two constructs which can be used to test whether
a subscript is held locally.

The function \verb$on$ is a member of the process group classes
(including the process array classes).  It determines whether the local
physical process holds any elements of the virtual process group
\begin{verbatim}
  if(p.on()) {
    ...
  } p.no() ;
\end{verbatim}
The code represented by the ellipsis is only executed by physical
processes which hold part of the process array \verb$p$.
Logically, \verb$no$ returns control to the whole of the original
active process group.  This logic will explained further in
section \ref{groups}.

Having established that some members of the virtual process array
is held locally, one proceeds to test whether subscripts embedded
in individual process dimensions are held locally using the \verb$at$
member of the process group class.  If \verb$s$ is a local subscript,
the idiom is
\begin{verbatim}
  if(s.at()) {
    ...
  } s.ta() ;
\end{verbatim}
Again, we defer explanation of the need for the matching \verb$ta$
call to section \ref{groups}.

Collecting together various fragments introduced so far, we can
write a complete program which modifies an element of a distributed
array.
\begin{verbatim}
  Procs2 p(4, 4) ;

  Range x(100, p.dim(1), BLK) ;
  Range y(200, p.dim(2), CYC, 10) ;

  Array2<float> a(p, x, y) ;

  Subscript s(x(30), t(y(50)) ;
  
  if(p.on()) {
    if(s.at()) {
      if(t.at()) {
        a(s, t) = 73 ;
      } t.ta() ;
    } s.ta() ;
  } p.no() ;
\end{verbatim}
The program assigns the value 73 to element \verb$(30, 50)$ of \verb$a$.

The user has to exercise some care when updating array elements.  It is
important to ensure that elements which are meant
replicated over a process group (according the mapping implied by the
array declaration) are updated with a consistent values.  It is easy
enough to devise a set of variable usage conventions which will ensure
this requirement is met---these conventions will be omitted here.

\section{\label{where} Distributing control: \em where}

If \verb$at$ is like a conditional, \verb$where$ is like a loop.  Instead
of a subscript it is parametrised by a range.
Consider the following fragment
\begin{verbatim}
  if(p.on()) {
    for(x.where() ; x.test() ; x.next()) {
      for(y.where() ; y.test() ; y.next()) {
        a(x, y) = x + y ;
      } y.erewh() ;
    } x.erewh() ;
  } p.no() ;
\end{verbatim}
The \verb$where$ member activates a \verb$Range$ as an ``iterator''.
The loop body executes once for every index value of \verb$x$ held
on the local process.

The assignment in the body illustrates two type-conversions defined on
the \verb$Range$ class.  A \verb$Range$ can be cooerced to an integer,
which is how \verb$x$ and \verb$y$ are used on the right hand side of
the assignment.  It can also be cooerced to a \verb$Subscript$, which
is how they are used on the left hand side.

If these cooercions appear while a range is activated as an iterator,
cooercion to an integer returns the range index associated with the
current loop iteration, while cooercion to a local subscript returns a
subscript embedded at the corresponding location.

The effect of the parallel loop above is to assign to each element
of \verb$a$ the sum of its two index values.


\section{\label{communication}Communication}

There are three families of communication operations in Adlib

\subsection{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(Array dst, Array src) ;
\end{verbatim}
The mappings of the source and destination arrays are arbitrary.
In common with all the communication routines described in this paper,
\verb$remap$ is a collective operation---it must be invoked on all
processes (in the active process group cf section \ref{groups}).

We will now give a small example of an Adlib program.  The HPF program
in figure \ref{nnHPF} is a toy example of the nearest neighbour update
paradigm.  The Adlib program in \ref{nnAdlib} is an equivalent Adlib
program.  Construction of the array sections and declaration of temporaries
has been lifted out of the loop over \verb$n$
\begin{figure}[btp]
\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}
\caption{\label{nnHPF}Simple nearest neighbour update in HPF.}
\end{figure}
\begin{figure}[btp]
\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) ;

    Array1<float> u_l(u, l), u_r(u, r) ;

    Range c(8, 1, 1, x) ;

    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}
\caption{\label{nnAdlib}Simple nearest neighbour update in Adlib.}
\end{figure}

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.


\subsection{The {\em gather-scatter} family}

The general \verb$gather$ operations have interfaces
\begin{verbatim}
  void gather(Array b, Array a, Array i_1) ;

  void gather(Array b, Array a, Array i_1, Array i_2) ;

  void gather(Array b, Array a, Array i_1, Array i_2, Array i_3) ;
  ...
\end{verbatim}
Here \verb$b$ is the {\em gathered data} and \verb$a$ is the {\em
scattered data}.  These are followed by subscript arrays, which are
integer arrays with the same shape and mapping as the gathered data.
The number of subscripts should be equal to the rank of the scattered
data, and their values should lie in the ranges expected by subscripts
of that array.  Data is copied from \verb$a$ to \verb$b$ with the
specified subscripting pattern.  A completely analogous primitive
\verb$scatter$ copies data from \verb$b$ to \verb$a$.

These operations are unnecesarily general if it is only required to
implement the patterns of access in Fortran 90 array syntax (but they
are needed for parallelising \verb$FORALL$, for example).  Vector
subscripts can be handled by the simpler primitives
\begin{verbatim}
  void vecGather(Array b, Array a, Array i_1) ;

  void vecGather(Array b, Array a, Array i_1, Array i_2) ;

  void vecGather(Array b, Array a, Array i_1, Array i_2, Array i_3) ;
  ...
\end{verbatim}
where now \verb$a$ and \verb$b$ have the same rank, and the subscripts
are rank-1 arrays, whose individual ranges are the same as the
corresponding to range of \verb$b$.  If any subscript argument is
\verb$NULL$ it is assumed that the gathered and scattered data have the
same extent in the associated dimension, and the operation behaves like
an array assignment with respect to that dimension.  \verb$vecScatter$
is similar.


\subsection{The reduction family}

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

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


\section{\label{groups}Process groups}

Having provided a few examples of working code, we turn to an idea
which is important to deeper understanding of Adlib---the process group.

A {\em process group} is a set of (virtual) processes.  The process
group has two r\"{o}les---a particular action can be performed within a
specified process group, or a particular data object can be
distributed over a specified process group.

The simplest example of a process group is a process array.  Adlib has
a more general idea of a process group, which is a ``slice'' of a
process array formed by restricting one or more of the process
dimensions to a single coordinate.

A process coordinate can be defined implicitly by a subscript.
The operator \verb$/$ is overloaded to construct a new process group
(class \verb$ProcessGroup$) from an existing one and a subscript.
\begin{verbatim}
  ProcessGroup q(p / s) ;
  ProcessGroup r(q / t) ;
  ProcessGroup s(p / s / t) ;
\end{verbatim}
The process groups \verb$q$, \verb$r$ and \verb$s$ are illustrated in
figure \ref{processgroups}.
\begin{figure}[btp]
\centerline{\psfig{figure=procgroup.eps,height=3in}}
\caption{\label{processgroups}Examples of process groups.  The square boxes
represent the 16 virtual processes in the process array $p$.  The dashed
lines embrace groups $q$, $r$ and $s$.}
\end{figure}
The {\em parent process array} of all these groups is \verb$p$.
A process group has a set of process dimensions taken from the
parent process array.  The dimension set for \verb$p$ contains
\verb$p.dim(1)$ and \verb$p.dim(2)$.  The dimension set for \verb$q$
contains just \verb$p.dim(2)$, while that for \verb$r$ contains just
\verb$p.dim(1)$.  The set for \verb$s$ is empty.

An immediate benefit of this generalised process group is that it
allows us to extend mapping of arrays in a way necessary to
fully support HPF.  HPF allows ``embedded'' alignments in templates.
\begin{verbatim}
  !$HPF PROCESSORS p(2, 2)

  !$HPF TEMPLATE t(10, 10)
  !$HPF DISTRIBUTE t(BLOCK, BLOCK) ONTO p

  INTEGER b(10)
  !$HPF ALIGN b(:) WITH t(:, 5)
\end{verbatim}
The Adlib equivalent is
\begin{verbatim}
  Procs2 p(2, 2) ;

  Range x(10, p.dim(0), BLK) ;
  Range y(10, p.dim(0), BLK) ;

  Array1<int> b(p / y(4), x) ;
\end{verbatim}
In section \ref{arrays} the first argument of the array constructor was
supposed to be the process {\em array} over which the data is
distributed; in general it can be an process {\em group}.  The ranges
of the array must be distributed over dimensions of this group.

\section{The active process group}

The second benefit of the generalisation is that it supports
representation of the ``active process group'' inside arbitrary
\verb$at$ and \verb$where$ constructs.  We proceed to define this idea
more carefully.

At any stage of execution of a program a particular process group is
singled out as the {\em active process group} (APG).  From the viewpoint of a
particular process, the active process group is the set of processes
sharing the current ``thread of control''.  Adlib supports MIMD
execution through the \verb$where$ construct, so there may be several
distinct processes groups active at the same time, with the physical
processes partitioned between these groups.

A powerful feature of Adlib, designed to support ``nested
parallelism'', is that collective operations such as communication
operations, array declarations, and even process array declarations, can
appear at any point of the program.  It is {\em not} required that
all physical processors engage in the operations; it is sufficient that
all processes in the active process group do so.  Any global
synchronisation implied by the collective operation affects just the
processes in the active group, leaving processes outside the group
undisturbed
\footnote{This requirement molds the idiom for the three control
constructs.  The operations \verb$on$, \verb$no$, \verb$at$, \verb$ta$,
\verb$where$ and \verb$erewh$ update a hidden data structure which
describes the active process group.  The data structure is interrogated
by various collective communication operations.  Although \verb$no$,
for example, does not return a value, it does have the important side
effect of restoring this data structure to the state it had before the
matching \verb$on$ call.}.

The three Adlib control constructs affect the active process group
in the following ways.  If \verb$p$ is a process group, inside
\begin{verbatim}
  if(p.on()) {
    ...
  } p.no() ;
\end{verbatim}
the active process group is \verb$p$.  If the active process group is
\verb$p$ and \verb$s$ is a subscript, inside
\begin{verbatim}
  if(s.at()) {
    ...
  } s.ta() ;
\end{verbatim}
the active process group is \verb$p / s$.  If the active process group is
\verb$p$ and \verb$x$ is a range, inside
\begin{verbatim}
  for(x.where() ; x.test() ; x.next()) {
    ...
  } x.erewh() ;
\end{verbatim}
the active process group is \verb$p / (Subscript) x$---employing
the cooercion from range to subscript described in section \ref{where}.

From these formulae we infer two important restrictions which can be
expressed in terms of the active process group
\begin{itemize}
\item
An {\em at} construct can appear if and only if its subscript is
derived from a range distributed over a dimension of the active
process group.
\item
A {\em where} construct can appear if and only if its range is
distributed over a dimension of the active process group.
\end{itemize}

\section{Accessibility}

There are some some restrictions on the arguments
of collective operations.  These restrictions can be expressed in
terms of ``accessibility''.
A process group \verb$q$ with parent array \verb$p$ is {\em accessible}
at a particular stage of program execution if the active process group
is the same as the one in effect when \verb$p$ was created, or if it is
a subarray of \verb$p$ which contains \verb$q$.  For example
\begin{verbatim}
Procs2 p(2, 2) ;

Range x(10, p.dim(0), BLK) ;
Range y(10, p.dim(1), BLK) ;

Subscript s(x(5)) ;
Subscript t(y(5)) ;

ProcessGroup q(p / s) ;

// Point A

if(p.on()) {
  // Point B

  if(s.at()) {
    // Point C

    if(t.at()) {
      // Point D
    } t.ta() ;
  } s.ta() ;
} p.no() ;
\end{verbatim}
The group \verb$q$ is accessible at point \verb$A$ because
the APG is the same as the one in effect when \verb$p$ was defined.
It is accessible at point \verb$B$ because the APG is a subarray
of \verb$p$ (viz \verb$p$ itself) which contains \verb$q$.
It is accessible at point \verb$C$ because the APG is a subarray
of \verb$p$ (this time \verb$q$ itself) containing \verb$q$.
The group \verb$q$ is {\em inaccessible} at point \verb$D$.

Informally the idea is that a process group is accessible if that group
is contained within the APG, with the intuitive understanding that a
process array is contained within the group active at the time it was
declared.

Two important restrictions can be expressed in terms of accesibility:
\begin{itemize}
\item
An {\em on} construct can appear if and only if its process group
is accessible.
\item
In general a collective operation on distributed data can appear only if
all its arguments are distributed over accessible process groups.
\end{itemize}

\section{Arrays and the active process group}

In section \ref{arrays} we gave an illustration of an array in which
the process group was omitted
\begin{verbatim}
  Array1<float> c(z) ;
\end{verbatim}
and stated that \verb$c$ was globally replicated with a collapsed
range.  In general if the process group argument is omitted the
array is distributed over the active process group.  It need not
be replicated.  It may have ranges distributed over this group,
as in
\begin{verbatim}
  Procs2 p(2, 2) ;

  if(p.on()) {
    Range x(10, p.dim(0), BLK) ;
    Range y(10, p.dim(1), BLK) ;

    Array2<float> u(x, y) ;
    Array1<int> v(x) ;

    // ...
  } p.no() ;
\end{verbatim}
The arrays \verb$u$ and \verb$v$ are distributed over \verb$p$.  
The latter array is replicated in the second dimension.

\section{Array sections and process groups}

In general the subscript arguments of the array section constructor are
a mixture ranges and local subscripts.  The section is distributed over
the process group of the parent array, restricted by any local
subscript arguments.  So in
\begin{verbatim}
  Procs2 p(2, 2) ;

  Range x(10, p.dim(0), BLK) ;
  Range y(10, p.dim(1), BLK) ;
  
  Array2<int> a(p, x, y) ;

  Array1<int> b(a, x, y(5)) ;
\end{verbatim}
the section \verb$b$ is distributed over \verb$p / y(5)$.

If a range currently activated as a \verb$where$ iterator is used as a
section subscript argument, it will (in effect) be cooerced to a local
subscript.

Uniquely amongst collective operations, the parent array argument of
the array section constructor
need not be accessible at the point of call.  It is only required is
that the {\em constructed} array be distributed over an accessible process
group.  With the declarations above we could have
\begin{verbatim}
  Subscript s(y(5)) ;

  if(s.at()) {
    Array1<int> b(a, x, s) ;

    // ...
  } s.ta() ;
\end{verbatim}
The process group \verb$p$, over which \verb$a$ is distributed, is not
accessible at the point where \verb$b$ is constructed.  The declaration
is legal because the process group \verb$p / s$ over which \verb$b$
is distributed {\em is} accessible (it is the current APG).

%
%----------------
%
%The library provides three operations which can be used to change the
%active process group.  This section describes the first two---{\em on}
%and {\em at}.
%
%As explained above, at a particular point of program execution,
%the active process group is the process group sharing the current
%``thread of control''.  Various operations in the Adlib communication
%library rely on knowing the active process group---for example some
%operations must synchronise all processes in this group, and others
%must broadcast information to all processes in the group.  In general
%it is important that the active process group be changed in a
%disciplined way, using the Adlib primitives provided.  These maintain a
%private data structure describing this group.
%
%When an Adlib program starts executing the active process group is
%{\em world}, a rank-1 process array containing one virtual process for
%each physical process on which the program has been invoked.
%
%The {\em on} construct is used to change the active process group.
%Suppose \verb$q$ is an accessible process group, then
%\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.  Immediately
%before the call the \verb$q.no()$ the process group must be \verb$q$
%(although it may have changed in the interim); after the call it is
%restored to whatever it was before the earlier matching call to
%\verb$q.on()$.
%
%The {\em at} construct is used to embed control within a dimension
%of the active process array.  For example, if the active process
%group is currently \verb$p$, the fragment of code in
%the previous section could be executed within a pair of nested {\em
%at} constructs:
%\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.
%
%There is a restriction on where the {\em at} construct can appear:
%\verb$e.at()$ can only be executed when the dimension in which \verb$e$
%is an embedding in an effective dimension of the active process group.
%
%If the active process group is initially \verb$q$, the effect of
%{\em at}($e$) is identical to {\em on}($q/e$), but using \verb$at$
%is simpler.
%
%
%\section{\label{where} Distributing control: \em where}
%
%If \verb$at$ is like a conditional, \verb$where$ is like a loop.  Instead
%of a subscript it is parametrised by a range.
%Suppose the active process group is currently \verb$q$, then:
%\begin{verbatim}
%  for(k.where() ; k.test() ; k.next()) {
%    b(k) = k() ;
%  } k.erewh() ;
%\end{verbatim}
%\verb$k.where()$ can only be executed when the dimension over which
%\verb$k$ is distributed is an effective dimension of the active process
%group.  Between the calls to \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.
%
%The fragment above introduces two other features.  In section
%\ref{arrays} it was explained how an embedding could be used as a
%simple subscript.  A range can also be used as a simple subscript when
%(and only when) it has been activated as a \verb$where$ iterator.  In
%this context a range used as a subscript behaves exactly like an
%embedding in the range, at the point corresponding to the current
%iteration of the loop.
%
%The other new feature is that, also when a range has been activated as
%an iterator, the \verb$()$ operator can be applied to it to find the
%current index value, as on the right hand side of the assignment.
%
%
%----------------
%
%There are two ways to subscript an array.  {\em Simple subscripting} is
%achieved with the overloaded \verb$()$ operator.  This operation
%returns a reference to an array element.  For now we will only
%illustrate the case where the arguments are of type \verb$Embed$---section
%\ref{where} describes situations in which a \verb$Range$ can be
%used as a simple subscript.
%\begin{verbatim}
%  b(f) = 17 ;
%  a(e, f) = 2 * b(f) ;
%\end{verbatim}
%The embeddings used as subscripts must be in the same primitive ranges
%as those of the corresponding ranges of the array, and the selected
%element is the one aligned to the primitive ranges in the same way as
%the subscripts.  If a range of the array is a derived range with no
%element at the specified point, the operation is ill-defined.
%Also, the simple subscript operation is ill-defined if executed
%on a process which isn't home to all embeddings used as arguments---the
%the fragment above could only be executed on the single process
%in group \verb$s$ (see figure \ref{processgroups}).  To put it another
%way, the active process group must be \verb$s$.
%
%The user has to exercise some care when updating array elements.  It is
%important to ensure that elements which are meant
%replicated over a process group (according the mapping implied by the
%array declaration) are updated with a consistent values.  Provided the
%active process group is only manipulated using the constructs introduced
%in sections \ref{at} and \ref{where}, it is easy enough to devise
%a set of variable usage conventions which will ensure this requirement
%is met---these conventions will be omitted here.
%
%The other way to subscript an array is by means of the section
%constructor
%\begin{verbatim}
%  Section1<float> d(a, sect(e, k)) ;
%\end{verbatim}
%declares \verb$d$ to be a section of \verb$a$.  The subscripts are the
%embedding \verb$e$, and the range \verb$k$.  The rules for
%embedding-valued subscripts are similar to those for simple
%subscripting, except that in this case there is no restriction about
%only performing the operation at the home of the
%embeddings---construction of a section is a collective operation.  A
%range-valued subscript must be representable as a range derived from
%the corresponding array range.  In the example, \verb$d$ represents a
%slice of the array \verb$a$---it provides an alias for the data in that
%slice.  The shape and mapping of \verb$d$ is identical to that of \verb$b$.
%
%The process group over which a section is distributed is defined to
%be the process group over which the subscripted array was distributed,
%restricted by any embedding-valued subscripts.  This process group
%must be accessible when the section is created.
%
%Neither mechanism for subscripting requires any transfer of data between
%processes.  If Adlib is used as the target of HPF translation, Fortran
%subscripting operations which {\em do} require data transfer must make
%explicit calls to the \verb$remap$ or gather-scatter primitives described
%in section \ref{communication}.
%
%The array classes and the section classes are derived from a common
%base class, \verb$Frame$, and have identical interfaces.  The
%\verb$Frame$ class also provides various inquiry functions: for
%example \verb$prc$ returns the process group over which the array is
%distributed, and \verb$rng$ returns a specified range of the array.
%\begin{verbatim}
%  ProcessGroup* Frame :: prc() ;
%  Range* Frame :: rng(const int axis) ;
%\end{verbatim}
%
%
%\section{Embeddings and process groups}
%
%An {\em embedding} is similar to a derived range, 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}
%declare that \verb$e$ is aligned to element 60 of the range \verb$x$.
%\verb$f$ is aligned to element 20 of the range \verb$k$.
%\verb$k$ has primitive range \verb$y$, so \verb$f$ is an
%embedding in \verb$y$, at element $64$.
%
%A {\em process group} is a set of (virtual) processes.  The process
%group has two r\"{o}les---a particular action can be performed within a
%specified process group, or a particular data object can be
%distributed over a specified process group.  The simplest example of a
%process group is a process array.  Adlib has a more general idea of a
%process group, which is a ``slice'' of a process array formed by
%restricting one or more of the process dimensions to a single
%coordinate.  The Adlib interface doesn't provide a direct means of
%specifying a process coordinate---a coordinate is defined 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 process groups \verb$q$, \verb$r$ and \verb$s$ are illustrated in
%figure \ref{processgroups}.
%\begin{figure}[btp]
%\centerline{\psfig{figure=procgroup.eps,height=3in}}
%\caption{\label{processgroups}Examples of process groups.  The square boxes
%represent the 16 virtual processes in the process array $p$.  The dashed
%lines embrace groups $q$, $r$ and $s$.}
%\end{figure}
%The {\em parent process array} of all these groups is \verb$p$.
%A process group has a set of {\em effective process dimensions} taken from the
%parent process array.  The effective dimension set for \verb$p$ contains
%\verb$p.dim(1)$ and \verb$p.dim(2)$.  The effective dimension set for \verb$q$
%contains just \verb$p.dim(2)$, while that for \verb$r$ contains just
%\verb$p.dim(1)$.  The set for \verb$s$ is empty.
%
%At any stage of execution of a program a particular process group is
%singled out as the {\em active process group}.  From the viewpoint of
%a particular process, the active process group is the set of processes
%sharing the current ``thread of control''.  Adlib supports a form of
%MIMD execution (see section \ref{where}) so there may be several
%distinct processes groups active at the same time, with the
%physical processes partitioned between these groups.
%
%A process group \verb$q$ with parent array \verb$p$ is {\em accessible}
%at a particular stage of program execution if the active process group
%is the same as the one in effect when \verb$p$ was created, or if it is
%a subarray of \verb$p$ which contains \verb$q$.
%
%
%\section{\label{communication}Communication}
%
%There are three families of communication operations in Adlib
%
%\subsection{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, but in
%common with all the communication routines described in this paper,
%\verb$remap$ is a collective operation.  All array-valued arguments
%must be distributed over process groups which are accessible at the
%point of the call.
%
%We will now give a small example of an Adlib program.  The HPF program
%in figure \ref{nnHPF} is a toy example of the nearest neighbour update
%paradigm.  The Adlib program in \ref{nnAdlib} is an equivalent Adlib
%program.  Construction of the array sections and declaration of temporaries
%has been lifted out of the loop over \verb$n$
%\begin{figure}[btp]
%\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}
%\caption{\label{nnHPF}Simple nearest neighbour update in HPF.}
%\end{figure}
%\begin{figure}[btp]
%\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) ;
%
%    Section1<float> u_l(u, sect(l)), u_r(u, sect(r)) ;
%
%    Range c(8, 1, 1, x) ;
%
%    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}
%\caption{\label{nnAdlib}Simple nearest neighbour update in Adlib.}
%\end{figure}
%
%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.
%
%
%\subsection{The {\em gather-scatter} family}
%
%The general \verb$gather$ operations have interfaces
%\begin{verbatim}
%  void gather(Frame& b, Frame& a, Frame* i_1) ;
%
%  void gather(Frame& b, Frame& a, Frame* i_1, Frame* i_2) ;
%
%  void gather(Frame& b, Frame& a, Frame* i_1, Frame* i_2,
%                                              Frame* i_3) ;
%  ...
%\end{verbatim}
%Here \verb$b$ is the {\em gathered data} and \verb$a$ is the {\em
%scattered data}.  These are followed by subscript arrays, which are
%integer arrays with the same shape and mapping as the gathered data.
%The number of subscripts should be equal to the rank of the scattered
%data, and their values should lie in the ranges expected by subscripts
%of that array.  Data is copied from \verb$a$ to \verb$b$ with the
%specified subscripting pattern.  A completely analogous primitive
%\verb$scatter$ copies data from \verb$b$ to \verb$a$.
%
%These operations are unnecesarily general if it is only required to
%implement the patterns of access in Fortran 90 array syntax (but they
%are needed for parallelising \verb$FORALL$, for example).  Vector
%subscripts can be handled by the simpler primitives
%\begin{verbatim}
%  void vecGather(Frame& b, Frame& a, Frame* i_1) ;
%
%  void vecGather(Frame& b, Frame& a, Frame* i_1, Frame* i_2) ;
%
%  void vecGather(Frame& b, Frame& a, Frame* i_1, Frame* i_2,
%                                                 Frame* i_3) ;
%  ...
%\end{verbatim}
%where now \verb$a$ and \verb$b$ have the same rank, and the subscripts
%are rank-1 arrays, whose individual ranges are the same as the
%corresponding to range of \verb$b$.  If any subscript argument is
%\verb$NULL$ it is assumed that the gathered and scattered data have the
%same extent in the associated dimension, and the operation behaves like
%an array assignment with respect to that dimension.  \verb$vecScatter$
%is similar.
%
%The {\em gather-scatter} family is related superficially to the {\em
%remap} family, but differs from it in a fairly deep way at the
%implementation level.  Simple remapping operations can be implemented
%efficiently in terms of direct message-passing; gather-scatter
%operations typically need data request protocols and bulk
%synchronisation.
%
%
%\subsection{The reduction family}
%
%     The simplest reduction primitive has the inteface
%\begin{verbatim}
%  void reduce(const int typeLen, char* res, Frame* src,
%              void (*opZero)(void*),
%              void (*opAccum)(void*, void*)) ;
%\end{verbatim}
%The cast to a character vector of length \verb$typeLen$, is replicated
%over the active process group.  The array \verb$src$ holds the input
%data; the accumulation operation is defined by the function
%\verb$opAccum$, and the function \verb$opZero$ sets data of the return
%type to the zero of the accumulation operation.
%
%Variants do reductions on pairs of arrays (scalar product operations
%and masked reductions) and reductions in single array dimensions, where
%the result is an array with rank reduced by one.
%
%\section{Miscellany}
%
%\subsection{Lower level interfaces}
%
%The interface described so far is probably at too high a
%level to be suitable as a target of compilation.  The expectation is
%that an intelligent compiler would in-line the implementations of the
%less efficient operations, in terms lower level interfaces.
%
%As an example, the implementation given for the {\em where} construct
%is fairly inefficient.  The iterator functions are quite complex, and
%calling the subscript member function on the arrays in every iteration
%is wasteful, when, in practise, data pointers are simply being
%incremented in most iterations.
%
%Lower level iterator functions are provided which just enumerate
%the set of individual contiguous index blocks held on the local
%physical process, and lower level inquiry functions on arrays provide
%direct access to the data layout---base addresses and strides.
%For example, the where construct given in section \ref{where}
%\begin{verbatim}
%  for(k.where() ; k.test() ; k.next()) {
%    b(k) = k() ;
%  } k.erewh() ;
%\end{verbatim}
%can be translated more efficiently by
%\begin{verbatim}
%  char*  b_base = b.dat() ;
%  Stride* b_str = b.str(1) ;
%
%  for(k.locBlocksEnum() ; k.locBlocksTest() ; k.locBlocksNext()) {
%    int count = k.blockCount() ;
%    int k_val = k() ;
%
%    char* b_data = b_base + b_str->offset(&k) ;
%    int   b_step = b_str->step(&k) ;
%
%    for(int i = 0 ; i < count ; i++) {
%      *((int*) b_data) = k_val ;
%
%      b_data += b_step ;
%      k_val++ ;
%    }
%  } 
%\end{verbatim}
%(Other lower level-functions directly manipulate the active process
%group data structure; these calls were ``optimised out'' in the example
%above, because there are no communication operations inside the {\em
%where} construct which access this data structure.)
%
%Within the implementation of higher level-operations like \verb$remap$,
%{\em where} constructs appear frequently.  They are implemented in the
%more efficient style illustrated here.
%
%\subsection{Non-Cartesian arrays}
%
%The original specification of Adlib called for support of {\em
%non-Cartesian arrays}.  These are non-rectangular arrays---essentially
%arrays of arrays.  The intention was that these would be understood by
%communication primitives like \verb$remap$, which could thus be used to
%move about array intermediates generated in translation of
%non-rectangular \verb$FORALL$ constructs.  Non-Cartesian arrays are not
%yet implemented.
%
%%\subsection{Promotions}
%
%
%\section{Fortran interface}
%
%The current Fortran interface to Adlib is quite restrictive (and
%inefficient).  Essentially it only provides access to the communication
%functions; Fortran arrays representing local segments of distributed
%arrays are passed in with dope vectors describing the data mapping.
%The interface code constructs Adlib class objects from this
%parametrisation, and dispatches the relevant C++ communication
%procedures.
%
%The Fortran interface provides functions which directly implement all
%the Fortran 90 intrinsic functions on arrays.
%
%
%\section{Implementation status}
%
%Adlib is part of the distribution of the Southamption High Performance
%Fortran, version 0.1, which is currently in Beta testing.
%It is written in C++, layered on top of MPI.
%
%The released version of Adlib is a prototype, offering full
%functionality, but poor performance.  Major optimisations are in
%progress (for example, a new version of \verb$remap$ is up to an order
%of magnitude faster on some platforms).


%\begin{thebibliography}{9}

%\bibitem{geometric} D.B.~Carpenter. {\em Geometric Parallelism.} Esprit
%Project PUMA workpackage 5.1, interim report.

%\end{thebibliography}

\end{document}

