
\documentstyle{article}

\input{psfig} 

\begin{document}

\sloppy

\pagestyle{plain}

\title{{\em Adlib} Language Reference \\
       \em [DRAFT]}

\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{\em [DRAFT]}

\maketitle

\newpage

\tableofcontents

\newpage

Adlib is implemented as a C++ class library, and Adlib programs can be
compiled with any standard C++ compiler.  But a well-designed class library
effectively extends the programming language in which it is
implemented.  This document introduces the basic principles of Adlib
programming, emphasizing the high-level, language-semantic view of
the library.  It deliberately omits details of lower level classes,
even where direct access to these classes may be highly desirable for
efficiency reasons.  As a rule, code inlining and optimization should
be a mechanical procedure, once the program is expressed in terms of
the higher level constructs introduced here.

\section{Process groups}

The Adlib model of distributed data is underpinned by a handful
of closely related classes for describing sets of processes.
The classes involved are
\begin{itemize}
\item
the {\em process grid},
\item
the {\em process dimension},
\item
the {\em process coordinate}, and
\item
the {\em process group}---a subset of a process grid.
\end{itemize}
Important associated concepts are the {\em active process group},
which abstracts the set of processes cooperating in a single
``loosely synchronous'' thread of control, and the ``distributed
control'' constructs {\em on} and {\em at} which manipulate this
group.

\subsection{Process grids and dimensions}

A {\em process grid} is a multi-dimensional set of
processes.  Any process grid is a member of the class \verb$Procs$.
Instances are typically created through constructors for the
subclasses \verb$Procs0$, \verb$Procs1$, \verb$Procs2$, \ldots, which
represent rank-0, rank-1, rank-2, \ldots, process grids.
(A rank-0 process grid is a scalar ``grid'' containing a single
virtual process.)

The standard constructor for a rank-\verb$R$ process grid takes \verb$R$
positive integer arguments---the extents of grid.
The specified size of the grid---the product of the extents---must be less
than or equal to the size of the process group active at the time of
declaration of the grid\footnote{The term ``active process group'' will be
precisely defined later.}.  At most one process from any particular grid
is mapped to each available physical process.

Examples of process grid declarations:
\small
\begin{verbatim}
  Procs2 p(2, 2) ;
  Procs0 s ;
\end{verbatim}
\normalsize
For convenience default constructors are also provided for
\verb$Procs1$, \verb$Procs2$, \ldots.  These will choose the extents
of the constructed grid by some heuristic, taking account of the available
number of processes.

A rank-\verb$R$ process grid has \verb$R$ associated {\em process dimensions}.
A process dimension is a member of the class \verb$Dimension$.  The
dimensions of a process grid are accessed through the inquiry
\begin{verbatim}
  Dimension Procs :: dim(int d) ;
\end{verbatim}
where \verb$d$ is in the range \verb$0, ..., R - 1$.  For example
\small
\begin{verbatim}
  Dimension p1 = p.dim(0), p2 = p.dim(1) ;
\end{verbatim}
\normalsize
\verb$p1$ is initialized to the first dimension of \verb$p$, and \verb$p2$ to
the second.

The extent of a process dimension can be determined through the member 
function
\begin{verbatim}
  int Dimension :: size() ;
\end{verbatim}
For example
\small
\begin{verbatim}
  const int n1 = p1.size(), n2 = p2.size() ;
\end{verbatim}
\normalsize
\verb$n1$ is initialized to the extent of \verb$p1$ and \verb$n2$ to
the extent of \verb$p2$.  In the example \verb$n1$ or \verb$n2$ will
both be 2.
The position of the local process in a process dimension can be
determined through the member function
\begin{verbatim}
  int Dimension :: crd() ;
\end{verbatim}
This returns a value in the range \verb$0, ..., n - 1$, where \verb$n$
is the extent of the dimension.

We will see later that there are ways to obtain a null process
dimension.  It is illegal to apply the \verb$size$ or \verb$crd$
inquiry functions to a null dimension.

\subsection{Coordinates}

A {\em coordinate} denotes a position in a particular process
dimension.  It is a member of the class \verb$Coord$.
\begin{verbatim}
  struct Coord {
    Dimension dim ;
    int crd ;

    Coord(int _crd, Dimension _dim) ;
  } ;
\end{verbatim}
A \verb$Coord$ is a simple record containing two publicly
accessible data members: \verb$dim$ and \verb$crd$.
\verb$dim$ is the process dimension in which the coordinate
is effective; \verb$crd$ is the coordinate itself.  \verb$crd$
must be in the range \verb$0, ..., n - 1$, where \verb$n$ is
the extent of the dimension.  For example, assuming the definitions
of \verb$p1$, \verb$p2$ given in the previous section,
\small
\begin{verbatim}
  Coord c(0, p1), d(1, p2) ;
\end{verbatim}
\normalsize
declares \verb$c$ as a coordinate in \verb$p1$ and \verb$d$
as a coordinate in \verb$p2$.

Although the data members of \verb$Coord$ are publicly
accessible, it is not normally necessary to read or
write them directly.  It is even quite unusual to create a
\verb$Coord$ object by direct use of its constuctor.  More commonly
these objects are created implicitly by creating objects of the derived
class \verb$Subscript$.

By definition, a null coordinate is one with a null \verb$dim$
field and an undefined \verb$crd$ field.

\subsection{Groups}

A (process) {\em group} may be a whole process grid or a {\em
restricted group}, which is some ``slice'' of a process grid.
In any case, a group is a member of the class \verb$Group$.

A restricted group is constructed with the operator
\begin{verbatim}
  Group Group :: operator/(Coord& c) const ;
\end{verbatim}
For example, assuming the definitions of \verb$p$, \verb$c$ and
\verb$d$ given in the previous two sections,
\small
\begin{verbatim}
  Group q = p / c ;
  Group r = q / d ;
\end{verbatim}
\normalsize
\begin{figure}[btp]
\centerline{\psfig{figure=groupsEg.eps,height=2.5in}}
\caption{\label{groupsEg}Examples of process groups.  The square boxes
represent the 4 processes in the process array $p$.  The dashed
lines embrace groups $p$, $q$ and $r$.}
\end{figure}
These groups are illustrated in figure \ref{groupsEg}.  The coordinate
operand must be a coordinate in a dimension of the group operand.  The
dimension set of the restricted group is the dimension
set of the operand group minus the dimension of the restricting
coordinate.
In the example, the dimension set of \verb$q$ is just \verb$p2$, and
dimension set of \verb$r$ is empty.

Applying a null coordinate to a group through the \verb$/$ operator
returns the original group, unchanged.

\subsection{The Active Process Group and the {\em on} construct}

At any point of program execution a particular group is singled out as
the {\em active process group}.  This is the group of processes
cooperating in the current ``thread of control''.  Before explaining
how the active process group is set, we need a couple of definitions.

There is a natural {\em contains} relationship between certain process
groups.  Group \verb$p$ contains group \verb$q$ if
\begin{enumerate}
\item
\verb$q$ is a process grid and
\verb$p$ was the active process group when \verb$q$
was declared (constructed), or
\item
\verb$q$ is a sub-group of \verb$p$, constructed by the \verb$/$ operation, or
\item
\verb$p$ contains some group \verb$r$ which in turn contains
\verb$q$---``contains'' is a transitive relation.
\end{enumerate}
These cases are illustrated by example at the end of this section.
As a matter of convention we will also say that a group contains itself.

A group is {\em accessible} at a particular point in program execution
if it is contained in the active process group.

The active process group can be altered through the {\em on} construct.
If \verb$p$ {\em is an accessible group} and \verb$S$ is some
statement, the {\em on} construct takes the form
\begin{verbatim}
  if(p.on())
    S
  p.no() ;
\end{verbatim}
The \verb$on$ member returns a truth value which is non-zero if the
physical process executing the code holds a process from \verb$p$.  So
the code inside the construct is only executed by processors that hold
part of \verb$p$.  After the \verb$p.on()$ call, \verb$p$ is the
designated active process group.  It loses this status after the
\verb$p.no()$ call---the earlier active process group is restored.

The idiom for the {\em on} construct is probably best regarded as an
atomic language construct, and the macros \begin{verbatim}
  #define on(p) if(p.on())
  #define no(p) p.no()
\end{verbatim}
are sometimes defined so that the {\em on} construct can be written 
slightly more compactly as\footnote{Syntactically this construct
resembles the atomic {\tt do S while(E) ;} statement of C or C++.
This is slightly deceptive.  The {\em on} construct is actually composed of
two separate C++ statements: {\tt on(P) S}, followed by {\tt no(P) ;}.
This is an inconvience imposed by the macro implementation.}
\begin{verbatim}
  on(p)
    S
  no(p) ;
\end{verbatim}

Finally we will illustrate the definition of the ``contains'' relation.
Take the example:
\small
\begin{verbatim}
  Procs1 p(6) ;
  on(p) {
    Procs2 r(2, 2) ;

    Coord c(0, r.dim(0)) ;
    Group q = r / c ;
  } no(p) ;
\end{verbatim}
\normalsize
\verb$p$ contains \verb$r$ by rule 1 above (\verb$p$ is the
active process group at the point of definition of \verb$r$), \verb$r$
contains \verb$q$ by rule 2, and \verb$p$ contains \verb$q$ by rule 3.

\subsection{The Initial Process Group}

The group active when the Adlib program starts is the {\em initial
process group}.  Only limited information is available or needed
about the structure of this group.  Its total size
will be the number of physical processes available.  This value is returned
by the global function
\begin{verbatim}
  int AdlibNProcs() ;
\end{verbatim}

\subsection{The {\em at} construct}

Two function members of the \verb$Coord$ record were ellided above:
\begin{verbatim}
  int  Coord :: at() ;
  void Coord :: ta() ;
\end{verbatim}
Suppose the active process group is \verb$p$,
\verb$c$ is a coordinate in a dimension of \verb$p$, and \verb$S$ is some
statement.  The {\em at} construct takes the form
\begin{verbatim}
  if(c.at())
    S
  c.ta() ;
\end{verbatim}
The \verb$c.at()$ member returns a truth value which is non-zero if the
physical process executing the code holds a process with the
coordinate defined by \verb$c$.
After the \verb$c.at()$ call, the active process group is \verb$p / c$.
The earlier active process group is restored after the \verb$c.ta()$
call.  Again, macros \verb$at$ and \verb$ta$
are sometimes defined so that the {\em at} construct can be written 
more compactly as
\begin{verbatim}
  at(c)
    S
  ta(c) ;
\end{verbatim}
The {\em at} construct can be viewed as a special case of the general
{\em on} construct.  An \verb$at(c)$ statement is essentially
equivalent to an \verb$on(p / c)$ statement.  However, the \verb$at$
version can be implemented more efficiently where it is applicable,
and is often more convenient in such circumstances.


\section{\label{Range}Index ranges}

     The process groups introduced in the previous sections are one of
two basic components from which Adlib distributed arrays are built.
The other primitive structure is the index range.  In general an index
range denotes a mapping of some interval \verb$0, ..., N - 1$ into a process
dimension.  The index range is represented by a member of the
\verb$Range$ class.

\subsection{Primitive ranges: distribution formats}

     There are presently three \verb$Range$ constructors that create
{\em primitive ranges}.  A primitive range is analogous to a dimension
of an HPF {\em template}.  It is typically distributed over some
process dimension.  The constructors are
\begin{verbatim}
  Range :: Range(const int extent,
                 const Layout layout = STANDARD) ;

  Range :: Range(const int extent, Dimension dim, const Format fmt,
                 const Layout layout = STANDARD) ;

  Range :: Range(const int extent, Dimension dim, const Format fmt,
                 const int blockSize,
                 const Layout layout = STANDARD) ;
\end{verbatim}
The different constructor create ranges with different distribution
formats.  In all cases the first argument is the extent of the created
range.

The first constructor creates a ``collapsed'' or sequential range.  The
whole of the index range is mapped to the local process.
The other two constructors create {\em distributed} ranges.

The second constructor creates a range with ``block'', ``simple cyclic'' or
``stepped'' block distribution format.  The \verb$fmt$ argument takes one of
the values \verb$BLK$, \verb$CYC$ or \verb$STP$.
Block and simple cyclic distribution are identical to the corresponding
HPF distribution formats.  In {\em stepped} block distribution the
first \verb$N mod P$ processes are assigned \verb$B + 1$ range elements
and the remaining processes are assigned \verb$B$ elements, where \verb$B =
[N / P]$.
Here \verb$N$ is the extent of the range and \verb$P$ is the extent
of the process dimension.

The third constructor creates a range with block or block cyclic
distribution format, taking a user-specified block size.  The
\verb$fmt$ argument takes one of the values \verb$BLK$, \verb$CYC$.
These distribution formats are identical to the corresponding HPF
formats.

The optional \verb$layout$ parameter of these constructors affects the
mapping of array elements into memory.  It will not be discussed in this
document.

There is an {\em orthogonality} relationship between certain 
primitive ranges.
Primitive range \verb$x$ is orthogonal to primitive range \verb$y$ if
\begin{enumerate}
\item
\verb$x$ and \verb$y$ are distributed over distinct dimensions of {\em
the same} process grid.
\item
\verb$x$ and \verb$y$ are distinct, and either or both are collapsed.
\end{enumerate}
Two primitive ranges are distinct if they are created in different
calls to one of the constructors above.

\subsection{Subranges}

The function
\begin{verbatim}
  Range Range :: subrng(const int extent,
                        const int base, const int stride = 1) ;
\end{verbatim}
creates a subrange.  Like any other range, a subrange has global indices
in the range \verb$0, ..., N - 1$, where \verb$N$ is the extent of
the range.  However, a subrange retains an alignment relation to
its parent range (and ultimately to its parent {\em primitive} range, if
the immediate parent is also a subrange).

Element \verb$i$ of the new range is aligned with (mapped to the same
processor as) element
\begin{verbatim}
  base + stride * i
\end{verbatim}
of the parent range.

Subranges inherit the orthogonality properties of their parent
primitive range.  Subranges \verb$x$ and \verb$y$ are orthogonal
if and only if their parent primitive ranges are orthogonal.

\subsection{Inquiries}

The members of \verb$Range$ include the inquiries
\begin{verbatim}
  int size() ;

  Dimension dim() ;

  Range prm() ;
  int bas() ;
  int str() ;
\end{verbatim}
Which return, respectively, the extent of the range, the dimension over
which it is distributed (or a null dimension for a collapsed range),
the parent primitive range of this range, and its alignment base and
stride relative to the primitive range.

\subsection{Subscripts}

A {\em subscript} is an abstraction of the idea of a ``local subscript''.
It denotes a particular position in a particular primitive range.

A \verb$Subscript$ is implemented as a simple record containing two
publicly accessible data members in addition to the members of
its base class \verb$Coord$:
\begin{verbatim}
  struct Subscript : public Coord {
    int blk ;
    int sub ;
  } ;
\end{verbatim}
\verb$blk$ and \verb$sub$ are components of a local subscript.
Their precise interpretation depends on the
implementation of the parent range, and is not strictly prescribed by the
general Adlib framework.  The {\em expected} use is as follows.
\begin{itemize}
\item
\verb$sub$ is an offset within a local block---for simple distribution
formats it is ``the'' local subscript.
\item
\verb$blk$ is intended for use in
``multi-block'' distribution formats such as {\em block cyclic}
distribution.  It identifies a particular local block, of which there
may be several.  For simple distribution formats with only a single
block per process, the \verb$blk$ field is unused.
\end{itemize}
A subscript record will normally be initialized by one of the members
of the \verb$Range$ class introduced in the next two sections.
Although its fields are publicly accessible, it is not normally
necessary to read or write them directly.

\subsection{\label{rangeSubs}Subscripting a range}

\begin{verbatim}
  Subscript& Range :: operator()(const int i) ;

  int Range :: operator()(Subscript& s) ;
\end{verbatim}
\normalsize
These are address translation operations.  They convert between global
index values and local subscripts.  A global index is an \verb$int$
value from \verb$0, ..., N - 1$, where \verb$N$ is the extent of the range.
A local subscript is a member of the class \verb$Subscript$.

The \verb$operator()(const int i)$ takes a global subscript into this
range, and returns a reference to a correponding local subscript.
For collapsed distribution formats the returned subscript contains a null
process coordinate.

The operator \verb$operator()(Subscript& s)$ takes a local subscript
and returns the corresponding global subscript into this range.
The argument must be aligned to an element of the range, otherwise
the operation is illegal.  Typically, the argument was originally
created from this range, or from one of its subranges.

For example, suppose \verb$x$ is some range of extent 75 or greater:
\small
\begin{verbatim}
  Range y = x.subrng(50, 25) ;  // y(i) aligned with x(25 + i).

  Subscript s(y(25)) ;          // `s' aligned with element 25 of `y'.

  int i = y(s) ;                // initialize `i' to 25

  int j = x(s) ;                // initialize j' to 50 (because
                                // `s' aligned with element 50 of `x').
\end{verbatim}
\normalsize

\subsection{The index class and the {\em where} construct}

The class \verb$Index$ is used as a distributed loop index.
The constructor takes a single range as its argument.
\begin{verbatim}
  Index :: Index(const Range& x) ;
\end{verbatim}
The Adlib distributed loop is called a {\em where} construct.
The function members
\begin{verbatim}
  void Index :: where() ;
  int  Index :: test()  ;
  void Index :: next()  ;
  void Index :: erewh() ;

  operator Index :: int() ;
\end{verbatim}
are used to implement this construct.  The \verb$Index$ class
has \verb$Subscript$ as a base class.

Suppose the active process group is \verb$p$,
\verb$x$ is a range which is (collapsed or) distributed over
a dimension of \verb$p$, \verb$i$ is an index for this range,
and \verb$S$ is some statement.  The {\em where} construct takes the form
\begin{verbatim}
  for(i.where() ; i.test() ; i.next())
    S
  i.erewh() ;
\end{verbatim}
Between the calls to \verb$i.where()$ and \verb$i.erewh()$ the
index \verb$i$ is ``activated as an iterator''.
As with the earlier control constructs, macros \verb$where$ and \verb$erewh$
are sometimes defined so that the {\em where} construct can be written 
more compactly as
\begin{verbatim}
  where(i)
    S
  erewh(i) ;
\end{verbatim}
The {\em where} construct implements a distributed loop,
as follows
\begin{itemize}
\item
The statement \verb$S$ executes once for every element of the range held
on the local processor.
\item
While an index is activated as an iterator, the \verb$Subscript$
component of the index is equal to the local subscript
associated with the current iteration, and the type
conversion \verb$operator int()$ 
allows the index to be coerced to the global subscript
associated with the current iteration.
\item
During an iteration of the loop, the active process group is
reduced to \verb$p / i$, assuming the coercion from index to
\verb$Subscript$ described above.
\end{itemize}
For example, suppose \verb$x$ is some range of extent 75 or greater,
distributed over a dimension of the active process group
\small
\begin{verbatim}
  Range y = x.subrng(50, 25) ;  // y(i) aligned with x(25 + i).

  Index j(y) ;
  where(j) {
    int i = j ;                 // initialize `i' to current global index.

    Subscript s = j ;           // `s' aligned with element `i' of `y'.

    int k = x(s) ;              // initialize `k' to 25 + i.

    ...
  } erewh(j) ;
\end{verbatim}
\normalsize
The main use of the {\em where} construct is in traversing distributed
arrays.  More meaningful examples must be postponed until the next section.

Normally the conversion of an index to an integer can be inserted
automatically by the compiler---it will be forced by context.
Occasionally an explicit cast to \verb$int$ may be required.


\section{Distributed arrays}

A {\em distributed array}, or simply an {\em array}, is a multi-dimensional
distributed data aggregate.  An array is a member of the class
\verb$Array$.  Instances are usually created through constructors for
the subclasses \verb$Array0$, \verb$Array1$, \verb$Array2$, \ldots,
which represent rank-0, rank-1, rank-2, \ldots, arrays.  These subclasses
are template classes, parametrized by the type of the element.

\subsection{Array constructors and inquiries}

The standard data constructor for a rank-\verb$R$ array takes
\verb$R + 1$ arguments---an accessible process group, \verb$p$,
followed by a list of \verb$R$ range objects.  These ranges must all be
orthogonal, and any distributed range must be distributed over a
dimension of \verb$p$.  The array as a whole is said to be
``distributed over \verb$p$''.
\small
\begin{verbatim}
  Procs1 p(4) ;
  Range x(100, p.dim(0), BLK), y(100) ;

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

  Array0<float> b(p) ;
\end{verbatim}
\normalsize
A second form of the constructor omits the process group argument.
This form is equivalent to passing the active process group as this
argument.
\small
\begin{verbatim}
  Procs1 p(4) ;
  on(p) {
    Range x(100, p.dim(0), BLK), y(100) ;

    Array2<int> a(x, y) ;

    Array0<float> b ;
  } no(p) ;
\end{verbatim}
\normalsize
The constructors allocate space to hold an array element
for each locally held subscript combination.

We should emphasize that because arrays can be declared using arbitrary
subranges of primitive ranges, and because they can be distributed over
arbitrary process groups including restricted groups, Adlib fully
supports the affine alignment model of HPF.

At a particular point in program execution an array is {\em accessible}
if it is distributed over an accessible process group.

The members
\begin{verbatim}
  Group Array :: grp() ;

  Range Array :: rng(int d) ;
\end{verbatim}
respectively return the group over which an array is distributed, and
one of its ranges.  \verb$d$ is in the range \verb$0, ..., R - 1$
where \verb$R$ is the rank of the array.

\subsection{Subscripting and scalar access rules}

The operators
\begin{verbatim}
  T& Array0<T> :: operator()() ;

  T& Array1<T> :: operator()(Subscript& s_1) ;

  T& Array2<T> :: operator()(Subscript& s_1, Subscript& s_2) ;

  ...
\end{verbatim}
are used to subscript an array.  Here \verb$T$ is a type parameter.
These operations look like function applications, taking local
subscript records as arguments.  They return a reference
to the associated local array element.

Some fundamental definitions
\begin{itemize}
\item
Any data object that is not a distributed array is a {\em
scalar}.  In particular distributed array {\em elements} are scalar.
\item
Any scalar data object is {\em replicated over} some group
(which may consist of a single process).
\item
A simple variable (not a distributed array element) is replicated over
the group active at the point at which it is declared or constructed.
\item
If \verb$a$ is an array distributed over \verb$p$, the array element
\begin{verbatim}
  a(s_1, s_2, ...)
\end{verbatim}
is replicated over the group
\begin{verbatim}
  p / s_1 / s_2 / ...
\end{verbatim}
(recall that \verb$Subscript$ is derived from \verb$Coord$, so a
local subscript can stand for a process coordinate).
\end{itemize}
Now, the Adlib {\em access rules} for scalar objects:
\begin{quote}
A scalar may be {\em read} only
if it is replicated over a group containing the active process group.
\end{quote}
and
\begin{quote}
A scalar may be {\em written} only when the active process
group is identical to to group over which the object is replicated
\end{quote}
The first rule forbids reading of variables not stored locally.
The second rule forbids writing to variables not stored locally,
and ensures that replicated variables are always updated
with globally consistent values.

For example
\small
\begin{verbatim}
  Procs1 p(4) ;
  on(p) {
    Range x(100, p.dim(0), BLK) ;

    Array<int> a(x) ;

    int v ;

    Subscript s(x(25)) ;

    v = a(s) ;    // illegal!

    a(s) = 17 ;   // illegal!

    at(s) {
      v = 17 ;    // illegal!
    } ta(s) ;

  } no(p) ;
\end{verbatim}
\normalsize
The first assignment is illegal by the first rule, because the
\verb$a(s)$ is only replicated over \verb$p / s$ while the active
process group is the whole of \verb$p$.  The array access is
non-local for most members of \verb$p$.  The second assignment is
forbidden by the second rule, for much the same reason.  This time most
members of \verb$p$ would be {\em writing} (identical values) to a
non-local location.  The third assignment is also forbidden by the
second rule.  It occurs while the the active process group is
\verb$p / s$, but \verb$v$ is replicated over the whole of \verb$p$.
In this case a single process would have write to locations on
all other processes in \verb$p$ or else the result would be
inconsistent values for \verb$v$ in different processes.

Finally, a legal Adlib program, which illustrates much of the
infrastructure established so far
\small
\begin{verbatim}
  Procs2 p(2, 2) ;
  on(p) {
    Range x(100, p.dim(0), BLK), y(10, p.dim(1), BLK) ;

    Array2<int> a(x, y) ;

    Index i(x), j(y) ;
    where(i) {
      where(j) {
        a(i, j) = i + j ;
      } erewh(j) ;
    } erewh(i) ;

  } no(p) ;
\end{verbatim}
\normalsize
The array \verb$a$ is distributed over \verb$p$.  The active
process group inside the nested {\em where} constructs is \verb$p / i / j$,
assuming the coercion from \verb$Index$ to \verb$Subscript$ (and thus
\verb$Coord$) effective inside a {\em where}.  The element
\verb$a(i, j)$ is defined thtrough the same cooercion, and is replicated
over the same process group, so the update is legal.  On the right
hand side of the assignment the coercion of \verb$Index$ to \verb$int$
is employed, yielding the global subscript value for the loop iteration.
The net result is to assign the sum of the global subscript values to
each element of the distributed array.

\subsection{\label{sections}Array sections}

Adlib supports array sections, analogous to Fortran array sections,
through the members
\begin{verbatim}
  Array0<T> Array0<T> :: sect() ;


  Array1<T> Array1<T> :: sect(Range x_1) ;

  Array0<T> Array1<T> :: sect(Subscript& s_1) ;


  Array2<T> Array2<T> :: sect(Range x_1, Range x_2) ;

  Array1<T> Array2<T> :: sect(Range x_1, Subscript& s_2) ;

  Array1<T> Array2<T> :: sect(Subscript& s_1, Range x_2) ;

  Array0<T> Array2<T> :: sect(Subscript& s_1, Subscript& s_2) ;


  ...
\end{verbatim}
These return new array objects referencing a section of the data in the
original.  The arguments must be subranges of, or subscripts in, the
corresponding ranges of the parent array\footnote{Because these functions
accept an arbitrary mixture of range and subscript arguments there are
2 to the {\tt R} members {\tt sect} defined for the rank-{\tt R} array class.
This is slightly extravagant, but it gives better type security than
the alternatives.}.

Suppose \verb$x$ and \verb$y$ are ranges of extent 100 distributed over
dimensions of the active process group, and \verb$a$ is declared as
\small
\begin{verbatim}
  Array2<int> a(x, y) ;
\end{verbatim}
\normalsize
This is comparable with the Fortran 90 declaration
\small
\begin{verbatim}
  INTEGER A(0 : 99, 0 : 99)
\end{verbatim}
\normalsize
Some examples of sections are
\small
\begin{verbatim}
  a.sect(x, y) ;                    // A ( : , : )

  a.sect(x.subrng(50, 25), y) ;     // A (25 : 74, : )

  a.sect(x, y.subrng(25, 25, 2)) ;  // A ( : , 25 : 73 : 2)

  a.sect(x, y(50)) ;                // A ( : , 50)
\end{verbatim}
\normalsize
The first example returns a section describing the whole of the
parent array (the section is essentially indistinguishable from the
parent).  The second and third examples use subranges to emulate
Fortran ``triplet subscripts''.  The fourth example uses a scalar
subscript to create an array of rank lower than the parent array.

If the parent array is distributed over \verb$p$ and the scalar
subscripts passed to \verb$sect$ are \verb$s_1, s_2, ...$, the
constructed section is distributed over \verb$p / s_1 / s_2 / ...$.
A call to \verb$sect$ is legal provided the {\em constructed}
section is distributed over an accessible process group.  This does
not necessarily require that the parent array is accessible---consider
this example:
\small
\begin{verbatim}
  void foo(Array1<int>) ;

  Array2<int> a(x, y) ;

  Subscript s(x(25)) ;
  at(s)
    foo(a.sect(s, y)) ;
  ta(s) ;
\end{verbatim}
\normalsize
The section constructor creates a rank-1 array representing an
individual column of \verb$a$.  If the active process group is
originally \verb$p$ the section is distributed over \verb$p / s$.  So the
call to the section constructor is legal, even though the whole of
\verb$p$ (and thus \verb$a$) is not accessible inside the {\em at}
construct.  For a more useful application of this rule,
the {\em at} could be replaced by a {\em where}:
\small
\begin{verbatim}
  Index i(x) ;
  where(i)
    foo(a.sect(i, y)) ;
  erewh(i) ;
\end{verbatim}
\normalsize
Here \verb$foo$ is applied in parallel to every column of \verb$a$.

\section{\label{communication}Communication}

\subsection{\tt shift}

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}
  void shift(Array dst, Array src,
             const int amount, const int dim, const int mode) ;
\end{verbatim}
The parameters \verb$dst$ and \verb$src$ are arrays, which must have
identical type, shape and mapping (they share the same process group
and range list).  The operation shifts the values
in \verb$src$ by \verb$amount$ places in the \verb$dim$ dimension, and
puts the result in \verb$dst$.  \verb$amount$ is a signed integer.
\verb$dim$ is in the range \verb$0, 1, ..., R - 1$, where \verb$R$
is the rank of the arrays.  \verb$mode$ is one of \verb$CYCL$ or
\verb$EDGE$, selecting either cyclic or ``edge-off'' shift.

The array arguments of \verb$shift$ must be accessible.  {\em All}
Adlib collective communication routines impose this requirement on
their array arguments.

With \verb$shift$ we can write one or two more worthwhile programs.  In
figure \ref{pde} the {\em where} 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) {
    Range x(N, p.dim(0), BLK), y(N, p.dim(1), BLK) ;

    Array2<float> w(x, y) ;

    // ... some code to initialize `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) ;
    where(i) {
      where(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)) ;
      } erewh(j) ;
    } erewh(i) ;

  } no(p) ;
\end{verbatim}
\caption{\label{pde}PDE solver kernel.}
\end{figure}
As an application of subranges, the {\em where} construct in figure
\ref{pde} could be replaced by
\small
\begin{verbatim}
    Index i(x.subrng(N - 2, 1)) ;
    Index j(y.subrng(N - 2, 1)) ;

    where(i) {
      where(j) {
        w(i, j) = 0.25 *
            (wnx(i, j) + wpx(i, j) + wny(i, j) + wpy(i, j)) ;
      } erewh(j) ;
    } erewh(i) ;
\end{verbatim}
\normalsize
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.

Figure \ref{life} performs an iteration of Conway's Life.
\begin{figure}[btp]
\begin{verbatim}
  Procs2 p(2, 2) ;
  on(p) {
    Range x(N, p.dim(0), BLK), y(N, p.dim(1), BLK) ;

    Array2<int> c(x, y) ;

    // ... some code to initialize `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) ;
    where(i) {
      where(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 ;
        }
      } erewh(j) ;
    } erewh(i) ;

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

It is important to realize that there are no restrictions on calling
Adlib communication routines beyond those that have already been stated.  It is
perfectly legitimate to make several calls in parallel, for example.
The following code invokes \verb$shift$ in parallel on the columns
of a pair of arrays to implement a skewed shift:
\small
\begin{verbatim}
  Array2<int> a(x, y), b(x, y) ;

  Index j(y) ;
  where(j)
    shift(a.sect(x, j), b.sect(x, j), j, 0, CYCL) ;
  erewh(j) ;
\end{verbatim}
\normalsize


\subsection{\tt remap}

A much more powerful cousin of \verb$shift$ is \verb$remap$.
The deceptively simple interface of \verb$remap$ is
\begin{verbatim}
  void remap(Array dst, Array 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
accessible.

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

  shift(a, b, 1, 0, EDGE) ;
\end{verbatim}
\normalsize
could be coded (more clumsily) as
\small
\begin{verbatim}
  remap(a.sect(x.subrng(N - 1, 1)), b.sect(x.subrng(N - 1, 0))) ;
\end{verbatim}
\normalsize
The code is comparable to the Fortran
\small
\begin{verbatim}
  REAL A (N), B (N)

  A (2 : N) = B (1 : N - 1)
\end{verbatim}
\normalsize
Because the destination array may contain replicated data, the
\verb$remap$ operation can also implement a wide variety of broadcast
and multicast operations.

\subsection{Gather-scatter operations}

Besides the family of regular data remapping operations Adlib provides
a {\em gather-scatter} family.  This include various operations that
allow arbitrary subscripting patterns in access to distributed arrays.

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,
\verb$b$.  The number of subscripts should be equal to the rank of the
scattered data, \verb$a$, and their values should lie in the ranges
expected for global 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.

\subsection{Reductions}

Finally Adlib provides a set of reduction operations based on
the corresponding Fortran 90 array intrinsics.  These include
boolean operations
\begin{verbatim}
  int all(Array_<int> src) ;
  int any(Array_<int> src) ;
  int count(Array_<int> src) ;
\end{verbatim}
and arithmetic operations
\begin{verbatim}
  T maxval(Array_<T> src) ;
  T minval(Array_<T> src) ;
  T sum(Array_<T> src) ;
  T product(Array_<T> src) ;
\end{verbatim}
Here \verb$_$ stands for an arbitrary rank and \verb$T$ stands for
an arithmetic type: \verb$int$, \verb$float$ or \verb$double$
(a defined \verb$complex$ type is also recognised by \verb$sum$ and
\verb$product$).

Versions which reduce in a single dimension, returning
an array reduced in rank by one, are also provided:
\begin{verbatim}
  void all(Array_<int> res, Array_<int> src, int dim) ;
  void any(Array_<int> res, Array_<int> src, int dim) ;
  void count(Array_<int> res, Array_<int> src, int dim) ;
\end{verbatim}
and
\begin{verbatim}
  void maxval(Array_<T> res, Array_<T> src, const int dim) ;
  void minval(Array_<T> res, Array_<T> src, const int dim) ;
  void sum(Array_<T> res, Array_<T> src, const int dim) ;
  void product(Array_<T> res, Array_<T> src, const int dim) ;
\end{verbatim}
as well as the search operations
\begin{verbatim}
  void maxloc(int* res, Array_<T> src) ;
  void minloc(int* res, Array_<T> src) ;
\end{verbatim}
which return the subscripts of maximum and minimum elements.

\section{\label{io}I/O}

Support for I/O comes in the form of variations on the standard C functions 
\verb$printf$ and \verb$scanf$.  Two variants of printf are
\begin{verbatim}
  void gprintf(char* control, ...) ;
  void aprintf(char* control, ...) ;
\end{verbatim}
\verb$gprintf$ outputs global values (values replicated over the active
process group).  The control string is identical to the control string
for the standard C function.  Only the root process in the active process
group will actually perform any output.

\verb$aprintf$ takes a list
of arrays as arguments.  The argument arrays should all have the same
shape.  The control string (and any format modifiers interspersed amongst
the array arguments) should be global values.  The print operation is
performed ``elementally'', equivalent to calling \verb$printf$ in turn
for every set of global subscripts of the arrays.
In addition to all the standard format specifiers, \verb$aprintf$
recognises two others.
\begin{itemize}
\item
\verb$R${\em D} format, where {\em D} is
a digit in the range \verb$0, ..., 9$ outputs the current value of
the {\em D}th subscript.  The \verb$R$ may be preceded by the same
format modifiers as for standard decimal integer format, \verb$d$.
\item
\verb$N$ format outputs a newline.  It can be
preceded by one format modifier, either a decimal number or an
asterisk, to specify the frequency with which the newline is
printed.  If the value of the modifier is \verb$n$, the newline is only
printed in every \verb$n$th elemental output.  The \verb$N$ specifier
is ignored in the intervening outputs.  
\end{itemize}
Note that neither \verb$R$ or \verb$N$ format
specifiers correspond to any argument of the \verb$aprintf$
(unless they have asterisk format modifiers).  They effectively alter the
behaviour of the control string according to the current subscript set.

For input the functions
\begin{verbatim}
  void gscanf(char* control, ...) ;
  void ascanf(char* control, ...) ;
\end{verbatim}
are provided.  \verb$gscanf$ inputs global values.  Only the root
process in the active process group actually performs the inputs.  The
input values are then broadcast to all members of the active process
group.  \verb$ascanf$ has the same relation to \verb$scanf$ as
\verb$aprintf$ has to \verb$printf$.  It inputs a list of arrays of the
same shape.  Both these functions take control strings identical to the
control strings of the standard C function.

For file I/O the variants
\begin{verbatim}
  void gfprintf(FILE* fd, char* control, ...) ;
  void gfscanf(FILE* fd, char* control, ...) ;

  void afprintf(FILE* fd, char* control, ...) ;
  void afscanf(FILE* fd, char* control, ...) ;

  FILE* gfopen(char* name, char* mode) ;
  void gfclose(FILE* fd) ;
\end{verbatim}
are provided.


\end{document}
--------------

Changes to existing implementation:

  1) Reintroduction of `Coord' base class.

To do:

  Revert name process array (instead of process grid)?

  Change name of ``restricted group'' to subgrid (or subarray) by
      analogy with subrange.

