
\documentstyle[psfig]{article}

\begin{document}

\sloppy

\pagestyle{plain}

\title{\em Programming in {\em ad++}}

\author{D.B. Carpenter \vspace{0.25in} \\ 
        \em Northeast Parallel Architectures Centre, \\
        \em Syracuse University, \\
        \em 111 College Place, \\
        \em Syracuse, New York 13244-410} 

\date{DRAFT}

\maketitle

\newpage

\tableofcontents

\newpage

\section{Overview of ad++}

{\em Adlib} is a C++ class library for data parallel programming.
It was originally designed as part of the run-time support system
for a public domain {\em High Performance Fortran} (HPF) compilation
system.  In this article we will emphasize the a user-level C++ interface to
Adlib called {\em ad++}, and illustrate how it can be used directly
for parallel programming in C++.

The ad++ library provides a set of abstract data types representing
parallel arrays.  As in HPF, an array can be distributed over a
logical {\em process array}, which the library maps transparently to
the available pool of physical processors.

The library also provides operations to implement a set of {\em
distributed control} constructs.  These constructs, called {\em on},
{\em at} and {\em overall} are data-parallel analogues of familiar
sequential control constructs like {\em if} and {\em for}.  They are
used for traversing parallel arrays.

Finally it provides a set of high-level communication
operations.  These are collective operations on parallel arrays.
They include
\begin{itemize}
\item
simple but general {\em remap} operations, which copy the whole
contents of one array to another of the same shape (but potentially
different mapping to the process array),
\item
generalised {\em gather-scatter} operations which allow any pattern of
array subscripting, and
\item
arithmetic reduction operations, which combine all elements of a
parallel array by some operation, such as addition or logical conjunction.
\end{itemize}

The ad++ interface embodies a high-level model of programming with
Adlib.  It comes with a caveat.  Although the array descriptor and
regular communication schedules of the underlying library are supposed
to be ``production-quality'', efficient implementations, the
distributed control macros of the ad++ interface, in particular the
distributed loop, are too inefficient to be used in real applications.
The kernel library definition describes transformations that can be
applied to make the {\em overall} construct acceptably efficient.

\section{This article}

Adlib has a rich functionality.  Its distributed data model is a
superset of the data model of HPF version 1.0.  Its control
constructs and communication library have been designed to fully
support {\em nested parallelism}, a powerful but often unimplemented
feature of HPF, which allows one to call parallel intrinisic functions
or user-defined {\em pure procedures} inside other parallel
constructs.

Rather than starting with complete, formal definitions of the ad++
classes and concepts, this article takes the reader as
quickly possible into ad++ programming through simple examples.  The
underlying concepts are then visited in more depth, in no
particular logical order.  By the end of the article
the reader should be familiar with all the main ideas in the library.

The article presumes some familiarity with data-parallel and SPMD
programming.  Familiarity with HPF would also be helpful.  Some
knowledge of C++ is required.

\section{Defining a process array}

ad++ provides a series of classes \verb$Procs1$, \verb$Procs2$,
\ldots derived from a common base class \verb$Procs$.  These classes
represent multi-dimensional {\em process arrays}.  A process array
represents a set of logical processes over which data and work can be
divided.

If there are fewer logical processes than processors available, each
logical process is mapped to a different processor, and some processors
hold none of the logical processes in the array.  In the present
implementation of Adlib it is not allowed to declare a process array
with more logical processes than the number of available
processors.

A {\em rank}-2 (two-dimensional) process array \verb$p$ is declared by
\begin{verbatim}
  Procs2 p(2, 2) ;
\end{verbatim}
\verb$p$ represents 4 processes arranged in a two by two array.  The
{\em shape} of a process array should be chosen by the programmer to
suit the the intended distribution format (blocking) of data arrays.
There is no implied pattern of connectivity or nearness between
individual processes.

The declaration of \verb$p$ is completely analogous to the HPF declaration
\begin{verbatim}
  !HPF$ PROCESSORS P (2, 2)
\end{verbatim}

A process array is {\em activated} by using the distributed control
macro {\tt ON}, and {\em deactivated} again by using the macro {\tt NO}.
We will always use these functions in a context like this:
\begin{verbatim}
  ON(p) {
    // ... some code
  } NO(p) ;
\end{verbatim}
This idiom is called an {\em on construct}.  The code inside the
construct is only executed by processors which hold part of \verb$p$.
Inside the construct, \verb$p$ is designated the {\em active
process group}.  It loses this status after on exit from the construct.

\section{\label{data}Distributed data}

A conventional array has a set of index ranges.  The ordinary C++ array
\begin{verbatim}
  float a [100] [10] ;
\end{verbatim}
has index ranges \verb$0..99$ and \verb$0..9$.  The index ranges
of an ad++ parallel array are more complex, because the elements of
the array are distributed over a process dimension.  A base class
\verb$Range$ is introduced to represent these ranges.
Two instances, \verb$x$ and \verb$y$ can be declared as follows
\begin{verbatim}
  BlockRange x(100, p.dim(0)), y(10, p.dim(1)) ;
\end{verbatim}
{\tt BlockRange} is a subclass of {\tt Range} which has simple
blockwise distribution format.
The first argument of the constructor for \verb$x$ specifies that the
{\em extent} of \verb$x$ is 100---its global indices run from
\verb$0..99$.  The second argument specifies that \verb$x$ is
distributed over the first dimension of \verb$p$.  The member
function \verb$dim$ has the signature
\begin{verbatim}
  Dimension Procs :: dim(const int d) ;
\end{verbatim}
Its argument is in the range $0, \ldots, R - 1$, where $R$ is the rank
of the process array.
It returns a new class of object representing an
individual dimension of a process array.
In this example
the extent of the process dimension is two, and array elements with
{\em global index} \verb$0..49$ are stored on the first row of processes and
elements with indices \verb$50..99$ on the second.

The range \verb$y$ is similar, but it has extent 10 and is distributed over
the second dimension of \verb$p$.

The \verb$x$, \verb$y$ declarations are comparable with the HPF
declarations
\begin{verbatim}
  !HPF$ TEMPLATE T (100, 10)
  !HPF$ DISTRIBUTE T (BLOCK, BLOCK) ONTO P
\end{verbatim}
The ranges \verb$x$ and \verb$y$ are analogous to the individual
dimensions of the template \verb$T$.

Returning to ad++, if \verb$p$ is the currently active process group,
a distributed array of floating point variables can be declared by
\begin{verbatim}
  Array2<float> a(x, y) ;
\end{verbatim}
This declaration is comparable to the HPF declarations
\begin{verbatim}
  REAL A (100, 10)
  !HPF$ ALIGN A WITH T
\end{verbatim}

The \verb$Array1$, \verb$Array2$,\ldots template classes are derived from
a base class \verb$DAD$ which provides various inquiry functions,
including
\begin{verbatim}
  Range DAD :: rng(const int d) ;
\end{verbatim}
The member \verb$rng$ is analogous to the \verb$dim$ member of
\verb$Procs$, but returns a range rather than a dimension.  Its
argument is in the range $0, \ldots, R - 1$, where $R$ is the rank of
the array.

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{elements}Accessing array elements}

Only a processor which holds a copy of an array element is allowed to
access that element directly.  Elements of an array can either be accessed
concurrently through a {\em distributed loop}, or they can be accessed
sequentially.  Concurrent access to distributed data is
particularly simple in ad++.  The range objects introduced in the
previous section can be used to construct {\em iterators} for distributed loops.
The iterators are activated by the macro \verb$OVERALL$.
Suppose \verb$p$ is the active process group, the code
\begin{verbatim}
  Index i(x), j(y) ;
  OVERALL(i) {
    OVERALL(j) {
      a(i, j) = i + j ;
    } ALLOVER(j) ;
  } ALLOVER(i) ;
\end{verbatim}
initialises every element of of \verb$a$ to the sum of its two {\em
global} index values.  A member of the \verb$Index$ class represents
the iterator of a distributed loop.
In general if \verb$i$ is an index the idiom
\begin{verbatim}
  OVERALL(i) {
    // ... some code
  } ALLOVER(i) ;
\end{verbatim}
is called an {\em overall construct}.

To explain better how the code fragment above works we need to
introduce a new class which represents {\em local subscripts}.
A local subscript defines a particular element of a distributed
range.  The range object behaves as a map from global index values to
local subscripts through the overloaded operator
\begin{verbatim}
  Location& Range :: operator()(const int) ;
\end{verbatim}
So the declarations
\begin{verbatim}
  Location s(x(75)), t(y(1)) ;
\end{verbatim}
create \verb$s$ as a local subscript representing element 75 of the
range \verb$x$, while \verb$t$ represents element 1 of \verb$y$.  A
\verb$Location$ object defines a particular coordinate within a
process array, and a particular offset within the index block (or array
block) held on a process at that coordinate.  Local subscripts can be
used directly to subscript arrays through the overloaded operator
\begin{verbatim}
  T& Array2<T> :: operator()(Location&, Location&) ;
\end{verbatim}
{\em But} use of this operator is only legal on a processor which
holds the selected element (a restriction which will be stated more
formally in section \ref{replicated}).  One way to test whether an element
is held locally is to use the third and final control construct
of ad++, the {\em at construct}.  The {\em at} construct looks rather
like the {\em on} construct, but uses the \verb$AT$ and \verb$TA$
macros, parametrized by members of \verb$Location$ class, as follows:
\begin{verbatim}
  AT(s) {
    AT(t) {
      a(s, t) = 76 ;
    } TA(t) ;
  } TA(s) ;
\end{verbatim}
The body of the construct executes only if the
processor executing the code holds a logical process 
with the coordinate defined by the subscript.  In general if
\verb$s$ is a local subscript the idiom for the {\em at} construct is
\begin{verbatim}
  AT(s) {
    // ... some code
  } TA(s) ;
\end{verbatim}

Now we return to the first example in this section.
The index object maintains some
internal state defining the global index value associated with the
current iteration.  The \verb$OVERALL$ macro is
defined so that the loop body executes just once for each
value of the global index held by the processor executing the code.
The body of the nested {\em overall} constructs:
\begin{verbatim}
  a(i, j) = i + j ;
\end{verbatim}
relies on a couple of clever tricks.
The use of \verb$i$ and \verb$j$ on the left hand exploits the fact
that the \verb$Index$ class is derived from the \verb$Location$ class.
While the index is activated, its \verb$Location$ component represents
the local subscript associated with the current iteration.
The use of \verb$i$ and \verb$j$ on the right hand side of the assignment
uses a defined conversion from \verb$Index$ to integer which returns
the global index associated with
the current iteration.  The equivalent code with explicit casts is
\begin{verbatim}
  a(i, j) = (int) i + (int) j ;
\end{verbatim}

This is a good point at which to collect together some of the
fragments introduced so far, to make our first complete, useless,
ad++ program
\begin{verbatim}
  Procs2 p(2, 2) ;

  ON(p) {
    BlockRange x(100, p.dim(0)), y(10, p.dim(1)) ;

    Array2<float> a(x, y) ;

    Index i(x), j(y) ;
    OVERALL(i) {
      OVERALL(j) {
        a(i, j) = i + j ;
      } ALLOVER(j) ;
    } ALLOVER(i) ;

  } NO(p) ;
\end{verbatim}
The program defines a process array, declares an array distributed
over the process array, and initialises its elements.  It is
comparable to the HPF program
\begin{verbatim}
  !HPF$ PROCESSORS P (4, 4)

  !HPF$ TEMPLATE T (100, 10)
  !HPF$ DISTRIBUTE T (BLOCK, BLOCK) ONTO P

  REAL A (100, 10)
  !HPF$ ALIGN A WITH T

  FORALL (I = 1 : 100, J = 1 : 10)
    A (I, J) = I + J
\end{verbatim}
There is one minor difference between the two programs and one major
difference.  The minor difference is that Fortran array indices start
from 1 by default, whereas Adlib global indices always start from 0.
The major difference is that the ad++ program specifies explicitly
that the computation \verb$i + j$ occurs on the process holding
element \verb$a(i, j)$.  In the HPF program the {\em owner computes}
heuristic adopted by most compilers would probably lead to \verb$I + J$
being computed on the home process of \verb$A(I, J)$, but this is not
required by the language definition.  HPF provides no means for the
programmer to state explicitly where a computation is performed---it is
at the compiler's discretion.  ad++, on the other hand, {\em forces} the
to programmer specify, through the distributed control constructs,
which process is responsible for every computation.

Although there are restrictions on the patterns of data access in the
body of the {\em overall} construct, arbitrary sequential control
constructs are allowed there.  For example, the kernel of a Mandelbrot
set computation is illustrated in figure \ref{mandel}.
\begin{figure}[btp]
\begin{verbatim}
  Procs2 p(2, 2) ;

  ON(p) {
    BlockRange x(N, p.dim(0)), y(N, p.dim(1)) ;

    Array2<float> colour(x, y) ;

    Index i(x), j(y) ;
    OVERALL(i) {
      OVERALL(j) {
        float cr = (4.0 * i - 2 * N) / (N - 1) ;
        float ci = (4.0 * j - 2 * N) / (N - 1) ;
        float zr = cr, zi = ci ;

        for (int i = 0 ; i < RESOLUTION &&
                         (zr * zr + zi * zi) < 4.0 ; i++) {
          zr = cr + zr * zr - zi * zi + cr ;
          zi = ci + 2 * zr * zi ;
        }

        colour (i, j) = i ;
      } ALLOVER(j) ;
    } ALLOVER(j) ;

  } NO(p) ;
\end{verbatim}
\caption{\label{mandel}Mandelbrot set kernel.}
\end{figure}

\section{\label{communication}Communication}

In Adlib, communication is normally achieved through collective operations
on distributed arrays.  One of the simplest is the \verb$shift$ operation,
whose interface is
\begin{verbatim}
  template<class T>
  void shift(const Section1<T>& dst, const Section1<T>& src,
             const int shift, const int dim, const Mode mode) ;

  template<class T>
  void shift(const Section2<T>& dst, const Section2<T>& src,
             const int shift, const int dim, const Mode mode) ;

  ...
\end{verbatim}
The parameters \verb$dst$ and \verb$src$ are arrays, which must have
identical type, shape and mapping (for now, we take this to mean that
they share the same range structures).  
{\tt Section1<T>}, {\tt Section2<T>}, \ldots are base classes of 
{\tt Array1<T>}, {\tt Array2<T>}, \ldots.
The operation shifts the values
in \verb$src$ by \verb$shift$ places in the \verb$dim$ dimension, and
puts the result in \verb$dst$.  \verb$shift$ is a signed integer.
\verb$dim$ is in the range $0, 1, \ldots, R - 1$, where $R$ is the rank of
the arrays.  \verb$mode$ is one of \verb$CYCL$ or \verb$EDGE$,
selecting either cyclic or ``edge-off'' shift.

With \verb$shift$ we can write some more meaningful programs.  In
figure \ref{pde} the {\em overall} construct replaces each element of
\verb$w$ (except those on the edges) with the average of the four
neighbouring values.  This is the kernel of simplified PDE solver.
\begin{figure}[btp]
\begin{verbatim}
  Procs2 p(2, 2) ;

  ON(p) {
    BlockRange x(N, p.dim(0)), y(N, p.dim(1)) ;

    Array2<float> w(x, y) ;

    // ... some code to initialise `w'

    Array2<float> wnx(x, y), wpx(x, y), wny(x, y), wpy(x, y) ;

    shift(wnx, w,  1, 0, EDGE) ;
    shift(wpx, w, -1, 0, EDGE) ;
    shift(wny, w,  1, 1, EDGE) ;
    shift(wpy, w, -1, 1, EDGE) ;

    Index i(x), j(y) ;
    OVERALL(i) {
      OVERALL(j) {
        if(i != 0 && i != N - 1 && j != 0 && j != N - 1)
          w(i, j) = 0.25 *
              (wnx(i, j) + wpx(i, j) + wny(i, j) + wpy(i, j)) ;
      } ALLOVER(j) ;
    } ALLOVER(i) ;

  } ON(p) ;
\end{verbatim}
\caption{\label{pde}PDE solver kernel.}
\end{figure}
Figure \ref{life} performs an iteration of Conway's Life.
\begin{figure}[btp]
\begin{verbatim}
  Procs2 p(2, 2) ;

  ON(p) {
    BlockRange x(N, p.dim(0)), y(N, p.dim(1)) ;

    Array2<int> c(x, y) ;

    // ... some code to initialise `c'

    Array2<int> cn_(x, y), cp_(x, y), c_n(x, y), c_p(x, y),
                cnn(x, y), cnp(x, y), cpn(x, y), cpp(x, y) ;

    shift(cn_, c,  1, 0, CYCL) ;
    shift(cp_, c, -1, 0, CYCL) ;
    shift(c_n, c,  1, 1, CYCL) ;
    shift(c_p, c, -1, 1, CYCL) ;
    shift(cnn, cn_,  1, 1, CYCL) ;
    shift(cnp, cn_, -1, 1, CYCL) ;
    shift(cpn, cp_,  1, 1, CYCL) ;
    shift(cpp, cp_, -1, 1, CYCL) ;

    Index i(x), j(y) ;
    OVERALL(i) {
      OVERALL(j) {
        switch (cn_(i, j) + cp_(i, j) + c_n(i, j) + c_p(i, j) +
                cnn(i, j) + cnp(i, j) + cpn(i, j) + cpp(i, j)) {
          case 2 :
            break ;
          case 3 :
            c(i, j) = 1 ;
            break ;
          default :
            c(i, j) = 0 ;
            break ;
        }
      } ALLOVER(j) ;
    } ALLOVER(i) ;

  } NO(p) ;
\end{verbatim}
\caption{\label{life}Conway's Life iteration.}
\end{figure}

Adlib provides many communication operations more powerful than
\verb$shift$.  They will be introduced in later sections.

\section{\label{subranges}Subranges}

The ranges introduce so far were {\em template ranges}.  Adlib also
has an idea of a {\em subrange}.  A subrange is a subrange
of some other range (and, ultimately, of some template range).  It
retains an {\em alignment} to its parent range.  The location of a
subrange element remains the same as the corresponding element of the
parent range.
\begin{verbatim}
  BlockRange x(N, p.dim(0)) ;
  Range u = x.subrng(N - 2, 1) ;
\end{verbatim}
The range \verb$u$ is a subrange of \verb$x$.  It has extent $N - 2$ and
offset 1.  Element 0 of \verb$u$ is aligned with element 1 of \verb$x$,
element 1 with element 2, and so on.  The last element of \verb$u$,
element $N - 3$, is aligned with the penultimate element, $N - 2$, of
\verb$x$.

As an immediate application, the {\em overall} construct in figure
\ref{pde} could be replaced by
\begin{verbatim}
    Index k(x.subrng(N - 2, 1)) ;
    Index l(y.subrng(N - 2, 1)) ;

    OVERALL(k) {
      OVERALL(l) {
        w(k, l) = 0.25 *
            (wnx(k, l) + wpx(k, l) + wny(k, l) + wpy(k, l)) ;
      } ALLOVER(l) ;
    } ALLOVER(k) ;
\end{verbatim}
This works because a local subscript constructed from a subrange
is exactly equivalent to a subscript constructed from a parent range at
an aligned point.  The advantage of the new version is that we have
eliminated an expensive test from the inner body of the loops.

If the original code had been something like
\begin{verbatim}
    Index i(x), j(y) ;
    OVERALL(i) {
      OVERALL(j) {
        if(i != 0 && i != N - 1 && j != 0 && j != N - 1)
          w(i, j) = i + j ;
      } ALLOVER(j) ;
    } ALLOVER(i) ;
\end{verbatim}
with a dependence on global index value, we could still perform
the above transformation by declaring \verb$k$, \verb$l$ as above, then
\begin{verbatim}
    OVERALL(k) {
      OVERALL(l) {
        w(k, l) = x(k) + y(l) ;
      } ALLOVER(l) ;
    } ALLOVER(k) ;
\end{verbatim}
This exploits the operator
\begin{verbatim}
  int Range :: operator()(Location&) ;
\end{verbatim}
which effectively allows a range to subscripted as if it were a
one-dimensional array holding its global index values.

It is possible to specify a stride in a subrange, as in
\begin{verbatim}
  Range t = x.subrng(10, 20, 2) ;
\end{verbatim}
Element 0 of range \verb$t$ is aligned with element 20 of range
\verb$x$, element 1 with element 22, etc.

Arrays can be declared with subranges.  This mechanism allows
affine alignment between arrays, as provided in HPF 1.0.

\section{\label{groups}Process groups}

A {\em process group} is a set of logical processes, such as a process
array.  In general a process group has two roles---a particular
action can be performed within a specified process group, or a
particular data object can be distributed over a specified process
group.

All the examples so far used process groups in a peripheral way.
One process array was declared, immediately activated by an
{\em on} construct, and deactivated at the end of the program.
This static approach to process configuration is
enough to write many useful programs, but Adlib provides
more flexibility, if that flexibility is needed.

A program can declare several different process arrays, possibly of
different rank.  Data arrays declared in the earlier examples were
always distributed over the unique {\em active process group}.  In
general the array constructor takes a process group as its last
argument, specifying that the data is distributed over that group.
In this way a program can contain coexisting arrays distributed
over different groups.  For example
\begin{verbatim}
  Procs2 p(2, 2) ;
  Procs1 q(3) ;

  BlockRange x(10, p.dim(0)), y(10, p.dim(1)) ;
  Array2<float> a(x, y, p) ;

  BlockRange z(100, q.dim(0)) ;
  Array1<int> b(z, q) ;

  ON(p) {
    // ... some code processing `a'
  } NO(p) ;

  ON(q) {
    // ... some code processing `b'
  } NO(q) ;
\end{verbatim}
Note that \verb$p$ and \verb$q$ can only activated in turn, {\em not}
concurrently.
We will see section \ref{remap} how data can be transferred between data arrays
distributed over different process groups.

Adlib also 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 is defined implicitly by a local subscript.
The operator \verb$/$ is overloaded to construct a new process group
(class \verb$Group$) from an existing 
process group and a subscript.
\begin{verbatim}
  Procs2 p(4, 4) ;

  BlockRange x(20, p.dim(0)), y(20, p.dim(1)) ;

  Location i(x(12)), j(y(7)) ;

  Group q(p / i) ;
  Group r(p / j) ;
  Group s(q / j) ;
\end{verbatim}
The 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 logical 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$.
Sometimes we refer to groups like \verb$q$, \verb$r$ and \verb$s$
as {\em restricted process groups}.  A process group is either a
process array or a restricted process group.

Any process group has a set of process dimensions
taken from its parent array.  The {\em dimension set} for \verb$p$ is
\verb$p.dim(0)$ and \verb$p.dim(1)$; the set for \verb$q$ is just
\verb$p.dim(1)$; the set for \verb$s$ is empty.

The generalised process group provides more refined way to describe the
active process group inside the ad++ control constructs (see section
\ref{apg}), and to describe the process groups over which general {\em
array sections} are distributed (see section \ref{sections}).

\section{\label{apg}The active process group}

At any point of execution of a program, one group is singled out as the
{\em active process group} (APG).  From the viewpoint of a particular
processor, the active process group is the set of processes sharing the
current ``thread of control''.

There is a natural {\em contains} relationship between certain process
groups.  Group $p$ contains group $q$ if
\begin{enumerate}
\item
$p$ was the active process group at the point at which $q$
was declared, or
\item
$q$ is a sub-array of $p$, constructed by the \verb$/$ operation.
\item
$p$ contains some process array $r$ which in turn contains $q$.
\end{enumerate}
For example
\begin{verbatim}
  Procs1 p(6) ;
  ON(p) {
    Procs2 r(2, 2) ;

    BlockRange x(100, r.dim(1)) ;
    Group q(r / x(50)) ;

    // ...
  } NO(p) ;
\end{verbatim}
Here, \verb$p$ contains \verb$r$ by rule 1 above, \verb$r$ contains
\verb$q$ by rule 2, and \verb$p$ contains \verb$q$ by rule 3.
As a matter of convention we say that a group contains itself.

%Adlib supports MIMD
%execution through the {\em overall} construct, so there may be several
%distinct processes groups active at the same time.

The three ad++ control constructs affect the active process group
in the following ways.
\begin{itemize}
\item
If the active process group is currently \verb$p$, and \verb$q$ is another
process group, inside
\begin{verbatim}
  ON(q) {
    // ...
  } NO(p) ;
\end{verbatim}
the \verb$ON(q)$ operation changes the active process group to
\verb$q$.  The \verb$NO(p)$ operation restores it to \verb$p$.
\item
If the active process group is currently \verb$p$ and \verb$s$ is a subscript,
then inside
\begin{verbatim}
  AT(s) {
    // ...
  } TA(s) ;
\end{verbatim}
the \verb$AT(s)$ operation changes the active process group to \verb$p / s$.
The \verb$TA(s)$ operation restores it to \verb$p$.
\item
If the active process group is \verb$p$ and \verb$i$ is an index, inside
\begin{verbatim}
  OVERALL(i) {
    // ...
  } ALLOVER(i) ;
\end{verbatim}
the \verb$OVERALL(i)$ operation changes the active process group to
\verb$p / i$, assuming the coercion from index to subscript explained
in section \ref{elements}.  The \verb$ALLOVER(i)$ operation restores it
to \verb$p$.
\end{itemize}
Each construct has a precondition
\begin{itemize}
\item
An {\em on} construct can appear only if its process
group is contained in the active process group.
\item
An {\em at} construct can appear only if its subscript is
derived from a range distributed over a dimension of the active
process group.
\item
A {\em overall} construct can appear only if the range of its index is
distributed over a dimension of the active process group.
\end{itemize}
One effect of these rules is to outlaw the appearance of nested {\em
at} or {\em overall} constructs if their subscripts or index ranges are
distributed in the same dimensions.  The groups activated by {\em at}
and {\em overall} are strictly smaller than the surrounding APG, reduced
in rank by one.  (The {\em on} construct, on the other hand, can leave
the APG unchanged, if its argument happens to be identical to the current
APG.)

\section{\label{sections}Array sections}

ad++ supports array sections analogous to Fortran array sections
through the member function \verb$sect$.

Suppose we have the ad++ declarations
\begin{verbatim}
  Procs2 p(2, 2) ;

  BlockRange x(10, p.dim(0)) ;
  BlockRange y(10, p.dim(1)) ;
  
  Array2<int> a(x, y, p) ;
\end{verbatim}
which are comparable to the HPF declarations
\begin{verbatim}
  !HPF$ PROCESSORS P (2, 2)
  !HPF$ TEMPLATE T (10, 10)
  !HPF$ DISTRIBUTE T(BLOCK, BLOCK) ONTO P

  INTEGER A(10, 10)
  !HPF$ ALIGN A (:, :) WITH T
\end{verbatim}
In ad++ a section of \verb$a$ can be introduced as follows
\begin{verbatim}
  Range u = x.subrng(8, 1) ;
  Range v = y.subrng(8, 1) ;

  Section2<int> b = a.sect(u, v) ;
\end{verbatim}
\verb$u$ and \verb$v$ are subranges similar to the ones introduced
in section \ref{subranges}.  The array \verb$b$ represents a
section of \verb$a$ containing only the non-edge points.  It provides
an alias for this section of \verb$a$'s data.  This alias can be passed
to ad++-defined procedures (including other section constructors) and
user-defined procedures in just the same way as a full data array.

The section \verb$b$ is comparable with the Fortran section
\begin{verbatim}
  A (2 : 9, 2 : 9)
\end{verbatim}
Fortran, unlike ad++, does not allow this section to be named, {\em
except} by passing it to a procedure and referencing it as a dummy
argument.

A local subscript can
be passed to a section-constructor, in place of a range.
With the earlier declarations we could also define
\begin{verbatim}
  Location i(y(5)) ;
  Section1<int> c = a.sect(x, i) ;
\end{verbatim}
which makes \verb$c$ analogous to the Fortran section
\begin{verbatim}
  A (:, 6)
\end{verbatim}

Note:
\begin{itemize}
\item
Any range or subscript passed to an array constructor must be derived
from the range used to construct the parent array argument.
\item
Like any other data array in ad++, a section is distributed over a
particular process group.  The section \verb$b$ is distributed over
\verb$p$.  The section \verb$c$ is distributed over \verb$p / y(5)$.
In general the section is distributed over the same group as the parent
array, restricted by any local subscript arguments.
\end{itemize}
Incidentally, it is not only array sections that can be distributed over
restricted process groups.  With the above declarations, the ad++ code
\begin{verbatim}
  Array1<int> d(x, p / i) ;
\end{verbatim}
is comparable to the HPF 1.0 code
\begin{verbatim}
  INTEGER D (10)
  !HPF$ ALIGN D (:) WITH T (:, 6)
\end{verbatim}

The \verb$DAD$ base class provides the inquiry function
\begin{verbatim}
  Group DAD :: grp() ;
\end{verbatim}
which returns the process group over which an array is distributed.

\section{\label{remap}\em remap}

     In section \ref{communication} we introduced one of the simplest
communication operations in Adlib---the shift.  A much more powerful
cousin of \verb$shift$ is \verb$remap$.

     The deceptively simple interface of \verb$remap$ is
\begin{verbatim}
  template<class T>
  void remap(const Section1<T>& dst, const Section1<T>& src) ;

  template<class T>
  void remap(const Section2<T>& dst, const Section2<T>& src) ;

  ...
\end{verbatim}
The two arguments are arrays of the same type and shape.  The operation
just copies \verb$src$ to \verb$dst$.  The mapping of the two arrays is
unrestricted.  They can be distributed differently over the same
process group, or they can be distributed over different process
groups.  The only constraint on the arguments is that they are both
{\em accessible}.  An array is accessible if it is distributed over a
process group contained in the active process group.  Nearly all
collective operations in Adlib require their array arguments to be
accessible\footnote{A significant exception is the section
constructor introduced in the last section, which only requires that the
{\em constructed} array is accessible.  The whole of the parent array need
not by accessible.}.

    Used in conjunction with array sections, \verb$remap$ can implement
many patterns of communication.  For example the shift in
\begin{verbatim}
  BlockRange x(N, p.dim(0)) ;
  Array1<float> a(x), b(x) ;

  shift(a, b, 1, 0, EDGE) ;
\end{verbatim}
could be coded (more clumsily) as
\begin{verbatim}
  Range u = x.subrng(N - 1, 1), v = x.subrng(N - 1, 0, x) ;
  remap(a.sect(u), b.sect(v)) ;
\end{verbatim}
Here we used the section constructor inline to create anonymous sections.
The code is comparable to the Fortran
\begin{verbatim}
  REAL A (N), B (N)

  A (2 : N) = B (1 : N - 1)
\end{verbatim}

\section{\label{replicated}Replicated data}

Consider the array declarations in
\begin{verbatim}
  Procs2 p(2, 2) ;
  ON(p) {
    BlockRange x(10, p.dim(0)) ;
    BlockRange y(10, p.dim(1)) ;
    
    Array2<int> a(x, y) ;
    Array1<int> b(x) ;
    Array0<int> c ;

    // ...
  } NO(p) ;
\end{verbatim}
Arrays like \verb$a$, with ranges distributed over all dimensions of
their process group, have been illustrated many times in earlier
examples.  Array \verb$b$, on the other hand, is distributed over the
active process group \verb$p$, but has no range distributed over
\verb$p.dim(1)$.  Array \verb$c$ has no range distributed over {\em
any} dimension of \verb$p$.

In general an array need not have ranges distributed over {\em all}
dimensions of its process group (but each distributed range of an array
must be distributed over a distinct dimension of that group).

Array \verb$b$ is {\em replicated} over dimension \verb$p.dim(1)$.
Similarly \verb$c$ is replicated over both dimensions of the process
array.

Any simple C++ variable is replicated over the process group
active at the time at its declaration.  The array \verb$c$ only differs
from a such a variable by being wrapped up as an array.
This mean that it can be passed to operations such as \verb$remap$.

The fragment
\begin{verbatim}
  remap(c, a.sect(x(5), y(5))) ;
\end{verbatim}
is a broadcast, copying the \verb$(5, 5)$ element of \verb$a$ into the
single replicated element of \verb$c$.  This value can then be referenced
simply as \verb$c()$.  Notice that both arguments of \verb$remap$ must
be rank-0 arrays here, so the second argument had to be a section.  We could
not simply write \verb$a(x(5), y(5))$, because that expression
evaluates to a simple \verb$int$\footnote{And this expression is
undefined except on the processor which holds the element.}, whereas
\verb$remap$ requires an array argument.

We have to follow some rule in updating replicated data, to
ensure that copies remain consistent.  An operation like
\begin{verbatim}
  Index i(x), j(y) ;
  OVERALL(i) {
    OVERALL(j) {
      a(i, j) = b(i) ;
    } ALLOVER(j) ;
  } ALLOVER(i) ;
\end{verbatim}
ought to be allowed, whereas
\begin{verbatim}
  OVERALL(i) {
    OVERALL(j) {
      b(i) = a(i, j) ;
    } ALLOVER(j) ;
  } ALLOVER(i) ;
\end{verbatim}
should be forbidden, because it would (presumably) create inconsistent
values for the elements of \verb$b$, which are supposed to be replicated
across different processors.

The rule is simple enough.  Suppose a rank-$R$ array $a$ is
distributed over process group $p$.  If $s_1, \ldots, s_R$ are suitable
local subscripts, then, as a matter of definition, the array element
$a(s_1, \ldots, s_R)$, is replicated over $p / s_1 / \ldots / s_R$.
Now the required rule is
\begin{quote}
An array element can only be updated when the active process group is
identical to the group over which the element is replicated.
\end{quote}
We can also generalize and make more precise a rule about general
access to array elements which was stated informally in section
\ref{elements}.  The new formulation is:
\begin{quote}
The value of an array element can only be accessed if it is replicated over
a group containing the active process group.
\end{quote}
With the understanding that simple C++ variables are replicated over
the group active at their point of declaration, we propose that
they satisfy the same access rules.

\section{\label{otherRanges}Other distribution formats}

So far we have only seen one distribution format for 
template ranges---simple block distribution.
Adlib currently supports several other formats
\begin{itemize}
\item
collapsed
\item
simple cyclic
\item
block cyclic
\item
step
\end{itemize}
A collapsed range is declared with the syntax
\begin{verbatim}
  Range x(100) ;
\end{verbatim}
The range \verb$x$ is not distributed across any process array.  It is
mapped into the memory of a single logical process.
For example
\begin{verbatim}
  Range x(100) ;
  Array1<float> a(x) ;

  Procs1 p(4) ;
  BlockRange y(100, p.dim(0)) ;
  Array1<float> b(y, p) ;

  // ... initialize `b'

  remap(a, b) ;
\end{verbatim}
The array \verb$a$ retains the slightly awkward syntax \verb$a(x(n))$ for
accessing element \verb$n$, but is otherwise essentially a sequential
array: a copy of all elements are held on all processes of the active
process group\footnote{A {\em where} construct parametrised by \verb$x$
would be perfectly legal, but an ordinary {\em for} loop is probably
more conveninent for processing \verb$a$.  An {\em at} construct
parametrised by a subscript in \verb$x$ is legal, but fairly redundant, as it
has no effect on the active process group.}.
The \verb$remap$ operation implements a ``concatenate'' operation which
copies the distributed array \verb$b$ to the sequential array \verb$a$.
In general an array can have a free mixture of distributed ranges
and collapsed ranges.

A range is declared with simple cyclic distribution by
\begin{verbatim}
  CyclicRange y(100, p.dim(d)) ;
\end{verbatim}
Element $i$ of the range is mapped to a process with coordinate
$i \bmod P_d$, where $P_d$ is the extent of \verb$p.dim(d)$.

{\em [HPF-style block-cyclic distribution is also supported, but
the ad++ syntax for the range constructor is under revision.]}
%\begin{verbatim}
%  Range z(100, p.dim(d), CYC, 10) ;
%\end{verbatim}
%mapping element $i$ to $[i / 10] \bmod P_d$.

{\em Step} distribution is specified by
\begin{verbatim}
  StepRange w(100, p.dim(d)) ;
\end{verbatim}
This format is similar to simple block distribution except that the first
$100 \bmod P_d$ processes are assigned $b + 1$ range elements and the
remaining processes are assigned $b$ elements, for suitably chosen block size
$b$.

All of the template ranges support subranges as described in section
\ref{subranges}.

\section{Other communication operations}

There are three main families of communication operations in Adlib
\begin{itemize}
\item
the {\em remap} family.
\item
the {\em gather-scatter} family, and
\item
the {\em reduction} family.
\end{itemize}
All the communication operations described here are {\em collective}
operations.  They must be invoked consistently by all members of the
active process group.  A powerful feature of Adlib, designed to support
``nested parallelism'', is that collective operations such as
communication operations and 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\footnote{It is generally required that all array arguments of
the operation are accessible, as explained in section \ref{remap}.}.  Any
synchronisation implied by the collective operation affects just the
processors cooperating in a particular active process group, leaving
other processors undisturbed.  So it is legal to call a {\em
shift} operation, say, inside an {\em overall} construct, as in
\begin{verbatim}
  Array2<int> a(x, y), b(x, y) ;

  Index j(y) ;
  OVERALL(j) {
    shift(b.sect(x, j), a.sect(x, j), j, 0, CYCL) ;
  } ALLOVER(j) ;
\end{verbatim}
which implements a skewed shift of \verb$a$.
The \verb$sect$ functions create rank-1 arrays representing
individual columns of \verb$a$ and \verb$b$\footnote{the final use of
{\em j} in the {\em shift} operation is as an integer global index.}.

The {\em remap} family includes \verb$remap$ itself, \verb$shift$
and a few similar operations.

The {\em gather-scatter} family includes various operations
which allow more complex non-linear subscripting patterns
in access to distribute arrays.

The general \verb$gather$ operations have interfaces
\begin{verbatim}
  template<class T>
  void gather(const Section1<T>& b, const Section1<T>& a,
              const Section1<int>& s_1) ;

  template<class T>
  void gather(const Section2<T>& b, const Section1<T>& a,
              const Section2<int>& s_1) ;
  ...

  template<class T>
  void gather(const Section1<T>& b, const Section2<T>& a,
              const Section1<int>& s_1,
              const Section1<int>& s_2) ;

  template<class T>
  void gather(const Section2<T>& b, const Section2<T>& a,
              const Section2<int>& s_1,
              const Section2<int>& s_2) ;
  ...
\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$.
Adlib also provides a {\em combining scatter} which
is parametrised by some combining function.


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}
  template<class T>
  void vecGather(const Section1<T>& b, const Section1<T>& a,
                 const Section1<int>* s_1) ;

  template<class T>
  void vecGather(const Section2<T>& b, const Section2<T>& a,
                 const Section1<int>* s_1,
                 const Section1<int>* s_2) ;

  ...
\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 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 simplest reduction primitive has the inteface
\begin{verbatim}
  template<class T>
  T sum(const Section1<T>& src) ;

  template<class T>
  T sum(const Section2<T>& src) ;

  ...
\end{verbatim}
This adds all elements of {\tt src}, broadcasting the result over the
active process group.  Variants include all reductions (including
searches and scalar products) from the Fortran 90 transformational
intrinsics.

\end{document}

