
\documentclass{book}

\usepackage{psfig}
\usepackage{makeidx}

\makeindex

\begin{document}

\sloppy

\pagestyle{plain}

\title{NPAC PCRC Runtime Kernel ({\em Adlib}) Definition \\
       \em [DRAFT]}

\author{Bryan Carpenter, Guansong Zhang and Yuhong Wen \vspace{0.25in} \\ 
        \em Northeast Parallel Architectures Centre, \\
        \em Syracuse University, \\
        \em 111 College Place, \\
        \em Syracuse, New York 13244-410} 

\maketitle

\newpage

\tableofcontents

%\newpage

\chapter{Introduction}

The library defined in this document is designed as a common runtime
kernel for manipulating HPF-style regular distributed arrays.  It is
not expected that the kernel interface described here will be used
directly by an application programmer.  It may not even appear directly
in code generated by a compiler.  Additonal interface code, built on
top of the kernel, will probably be needed.

One example of a user-level interface to the kernel is the {\em ad++}
interface.  This is a set of C++ header files which define type-secure
template classes---{\em container classes}---representing distributed
arrays, various macros implementing {\em distributed control}
constructs, and template functions for performing transformations on
distributed arrays.  The latter functions fulfil a role something like
the array transformational intrinsics of Fortran 90.  In particular,
they abstract communication.

Compiler-level interfaces, on the other hand, provide any additional
run-time structure assumed by the distributed array model of the source
language, and make the kernel callable from the target language of the
compiler.  In principle this target language could be machine code, but
historically the library has been used by source-to-source translators
targetting Fortran 77 or Fortran 90.  So existing ``compiler-level''
interfaces to the kernel are actually Fortran bindings.  A Java
interface is under development.

The kernel itself provides:
\begin{itemize}
\item
A distributed array descriptor (DAD), implemented as a series
of C++ classes.
\item
A large set of {\em communication schedules} implementing Fortran-90
like array transformational functions and other basic communication
operations.
\item
As part of the DAD---support for ``distributed control''.  In practise
what this means is support for ``distributed loops'': support
for translation of parallel loops whose index range is distributed
over some processor set.
\end{itemize}

This document is not supposed to be read in isolation.  The underlying
model of data distribution should be understood, for example by
learning the user-level interface to the library, before attempting
direct use of the kernel.

The next three chapters define the components of the Adlib array
descriptor---groups, ranges, then the array descriptor record itself.
Chapter \ref{schedules} describes the communication library.  This will
followed by a chapter on the {\tt ad++} interface, then a chapter about
using the Adlib descriptor technology in translation of distributed
loops.  A final chapter will discuss the implementation of the
communication schedules.

\chapter{Process Groups}

The Adlib idea of a process group is analogous to the MPI idea
of {\em group}.  The Adlib version is more specialized.  Adlib groups
are frequently created and modified in the runtime.  For efficiency it
is important to provide a specialized lightweight representation---one
cannot afford to import the general group technology of MPI.  For
example, Adlib needs the structure of multi-dimensional grids without
the overheads involved in building an MPI {\em Cartesian
communicator}.

The most direct analogue of the MPI Cartesian communicator is
the Adlib {\em process array}, represented by a {\tt Procs} object.
Even in Adlib, constructing a process array is a relatively expensive
procedure.  It involves initializing several sub-structures.  The {\em
general} group object of Adlib---class {\tt Group}---has a much more
streamlined implementation.  {\tt Group} is essentially a handle
class.  Its objects contain a pointer to a parent {\tt Procs} object
plus a few extra words defining a subset of that Cartesian grid.  {\tt Group}
objects are created, copied, changed, and discarded freely within the
library code.  They can be handled with similarly free rein in user
code.

\section{General Definitions}

\begin{description}
\index{initial process group}%
\index{process group!initial}%
\item{Initial process group:}
The set processes on which an Adlib program is initiated.

\index{active process group}%
\index{process group!active}%
\item{Active process group:} 
The set of processes notionally sharing the local thread of control.
This may be the initial process group or it may be an arbitrary subset
of the initial process group.  When an Adlib program starts
the active process group is the initial process group.

The logical active process group may be changed by operations that
cause some processors to skip a block of code (leaving the remaining
processors active for that block), or cause the current active process
group to be partitioned into a set of smaller groups, with each group
acting independently for some time.

Every process executing an Adlib program must maintain a static data
structure, {\tt apg}, describing the current active process group.
This variable is read by collective functions in the library to
determine which processes are cooperating in the operation.  If the
logical active process group changes, the variable {\tt apg} must be
updated (see section \ref{apg}) before invoking a collective
operation.  During the library initialization procedure, {\tt apg}
is set to a value describing the initial process group.

\index{collective object}%
\item{Collective object:}
A collection of similar objects, one in every process from a particular
group, which can also be viewed as a single logical entity.

\index{collective operation}%
\item{Collective operation:}
An operation executed cooperatively by all members of the active
process group.  Typically this will take the form of a call to the same
function with the same arguments.  In this context two arguments are
``the same'' if they are simple expressions with the same value, or are
references to local components of the same collective object.

A collective operation may or may not involve synchronization between
members of the active process group.  In general the programmer should
work on the (worst case) assumption that synchronization {\em is}
implied.  If any member of the active process group fails to engage in
a collective operation that others are executing, or executes
collective operations in a different order to other members of the
group, the program is liable to fail.

Examples of collective operations are constructors for collective
objects and collective communication operations.

\index{process array}%
\item{Process array:} Some subset of the initial process group,
organized in a Cartesian grid.

\index{coordinate}%
\item{Coordinate:} Dimensions of a process array are labelled by {\em
coordinates}.

\index{process group}%
\item{Process group:} In general, either a process array, or some slice
of a process array defined by uniquely fixing the coordinate in one or
more of its dimensions.

\index{process id}%
\item{Process id}: An identifier relative to a particular process
group\footnote{Called a {\em rank} in MPI.  Following Fortran,
we will reserve ``rank'' for the dimensionality of arrays or process arrays.}.
If the size of the group is $P$, the id is in the range $0 \ldots P - 1$.
Relative to a one-dimensional process array, the value of the process
id coincides with the value of the unique coordinate.  The id relative
to the initial process group is also called the {\em absolute process id}.

\end{description}

\newpage

\index{Procs@{\tt Procs} class}%
\section{class {\tt Procs}}

\index{process array}
A {\em process array} is a set of processes organized in a
multi-dimensional grid.  A process array is described by a
collective object with local components of class {\tt Procs}.
The public interface of the {\tt Procs} class is
\small
\begin{verbatim}
  class Dimension ;
  class DimensionSet ;

  class Procs {
  public :
    Procs(const int _rank, int* _n, int* subIds = 0) ;
    ~Procs() ;

    int rnk() const ;
    Dimension dim(const int r) const ;

    DimensionSet dims() const ;

    int member() const ;

    int size() const ;

    int id() const ;

    int id_abs(const int id) const ;

    int lead_abs() const ;

  private :
    Procs() ;
    Procs(const Procs& p) ;

    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructors and destructors}

\begin{verbatim}
Procs(const int _rank, int* _shape, int* ids = 0)
\end{verbatim}
The normal constructor.  Initializes a {\tt Procs} object describing
a process grid of rank {\tt \_rank} and shape {\tt \_shape}.  The rank is
a non-negative integer.  If it is zero the new group is a scalar
``grid'' containing a single process.  The shape is a vector of {\tt
\_rank} positive integer extents.  The size, $P$, of the new grid is the
product of the elements of {\tt \_shape}.  This must be less than or
equal to the size of the active process group.

If the optional argument {\tt ids} is specified, this should be
a vector of $P$ distinct values, each in the range $0, \ldots, A - 1$.
$A$ is the size of the group defined by the current value of {\tt apg}.
It defines a mapping of the new process group into the active process
group.  If the {\tt ids} argument is omitted, the library selects an
arbitrary mapping.  In either case if $P$ is less than $A$, some
members of the active process group are not identified with any member
of the new grid.  At most one member of the new grid may be mapped to
each process of the active group.

This constructor is a collective operation, and calls to it should
obey the normal rules for collective operations.

\begin{verbatim}
Procs()
\end{verbatim}
The default constructor is {\em private}.  Creating an uninitialized
{\tt Procs} object is not allowed in normal code.
%{\em [This may be a bad restriction.  It makes arrays of {\tt Procs}
%impossible.  On the other hand, arrays of {\tt Procs*} are OK.]}

\begin{verbatim}
Procs(const Procs& p)
\end{verbatim}
The copy constructor is {\em private}.  Copying a {\tt Procs} object is
not allowed in normal code.

\begin{verbatim}
~Procs()
\end{verbatim}
Destructor.

\subsection{Methods}

\index{rnk@{\tt rnk}!member of {\tt Procs}}%
\begin{verbatim}
rnk()
\end{verbatim}
\index{rank!of process array}%
An inquiry function returning the rank (dimensionality) of the grid.

\index{dim@{\tt dim}!member of {\tt Procs}}%
\begin{verbatim}
dim(const int r)
\end{verbatim}
\index{process dimension}
An inquiry function returning an object that describes the {\tt r}th
dimension of the grid.  The argument {\tt r} is in the range
$0, \ldots, R - 1$ where $R$ is the rank of the grid.

\index{dims@{\tt dims}!member of {\tt Procs}}%
\begin{verbatim}
dims()
\end{verbatim}
An inquiry function returning an object that describes the complete set of
dimensions of the grid.

\index{member@{\tt member}!member of {\tt Procs}}%
\begin{verbatim}
member()
\end{verbatim}
An inquiry function which returns 1 if a process from the grid is
mapped to the local process, and 0 if not.  In other words, a boolean function
that returns true iff this process is a member of the grid.

\index{size@{\tt size}!member of {\tt Procs}}%
\begin{verbatim}
size()
\end{verbatim}
An inquiry function returning the total number of processes, $P$, in the
grid.

\index{id@{\tt id}!member of {\tt Procs}}%
\begin{verbatim}
id()
\end{verbatim}
An inquiry function that returns the id of the local process relative
to this grid.  Its value is defined if and only if the local process is
a member of the grid, in which case the result is in the range $0,
\ldots P - 1$.

\index{id\_abs@{\tt id\_abs}!member of {\tt Procs}}%
\begin{verbatim}
id_abs(const int id)
\end{verbatim}
A conversion function from id relative to this grid to id relative to
the initial process group---ie, to absolute process id.

\index{lead\_abs@{\tt lead\_abs}!member of {\tt Procs}}%
\begin{verbatim}
lead_abs()
\end{verbatim}
The absolute id of the lead process of the grid---equivalent to
{\tt id\_abs(0)}.

\subsection{Examples}

\small
\begin{verbatim}
  int shp [1] = {4} ;
  Procs p(1, shp) ;
\end{verbatim}
\normalsize
Creates a one-dimensional process array representing a linear set of
4 processes.  The active process group must contain at least 4
processes when the declaration of {\tt p} is encountered.

\small
\begin{verbatim}
  int shp [4] = {2, 2, 2, 2} ;
  Procs h(4, shp) ;
\end{verbatim}
\normalsize
Creates a process array representing a 4-dimensional binary hypercube.
The active process group must contain at least 16 processes when the
declaration of {\tt h} is encountered.

\small
\begin{verbatim}
  int shp [2] = {2, 3}, ids [6] = {0, 1, 3, 6, 10, 15} ;
  Procs q(2, shp, ids) ;
\end{verbatim}
\normalsize
Creates a process array representing a 2 by 3 grid with a user-defined
mapping to members of the active process group.  The active process
group must contain at least 16 processes when the declaration of {\tt
q} is encountered (because {\tt ids} includes values up to 15).

\small
\begin{verbatim}
  Procs s(0, 0) ;
\end{verbatim}
\normalsize
Creates scalar process grid containing a single process.

\newpage

\index{process dimension}
\index{Dimension@{\tt Dimension} class}%
\section{class {\tt Dimension}}

A {\em process dimension} is a dimension of a process array.
A process dimension is described by a
collective object with local components of class {\tt Dimension}.
The public interface of the {\tt Dimension} class is
\small
\begin{verbatim}
  class Dimension {
  public :
    Dimension() ;

    int size() const ;
    int crd() const ;

    int str_prc() const ;

    operator int() const ;

  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructors and destructors}

\begin{verbatim}
Dimension()
\end{verbatim}
The default constructor.  Initializes a {\tt Dimension} object describing
a {\em collapsed dimension}.  This is a degenerate, ``internal'' dimension,
not associated with a process array.

\subsection{Methods}

\index{size@{\tt size}!member of {\tt Dimension}}%
\begin{verbatim}
size()
\end{verbatim}
An inquiry function returning the extent, $N$, of the dimension.  For a
dimension of a process array, this is the extent specified in the shape
vector for that array.  For a collapsed dimension, $N$ defined to be 1.

\index{crd@{\tt crd}!member of {\tt Dimension}}%
\begin{verbatim}
crd()
\end{verbatim}
An inquiry function returning an integer coordinate for the local
process relative to this process dimension.  For a process array
dimension the result value is only defined if the local process is a
member of the parent array.  It is then in the range $0, \ldots, N - 1$,
where $N$ is the extent of the dimension.  For a collapsed dimension,
the result is 0.

\index{str\_prc@{\tt str\_prc}!member of {\tt Dimension}}%
\begin{verbatim}
str_prc()
\end{verbatim}
An inquiry function defining the stride in process id (relative
to the parent array) associated with this dimension.  Undefined for
a collapsed dimension.

\subsection{Operators}

\begin{verbatim}
operator int()
\end{verbatim}
Returns a non-zero value if the dimension belongs to a process array.
Returns 0 if the dimension is collapsed.  {\em [Replace this with a
{\tt dims} member?]

\subsection{Examples}

\small
\begin{verbatim}
  int shp [2] = {2, 3} ;
  Procs p(2, shp) ;

  Dimension d = p.dim(0), e = p.dim(1) ;
  Dimension f ;
\end{verbatim}
\normalsize
Create a process array {\tt p} representing a 2 by 3 grid.
The active process group must contain at least 6 processes when
the declaration of {\tt p} is encountered.  Set {\tt d} to represent
the first dimension of {\tt p} and {\tt e} to represent the second.
Set {\tt f} to a collapsed dimension.

The inquiries {\tt d.size()}, {\tt e.size()} and {\tt f.size()} return
2, 3 and 1 respectively.  The inquiries {\tt d.crd()} and {\tt e.crd()}
will return values in the ranges $\{ 0, 1 \}$ and $\{ 0, 1, 2 \}$
respectively {\em if} the inquiry {\tt p.member()} returns value
1.  They return unspecified values if {\tt p.member()} returns 0.  The
inquiry {\tt f.crd()} will return 0.

\subsection{Implementation notes}

{\tt Dimension} is currently implemented as a simple,
non-reference-counting handle class.
If it is a process array dimension it contains a pointer to an
object of type {\tt DimensionRep}
associated with the parent {\tt Procs} structure.
If it is collapsed dimension it contains a null pointer.


\newpage

\index{dimension set}
\index{DimensionSet@{\tt DimensionSet} class}%
\section{class {\tt DimensionSet}}

A {\em dimension set} is some subset of the dimensions of a particular
process array.  A dimension set is described by a
collective object {\em [?]} with local components of class {\tt DimensionSet}.
The public interface of the {\tt DimensionSet} class is
\small
\begin{verbatim}
  class Dimension ;

  class DimensionSet {
  public :
    DimensionSet() ;

    int member(Dimension d) const ;

    int isEqual(DimensionSet ds) const ;
    int contains(DimensionSet ds) const ;

    operator int() const ;

    DimensionSet operator+(DimensionSet ds) const ;
    DimensionSet operator-(DimensionSet ds) const ;

    DimensionSet& operator+=(DimensionSet ds) ;
    DimensionSet& operator-=(DimensionSet ds) ;

    DimensionSet operator+(Dimension d) const ;
    DimensionSet operator-(Dimension d) const ;

    DimensionSet& operator+=(Dimension d) ;
    DimensionSet& operator-=(Dimension d) ;

  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructors and destructors}

\begin{verbatim}
DimensionSet()
\end{verbatim}
The default constructor.  Initializes a {\tt DimensionSet} object to
an empty set.

\subsection{Methods}

\index{member@{\tt member}!member of {\tt Dimension}}%
\begin{verbatim}
member(Dimension d)
\end{verbatim}
Inquiry function.  Returns a non-zero result if {\tt d} is a member of
this set, and 0 if it is not.

\index{isEqual@{\tt isEqual}!member of {\tt Dimension}}%
\begin{verbatim}
isEqual(DimensionSet ds)
\end{verbatim}
Returns a non-zero result if this set is equal to {\tt ds} and 0 if it
is not.

\index{contains@{\tt contains}!member of {\tt Dimension}}%
\begin{verbatim}
contains(DimensionSet ds)
\end{verbatim}
Returns a non-zero result if this set contains {\tt ds} and 0 if it
does not.

\subsection{Operators}

\begin{verbatim}
operator int()
\end{verbatim}
Returns a non-zero value if the set is non-empty, or 0 if it is empty.

\begin{verbatim}
operator+(DimensionSet ds)
\end{verbatim}
Create a new set containing the union of this set with {\tt ds}.  If
both input sets are non-empty, they must contain dimensions from the same
process array.

\begin{verbatim}
operator-(DimensionSet ds)
\end{verbatim}
Create a new set by subtracting {\tt ds} from this set.  If both input
sets are non-empty, they must contain dimensions from the same process
array.

\begin{verbatim}
operator+=(DimensionSet ds)
\end{verbatim}
Replace this set by its union with {\tt ds}.  If both input sets are
non-empty, they must contain dimensions from the same process array.

\begin{verbatim}
operator-=(DimensionSet ds)
\end{verbatim}
Subtract {\tt ds} from this set.  If both input sets are non-empty, they must
contain dimensions from the same process array.

\begin{verbatim}
operator+(Dimension d)
\end{verbatim}
Create a new set by adding a dimension to this set.  If the set
is non-empty before this operation {\tt d} must be collapsed or a
dimension from the same process array as the current elements.  Adding
a collapsed dimension, or one already in the set, does not change the
set.

\begin{verbatim}
operator-(Dimension d)
\end{verbatim}
Create a new set by removing {\tt d} from this set.  If the set is
non-empty before this operation {\tt d} must be collapsed or a
dimension from the same process array as the current elements.
Removing a collapsed dimension, or one not in the set, does not change
the set.

\begin{verbatim}
operator+=(Dimension d)
\end{verbatim}
Add a dimension to this set.  If the set is non-empty before
this operation {\tt d} must be collapsed or a dimension from the same
process array as the current elements.  Adding a collapsed dimension,
or one already in the set, does not change the set.

\begin{verbatim}
operator-=(Dimension d)
\end{verbatim}
Remove a dimension from this set.  If the set is non-empty
before this operation {\tt d} must be collapsed or a dimension from
the same process array as the current elements.  Removing a collapsed
dimension, or one not in the set, does not change the set.

\subsection{Examples}

\small
\begin{verbatim}
  int shp [3] = {2, 2, 2} ;
  Procs p(3, shp) ;

  DimensionSet ds ;
  ds += p.dim(0) ;
  ds += p.dim(2) ;
\end{verbatim}
\normalsize
Create a process array {\tt p} representing a 3 dimensional binary
hypercube.  Create {\tt ds} as an empty dimension set, then add the
first and third dimension of {\tt p} to it.

\index{dimension set!representation of}%
\subsection{Implementation notes}

{\tt DimensionSet} is currently realized as a simple, one-word
record containing a {\tt long} integer used as a bitmask.
All the members can be implemented as short
inline functions using bitwise operations---this class is very
lightweight.

This implementation imposes the Adlib kernel's only limitation on
dimensionality---the number of process dimensions in a process array
should normally be less than the number of bits in a {\tt long}
integer.  Unless, for unknown reasons, an application
involves a process array with many dimensions of unit extent, this
constraint is not really stronger than the tacit assumption that all processes
can be distinctly labelled by a single integer.  On a 32-bit computer,
for example, this implementation theoretically supports binary
hypercubes of up to about 4 billion processors\ldots

\newpage

\index{process group}
\index{Group@{\tt Group} class}%
\section{class {\tt Group}\label{group}}

A process group is described by an object of class {\tt Group}.
The public interface of the {\tt Group} class is
\small
\begin{verbatim}
  class Procs ;
  class DimensionSet ;

  class Group {
  public :
    Group() ;
    Group(const Procs& p) ;

    const Procs* prc() const ;

    DimensionSet dims() const ;

    int isEqual(const Group& p) const ;
    int contains(const Group& p) const ;

    int member() const ;

    int size() const ;

    int id() const ;

    int id_prc(const int id) const ;
    int id_abs(const int id) const ;

    int lead_prc() const ;
    int lead_abs() const ;

    void restrict(Dimension d, const int coord) ;
    void restrict(Dimension d) ;
    void restrict(DimensionSet ds) ;

  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructors and destructors}

\begin{verbatim}
Group()
\end{verbatim}
The default constructor.  Creates an uninitialized {\tt Group} object.

\begin{verbatim}
Group(const Proc& p)
\end{verbatim}
Conversion constructor.  Initializes a {\tt Group} object representing
all processes in process array {\tt p}.  By definition {\tt p} is the
{\em parent process array} of the constructed group.  The new group
object can subsequently be reduced to a subset of {\tt p} by using
the {\tt restrict} members below.

\subsection{Methods}

\index{prc@{\tt prc}!member of {\tt Group}}%
\begin{verbatim}
prc()
\end{verbatim}
An inquiry function returning a pointer to the local {\tt Procs} object
associated with the parent process array.

\index{dims@{\tt dims}!member of {\tt Group}}%
\begin{verbatim}
dims()
\end{verbatim}
An inquiry function returning the effective dimension set of this
group.  This is a subset of the dimensions of the parent process array,

\index{isEqual@{\tt isEqual}!member of {\tt Group}}%
\begin{verbatim}
isEqual(const Group& p)
\end{verbatim}
A comparision operation that returns a non-zero value if {\tt p}
is equal to this group.  The definition of equality used here is that
groups are equal if they share the same parent process
array\footnote{Their parent arrays must be described by the {\em same
object}, not merely be structurally similar.}, their dimension sets are
equal, and their lead processes are the same.


\index{contains@{\tt contains}!member of {\tt Group}}%
\begin{verbatim}
contains(const Group& p)
\end{verbatim}
A comparision operation that returns a non-zero value if this
group contains {\tt p}.  The definition of ``contains''
used here is as follows: {\tt q} contains {\tt p} if
\begin{enumerate}
\item
{\tt p} is equal to {\tt q} according to the definition above, {\em or}
\item
{\tt p} represents a whole process array,
and {\tt q} was the active process group when that process array was created,
{\em or}
\item
{\tt p} can be obtained by applying a {\tt restrict} method to {\tt q}
(see below), {\em or}
\item
{\tt q} contains some group {\tt r} and {\tt r} contains {\tt p}---the
relation is transitive.
\end{enumerate}
This definition of {\em contains} is stricter than the intuitive
definition based on comparision of the sets of processes in the groups.
It can often be computed more directly.

\index{member@{\tt member}!member of {\tt Group}}%
\begin{verbatim}
member()
\end{verbatim}
An inquiry function that returns a non-zero value if the local
process is a member of the group, and 0 if not.

\index{size@{\tt size}!member of {\tt Group}}%
\begin{verbatim}
size()
\end{verbatim}
An inquiry function returning the total number of processes, $P$, in the
group.

\index{id@{\tt id}!member of {\tt Group}}%
\begin{verbatim}
id()
\end{verbatim}
An inquiry function that returns the id of the local process relative
to this group.  Its value is defined if and only if the local process is
a member of the group, in which case it is in the range $0, \ldots P - 1$.

\index{id\_prc@{\tt id\_prc}!member of {\tt Group}}%
\begin{verbatim}
id_prc(const int id)
\end{verbatim}
A conversion function from id relative to this group to id relative to
the parent process array.

\index{id\_abs@{\tt id\_abs}!member of {\tt Group}}%
\begin{verbatim}
id_abs(const int id)
\end{verbatim}
A conversion function from id relative to this group to id relative to
the initial process group---ie, to absolute process id.
Equivalent to {\tt prc()->id\_abs(id\_prc(id))}

\index{lead\_prc@{\tt lead\_prc}!member of {\tt Group}}%
\begin{verbatim}
lead_prc()
\end{verbatim}
The id relative to the parent process array of the lead process of this
group---equivalent to {\tt id\_prc(0)}.

\index{lead\_abs@{\tt lead\_abs}!member of {\tt Group}}%
\begin{verbatim}
lead_abs()
\end{verbatim}
The absolute id of the lead process of the group---equivalent to
{\tt id\_abs(0)}.

\index{restrict@{\tt restrict}!member of {\tt Group}}%
\begin{verbatim}
restrict(Dimension d, const int coord)
\end{verbatim}
Reduce the process group by restricting the coordinate in {\tt d} to
the value {\tt coord}.  The operation removes {\tt d} from {\tt dims()}.
It is ill-defined if {\tt d} is not a member of {\tt dims()} beforehand.
It is a null operation if {\tt d} is collapsed.
%This is a collective operation.

\index{restrict@{\tt restrict}!member of {\tt Group}}%
\begin{verbatim}
restrict(Dimension d)
\end{verbatim}
Reduce the process group by restricting the coordinate in {\tt d} to
the value associate with the local process, equivalent to
{\tt restrict(d, d.crd())}.  The operation
is ill-defined if the local process is not a member of the parent process
array, or if {\tt d} is not a member of {\tt dims()} beforehand.
It is a null operation if {\tt d} is collapsed.
%This is a collective operation.

\index{restrict@{\tt restrict}!member of {\tt Group}}%
\begin{verbatim}
restrict(DimensionSet ds)
\end{verbatim}
Reduce the process group by restricting the coordinate in all dimensions
from {\tt ds} to
the values associate with the local process.  Equivalent to
applying {\tt restrict(d)} for every member, {\tt d}, of {\tt ds}.
The operation
is ill-defined if the local process is not a member of the parent process
array, or if {\tt ds} is not a subset of {\tt dims()} beforehand.


\subsection{Examples}

\small
\begin{verbatim}
  int shp [2] = {2, 2} ;
  Procs p(2, shp) ;

  Group q = p ;
  q.restrict(p.dim(0), 0) ;

  Group r = q ;
  r.restrict(p.dim(1), 1) ;
\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 {\tt p}.  The dashed
lines embrace groups {\tt p}, {\tt q} and {\tt r}.}
\end{figure}
These groups are illustrated in figure \ref{groupsEg}.
The dimension set of {\tt q} contains just {\tt p.dim(1)}, and
dimension set of {\tt r} is empty.


\subsection{Implementation notes}

{\tt Group} can be realized as a simple three-word record containing a
pointer to the parent {\tt Procs} object, a {\tt DimensionSet} (one
word) representing the set of effective dimensions, and an integer
specifying the id relative to the parent process array of the lead
process of the group.  These are the values returned by 
{\tt prc}, {\tt dims} and {\tt lead\_prc} respectively.

\clearpage

\section{Group {\tt apg}\label{apg}}

The static variable {\tt apg} is accessed by most of the collective operations
in the library.
Its value should reflect the currently effective {\em active
progress group}.  Its declaration is
\small
\begin{verbatim}
    extern Group apg ;
\end{verbatim}
\normalsize
When an Adlib program starts the value of {\tt apg} represents the
initial process group.
If collective operations are to function properly there is an onus on
the programmer to maintain the value of {\tt apg} consistently.  In
this section three common idiomatic ways of modifying the active
process group are discussed.

The first idiom involves a conditional construct which restricts
the set of processes performing a block of code to
some group, {\tt p}.  Membership
of the local process in this group is determined by calling
{\tt p.member()}, as follows:
\small
\begin{verbatim}
  if(p.member()) {
    ...
  }
\end{verbatim}
\normalsize
If it is necessary to invoke collective library operations {\em inside} the
construct, {\tt apg} must be reset appropriately.  Assuming the
construct appears at the point where {\tt p} is a subset of the active
process group, the logical active process group
inside the construct will be the whole of {\tt p}.  Appropriate manipulations
of {\tt apg} are
\small
\begin{verbatim}
  Group apgSave = apg ;
  if(p.member()) {
    apg = p ;
    ...
  }
  apg = apgSave ;
\end{verbatim}
\normalsize
The only subtlety is the need to save the old value of {\tt apg} so
that it can be restored on completion of the construct.  With these
manipulations of the {\tt apg} variable we can
safely invoke collective operations before, during
and after the conditional construct.  This idiom will sometimes
be called an {\em on} construct.  In the ad++ interface to Adlib
macros {\tt ON}/{\tt NO} are defined to allow the whole of the
fragment above to be written as
\small
\begin{verbatim}
  ON(p) {
    ...
  } NO(p) ;
\end{verbatim}
\normalsize

A second common idiom for modifiying {\tt apg} occurs when the
logical active process group is partitioned by breaking up one of its
process dimensions.  Suppose the current active process group is a
multi-dimensional array of processes.  One of its process
dimensions is {\tt d}.  Suppose we need to perform
operations {\em collectively} across dimensions {\em orthogonal} to {\tt d},
but {\em independently} for each value of the {\tt d} coordinate.
In this case the value of {\tt apg} should be temporarily changed as
follows
\small
\begin{verbatim}
  Group apgSave = apg ;
  apg.restrict(d) ;
  ...
  apg = apgSave ;
\end{verbatim}
\normalsize
In the ad++ interface, for example, this kind of manipulation of {\tt
apg} occurs in the {\tt AT}/{\tt TA} construct and {\tt OVERALL}/{\tt
ALLOVER} distributed loop.

The preceding idiom allows for regular partitioning
of the active process group across one of its dimensions.
A different technique can be used to achieve arbitrary partitioning.
Suppose each of $A_1, \ldots, A_n$ is a set of processes,
and together they partition the current active process group, $A$.
For each $i$ in $1, \ldots, n$, $a_i$ is a vector of
ids (relative to $A$) for the processes in $A_i$, and
$r_i$ and $s_i$ define a rank and
a shape for a grid of size $|A_i|$.
Now, if the local process is a member of $A_l$, the following constructor call 
\small
\begin{tabbing}
\verb$  Procs p($$r_l${\tt , }$s_l${\tt , }$a_l${\tt )}
\end{tabbing}
\normalsize
creates $n$ logically {\em distinct} collective objects representing
non-overlapping process arrays.  An {\em on} construct using {\tt p} will
now partition the active process group as required.
For example, suppose the current active process group has 5 processes.
We can partition these temporarily into groups of 2 and 3 as follows
\small
\begin{verbatim}
  int shp [1], *ids ;
  if(apg.id() < 2) {
    shp [0] = 2 ; 
    ids = {0, 1} ;
  }
  else {
    shp [0] = 3 ; 
    ids = {2, 3, 4} ;
  }

  Procs p(1, shp, ids) ;

  Group apgSave = apg ;
  if(p.member()) {
    apg = p ;
    ...
  }
  apg = apgSave ;
\end{verbatim}
\normalsize
This use of the {\tt Procs} constructor departs slightly from
usual rules for collective operations, because when the constructor is
called the value of {\tt apg} is the original active process group, but
its arguments take different values in sectors of that group which will
later be in separate partitions.

Notice that the idioms we have introduced in this section can be nested
freely.  As usual, the only subtlety is in ensuring that old values of
the active process group are restored properly when the constructs
complete.  This can be achieved either by using a suitable series of
automatic variables (like {\tt apgSave}), or by using an explicit stack of
group objects.

%\subsection{Examples}

\chapter{Ranges}

An Adlib {\em range} is a map from an integer interval $0, \ldots, N -
1$ into a process dimension.  Each value, or {\em global subscript}, in
the interval is mapped to a particular process coordinate.  While the
library does {\em not} support completely general, irregular mappings
from global subscript to process coordinate, it does provide many of
the most popular options ({\em block}, {\em cyclic}, {\em
block-cyclic}, etc).  In particular the allowed mappings support all
distribution formats and intra-dimensional alignments of HPF 1.0,
and the irregular block distribution format of HPF 2.0.


Adlib currently supports three kinds of range, distinguished by an
integer called the {\em level} of the range.  The simplest distribution
formats of HPF (including simple block and simple cyclic distribution) are
described by {\em level 1} ranges.  Block-cyclic distribution format is
described by a {\em level 2} range.  For completeness, Adlib adds {\em
level 0} ranges.  These are ranges that describe an unadorned process
dimension, or a subrange of a process dimension.

\section{General Definitions}

\begin{description}

\item{Level:}
A non-negative integer, characteristic of any range.


\item{Primitive range:}
The range of a process dimension.  The global subscripts are 
simply the coordinates of the process dimension.

A primitive range has level 0.

\item{Subrange:}
A range defined as a (strided) subinterval of some parent range.

A subrange retains an {\em alignment} relation to the
parent range---the mapping of a subrange element to the process
dimension is the same as that of the corresponding element of the
parent range.  Subranges can be used to implement the general
alignment options of HPF.

The level of a subrange is the same as the level of the parent range.

\item{Template range:}
A range that is not a subrange of any range except itself.
Template ranges thus include primitive ranges, block-distributed ranges
with (in HPF terms) identity alignment, and cyclic-distributed ranges
with identity alignment.

Template ranges can be used to represent the dimensions of an HPF
template.

\item{Parent template range:}
Any range is a subrange of its unique {\em parent template}.

\item{Kernel range:} Any range of level higher than 0 is distributed
over some {\em kernel range}.

The level of a range's kernel one less than range's own level.  For
example, the kernel of a range with HPF-like block distribution or
simple cyclic distribution is a primitive range---a process-dimension
range.  The kernel of a range with HPF-like block-cyclic distribution,
on the other hand, is a range with simple cyclic distribution.

%\item{Simple range:}
%A range whose kernel is a primitive range (ie, a process dimension).
%A simple range has level 1.
%
%In HPF, block distributed array dimensions and simple-cyclic distributed
%array dimensions correspond to simple ranges.
%{\em Block-cyclic} distribution, in contrast, cannot be represented by
%a simple Adlib range.  A block-cyclic distribution is regarded as a level
%2 range distributed blockwise, with a cyclically distributed simple
%range as kernel.

%In principle an Adlib range could be level-1 without being simple.  A
%level-1 range could be distributed over a {\em subrange} of a process
%dimension.  This does not correspond to any HPF 1.0 distribution
%format.  Such ranges are not part of the {\tt Range} hierarchy
%documented in this document, but they are supported by the underlying
%implementation of the library.

%Note that simple ranges {\em do not} have a particularly special status
%in Adlib.  They are defined here only because they are a common case
%and will recur in examples.

\item{Global subscript:} The primary subscript associated with a range.
A value from the interval $0, \ldots,${\tt size()}$ - 1$.  Sometimes just
called the {\em subscript}.

\item{Template subscript:} For any element of a range, the associated
global subscript in the parent template range.

\item{Kernel subscript:} For any element of a range, the associated
global subscript in the kernel range (for level 1 ranges this is the
process coordinate).

\item{Block:} The section of a range associated with a particular fixed
value of the kernel subscript (for level 1 ranges, the section of the
range mapped to a particular process coordinate).  Any
element of the range lies in a particular block.  Note that elements of
a block need not have contiguous global subscripts---in cyclic
distribution format, adjacent elements of the block have template
subscript differing by the extent of the kernel.

\item{Shell subscript:} For any element of a range, a subscript
identifying the position of the element within its own block.
In general there is a one-to-one mapping between between
legal kernel-subscript/shell-subscript pairs and legal template
subscripts.

\end{description}

\begin{figure}[btp]
\centerline{\psfig{figure=blocksubs.eps,height=4in}}
\caption{\label{blocksubs}Illustration of various subscripts
for a block-distributed subrange.}
\end{figure}

\begin{figure}[btp]
\centerline{\psfig{figure=cyclicsubs.eps,height=4in}}
\caption{\label{cyclicsubs}Illustration of various subscripts
for a cyclic-distributed subrange with stride 2.}
\end{figure}

\newpage

\section{struct {\tt Location}\label{subscripts}}

A record that bundles together a process dimension, a coordinate, a
template subscript, and any shell subscripts implied by a particular
global subscript value in a particular range.

The interface of the {\tt Location} struct is
\small
\begin{verbatim}
  struct Location {
    Dimension dim ;
    int crd ;

    int tem ;
    int sub ;
    int blk ;
  } ;

  Group operator/(const Group& p, const Location& i) ;
  Group operator/(const Procs& p, const Location& i) ;
\end{verbatim}
\normalsize
The {\tt Location} record does not include the global subscript
itself.  This means that a {\tt Location} record constructed from a
subrange is identical to a {\tt Location} record representing the
aligned element of the parent range, although global subscript relative
to the two ranges are generally different.

\subsection{Public data fields}

\begin{verbatim}
dim
\end{verbatim}
The {\tt dim} field should define the process dimension of the parent
range.

\begin{verbatim}
crd
\end{verbatim}
The {\tt crd} field should define the coordinate in {\tt dim} of
processes holding the location.

\begin{verbatim}
tem
\end{verbatim}
The template subscript associated with the location.

\begin{verbatim}
sub
\end{verbatim}
The shell subscript associated with the location.  Undefined if the
range has level 0.

\begin{verbatim}
blk
\end{verbatim}
Used only for level 2 ranges.  This field specifies the block that
contains the location.  Technically it is a shell subscript in the
immediate kernel of the parent range (that kernel being a level 1 range).

\subsection{Related operators}

\begin{verbatim}
operator/(const Group& p, const Location& i)
\end{verbatim}
Create a new group formed by restricting this group by {\tt i}.
The inline definition is
\small
\begin{verbatim}
  Group operator/(const Group& p, const Location& i) {
    Group result(p) ;
    result.restrict(i.dim, i.crd) ;
    return result ;
  }
\end{verbatim}
\normalsize

\begin{verbatim}
operator/(const Procs& p, const Location& i)
\end{verbatim}
Create a new group formed by restricting this process array by {\tt i}.
The inline definition is
\small
\begin{verbatim}
  Group operator/(const Procs& p, const Location& i) {
    Group result(p) ;
    result.restrict(i.dim, i.crd) ;
    return result ;
  }
\end{verbatim}
\normalsize


\newpage

\section{struct {\tt Block}}

A record parametrizing an individual block of a range.  It includes
size (count) of the block, together with global, template and shell
subscript bases and steps.

The interface of the {\tt Block} struct is
\small
\begin{verbatim}
  struct Block {
    int count ;

    int glb_bas, glb_stp ;

    int tem_bas, tem_stp ;

    int sub_bas, sub_stp ;
  } ;
\end{verbatim}
\normalsize

\subsection{Public data fields}

\begin{verbatim}
count
\end{verbatim}
The number of elements in the block.

\begin{verbatim}
glb_bas
\end{verbatim}
The global subscript of the first element in the block. 

\begin{verbatim}
glb_stp
\end{verbatim}
The increment of the global subscript between adjacent elements in the
block.  For most distribution formats this will be 1, but we have to
allow for cyclically distributed ranges, where blocks are generally
strided sections of the parent range.

\begin{verbatim}
tem_bas
\end{verbatim}
The template subscript of the first element in the block. 

\begin{verbatim}
tem_stp
\end{verbatim}
The increment of the template subscript between adjacent elements in the block.
For simple distribution formats this will be 1, but we have to
allow for ranges with strided alignment (and cyclically distributed ranges,
see above).

\begin{verbatim}
sub_bas
\end{verbatim}
The shell subscript of the first element in the block. 

\begin{verbatim}
sub_stp
\end{verbatim}
The increment of the shell subscript between adjacent elements in the block.
Again, we have to allow for ranges with strided alignment.

\section{class {\tt Range}\label{range}}

A {\em range} is a mapping from an integer interval to a process dimension.
A range is described by a
collective object with local components of class {\tt Range}.
The public interface of the {\tt Range} class is given in figure
\ref{rangeInterface}.

\begin{figure}[p]
\small
\begin{verbatim}
  class Range {
  public :
    Range() ;
    Range(const Range& x) ;
    ~Range() ;

    Range& operator=(const Range& x) ;

    int size() const ;

    Dimension dim() const ;

    Range tem() const ;
    int bas() const ;
    int str() const ;

    int lev() const ;
    Range ker() const ;
    Range shell() const ;

    Format format() const ;

    int isAligned(const Range& x) ;

    Range subrng(const int extent,
                 const int base = 0, const int stride = 1) const ;

    void location(Location* loc, const int glb) const ;

    void block(Block* blk, const int ker_glb) const ;
    int local(int* glb) const ;

    Range subker() const ;

    int volume() const ;
    int offset(const Location& loc) const ;

    int disp(const int sub) const ;
    int step(const int sub_stp) const ;

    Location operator()(const int k) ;
    int idx(const Location& loc) const ;
  } ;
\end{verbatim}
\normalsize
\caption{\label{rangeInterface}Public interface of the {\tt Range} class.}
\end{figure}

The constructors of the {\tt Range} class itself do not implement any
specific distribution formats.  These are provided by the constructors
for a series of derived classes.

\subsection{Constructors and destructors}

\begin{verbatim}
Range()
\end{verbatim}
The default constructor.  Creates a null (uninitialized) range object.
The only members that can legally be applied to such an object are
the assignment {\tt operator=(const Range\& x)}
% the conversion {\tt operator RangeRep*()}, 
and the copy constructor.

\begin{verbatim}
Range(const Range& x)
\end{verbatim}
Copy constructor.  {\tt Range} is implemented as a reference-counted
handle class to an object of type {\tt RangeRep}.  The copy constructor
copies the reference and increments the reference count in the
representation object.

\begin{verbatim}
~Range()
\end{verbatim}
Destructor.  If the range is non-null, the representation object's
reference count is decremented.  If this reduces the count to 0,
the representation object is deleted.


\subsection{Methods}

\begin{verbatim}
size()
\end{verbatim}
An inquiry function returning the extent of the range.

\begin{verbatim}
dim()
\end{verbatim}
An inquiry function returning the underlying process dimension.  For
a collapsed range this is a collapsed dimension.

\begin{verbatim}
tem()
\end{verbatim}
An inquiry function returning the parent template range.

\begin{verbatim}
bas()
\end{verbatim}
An inquiry function returning the alignment base of this range in
the parent template range.  Element 0 of this range corresponds to
element {\tt bas()} in the template range.

\begin{verbatim}
str()
\end{verbatim}
An inquiry function returning the alignment stride of this range
relative to the parent template range.  Adjacent elements of this range
correspond to elements separated by {\tt str()} in the template range.
The result may be positive or negative (not zero).

\begin{verbatim}
lev()
\end{verbatim}
An inquiry function returning the level of this range.  Zero for
(a range describing) a process dimension or subrange of a process
dimension, positive for any other range.

\begin{verbatim}
ker()
\end{verbatim}
An inquiry function returning the kernel range.  In general this is a
range of level one lower than this range.  Result is undefined for
level 0 ranges.

\begin{verbatim}
shell()
\end{verbatim}
An inquiry function returning the shell range.  This is a collapsed
range large enough to describe any block of the parent template range.
Result is undefined for level 0 ranges.

\begin{verbatim}
format()
\end{verbatim}
An inquiry function returning a code that specifies the distribution format
of this range.  The result is a member of the enumeration type:
\small
\begin{verbatim}
  enum Format {DIST_PRIMITIVE, DIST_COLLAPSED,
               DIST_BLOCK, DIST_CYCLIC, DIST_BLOCK_CYCLIC, 
               DIST_IRREG, ...} ;
\end{verbatim}
\normalsize

\begin{verbatim}
isAligned(const Range& x)
\end{verbatim}
A comparision operation that returns a non-zero value if
{\tt x} is {\em alignment equivalent} with this range.
The definition of alignement equivalence used here is that
ranges are aligned if their parent template ranges are aligned, and they
have the same extent and alignment base and stride.  Template ranges
are aligned if they are distributed over the same dimension of the same
process array\footnote{The process arrays must be described by the {\em same
object}, not merely structurally similar process arrays.}, and
distribution parameters such as the distribution format and local block
sizes are the same.  Alignment equivalence {\em does not} require local
memory layout parameters (in particular ghost extension widths) to be
identical.

\begin{verbatim}
subrng(const int extent, const int base, const int stride)
\end{verbatim}
Returns a {\tt Range} object representing a subrange of this range.
The size of the subrange is {\tt extent} and its elements are labelled
$0, \ldots, ${\tt extent}$ - 1$.  The subrange includes elements
\small
\begin{verbatim}
  base, base + stride, base + 2 * stride, ...,
                       base + (extent - 1) * stride
\end{verbatim}
\normalsize
from the parent.  The elements of the subrange
are mapped to the underlying process dimension in the same way as the
corresponding elements of the parent range (they are {\em aligned} with
the corresponding elements of the parent).  The value of {\tt stride}
must be positive or negative (not zero).  The values of {\tt base} and
{\tt base + (extent - 1) * stride} must be in the range $0, \ldots,
${\tt size()}$ - 1$.  If the {\tt stride} actual argument is omitted,
it defaults to 1.  If the {\tt base} actual argument is also omitted,
it defaults to 0.

If this range (the parent) is itself a subrange, the alignment
parameters {\tt base} and {\tt stride} for the new subrange are
composed with those of the parent, to give a simple map to the common
template range.

\begin{verbatim}
location(Location* loc, const int glb)
\end{verbatim}
Overwrites {\tt *loc} with a location record corresponding to the element
of the range with global subscript {\tt glb}.

\begin{verbatim}
block(Block* blk, const int ker_glb)
\end{verbatim}
This function is defined only for ranges {\em with level higher than 0}.
Given a kernel subscript value, {\tt ker\_glb}, writes the parameters
of the associated block in {\tt *blk}.
Used in translation of parallel loops---see section \ref{loops} for examples.

The value written to {\tt blk->glb\_bas} is the smallest value of the
global subscript contained in the block.  The corresponding values of
the template subscript and shell subscript overwrite {\tt
blk->tem\_bas} and {\tt blk->sub\_bas} respectively.  The number of
active elements in the block overwrites {\tt blk->count}.

The difference in the values of global, template and shell subscripts
between adjacent active elements in the block overwrite {\tt blk->glb\_stp},
{\tt blk->tem\_stp} and {\tt blk->sub\_stp} respectively.

\begin{verbatim}
local(int* glb)
\end{verbatim}
This function is defined {\em only for level 0 ranges}, and then
only if the local process is a member of the process array to
which {\tt dim()} belongs.  It returns
the value 1 if the local process holds an element of the range
and zero otherwise.
If the range is primitive---a complete process dimension, the result
is always non-zero.  For a subrange it may be zero.
Used in translation of parallel loops---see section \ref{loops} for
examples.

If the result is non-zero, the value of the global subscript of
the local process with respect to the range overwrites {\tt *glb}.
If the range is primitive, the global subscript is value of the local
coordinate.  For a subrange of a primitive range it is 
{\tt (crd - bas()) / str()} where {\tt crd} is the local coordinate.

\begin{verbatim}
subker()
\end{verbatim}
A subrange of the kernel, including all elements of the kernel for
which the function {\tt block} defines a non-empty block.  Used to
optimize the procedure for enumerating all blocks of a range---see
section \ref{loops}.  Result is undefined for level 0 ranges.

\begin{verbatim}
volume()
\end{verbatim}
A bound on the number of elements associated with
any single process for an array allocated with this range.
This member is used directly
to control the allocation of memory for elements of distributed arrays.

\begin{verbatim}
offset(const Location& loc)
\end{verbatim}
Returns the total offset for the location {\tt loc}.
For any legal value of {\tt loc} the inequality
\small
\begin{verbatim}
  offset(loc) < volume()
\end{verbatim}
\normalsize
holds.

\begin{verbatim}
disp(const int sub)
\end{verbatim}
Translation from shell subscript, {\tt sub}, to an offset
(displacement) in a local array segment.  
This function is defined only for ranges {\em with level higher than 0}.
It is often the identity function (returning the value of its argument),
but may, for example add an offset
if the range has ghost regions, or implement some more complicated
packing function for arrays with strided alignment.

For a {\em level 1} range the identity
\small
\begin{verbatim}
  offset(i) = disp(i.sub)
\end{verbatim}
\normalsize
holds.
Especially for {\em collapsed} ranges this formula provides a simple
way to compute the offset without introducing a {\tt Location}
record.  Note that for {\em any range} with level higher than zero we have the
identity
\small
\begin{verbatim}
  disp(sub) = shell().disp(sub)
\end{verbatim}
\normalsize
so for any legal value of {\tt sub} the inequality
\small
\begin{verbatim}
  disp(sub) < shell().volume()
\end{verbatim}
\normalsize
holds.

For level 2 ranges, the result of {\tt disp} does {\em not}
include the contribution to the total offset arising from the
displacement of the block base (parametrized by the {\tt blk} field int the
location record).  However a complete identity in the level 2 case is
\small
\begin{verbatim}
  offset(i) = disp(i.sub) +
              shell().volume() * ker().disp(i.blk)
\end{verbatim}
\normalsize

\begin{verbatim}
step(const int sub_stp)
\end{verbatim}
This function returns the difference in the value of {\tt offset} between
two points in the same block of the range separated in shell subscript
by {\tt sub\_stp}.  This member is obsolescent---for all range classes
documented here {\tt step} implements the identity function,
returning the value of its argument.  In some undocumented classes {\tt
step} divides by a scaling factor to support a dense packing scheme for
arrays with strided alignment, and various functions in the library
call {\tt step} to support a compiler which uses that scheme.

\begin{verbatim}
idx(const Location& loc)
\end{verbatim}
Returns global subscript in this range associated with location {\tt loc}.
Equivalent to
\small
\begin{verbatim}
  int idx(const Location& loc) const {
    return (loc.tem - bas()) / str() ;
  }
\end{verbatim}
\normalsize

\subsection{Operators}

\begin{verbatim}
operator()(const int glb)
\end{verbatim}
Returns a {\tt Location} object associated with global subscript
value {\tt glb}.  Equivalent to
\begin{verbatim}
  Location operator()(const int glb) {
    Location res;
    location(&res, glb) ;
    return res ;
  }
\end{verbatim}

\begin{verbatim}
operator=(const Range& x)
\end{verbatim}
Assignment operator.  Copies the reference in handle {\tt x} and
increments the reference count in the representation object.
Decrements the reference count of (and deletes, if necessary) any
representation object referenced by the assignment variable prior to
the assignment.

%\begin{verbatim}
%operator RangeRep*()
%\end{verbatim}
%Returns a pointer to the representation object.  Returns a null pointer
%if the range is null.
%
%This low-level operator is useful (for example for testing for a null
%range), but note that it returns a handle which is not recorded in
%the reference count of the representation object.  The specific value
%of the result is therefore ``ephemeral''---a reference that can easily
%be rendered invalid by unexpected deletion of the representation
%object.

\newpage

\section{class {\tt CollapsedRange}\label{collapsedRanges}}

The class {\tt CollapsedRange} is a subclass of {\tt Range} describing
{\em collapsed} (sequential) ranges.  The {\tt format} inquiry
returns {\tt DIST\_COLLAPSED} for a {\tt CollapsedRange} or any subrange.

The public interface of the {\tt CollapsedRange} class is
\small
\begin{verbatim}
  class CollapsedRange : public Range {
  public :
    CollapsedRange(const int extent) ;
  }
\end{verbatim}
\normalsize

\subsection{Constructors}

\begin{verbatim}
CollapsedRange(const int extent)
\end{verbatim}
Creates a {\em collapsed} template range.  This is a range of size
{\tt extent} mapped entirely to the local process.
The {\tt dim()} inquiry applied to a collapsed range returns a
collapsed dimension.  The level of a collapsed range is 1.
The {\tt ker()} inquiry will return a primitive range representing a
collapsed dimension\footnote{This is different to a null range.}.

\newpage

\section{class {\tt DimRange}\label{primitiveRanges}}

The class {\tt DimRange} is a subclass of {\tt Range} describing
{\em primitive} ranges.  The {\tt format} inquiry
returns {\tt DIST\_PRIMITIVE} for a {\tt DimRange} or any subrange.

The public interface of the {\tt DimRange} class is
\small
\begin{verbatim}
  class DimRange : public Range {
  public :
    DimRange(Dimension dim) ;
  }
\end{verbatim}
\normalsize

\subsection{Constructors}

\begin{verbatim}
DimRange(Dimension dim)
\end{verbatim}
Creates a level 0 template range (a primitive range) describing
{\tt dim}.  The size of this range is {\tt dim.size()}.  The {\tt
dim()} inquiry applied to the constructed range returns the constructor
argument.  The {\tt ker()} inquiry is undefined.

\newpage

\section{class {\tt BlockRange}\label{blockRanges}}

The class {\tt BlockRange} is a subclass of {\tt Range} describing
{\em uniform block-distributed} ranges.  The {\tt format} inquiry
returns {\tt DIST\_BLOCK} for a {\tt BlockRange} or any subrange.

The public interface of the {\tt BlockRange} class is
\small
\begin{verbatim}
  class BlockRange : public Range {
  public :
    BlockRange(const int extent, Dimension dim) ;

    BlockRange(const int extent, Dimension dim,
               const int wlo, const int whi) ;
  }
\end{verbatim}
\normalsize

\subsection{Constructors}

\begin{verbatim}
BlockRange(const int extent, Dimension dim)
\end{verbatim}
Creates a block-distributed range of extent {\tt extent} and
kernel {\tt dim}.  The block size is
\small
\begin{verbatim}
  (extent + dim.size() - 1) / dim.size()
\end{verbatim}
\normalsize
The constructed range is a template range.

\begin{verbatim}
BlockRange(const int extent, Dimension dim,
           const int wlo, const int whi)
\end{verbatim}
Similar to the constructor above, but arrays constructed with this
range (or its subranges) have ghost regions of width {\tt wlo}, {\tt whi}
at the upper and lower edges of each block of the range.

\newpage

\section{class {\tt CyclicRange}\label{cyclicRanges}}

The class {\tt CyclicRange} is a subclass of {\tt Range} describing
{\em cyclically-distributed} ranges.  The {\tt format} inquiry
returns {\tt DIST\_CYCLIC} for a {\tt CyclicRange} or any subrange.

The public interface of the {\tt CyclicRange} class is
\small
\begin{verbatim}
  class CyclicRange : public Range {
  public :
    CyclicRange(const int extent, Dimension dim) ;
  }
\end{verbatim}
\normalsize

\subsection{Constructors}

\begin{verbatim}
CyclicRange(const int extent, Dimension dim)
\end{verbatim}
Creates a cyclically-distributed range of extent {\tt extent} and
kernel {\tt dim}.  The number of cycles is
\small
\begin{verbatim}
  (extent + dim.size() - 1) / dim.size()
\end{verbatim}
\normalsize
The constructed range is a template range.

\newpage

\section{class {\tt BlockCyclicRange}\label{blockCyclicRanges}}

The class {\tt BlockCyclicRange} is a subclass of {\tt Range} describing
{\em block-cyclically-distributed} ranges.  The {\tt format} inquiry
returns {\tt DIST\_BLOCK\_CYCLIC} for a {\tt BlockCyclicRange}
(or any subrange).  The {\tt lev} inquiry returns the value 2.

The public interface of the {\tt BlockCyclicRange} class is
\small
\begin{verbatim}
  class BlockCyclicRange : public Range {
  public :
    BlockCyclicRange(const int extent, Dimension dim,
                     const int blockSize) ;
  }
\end{verbatim}
\normalsize

\subsection{Constructors}

\begin{verbatim}
BlockCyclicRange(const int extent, Dimension dim,
                 const int blockSize)
\end{verbatim}
Creates a block-cyclically-distributed range of extent {\tt extent}
distributed cyclically over dimension {\tt dim} with block-size {\tt
blockSize}.  The constructed block-cyclic range is a template range.
The number of blocks is
\small
\begin{verbatim}
  numBlocks = (extent + blockSize - 1) / blockSize
\end{verbatim}
\normalsize
The kernel of the range is a simple cyclically-distributed template range
with number of cycles given by
\small
\begin{verbatim}
  numCycles = (numBlocks + dim.size() - 1) / dim.size()
\end{verbatim}
\normalsize
The extent of the kernel range is thus
\small
\begin{verbatim}
  numCycles * dim.size().
\end{verbatim}
\normalsize

The detailed structure of a block-cyclic range can be discovered
with the aid of the {\tt lev} and {\tt ker} inquiries.

\newpage

\section{class {\tt IrregRange}\label{irregRanges}}

The class {\tt IrregRange} is a subclass of {\tt Range} describing
{\em irregular block-distributed} ranges.  The {\tt format} inquiry
returns {\tt DIST\_IRREG} for an {\tt IrregRange} or any subrange.

The public interface of the {\tt IrregRange} class is
\small
\begin{verbatim}
  class IrregRange : public Range {
  public :
    IrregRange(Dimension dim, int* blocks) ;
  } ;
\end{verbatim}
\normalsize

\subsection{Constructors}

\begin{verbatim}
IrregRange(Dimension dim, int blocks [])
\end{verbatim}
Creates a irregular block-distributed with
kernel {\tt dim}.  The array {\tt blocks} should have
{\tt dim.size()} elements containing non-negative integers.  These define
the block size associated with each process.  The extent of the
range is
\small
\begin{displaymath}
\sum_{i = 0}^{\mbox{\tt dim.size()}} \mbox{\tt blocks [} i \mbox{\tt ]}
\end{displaymath}
\normalsize
The constructed range is a template range.

\newpage

\chapter{Arrays\label{arrays}}

An Adlib array is a rectangular distributed array of any rank, whose
elements are partioned or replicated across some set of processes.
The layout of the array is described by an object of type {\tt DAD}
which contains
\begin{itemize}
\item
The {\em rank}, {\tt R} of the array (ie, its number of dimensions).
{\tt R} is greater than or equal to zero.
\item
The {\em process group} over which the elements of the array are distributed.
\item
A vector of {\tt R} {\em dimension map objects}, describing the shape
of the array, and the mapping of its index space into the dimensions of
of the process group, and the memory strides in the locally-held
segment of the array.
\end{itemize}
The definition of the array is completed by a local array, or a pointer
to a base address in the memory of each process, where the elements are
actually stored.  The type of the array elements is determined by the
type of the local array segment---the {\tt DAD} itself is blind
to element type.

Note that the Adlib kernel makes no intrinsic assumptions about the
ordering of array elements in local memory.  For example, when a new
distributed array is created, the dimension map vectors can set up to describe
situations where either the first or the last dimension is ``most
rapidly varying'' in memory\footnote{There is a caveat---although all
functions in the library will operate correctly regardless of majority,
many of them are optimized to perform best on the assumption of first
dimension most rapidly varying---the Fortran convention.}.  Similarly,
no assumption is made that array elements fill a contiguous region of
memory.  In Fortran 90 terms, a {\tt DAD} record can describe an
arbitrary {\em regular section} of some parent array.

\newpage

\section{struct {\tt Map}\label{maps}}

A {\em dimension map} is part of a distributed array descriptor.  It is
a map from a {\tt Location} to an offset in a local data segment.
Dimension maps are associated with particular parent ranges.  They also
incorporate a memory stride.

The public interface of the {\tt Map} class is
\small
\begin{verbatim}
  struct Map {
    Map() ;
    Map(Range _range, const int _stride) ;

    Map ker() const ;
    Map shell() const ;

    Range rng() const ;
    int str() const ;

    int offset(const Location& i) const ;

    int disp(const int sub) const ;
    int step(const int sub_stp) const ;

    Range range ;
    int stride ;
  } ;
\end{verbatim}
\normalsize

\subsection{Constructors and destructors}

\begin{verbatim}
Map()
\end{verbatim}
The default constructor.  Creates a null (uninitialized) dimension map object.

\begin{verbatim}
Map(Range _range, const int _stride)
\end{verbatim}
Create a dimension map with parent range {\tt \_range} and memory stride
{\tt \_stride}.

\subsection{Methods}

\begin{verbatim}
ker()
\end{verbatim}
An inquiry function returning the kernel dimension map.  This is a dimension map
associated with the kernel of the parent range.  Undefined for
dimension maps with level 0 parent ranges.

Equivalent to
\small
\begin{verbatim}
  Map ker() const {
    return Map(rng().ker(), rng().shell().volume() * str()) ;
  }
\end{verbatim}
\normalsize

\begin{verbatim}
shell()
\end{verbatim}
An inquiry function returning the shell dimension map.  This is a dimension map
associated with the shell of the parent range.  Undefined for
dimension maps with level 0 parent ranges.

Equivalent to
\small
\begin{verbatim}
  Map shell() const {
    return Map(rng().shell(), str()) ;
  }
\end{verbatim}
\normalsize

\begin{verbatim}
str()
\end{verbatim}
An inquiry function returning the
stride used in creation of this dimension map.  
To avoid confusion, note well that this is a {\em memory stride}, and
this concept is completely unrelated to the {\em alignment stride},
returned by the {\tt str} member of {\tt Range}.

\begin{verbatim}
offset(const Location& i)
\end{verbatim}
Returns the offset in local array segment produced by location {\tt i}.

Equivalent to
\small
\begin{verbatim}
  int offset(const Location& i) const {
    return str() * rng().offset(i) ;
  }
\end{verbatim}
\normalsize

\begin{verbatim}
disp(const int sub)
\end{verbatim}
Returns the offset in local array segment produced by shell subscript {\tt sub}.

Equivalent to
\small
\begin{verbatim}
  int disp(const int sub) const {
    return str() * rng().disp(sub) ;
  }
\end{verbatim}
\normalsize

\begin{verbatim}
step(const int sub_stp)
\end{verbatim}
The difference in the value of {\tt offset}---the local segment
offset---between two points in the same block of the range differing
in shell subscript by an amount {\tt sub\_stp}.

For all standard ranges this is equivalent to
\small
\begin{verbatim}
  int step(const int sub_stp) const {
    return str() * sub_stp ;
  }
\end{verbatim}
\normalsize
It is actually implemented as
\small
\begin{verbatim}
  int step(const int sub_stp) const {
    return str() * rng().step(sub_stp) ;
  }
\end{verbatim}
\normalsize
---see the discussion of {\tt Range :: step} in section \ref{range}.

\newpage

\section{struct {\tt DAD}}

A {\em distributed array descriptor} describes the layout of the elements of
a distributed array.  An array descriptor is represented by a
collective object with local components of class {\tt DAD}.
The public interface of the {\tt DAD} class is
\small
\begin{verbatim}
  struct DAD {
    DAD(const int _rank, const Group& _group, Map* _maps) ;

    DAD(const int _rank, const Group& _group) ;

    DAD() ;

    int rnk() const ;

    const Group &grp() const ;

    const Range rng(const int r) const ;

    int str(const int r) const ;

    const Map &map(const int r) const ;

    DimensionSet sig() const ;

    int rank ;

    Group group ;

    Map* maps ;
  } ;
\end{verbatim}
\normalsize

\subsection{Public data fields}

\begin{verbatim}
rank
\end{verbatim}
The rank, {\tt R}, of the array.  Greater than or equal to zero.

\begin{verbatim}
group
\end{verbatim}
The group over which the array is distributed.

\begin{verbatim}
maps
\end{verbatim}
The vector of dimension maps of the array.
Size of the vector should be {\tt R}.
Distributed ranges in the maps held in this vector should be distributed over
distinct (orthogonal) dimensions of {\tt group}.

\subsection{Constructors}

\begin{verbatim}
DAD(const int _rank, const Group& _group, Map* _maps)
\end{verbatim}
The normal constructor.  Initializes all fields of the {\tt DAD} object,
simply copying the values passed as arguments.  The constructor {\em does
not} allocate any new vector internally.  The 
{\tt \_maps} pointer is simply copied.  It is the caller's
responsibility to ensure that associated vector persists as long as the 
constructed {\tt DAD} record.

\begin{verbatim}
DAD(const int _rank, const Group& _group)
\end{verbatim}
Simplified constructor.  The {\tt maps} field is left undefined.  Since
it is publically accessibly, it can be initialized later.

\begin{verbatim}
DAD()
\end{verbatim}
Default constructor.  All fields are left undefined.

\subsection{Methods}

\begin{verbatim}
rnk()
\end{verbatim}
An inquiry function returning the rank of the array
(the value of {\tt rank}).

\begin{verbatim}
grp()
\end{verbatim}
An inquiry function returning the group over which the array
is distributed (the value of {\tt group}).

\begin{verbatim}
rng(const int r)
\end{verbatim}
An inquiry function returning the {\tt r}th range of the array---the
value of {\tt map(r).rng()}.

\begin{verbatim}
str(const int r)
\end{verbatim}
An inquiry function returning the {\tt r}th memory stride of the
array---the value of {\tt map(r).str()}.

\begin{verbatim}
map(const int r)
\end{verbatim}
An inquiry function returning the {\tt r}th dimension map of the array---the
value of {\tt maps [r]}.

\begin{verbatim}
DimensionSet sig()
\end{verbatim}
Return the {\em signature} of the array.  The signature is the set of
process dimensions over which the ranges of the array are distributed.
Equivalent to
\small
\begin{verbatim}
  DimensionSet sig() const {
    DimensionSet signature ;
    for(int r = 0 ; r < rank ; r++)
      signature += rng(r).dim() ;
    return signature ;
  }
\end{verbatim}
\normalsize
One common use for the {\tt sig} member is to compute the set of process
dimensions over which the array is replicated.  This is given by
\small
\begin{verbatim}
  grp().dims() - sig()
\end{verbatim}
\normalsize

\newpage

\section{Examples}

Suppose {\tt p} is a group and {\tt x} and {\tt y} are ranges distributed
over dimensions of this group.  We want to create a new distributed
array of floating point numbers described by these parameters.
A typical procedure would be
\small
\begin{verbatim}
  Map [2] a_maps ;

  int size = 1 ;

  a_maps [0] = Map(x, size) ;
  size *= x.volume() ;
  a_maps [1] = Map(y, size) ;
  size *= y.volume() ;

  DAD a_frm(2, p, a_maps) ;
  float* a_dat = new float [size] ;
\end{verbatim}
\normalsize
New dimension maps are created in the vector {\tt maps}.  This code implements
an array with first dimension ``most-rapidly-varying'' in
memory\footnote{To implement an array with last dimension most-rapidly
varying one would simply reverse the order of construction of the dimension
maps.}.
After the two multiplications by {\tt Range :: volume} the value accumulated in
{\tt size} is the total volume of the local array segment.
The group and map vector are installed in {\tt a\_frm}
and the local data segment is allocated in {\tt a\_dat}.

Now suppose {\tt i} and {\tt j} are {\tt Location} objects with parent
ranges {\tt x} and {\tt y} respectively.  We want to access the array element
associated with these subscripts.  A typical procedure would be
\small
\begin{verbatim}
  Location i(x(l1)), j(y(l2)) ;
  ...
  if(i.dim.crd() == i.crd)
    if(j.dim.crd() == j.crd) {
       ...
       a_dat [a_frm.map(0).offset(i) + a_frm.map(1).offset(j)]
       ...
    }
\end{verbatim}
\normalsize
First we test if the element is held on the local process by looking
at the coordinate field in the subscript objects\footnote{An outer
test may be needed, to see if the local process is a member of {\tt p}
(ie, of {\tt a\_frm.grp()})}, then the {\tt offset} member is applied to
the map objects to find the offsets in the local data segment.
Compared with the sort of address computations involved in accessing
elements of sequential arrays, free use of calls to member functions
incurs a large, frequently intolerable, performance penalty.  General
techniques for eliminating these penalties are discussed in section
\ref{loops}.

Suppose we want to set up a description of a two-dimensional
section of {\tt a}, with subranges of {\tt x} and {\tt y}
(something like {\tt a(l1:u1, l2:u2)} in Fortran).
\small
\begin{verbatim}
  Map [2] b_maps ;

  b_maps [0] = Map(x.subrng(n1, l1), a.str(0)) ;
  b_maps [1] = Map(y.subrng(n2, l2), a.str(1)) ;
  
  DAD b_frm(2, p, b_maps) ;
  float* b_dat = a_dat ;
\end{verbatim}
\normalsize
The memory strides and local data segment are copied from the original array.
(Here {\tt n1} is {\tt u1 - l1 + 1} and {\tt n2} is {\tt u2 - l2 + 1}.)

If, instead, we wanted to set up a description of a one dimensional
section of {\tt a}, with global subscript {\tt l1} in the first dimension,
retaining the whole of the second dimension (something like {\tt a(l1, :)}
in Fortran) we could write
\small
\begin{verbatim}
  Map [1] c_maps ;

  c_maps [0] = a.map(1) ;
  
  Location i(x(l1)) ;

  DAD c_frm(1, p / i, c_maps) ;
  float* c_dat = a_dat + a_frm.map(0).offset(i) ;
\end{verbatim}
\normalsize
No new map objects need be created:  the dimension map of the
unsubscripted dimension is copied from the original array descriptor.
The process group over which the section is distributed is {\tt p /
i}.  The offset for the first dimension is added to the base address of
the original array\footnote{The offset pointer value is only valid on
processes that hold part of the section, but it does no harm to do the
addition on other processes.  The value {\tt b\_dat} should never be
{\em used} on processes where it is not valid---ie on processes outside
the group {\tt p / i}.}.
One can access element {\tt j} of the section {\tt c} by
\small
\begin{verbatim}
  if(c_frm.grp().member())
    if(j.dim.crd() == j.crd) {
       ...
       c_dat [c_frm.map(0).offset(j)]
       ...
    }
\end{verbatim}
\normalsize
The two examples given above easily generalize to allow construction
any Fortran-90 style {\em regular section} of any distributed array.

\section{Array shape\label{shape}}

As in Fortran, the {\em shape} of an array, $a$, is defined as the vector of
extents of its ranges, ie $(\mbox{\tt a.rng(0).size()}, \ldots,
\mbox{\tt a.rng(R-1).size()})$, where $R$ is the rank of the array.

\section{Alignment\label{alignment}}

An array, {\tt a} is {\em aligned with} an array {\tt b} if they are
distributed over the equivalent process groups and their ranges
are all equivalent:
\begin{displaymath}
\begin{array}{lll}
\mbox{\tt a.grp()} & \approx & \mbox{\tt b.grp()} \\
\\
\mbox{\tt a.rng(0)} & \approx & \mbox{\tt b.rng(0)} \\
& \vdots \\
\mbox{\tt a.rng(R-1)} & \approx & \mbox{\tt b.rng(R-1)}
\end{array}
\end{displaymath}
The equivalance relations can be assumed to be the ones defined by the
members {\tt Group :: isEqual} and {\tt Range :: isAligned}.
Informally, two groups or two ranges are equivalent if
they are {\em structurally equivalent}\footnote{A special feature is
that alignment equivalence of ranges does not imply that the ranges
must have the same {\em layout} options.  So, for example, two arrays may be
aligned even if one has ghost extensions and the other doesn't.}.  The
informal meaning of array alignment is that corresponding elements of
the two arrays are stored on the same process, or replicated over the
same group of processes.

The array, {\tt a} is aligned with {\tt b} {\em with replicated-alignment} in
some dimensions if the groups are equivalent, and the ranges of {\tt a} can
be paired with equivalent ranges of {\tt b} by omitting the ranges of {\tt b}
associated with the specified dimensions.

\section{Accessibility\label{accessibility}}

An array, {\tt a}, is {\em accessible} at a particular point in program
execution if it is distributed over a group contained in the
active process group:
\begin{displaymath}
\mbox{\tt a.grp()} \subseteq \mbox{\tt apg}
\end{displaymath}
The contains relation can be assumed to be the one defined by the
member {\tt Group :: contains}.
Informally this means that all copies of all elements of the
array are available within the set of processes sharing the
current thread of control.

\chapter{Communication schedules\label{schedules}}

This chapter defines the Adlib communication library.  Currently all
communication functions in Adlib take the form of collective
transformations on distributed arrays.  These transformations are
implemented in terms {\em communication schedules}.  Each kind of
transformation has an associated class of schedules.  Specific
instances of these schedules, involving particular data arrays and
particular parameters, are created as objects from the classes
concerned.  {\em Executing} a schedule initiates the communications
required to implement the transformation.  A single schedule may be
executed many times, repeating the same communication pattern.

Future versions of Adlib may support other communication paradigms.  A
convenient extension would allow primitives for {one-sided
communication}.  These would permit direct read or write access to
remote patches of distributed arrays.

\section{General features of schedules}

Typically the communication schedules described in this chapter have
only three public members: a constructor, a destructor, and an {\tt
execute} member.

Usually the constructor is passed all the detailed information
describing how the input and output data is organized and
how it is to be transformed.  This includes the array descriptors
and any parameters of the transformation.  The constructor
may perform extensive processing on these arguments to convert them
into a simplified list of data movements.  In some cases this
processing may involve exchange of information---ie,
communication---between the active processes.  A schedule constructor
should always be treated as a collective operation.
As usual with arguments of collective operations, every member
of the active process group must pass consistent arguments to the
schedule constructor call.  In particular this means that any simple
value passed to a schedule constructor (any argument that is not a
local component of a collective object such as a DAD, or a vector
of local array elements associated with a DAD) must have {\em
identical} values in every process.

Local segment addresses of input and output arrays---the vectors
where individual array elements are stored---are usually {\em not}
passed to the schedule constructor.  Instead these addresses are passed
to the {\tt execute} member.  One practical reason for not storing the
data pointers in the schedule itself is that these vectors are typically
allocated by the user, outside control of the library.  The user's
program may be written in a programming language other than C++.
Cacheing pointers to memory allocated and managed outside the library
itself can cause problems in some programming environments---especially
in garbage-collected languages such as Java.  Another advantage of
specifying the data pointers at execution time rather than schedule
construction time is that in principle it allows the same schedule to
be used with different arrays, providing corresponding arrays
have identical DADs.

The {\tt execute} member nearly always involves communication.  It
should of course be treated as a collective operation, executed by all
members of the active process group.

Most schedule constructors will access the {\tt apg} variable.  The
state of this variable should accurately describe the set of processes
involved in creating the schedule.  The active process group at the
point of execution of a schedule should be the same as the active
process group at its point of creation.

The following sections describe the interfaces of the schedule
classes.  The choice of transformations in the current schedule library
has been strongly influenced by HPF.  Apart from a handful of
generic operations like {\tt Remap}, {\tt Gather}, {\tt Scatter} and
{\tt WriteHalo}, most of the schedules are designed to support
the specific array syntax and array transformational intrinsics
of Fortran 90\footnote{An exception is the {\tt MultiShift} schedule,
which was actually introduced to support the array syntax of C*.}.
Focussing on Fortran provides a concrete standard with respect to which
some kind of completeness can be achieved.

In the interfaces given in the following sections, only the constructor
and the {\tt execute} members will be exhibited.  Base classes (public
or otherwise), members of base classes, destructors, etc, will be
suppressed.  Subsections describing the constructors detail any
restrictions the arguments must satisfy.  Subsections describing
the {\tt execute} members specify the effects of the schedules.
Below we briefly discuss various terms and notations used, following
the subheadings used in the schedule definitions.

\subsection{Value restrictions}

These are simply restrictions on the input values of data, such
as constraints ensuring values used as subscripts are in the required
bounds.

\subsection{Type restrictions}

\label{POD}

These are restrictions on the types of array elements.  Typically
if an array's elements are to be communicated, they must have {\em POD}
type.  The idea of a POD type is defined in the ANSI C++ standard.
Informally it is any type that can be copied to a byte array by
standard operations such as {\tt memcpy}.

Schedules that perform arithmetic operations or comparisions will
impose further restrictions on the types of the array elements.
In the current library all such schedules are template classes,
parametrized by the element type.  The template argument can only
be instantiated to a type that supports a suitable set of arithmetic
operations.

\subsection{Shape restrictions}

Restrictions on the shape of the array arguments, such as the requirement
that a particular pair of arrays passed to the constructor should
have the same shape.

\subsection{Alignment restrictions}

Many of the schedules in the library assume some alignment relations
(see section \ref{alignment}) between their array arguments.  Although
these are usually natural restrictions from the point of view of the
parallel implementation, they can sometimes take programmers by
surprise, or appear unnecessarily complex.

For example, it is required that the source array for a {\tt Shift} is
aligned with the destination array.  This sometimes surprises people,
although it probably shouldn't.  Historically, an essential feature of
the shift operation is that it can be implemented very efficiently by
simple nearest neighbour communications.  The library could easily have
been defined to implement shift without the alignment constraint, but
then implementation would be essentially the same as the more complex
{\tt Remap} operation,  and the main point of providing {\tt Shift} is
that it is a simpler, relatively light-weight operation.  If versions
of the library functions without alignment restrictions are needed,
they can always be constructed by combining the constrained operation
with {\tt Remap} operations.

Because the alignment constraints implied by particular implementations
of the schedules can be quite complex, the restrictions are sometimes
simplified slightly in the following sections.  The conditions given
are always sufficient, but sometimes weaker conditions would have been
adequate.  For simplicity, we restrict ourselves to the vocabularly
defined in section \ref{alignment}.

\subsection{Accessibility restrictions}

Accessibility restrictions are needed to ensure that copies
of array elements are available inside the group of processes that
execute a schedule.  Access to elements stored outside the active
process group is not allowed by the collective communication paradigm
currently implemented by Adlib.

\subsection{Argument lifetime}

This usually refers to the situation where a pointer to a DAD is
passed to a schedule constructor.  To avoid the overhead of copying the
DAD, the schedule often saves a reference to the existing DAD object.
The programmer must then ensure that the DAD is not deleted during the
lifetime of the schedule.  

Deleting a DAD before completing communications involving the
associated array would be fairly unusual in practise, so these
``argument lifetime'' restrictions are not expected to be
troublesome.

\subsection{Effect}

In describing the effect of schedules, array subscripting notation will
often be used informally.  In this context, the subscripting should
always be understood in terms of global subscripts to abstract global
arrays, without reference to the distributed nature of the actual arrays.

\subsection{Replicated data} 

By definition, an array is replicated over a particular process
dimension if the dimension appears in its process group but not its
signature (ie, the array has no range distributed over the dimension
concerned).

As a rule it is good practise for programmers to maintain the same
values in all copies of an element of a replicated array.  If all
arrays input to the communication schedules meet this requirement, it
is guaranteed that those output do.  This is not an absolute
requirement on arrays passed to schedules, and the sections on
individual schedules discuss the effect of defaulting on this rule.

\subsection{Overlap restrictions} 

In general the library does not allow in-place updates.  No array
written by a communication schedule should overlap with an array read
by the schedule.  The sections on individual to schedules give the
specific restrictions.

\newpage

\section{class {\tt Remap}}

A {\em remap schedule} is a communication schedule for copying the
elements of one distributed array to another.  The source and
destination must have the same shape and same element-type, but no
relation between the mapping of the two arrays is required.
If the target array has a replicated mapping, the remap operation
implements a broadcast.

A remap schedule is described by a
collective object with local components of class {\tt Remap}.
The public interface of the {\tt Remap} class is
\small
\begin{verbatim}
  class DAD ;

  class Remap {
  public :
    Remap(const DAD* dst, const DAD* src, const int len) ;

    void execute(void* dstDat, void* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
Remap(const DAD* dst, const DAD* src, const int len)
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
destination array is described by the DAD {\tt *dst}.
{\tt len} specifies the size of each array element, in bytes.

\paragraph{Type restrictions:} The elements of the source and
destination arrays must have the same type.  This must be a
POD type (see section \ref{POD}) of size {\tt len} bytes.

\paragraph{Shape restrictions:}  The source and destination
array must have the same shape (see section \ref{shape}).

\paragraph{Accessibility restrictions:} The source 
and destination arrays must be accessible
(see section \ref{accessibility}).

\paragraph{Argument lifetime:} The {\tt dst} and {\tt src}
arguments are stored in the schedule as references.  The associated
objects must persist for the lifetime of the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(void* dstDat, void* srcDat)
\end{verbatim}
Arguments are the base addresses for local segments of the
destination and source arrays.  They should point to vectors of
the locally held elements.

\paragraph{Effect:} Copy the elements of the source array to the
corresponding elements of the destination array.

\paragraph{Replicated data:}  If the source array has replicated
mapping, the value for a particular element is taken from {\em one} of
its copies.  If the destination array has replicated mapping, identical
values are broadcast to {\em every} copy of the element.

\paragraph{Overlap restrictions:} In-place updates are not allowed.  The
pairs {\tt *dst}, {\tt dstDat} and {\tt *src}, {\tt srcDat} must define
non-overlapping arrays.

\newpage

\section{class {\tt Shift}\label{shift}}

A {\em shift schedule} is a communication schedule for shifting the
elements of a distributed array along one of its dimensions, placing
the result in another array.  The source and destination have the same
shape and same element-type, and they must have a certain alignment
relation.

A shift schedule is described by a collective object with local
components of class {\tt Shift}.  The public interface of the {\tt
Shift} class is
\small
\begin{verbatim}
  class DAD ;
  enum Mode {CYCL, EDGE, NONE} ;

  class Shift {
  public :
    Shift(const DAD* dst, const DAD* src, const int len,
          const int shift, const int dim, const Mode mode) ;

    void execute(void* dstDat, void* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
Shift(const DAD* dst, const DAD* src, const int len,
      const int shift, const int dim, const Mode mode)
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
destination array is described by the DAD {\tt *dst}.
{\tt len} specifies the size of each array element, in bytes.
The shift amount, which may be negative, is given by {\tt shift}.  The
{\tt dim} argument selects the array dimension in which the shift
occurs.  The flag {\tt mode} specifies the type of shift.
It takes one of the values {\tt CYCL}, {\tt EDGE} or {\tt NONE}.

\paragraph{Value restrictions:}
The value of {\tt dim} must be in the range $0, \ldots, R - 1$ where
$R$ is the rank of the source array.

\paragraph{Type restrictions:}
The elements of the source and destination arrays must have the same
type.  This must be a POD type (see section \ref{POD}) of size {\tt
len} bytes.

\paragraph{Shape restrictions:}
The source and destination array must have the same shape (see section
\ref{shape}).

\paragraph{Alignment restrictions:}
The source array {\em must be aligned with} the destination array
(see section \ref{alignment}).

\paragraph{Accessibility restrictions:}
The source and destination arrays
must be accessible (see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt dst} and {\tt src} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(void* dstDat, void* srcDat)
\end{verbatim}
Arguments are the base addresses for local segments of the
destination and source arrays.  They should point to vectors of
the locally held elements.

\paragraph{Effect:}
On exit, if {\tt mode} is {\tt CYCL}, the value of
\small
\begin{tabbing}
\verb$  dst [$$x_0, \ldots, x_{\mbox{\tt dim}}, \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is
\small
\begin{tabbing}
\verb$  src [$$x_0, \ldots,
x_{\mbox{\tt dim}} + \mbox{\tt shift} \ \bmod N,
\ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
where $N$ is the extent of dimension {\tt dim}.
If {\tt mode} is {\tt EDGE}, the exit value of the {\tt dst} element is
\small
\begin{tabbing}
\verb$  src [$$x_0, \ldots,
x_{\mbox{\tt dim}} + \mbox{\tt shift},
\ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
if $x_{\mbox{\tt dim}} + \mbox{\tt shift}$ is in the range $0, \ldots, N - 1$,
or {\em unchanged from the entry value}, if not.
If {\tt mode} is {\tt NONE} executing the schedule has no effect.

\paragraph{Replicated data:} 
If the arrays have replicated mapping, values for individual
copies of the destination are generally taken from the nearest copy of
the corresponding source array element.  The definition of ``nearest''
is implementation dependent.  This schedule does not implement a
broadcast---consistent replication of copies in the destination array
relies on consistency of copies of the source array.

\paragraph{Overlap restrictions:} In-place updates are not allowed.  The
pairs {\tt *dst}, {\tt dstDat} and {\tt *src}, {\tt srcDat} must define
non-overlapping arrays.

\newpage

\section{class {\tt Skew}}

A {\em skew schedule} is a communication schedule for performing a
skewed shift---a shift where the shift amount is itself an array---in a
particular dimension of a distributed array placing the result in
another array.  The source and destination must have the same shape and
same element-type, and they must have a certain alignment relation.

A skew schedule is described by a collective object with local
components of class {\tt Skew}.  The public interface of the {\tt Skew}
class is
\small
\begin{verbatim}
  class DAD ;
  enum Mode {CYCL, EDGE, NONE} ;

  class Skew {
  public :
    Skew(const DAD* dst, const DAD* src, const int len,
         const DAD* shf, int* shfDat, const int dim,
         const Mode mode) ;

    void execute(void* dstDat, void* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
Skew(const DAD* dst, const DAD* src, const int len,
     const DAD* shf, int* shfDat,
     const int dim, const Mode mode)
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
destination array is described by the DAD {\tt *dst}.
{\tt len} specifies the size of each array element, in bytes.  The
array of shift amounts (any of which may be negative), is described by the
DAD {\tt shf}.  The base address for the local segment of this array
is {\tt shfDat}.  The shift-amount array should have rank one less
than the source array.
The {\tt dim} argument selects the array dimension in which the shift
occurs.  The flag {\tt mode} specifies the type of shift.
It takes one of the values {\tt CYCL}, {\tt EDGE} or {\tt NONE}.

\paragraph{Value restrictions:}
The value of {\tt dim} must be in the range $0, \ldots, R - 1$ where
$R$ is the rank of the source array.

\paragraph{Type restrictions:}
The elements of the source and destination arrays must have the same
type.  This must be a POD type (see section \ref{POD}) of size {\tt
len} bytes.

\paragraph{Shape restrictions:}
The source and destination array must have the same shape (see section
\ref{shape}).  The shape of the shift array must be obtained from the
shape of the source array by deleting dimension {\tt dim}.


\paragraph{Alignment restrictions:}
The source array {\em must be aligned with} the destination array
The shift-amount array should be aligned with the destination array,
with replicated alignment over dimension {\tt dim} (see section
\ref{alignment}).

\paragraph{Accessibility restrictions:}
The source array, the shift-amount array, and
the destination array must be accessible (see section
\ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt dst} and {\tt src} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.  (There are no such requirements for the
shift-amount array).

\subsection{Method}

\begin{verbatim}
execute(void* dstDat, void* srcDat)
\end{verbatim}
Arguments are the base addresses for local segments of the
destination and source arrays.  They should point to vectors of
the locally held elements.

\paragraph{Effect:}
The description of the exit value of {\tt dst} is identical to
the description after execution of a {\tt Shift} schedule (see
section \ref{shift}), except that the constant {\tt shift} is replaced by
\small
\begin{tabbing}
\verb$  shf [$$x_0, \ldots, x_{\mbox{\tt dim} - 1},
x_{\mbox{\tt dim} + 1}, \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize

\paragraph{Replicated data:} 
If the arrays have replicated mapping, values for individual
copies of the destination are generally taken from the nearest copy of
the corresponding source array element.  The definition of ``nearest''
is implementation dependent.  This schedule does not implement a
broadcast---consistent replication of copies in the destination array
relies on consistency of copies of the source array.

\paragraph{Overlap restrictions:} In-place updates are not allowed.  The
pairs {\tt *dst}, {\tt dstDat} and {\tt *src}, {\tt srcDat} must define
non-overlapping arrays.


\newpage

\section{class {\tt MultiShift}}

A {\em multishift schedule} is a communication schedule for shifting
the elements of a distributed array along some or all of its dimensions
concurrently, placing the result in another array.  The source and
destination must have the same shape and same element-type, and they
must have a certain alignment relation.

A multishift schedule is described by a collective object with local
components of class {\tt MultiShift}.  The public interface of the {\tt
MultiShift} class is
\small
\begin{verbatim}
  class DAD ;
  enum Mode {CYCL, EDGE, NONE} ;

  class MultiShift {
  public :
    MultiShift(const DAD* dst, const DAD* src, const int len,
               int shift [], Mode mode []) ;

    void execute(void* dstDat, void* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
MultiShift(const DAD* dst, const DAD* src, const int len,
           int shift [], Mode mode [])
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
destination array is described by the DAD {\tt *dst}.
{\tt len} specifies the size of each array element, in bytes.
Vectors {\tt shift} and {\tt mode} have extent $R$---the rank of
the source array.
The shift amount, which may be negative, in
dimension $r$ is given by {\tt shift [}$r${\tt ]}.
The flag {\tt mode [}$r${\tt ]} specifies the type of shift:
It takes one of the values {\tt CYCL}, {\tt EDGE} or {\tt NONE}.

\paragraph{Value restrictions:}
The value of {\tt dim} must be in the range $0, \ldots, R - 1$ where
$R$ is the rank of the source array.

\paragraph{Type restrictions:}
The elements of the source and destination arrays must have the same
type.  This must be a POD type (see section \ref{POD}) of size {\tt
len} bytes.

\paragraph{Shape restrictions:}
The source and destination array must have the same shape (see section
\ref{shape}).

\paragraph{Alignment restrictions:}
The source array {\em must be aligned with} the destination array
(see section \ref{alignment}).

\paragraph{Accessibility restrictions:}
The source and destination arrays
must be accessible (see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt dst} and {\tt src} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(void* dstDat, void* srcDat)
\end{verbatim}
Arguments are the base addresses for local segments of the
destination and source arrays.  They should point to vectors of
the locally held elements.

\paragraph{Effect:}
Equivalent in effect (not in implementation) to successive
execution of $R$ schedules of the form
\small
\begin{tabbing}
\verb$  Shift(dst, src, len,$ $r$\verb$, shift [$$r$\verb$], mode [$$r$\verb$])$
\end{tabbing}
\normalsize
for $r$ in the range $0, \ldots, R - 1$ (see section \ref{shift}).

\paragraph{Replicated data:} 
If the arrays have replicated mapping, values for individual
copies of the destination are generally taken from the nearest copy of
the corresponding source array element.  The definition of ``nearest''
is implementation dependent.  This schedule does not implement a
broadcast---consistent replication of copies in the destination array
relies on consistency of copies of the source array.

\paragraph{Overlap restrictions:} In-place updates are not allowed.  The
pairs {\tt *dst}, {\tt dstDat} and {\tt *src}, {\tt srcDat} must define
non-overlapping arrays.

\newpage

\section{class {\tt WriteHalo}}

A {\em write-halo schedule} is a communication schedule for filling
{\em overlap regions} or {\em ghost cells} surrounding the
local segment of a distributed array.
A write-halo schedule is described by a
collective object with local components of class {\tt WriteHalo}.
The public interface of the {\tt WriteHalo} class is
\small
\begin{verbatim}
  class DAD ;
  enum Mode {CYCL, EDGE, NONE} ;

  class WriteHalo {
  public :
    WriteHalo(const DAD* src, const int len,
              const int wlo [], const int whi [],
              const Mode [] mode) ;

    void execute(void* srcDat) ;
  private :
    ...
  }
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
WriteHalo(const DAD* src, const int len,
          const int wlo [], const int whi [],
          const Mode [] mode)
\end{verbatim}
The array is described by the DAD {\tt *src}.
{\tt len} specifies the size of each array element, in bytes.
The vectors {\tt wlo}, {\tt whi} and {\tt mode} have extent $R$---the rank of
the array.

Vectors {\tt wlo} and {\tt wlo} define the halo of ghost
cells updated by the schedule.
The upper and lower widths in dimension $r$ are given
by {\tt wlo [}$r${\tt ]} and {\tt whi [}$r${\tt ]}.  These values
are non-negative, and can only be non-zero if array {\tt src}
actually has suitable ghost extensions in the dimension concerned.
More specifically, if the array {\tt src} was created using a range with
ghost extensions $\mbox{\tt wlo}_{\mbox{act}}$,
$\mbox{\tt whi}_{\mbox{act}}$---eg, a range created by by a constructor
call such as
{\tt BlockRange(N, d,}$\mbox{\tt wlo}_{\mbox{act}}${\tt
,}$\mbox{\tt whi}_{\mbox{act}}{\tt )}$---as its $r$th dimension,
it is required that
\begin{eqnarray*}
\mbox{\tt whi [}r\mbox{\tt]} \le \mbox{\tt whi}_{\mbox{act}} \\
\mbox{\tt wlo [}r\mbox{\tt]} \le \mbox{\tt wlo}_{\mbox{act}}
\end{eqnarray*}
The situation is complicated if the array is a section, or
some other array with non-trivial alignment stride.  In practise it is
unusual to construct {\tt WriteHalo} schedules for such
arrays, but for completeness we describe the constraints that
apply in that case.  First, by definition, the ghost extensions of
a subrange are those of its template range.  Now,
suppose the {\em array of which {\tt src} is a section} has ghost
extensions $\mbox{\tt wlo}_{\mbox{act}}$, $\mbox{\tt whi}_{\mbox{act}}$.
If the alignment stride of {\tt src.rng(}$r${\tt )}
is $s$, the required constraints are
\begin{eqnarray*}
s \times \mbox{\tt whi [}r\mbox{\tt]} \le \mbox{\tt whi}_{\mbox{act}} \\
s \times \mbox{\tt wlo [}r\mbox{\tt]} \le \mbox{\tt wlo}_{\mbox{act}}
\end{eqnarray*}
The point to note is that the widths defined in the {\tt
WriteHalo} construtor are expressed in terms of the global subscript of
the range of the array, whereas the ghost extensions of the
array are measured in units of {\em template range} subscripts.

The vector {\tt mode} defines how ghost cells are updated in each
dimension---including how the cells at the extremes of the array
are updated.  Its elements take value {\tt CYCL}, {\tt EDGE}
or {\tt NONE}.

Note that (as usual for ordinary data arguments of collective
constructors) the vectors {\tt wlo}, {\tt whi} and {\tt mode} must have
identical values in all members of the active process group.

\paragraph{Type restrictions:}
The elements of array must be a POD type (see section \ref{POD}) of
size {\tt len} bytes.

\paragraph{Accessibility restrictions:}
The array must be accessible (see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt src} argument is stored in the schedule as
a reference.  The associated object must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(void* srcDat)
\end{verbatim}
Argument is the base addresses for the local segment of the
array.  It should point to a vector of the locally held elements.

\paragraph{Effect:}
\begin{figure}[btp]
\centerline{\psfig{figure=WriteHalo.eps,height=3in}}
\caption{Illustration of the effect of executing a write-halo
schedule.\label{writeHaloFig}}
\end{figure}

We distinguish between the locally held {\em physical segment} of an array
and the surrounding {\em ghost region}, which is used to cache local copies
of remote elements.  The effect of this operation
is to overwrite a portion of the ghost region---a halo of extent
defined by the {\tt wlo}, {\tt whi} vectors of the constructor---with
values from processes holding the corresponding elements in their physical
segments.  The operation is visualized in figure \ref{writeHaloFig}.
Note that, so long as it fits in the ghost area {\em allocated} for the
array, there is no restriction on the width of the halo region.  In
particular, the width of the halo region may be larger than the width
of the neighbouring physical segment, in which case values will be
fetched from next-nearest neighbours, and so on.

If the value of the {\tt mode} element for a dimension is {\tt EDGE},
ghost cells past the extreme ends of the array range are not updated
by the the write-halo operation.  If the value is {\tt CYCL}, those
cells are updated assuming cyclic wraparound\footnote{This option
may lead to odd effects if the source array is actually a section
with a triplet subscript.  The updated cells, past the ends of the
section, may actually reside in the physical segment of the parent
array.}.
If the value is {\tt NONE}, there is no updating at all of the ghost
cells associated with this dimension.

\paragraph{Replicated data:} 
If the array has replicated mapping, values for individual
copies of the ghost cell are generally taken from the nearest copy of
the corresponding physical array element.  The definition of ``nearest''
is implementation dependent.  This schedule does not implement a
broadcast---consistent replication of copies in the final state
of the array relies on consistency of copies in the initial
state of the array.

\newpage

\section{class {\tt Gather}\label{gather}}

A {\em gather schedule} is a communication schedule for collecting
an arbitrary set of values from
one distributed array (the source array) into the elements of
another (the destination array).  The selected set of elements is defined by a
vector of {\em subscript arrays}, with an optional {\em mask array}.
A gather schedule is described by a
collective object with local components of class {\tt Gather}.
The public interface of the {\tt Gather} class is
\small
\begin{verbatim}
  class DAD ;

  class Gather {
  public :
    Gather(const DAD* dst, const DAD* src, const int len,
           const DAD* subs [], const int* subsDat [],
           const DAD* msk, const int* mskDat) ;

    void execute(void* dstDat, void* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
Gather(const DAD* dst, const DAD* src, const int len,
       const DAD* subs [], const int* subsDat [],
       const DAD* msk, const int* mskDat)
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
destination array is described by the DAD {\tt *dst}.
{\tt len} specifies the size of each array element, in bytes.
The vectors {\tt subs} and {\tt subsDat} have extent $R$---the rank of
the {\em source} array.  The subscript arrays are defined by the pairs {\tt
*subs [}$r${\tt ]}, {\tt subsDat [}$r${\tt ]}.  If {\tt msk} is
non-null, the pair {\tt *msk}, {\tt mskDat} defines a mask
array\footnote{The communication {\em pattern} encoded in the
constructed schedule depends on the detailed values of the subscript
and mask arrays, whearas it does not depend the actual values in the
source and destination arrays.  This is why the element pointers for
the subscripts and mask are passed to the constructor, whereas those
for source and destination are not.  Note that the constructed schedule
holds an internally processed version of the subscript and mask
information---it does not retain any pointers the input element
arrays.}.

\paragraph{Value restrictions:}
All elements of the $r$th subscript array must be in the range
$0, \ldots, N - 1$ where $N$ is the extent of the source array
in its $r$th dimension.

\paragraph{Type restrictions:}
The elements of the source and destination arrays must have the same
type.  This must be a POD type (see section \ref{POD}) of size {\tt
len} bytes.

\paragraph{Shape restrictions:}
The destination array, all subscript arrays, and the mask array, if
defined,  must have the same shape (see section \ref{shape}).

\paragraph{Alignment restrictions:}
All subscript arrays and the mask array, if defined, {\em must be
aligned with} the destination array (see section
\ref{alignment}).

\paragraph{Accessibility restrictions:}
The source and subscript arrays, the mask array, if defined,
and the destination array must all be accessible (see
section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt dst} and {\tt src} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.  (There are no such requirements for the
subscript and mask arrays).

\subsection{Methods}

\begin{verbatim}
execute(void* dstDat, void* srcDat)
\end{verbatim}
Arguments are the base addresses for local segments of the
destination and source arrays.  They should point to vectors of
the locally held elements.

\paragraph{Effect:}
On exit, the value of
\small
\begin{tabbing}
\verb$  dst [$$x_0, \ldots, x_{S - 1}${\tt ]}
\end{tabbing}
\normalsize
is
\small
\begin{tabbing}
\verb$  src [$$\mbox{\tt subs}_0$\verb$ [$$x_0, \ldots, x_{S - 1}$\verb$], ...,$
              $\mbox{\tt subs}_{R - 1}$\verb$ [$$x_0, \ldots, x_{S - 1}${\tt ]]}
\end{tabbing}
\normalsize
{\em unless} the mask array is defined and
\small
\begin{tabbing}
\verb$  msk [$$x_0, \ldots, x_{S - 1}${\tt ]}
\end{tabbing}
\normalsize
was zero, in which case the exit value of the {\tt dst} element is
unchanged from the entry value.  Here $\mbox{\tt subs}_r$ denotest the
$r$th subscript array and $S$ is the rank of the destination
array.

\paragraph{Replicated data:}  If the source array has replicated
mapping, the value for a particular element is taken from {\em one} of
its copies.  If the destination array has replicated mapping, identical
values are broadcast to {\em every} copy of each element.

\paragraph{Overlap restrictions:} In-place updates are not allowed.  The
pairs {\tt *dst}, {\tt dstDat} and {\tt *src}, {\tt srcDat} must define
non-overlapping arrays.

\newpage

\section{class {\tt Scatter}\label{scatter}}

A {\em scatter schedule} is a communication schedule for scattering
values from
one distributed array (the source array) into elements of another
another (the destination array) in an arbitrary way.
The target set of elements is defined by a
vector of {\em subscript arrays}, with an optional {\em mask array}.
A scatter schedule is described by a
collective object with local components of class {\tt Scatter}.
The public interface of the {\tt Scatter} class is
\small
\begin{verbatim}
  class DAD ;

  class Scatter {
  public :
    Scatter(const DAD* src, const DAD* dst, const int len,
            const DAD* subs [], const int* subsDat [],
            const DAD* msk, const int* mskDat) ;

    void execute(void* srcDat, void* dstDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
Scatter(const DAD* src, const DAD* dst, const int len,
        const DAD* subs [], const int* subsDat [],
        const DAD* msk, const int* mskDat)
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
destination array is described by the DAD {\tt *dst}.
{\tt len} specifies the size of each array element, in bytes.
The vectors {\tt subs} and {\tt subsDat} have extent $R$---the rank of
the {\em destination} array.  The subscript arrays are defined by the pairs {\tt
*subs [}$r${\tt ]}, {\tt subsDat [}$r${\tt ]}.  If {\tt msk} is
non-null, the pair {\tt *msk}, {\tt mskDat} defines a mask array.

Note well that the source and destination arguments of {\tt Scatter}
members are reversed relative to the conventions for other
communication schedules.  This is to emphasize the symmetry with {\tt
Gather}.

\paragraph{Value restrictions:}
All elements of the $r$th subscript array must be in the range
$0, \ldots, N - 1$ where $N$ is the extent of the destination array
in its $r$th dimension.

\paragraph{Type restrictions:}
The elements of the source and destination arrays must have the same
type.  This must be a POD type (see section \ref{POD}) of size {\tt
len} bytes.

\paragraph{Shape restrictions:}
The source array, all subscript arrays, and the mask array, if
defined,  must have the same shape (see section \ref{shape}).

\paragraph{Alignment restrictions:}
All subscript arrays and the mask array, if defined, {\em must be
aligned with} the source array (see section
\ref{alignment}).

\paragraph{Accessibility restrictions:}
The source and subscript arrays, the mask array, if defined, and
the destination array must be all accessible (see
section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt dst} and {\tt src} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.  (There are no such requirements for the
subscript and mask arrays).


\subsection{Methods}

\begin{verbatim}
execute(void* srcDat, void* dstDat)
\end{verbatim}
Arguments are the base addresses for local segments of the
source and destination arrays.  They should point to vectors of
the locally held elements.

\paragraph{Effect:}
If {\tt msk} was non-null, the effect is like executing
the conditional assignment
\small
\begin{tabbing}
\verb$  if(msk [$$x_0, \ldots, x_{S - 1}${\tt ])} \\
\verb$    dst [$$\mbox{\tt subs}_0$\verb$ [$$x_0, \ldots, x_{S - 1}$\verb$], ...,$
              $\mbox{\tt subs}_{R - 1}$\verb$ [$$x_0, \ldots, x_{S - 1}$\verb$]] =$ \\
\verb$                         src [$$x_0, \ldots, x_{S - 1}${\tt ]}
\end{tabbing}
\normalsize
for every tuple $(x_0, \ldots, x_{S - 1})$ of global subscripts
of the source array.  These assignments are executed in an undefined order.
If {\tt msk} is a null pointer, the assignment is unconditional.
Here $\mbox{\tt subs}_r$ denotest the $r$th subscript array.

\paragraph{Replicated data:}  If the source array has replicated
mapping, the value for a particular element is taken from {\em one} of
its copies.  If the destination array has replicated mapping, identical
values are broadcast to {\em every} copy of each element.

\paragraph{Overlap restrictions:} In-place updates are not allowed.  The
pairs {\tt *dst}, {\tt dstDat} and {\tt *src}, {\tt srcDat} must define
non-overlapping arrays.

%{\em [More consistent with interface for reduction schedules if
%split into {\tt Gather} and {\tt GatherMsk}.]}

\newpage

\section{class {\tt VecGather}}

A {\em vector-subscript gather schedule} is a communication schedule
for collecting a set of values from one distributed array (the source
array) into the elements of another array of the same rank (the
destination array).  The selected set of elements is defined by a
vector of rank-1 arrays---the {\em subscript arrays}.
This schedule
can be regarded as an optimized special case of the general gather
schedule of section \ref{gather}.  It is functionally equivalent
to certain Fortran-90 array assignments involving vector subscripts.
A vector-subscript gather schedule is described by a collective object
with local components of class {\tt VecGather}.
The public interface
of the {\tt VecGather} class is
\small
\begin{verbatim}
  class DAD ;

  class VecGather {
  public :
    VecGather(const DAD* dst, const DAD* src, const int len,
              const DAD* subs [], const int* subsDat []) ;

    void execute(void* dstDat, void* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
VecGather(const DAD* dst, const DAD* src, const int len,
          const DAD* subs [], const int* subsDat [])
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
destination array is described by the DAD {\tt *dst}.
{\tt len} specifies the size of each array element, in bytes.
The source and destination arrays have the same rank, $R$.
The vectors {\tt subs} and {\tt subsDat} have extent $R$.
If {\tt subs [}$r${\tt ]} is non-null,
the pair {\tt *subs [}$r${\tt ]}, {\tt subsDat [}$r${\tt ]} defines
the $r$th subscript array.

\paragraph{Value restrictions:}
If the $r$th subscript array is defined, all its elements must be in
the range $0, \ldots, N - 1$ where $N$ is the extent of the source
array in its $r$th dimension.

\paragraph{Type restrictions:}
The elements of the source and destination arrays must have the same
type.  This must be a POD type (see section \ref{POD}) of size {\tt
len} bytes.

\paragraph{Shape restrictions:}
If the $r$th subscript array is defined it must be rank-1 and its
extent must be $M$, where
$M$ is the extent of the destination array in its $r$th dimension.

If the $r$th subscript array is {\em undefined} (because {\tt subs
[}$r${\tt ]} is null) the destination and source arrays must have the
same extent in their $r$th dimensions.

\paragraph{Alignment restrictions:}
If defined, the $r$th subscript array must be aligned to the
destination array, {\em with replicated alignment in all dimensions
except $r$} (see section \ref{alignment}).

\paragraph{Accessibility restrictions:}
The source and subscript arrays and
the destination array must all be accessible (see
section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt dst} and {\tt src} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.  (There are no such requirements for the
subscript arrays.)
\subsection{Methods}

\begin{verbatim}
execute(void* dstDat, void* srcDat)
\end{verbatim}
Arguments are the base addresses for local segments of the
destination and source arrays.  They should point to vectors of
the locally held elements.

\paragraph{Effect:}
On exit, the value of
\small
\begin{tabbing}
\verb$  dst [$$x_0, \ldots, x_{S - 1}${\tt ]}
\end{tabbing}
\normalsize
is
\small
\begin{tabbing}
\verb$  src [$$\mbox{\tt subs}_0$\verb$ [$$x_0$\verb$], ...,$
              $\mbox{\tt subs}_{R - 1}$\verb$ [$$x_{R - 1}${\tt ]]}
\end{tabbing}
\normalsize
Here $\mbox{\tt subs}_r$ denotest the $r$th subscript array.
If {\tt subs [}$r${\tt ]} is null, the value of the expression
$\mbox{\tt subs}_r$\verb$ [$$x_r$\verb$]$ in this formula
is defined to be $x_r$ (hence if all subscripts are undefined,
this operation is equivalent to a {\tt Remap} operation).

\paragraph{Replicated data:}  If the source array has replicated
mapping, the value for a particular element is taken from {\em one} of
its copies.  If the destination array has replicated mapping, identical
values are broadcast to {\em every} copy of each element.

\paragraph{Overlap restrictions:} In-place updates are not allowed.  The
pairs {\tt *dst}, {\tt dstDat} and {\tt *src}, {\tt srcDat} must define
non-overlapping arrays.

\newpage

\section{class {\tt VecGatherMsk}}

A {\em masked vector-subscript gather schedule} is a communication schedule
for collecting a set of values from one distributed array (the source
array) into the elements of another array of the same rank (the
destination array).  The selected set of elements is defined by a
vector of rank-1 arrays---the {\em subscript arrays}---and controlled
by a mask array.  This schedule
can be regarded as an optimized special case of the general gather
schedule of section \ref{gather}.  It is functionally equivalent
to certain Fortran-90 array assignments involving vector subscripts and
executed inside {\tt WHERE} statements.
A masked vector-subscript gather schedule is described by a collective object
with local components of class {\tt VecGatherMsk}.
The public interface of the {\tt VecGatherMsk} class is
\small
\begin{verbatim}
  class DAD ;

  class VecGatherMsk {
  public :
    VecGatherMsk(const DAD* dst, const DAD* src, const int len,
                 const DAD* subs [], const int* subsDat [],
                 const DAD* msk, const int* mskDat) ;

    void execute(void* dstDat, void* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
VecGatherMsk(const DAD* dst, const DAD* src, const int len,
             const DAD* subs [], const int* subsDat [],
             const DAD* msk, const int* mskDat)
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
destination array is described by the DAD {\tt *dst}.
{\tt len} specifies the size of each array element, in bytes.
The source and destination arrays have the same rank, $R$.
The vectors {\tt subs} and {\tt subsDat} have extent $R$.
If {\tt subs [}$r${\tt ]} is non-null,
the pair {\tt *subs [}$r${\tt ]}, {\tt subsDat [}$r${\tt ]} defines
the $r$th subscript array.
The pair {\tt *msk}, {\tt mskDat} defines a mask array.

\paragraph{Value restrictions:}
If the $r$th subscript array is defined, all its elements must be in
the range $0, \ldots, N - 1$ where $N$ is the extent of the source
array in its $r$th dimension, {\em unless} the subscript element is
unused because of masking.  (In other words, this restriction need not apply
for elements
\small
\begin{tabbing}
\verb$  $$\mbox{\tt subs}_r$\verb$ [$$x_r$\verb$]$
\end{tabbing}
\normalsize
such that
\small
\begin{tabbing}
\verb$  msk [$$x_0, \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is zero for all allowed values of $x_0, \ldots, x_{r-1}, x_{r+1},
\ldots, x_{R-1}$.)

\paragraph{Type restrictions:}
The elements of the source and destination arrays must have the same
type.  This must be a POD type (see section \ref{POD}) of size {\tt
len} bytes.

\paragraph{Shape restrictions:}
If the $r$th subscript array is defined it must be rank-1 and its
extent must be $M$, where
$M$ is the extent of the destination array in its $r$th dimension.

If the $r$th subscript array is {\em undefined} (because {\tt subs
[}$r${\tt ]} is null) the destination and source arrays must have the
same extent in their $r$th dimensions.

The mask array must have the same shape as the destination array (see
section \ref{shape}).

\paragraph{Alignment restrictions:}
If defined, the $r$th subscript array must be aligned to the
destination array, {\em with replicated alignment in all dimensions
except $r$}.
The mask array {\em must be aligned with} the destination array
(see section \ref{alignment}).

\paragraph{Accessibility restrictions:}
The source, subscript, mask array, and the
destination array must all be accessible (see section
\ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt dst} and {\tt src} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.  (There are no such requirements for the
subscript and mask arrays).
\subsection{Methods}

\begin{verbatim}
execute(void* dstDat, void* srcDat)
\end{verbatim}
Arguments are the base addresses for local segments of the
destination and source arrays.  They should point to vectors of
the locally held elements.

\paragraph{Effect:}
On exit, the value of
\small
\begin{tabbing}
\verb$  dst [$$x_0, \ldots, x_{S - 1}${\tt ]}
\end{tabbing}
\normalsize
is
\small
\begin{tabbing}
\verb$  src [$$\mbox{\tt subs}_0$\verb$ [$$x_0$\verb$], ...,$
              $\mbox{\tt subs}_{R - 1}$\verb$ [$$x_{R - 1}${\tt ]]}
\end{tabbing}
\normalsize
{\em unless}
\small
\begin{tabbing}
\verb$  msk [$$x_0, \ldots, x_{S - 1}${\tt ]}
\end{tabbing}
\normalsize
was zero, in which case the exit value of the {\tt dst} element is
unchanged from the entry value.
Here $\mbox{\tt subs}_r$ denotest the $r$th subscript array.
If {\tt subs [}$r${\tt ]} is null, the value of the expression
$\mbox{\tt subs}_r$\verb$ [$$x_r$\verb$]$ in this formula
is defined to be $x_r$ (hence if all subscripts are undefined,
this operation is equivalent to a {\tt Remap} operation).

\paragraph{Replicated data:}  If the source array has replicated
mapping, the value for a particular element is taken from {\em one} of
its copies.  If the destination array has replicated mapping, identical
values are broadcast to {\em every} copy of each element.

\paragraph{Overlap restrictions:} In-place updates are not allowed.  The
pairs {\tt *dst}, {\tt dstDat} and {\tt *src}, {\tt srcDat} must define
non-overlapping arrays.

\newpage

\section{class {\tt VecScatter}}

A {\em vector-subscript scatter schedule} is a communication schedule
for scattering values from
one distributed array (the source array) into elements of another
(the destination array).
The target set of elements are defined by a
vector of rank-1 arrays---the {\em subscript arrays}.
This schedule
can be regarded as an optimized special case of the general scatter
schedule of section \ref{scatter}.  It is functionally similar
to certain Fortran-90 array assignments involving vector
subscripts---minus the constraints
that enforce determinism in Fortran.
A vector-subscript scatter schedule is described by a
collective object with local components of class {\tt VecScatter}.
The public interface of the {\tt VecScatter} class is
\small
\begin{verbatim}
  class DAD ;

  class VecScatter {
  public :
    VecScatter(const DAD* src, const DAD* dst, const int len,
               const DAD* subs [], const int* subsDat []) ;

    void execute(void* srcDat, void* dstDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
VecScatter(const DAD* src, const DAD* dst, const int len,
           const DAD* subs [], const int* subsDat [])
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
destination array is described by the DAD {\tt *dst}.
{\tt len} specifies the size of each array element, in bytes.
The source and destination arrays have the same rank, $R$.
The vectors {\tt subs} and {\tt subsDat} have extent $R$.
If {\tt subs [}$r${\tt ]} is non-null,
the pair {\tt *subs [}$r${\tt ]}, {\tt subsDat [}$r${\tt ]} defines
the $r$th subscript array.

Note well that the source and destination arguments of {\tt VecScatter}
members are reversed relative to the conventions for other
communication schedules.  This is to emphasize the symmetry with {\tt
VecGather}.

\paragraph{Value restrictions:}
If the $r$th subscript array is defined, all its elements must be in
the range $0, \ldots, N - 1$ where $N$ is the extent of the destination
array in its $r$th dimension.

\paragraph{Type restrictions:}
The elements of the source and destination arrays must have the same
type.  This must be a POD type (see section \ref{POD}) of size {\tt
len} bytes.

\paragraph{Shape restrictions:}
If the $r$th subscript array is defined it must be rank-1 and its
extent must be $M$, where
$M$ is the extent of the source array in its $r$th dimension.

If the $r$th subscript array is {\em undefined} (because {\tt subs
[}$r${\tt ]} is null) the destination and source arrays must have the
same extent in their $r$th dimensions.

\paragraph{Alignment restrictions:}
If defined, the $r$th subscript array must be aligned to the
source array, {\em with replicated alignment in all dimensions
except $r$} (see section \ref{alignment}).

\paragraph{Accessibility restrictions:}
The source and subscript arrays and the
the destination array must all be accessible (see
section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt dst} and {\tt src} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.  (There are no such requirements for the
subscript arrays).

\subsection{Method}

\begin{verbatim}
execute(void* srcDat, void* dstDat)
\end{verbatim}
Arguments are the base addresses for local segments of the
source and destination arrays.  They should point to vectors of
the locally held elements.

\paragraph{Effect:}
The effect is like executing the assignment
\small
\begin{tabbing}
\verb$  dst [$$\mbox{\tt subs}_0$\verb$ [$$x_0$\verb$], ...,$
              $\mbox{\tt subs}_{R - 1}$
\verb$[$$x_{R - 1}$\verb$]] = src [$$x_0, \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
for every tuple, $(x_0, \ldots, x_{R - 1})$, of global subscripts
of the source array.  These assignments are executed in an undefined order.
Here $\mbox{\tt subs}_r$ denotest the $r$th subscript array.
If {\tt subs [}$r${\tt ]} is null, the value of the expression
$\mbox{\tt subs}_r$\verb$ [$$x_r$\verb$]$ in the left-hand-side of the
assignment is defined to be $x_r$ (hence if all subscripts are undefined,
this operation is equivalent to a {\tt Remap} operation).

\paragraph{Replicated data:}  If the source array has replicated
mapping, the value for a particular element is taken from {\em one} of
its copies.  If the destination array has replicated mapping, identical
values are broadcast to {\em every} copy of each element.

\paragraph{Overlap restrictions:} In-place updates are not allowed.  The
pairs {\tt *dst}, {\tt dstDat} and {\tt *src}, {\tt srcDat} must define
non-overlapping arrays.

\newpage

\section{class {\tt VecScatterMsk}}

A {\em masked vector-subscript scatter schedule} is a communication schedule
for scattering values from
one distributed array (the source array) into elements of another
(the destination array).
The target set of elements are defined by a
vector of rank-1 arrays---the {\em subscript arrays}.
This schedule
can be regarded as an optimized special case of the general scatter
schedule of section \ref{scatter}.  It is functionally similar
to certain Fortran-90 array assignments involving vector subscripts
and executed inside {\tt WHERE} statements---minus the constraints
that enforce determinism in Fortran.
A vector-subscript scatter schedule is described by a
collective object with local components of class {\tt VecScatterMsk}.
The public interface of the {\tt VecScatterMsk} class is
\small
\begin{verbatim}
  class DAD ;

  class VecScatterMsk {
  public :
    VecScatterMsk(const DAD* src, const DAD* dst, const int len,
                  const DAD* subs [], const int* subsDat [],
                  const DAD* msk, const int* mskDat) ;

    void execute(void* srcDat, void* dstDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
VecScatterMsk(const DAD* src, const DAD* dst, const int len,
              const DAD* subs [], const int* subsDat [],
              const DAD* msk, const int* mskDat)
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
destination array is described by the DAD {\tt *dst}.
{\tt len} specifies the size of each array element, in bytes.
The source and destination arrays have the same rank, $R$.
The vectors {\tt subs} and {\tt subsDat} have extent $R$.
If {\tt subs [}$r${\tt ]} is non-null,
the pair {\tt *subs [}$r${\tt ]}, {\tt subsDat [}$r${\tt ]} defines
the $r$th subscript array.
The pair {\tt *msk}, {\tt mskDat} defines a mask array.

{\em Note:} the source and destination arguments of {\tt VecScatterMsk}
members are reversed relative to the conventions for most
communication schedules.  This is to emphasize the symmetry with {\tt
VecGatherMsk}.

\paragraph{Value restrictions:}
If the $r$th subscript array is defined, all its elements must be in
the range $0, \ldots, N - 1$ where $N$ is the extent of the destination
array in its $r$th dimension, {\em unless} the subscript element is
unused because of masking.  (In other words, this restriction need not apply
for elements
\small
\begin{tabbing}
\verb$  $$\mbox{\tt subs}_r$\verb$ [$$x_r$\verb$]$
\end{tabbing}
\normalsize
such that
\small
\begin{tabbing}
\verb$  msk [$$x_0, \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is zero for all allowed values of $x_0, \ldots, x_{r-1}, x_{r+1},
\ldots, x_{R-1}$.)

\paragraph{Type restrictions:}
The elements of the source and destination arrays must have the same
type.  This must be a POD type (see section \ref{POD}) of size {\tt
len} bytes.

\paragraph{Shape restrictions:}
If the $r$th subscript array is defined it must be rank-1 and its
extent must be $M$, where $M$ is the extent of the source array in its
$r$th dimension.

If the $r$th subscript array is {\em undefined} (because {\tt subs
[}$r${\tt ]} is null) the destination and source arrays must have the
same extent in their $r$th dimensions.

The mask array must have the same shape as the source array (see
section \ref{shape}).

\paragraph{Alignment restrictions:}
If defined, the $r$th subscript array must be aligned to the
source array, {\em with replicated alignment in all dimensions
except $r$}.
The mask array {\em must be aligned with} the source array
(see section \ref{alignment}).

\paragraph{Accessibility restrictions:}
The source, subscript, mask arrays, and
destination array must all be accessible (see
section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt dst} and {\tt src} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.  (There are no such requirements for the
subscript and mask arrays).

\subsection{Method}

\begin{verbatim}
execute(void* srcDat, void* dstDat)
\end{verbatim}
Arguments are the base addresses for local segments of the
source and destination arrays.  They should point to vectors of
the locally held elements.

\paragraph{Effect:}
The effect is like executing the conditional assignment
\small
\begin{tabbing}
\verb$  if(msk [$$x_0, \ldots, x_{S - 1}${\tt ])} \\
\verb$    dst [$$\mbox{\tt subs}_0$\verb$ [$$x_0$\verb$], ...,$
              $\mbox{\tt subs}_{R - 1}$
\verb$[$$x_{R - 1}$\verb$]] = src [$$x_0, \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
for every tuple, $(x_0, \ldots, x_{R - 1})$, of global subscripts
of the source array.  These assignments are executed in an undefined order.
Here $\mbox{\tt subs}_r$ denotest the $r$th subscript array.
If {\tt subs [}$r${\tt ]} is null, the value of the expression
$\mbox{\tt subs}_r$\verb$ [$$x_r$\verb$]$ in the left-hand-side of the
assignment is defined to be $x_r$.

\paragraph{Replicated data:}  If the source array has replicated
mapping, the value for a particular element is taken from {\em one} of
its copies.  If the destination array has replicated mapping, identical
values are broadcast to {\em every} copy of each element.

\paragraph{Overlap restrictions:} In-place updates are not allowed.  The
pairs {\tt *dst}, {\tt dstDat} and {\tt *src}, {\tt srcDat} must define
non-overlapping arrays.

\newpage

\section{class {\tt ScatterComb}}

{\em [There are are existing schedules for combining scatter,
but their interface is under revision.]}

\section{class {\tt Reshape}}

{\em [There are are existing schedules for this F90 intrinsic,
but their interface is under revision.]}

\newpage

\section{class {\tt Sum}}

A {\em sum schedule} is a communication schedule for adding together
all elements of a distributed array (the source array).
A sum schedule is described by a
collective object with local components of class {\tt Sum}.
The public interface of the {\tt Sum} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class Sum {
  public :
    Sum(const DAD* src) ;

    void execute(T* res, T* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
Sum(const DAD* src)
\end{verbatim}
The source array is described by the DAD {\tt *src}.  It will have
elements of type {\tt T}.

\paragraph{Type restrictions:}
{\tt T} should be a POD type (see section \ref{POD}).  A conventional
binary addition operator, {\tt +}, must be defined for objects of type
{\tt T}, the assignment operator {\tt +=} must operate in
a compatible way, and the symbol 0 must be convertible to type {\tt T},
yielding a zero of the addition operation.

All standard arithmetic types of C++ satisfy these requirements
for {\tt T}.

\paragraph{Accessibility restrictions:}
The source array must be accessible (see section
\ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt src} argument is stored in the schedule as a
reference.  The associated object must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* res, T* srcDat)
\end{verbatim}
The arguments are the address to which the result should be written and
the base address of the local segment of the source array.  The latter
should point to a vector of the locally held elements.

\paragraph{Effect:}
Executing the schedule adds together all elements of the array in an
unspecified order.  The result value, written to {\tt *res}, is
broadcast to all members of the active process group.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values for
particular elements are generally taken from the nearest copy.  The
definition of ``nearest'' is implementation dependent.

\newpage

\section{class {\tt SumMsk}}

A {\em masked sum schedule} is a communication schedule for adding together
all elements of a distributed array (the source array) under the
control of a mask array.
A masked sum schedule is described by a
collective object with local components of class {\tt SumMsk}.
The public interface of the {\tt SumMsk} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class SumMsk {
  public :
    SumMsk(const DAD* src, const DAD* msk) ;

    void execute(T* res, T* srcDat, int* mskDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
SumMsk(const DAD* src, const DAD* msk)
\end{verbatim}
The source array is described by the DAD {\tt *src}.  It will have
elements of type {\tt T}.
The mask array is described by the DAD {\tt *msk}.

\paragraph{Type restrictions:}
{\tt T} should be a POD type (see section \ref{POD}).  A conventional
binary addition operator, {\tt +}, must be defined for objects of type
{\tt T}, the assignment operator {\tt +=} must operate in
a compatible way, and the symbol 0 must be convertible to type {\tt T},
yielding a zero of the addition operation.

All standard arithmetic types of C++ satisfy these requirements
for {\tt T}.

\paragraph{Shape restrictions:}
The mask array must have the same shape as the source array (see section
\ref{shape}).

\paragraph{Alignment restrictions:}
The mask array {\em must be aligned with} the source array
(see section \ref{alignment}).

\paragraph{Accessibility restrictions:}
The source array and the mask array must be accessible
(see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt src} and {\tt msk} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* res, T* srcDat, int* mskDat)
\end{verbatim}
The arguments are the address to which the result should be
written and the base addresses of
the local segments of the source and mask arrays.  The latter should
point to vectors of the locally held elements.

\paragraph{Effect:}
Executing the schedule adds together all elements of the array for
which the corresponding element of the mask array is non-zero.  The
addition is performed in an unspecified order.  The result value,
written to {\tt *res}, is broadcast to all members of the active
process group.

\paragraph{Replicated data:} 
If the source or mask array has replicated mapping, values for
particular elements are generally taken from the nearest copy.  The
definition of ``nearest'' is implementation dependent.

\newpage

\section{class {\tt Product}}

A {\em product schedule} is a communication schedule for multiplying together
all elements of a distributed array (the source array).
A product schedule is described by a
collective object with local components of class {\tt Product}.
The public interface of the {\tt Product} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class Product {
  public :
    Product(const DAD* src) ;

    void execute(T* res, T* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
Product(const DAD* src)
\end{verbatim}
The source array is described by the DAD {\tt *src}.  It will have
elements of type {\tt T}.

\paragraph{Type restrictions:}
{\tt T} should be a POD type (see section \ref{POD}).  A conventional
binary multiplication operator, {\tt *}, must be defined for objects of type
{\tt T}, the assignment operator {\tt *=} must operate in
a compatible way, and the symbol 1 must be convertible to type {\tt T},
yielding a unit of the multiplication operation.

All standard arithmetic types of C++ satisfy these requirements
for {\tt T}.

\paragraph{Accessibility restrictions:}
The source array must be accessible (see section
\ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt src} argument is stored in the schedule as a
reference.  The associated object must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* res, T* srcDat)
\end{verbatim}
The arguments are the address to which the result should be written and
the base address of the local segment of the source array.  The latter
should point to a vector of the locally held elements.

\paragraph{Effect:}
Executing the schedule multiplies together all elements of the array in an
unspecified order.  The result value, written to {\tt *res}, is
broadcast to all members of the active process group.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values for
particular elements are generally taken from the nearest copy.  The
definition of ``nearest'' is implementation dependent.

\newpage

\section{class {\tt ProductMsk}}

A {\em masked product schedule} is a communication schedule for multiplying
 together all elements of a distributed array (the source array) under the
control of a mask array.
A masked product schedule is described by a
collective object with local components of class {\tt ProductMsk}.
The public interface of the {\tt ProductMsk} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class ProductMsk {
  public :
    ProductMsk(const DAD* src, const DAD* msk) ;

    void execute(T* res, T* srcDat, int* mskDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
ProductMsk(const DAD* src, const DAD* msk)
\end{verbatim}
The source array is described by the DAD {\tt *src}.  It will have
elements of type {\tt T}.
The mask array is described by the DAD {\tt *msk}.

\paragraph{Type restrictions:}
{\tt T} should be a POD type (see section \ref{POD}).  A conventional
binary multiplication operator, {\tt *}, must be defined for objects of type
{\tt T}, the assignment operator {\tt *=} must operate in
a compatible way, and the symbol 1 must be convertible to type {\tt T},
yielding a unit of the multiplication operation.

All standard arithmetic types of C++ satisfy these requirements
for {\tt T}.

\paragraph{Shape restrictions:}
The mask array must have the same shape as the source array (see section
\ref{shape}).

\paragraph{Alignment restrictions:}
The mask array {\em must be aligned with} the source array
(see section \ref{alignment}).

\paragraph{Accessibility restrictions:}
The source array and the mask array must be accessible.
(see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt src} and {\tt msk} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* res, T* srcDat, int* mskDat)
\end{verbatim}
The arguments are the address to which the result should be
written and the base addresses of
the local segments of the source and mask arrays.  The latter should
point to vectors of the locally held elements.

\paragraph{Effect:}
Executing the schedule multiplies together all elements of the array for
which the corresponding element of the mask array is non-zero.  The
mulitplication is performed in an unspecified order.  The result value,
written to {\tt *res}, is broadcast to all members of the active
process group.

\paragraph{Replicated data:} 
If the source or mask array has replicated mapping, values for
particular elements are generally taken from the nearest copy.  The
definition of ``nearest'' is implementation dependent.

\newpage

\section{class {\tt Maxval}}

A {\em maximum value schedule} is a communication schedule for finding
the largest element of a distributed array (the source array).
A maximum value schedule is described by a
collective object with local components of class {\tt Maxval}.
The public interface of the {\tt Maxval} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class Maxval {
  public :
    Maxval(const DAD* src) ;

    void execute(T* res, T* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
Maxval(const DAD* src)
\end{verbatim}
The source array is described by the DAD {\tt *src}.  It will have
elements of type {\tt T}.

\paragraph{Type restrictions:}
{\tt T} should be a POD type.  Conventional
binary comparision operators, {\tt >} and {\tt <}, must be defined for
objects of type {\tt T}, and a function {\tt mostneg} must be
overloaded with the entry point
\small
\begin{verbatim}
  void mostneg(T* res) ;
\end{verbatim}
\normalsize
which sets {\tt *res} to the smallest allowed value of type {\tt T}.
The Adlib header files define {\tt mostneg} for all the standard
arithmetic types of C++, so these types satisfy all the
requirements for {\tt T}.

\paragraph{Accessibility restrictions:}
The source array must be accessible (see section
\ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt src} argument is stored in the schedule as a
reference.  The associated object must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* res, T* srcDat)
\end{verbatim}
The arguments are the address to which the result should be written and
the base address of the local segment of the source array.  The latter
should point to a vector of the locally held elements.

\paragraph{Effect:}
Executing the schedule finds the largest element of the array.
The maximum value, written to {\tt *res}, is broadcast to all members
of the active process group.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values for
particular elements are generally taken from the nearest copy.  The
definition of ``nearest'' is implementation dependent.

\newpage

\section{class {\tt MaxvalMsk}}

A {\em masked maximum value schedule} is a communication schedule for
finding the largest element of a distributed array (the source array)
under the control of a mask array.
A masked maximum value schedule is described by a
collective object with local components of class {\tt MaxvalMsk}.
The public interface of the {\tt MaxvalMsk} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class MaxvalMsk {
  public :
    MaxvalMsk(const DAD* src, const DAD* msk) ;

    void execute(T* res, T* srcDat, int* mskDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
MaxvalMsk(const DAD* src, const DAD* msk)
\end{verbatim}
The source array is described by the DAD {\tt *src}.  It will have
elements of type {\tt T}.
The mask array is described by the DAD {\tt *msk}.

\paragraph{Type restrictions:}
{\tt T} should be a POD type.  Conventional
binary comparision operators, {\tt >} and {\tt <}, must be defined for
objects of type {\tt T}, and a function {\tt mostneg} must be
overloaded with the entry point
\small
\begin{verbatim}
  void mostneg(T* res) ;
\end{verbatim}
\normalsize
which sets {\tt *res} to the smallest allowed value of type {\tt T}.
The Adlib header files define {\tt mostneg} for all the standard
arithmetic types of C++, so these types satisfy all the
requirements for {\tt T}.

\paragraph{Shape restrictions:}
The mask array must have the same shape as the source array (see section
\ref{shape}).

\paragraph{Alignment restrictions:}
The mask array {\em must be aligned with} the source array
(see section \ref{alignment}).

\paragraph{Accessibility restrictions:}
The source array and the mask array must be accessible.
(see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt src} and {\tt msk} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* res, T* srcDat, int* mskDat)
\end{verbatim}
The arguments are the address to which the result should be
written and the base addresses of
the local segments of the source and mask arrays.  The latter should
point to vectors of the locally held elements.

\paragraph{Effect:}
Executing the schedule finds the largest element of the array for
which the corresponding element of the mask array is non-zero.
The maximum value,
written to {\tt *res}, is broadcast to all members of the active
process group.

\paragraph{Replicated data:} 
If the source or mask array has replicated mapping, values for
particular elements are generally taken from the nearest copy.  The
definition of ``nearest'' is implementation dependent.

\newpage

\section{class {\tt Minval}}

A {\em minimum value schedule} is a communication schedule for finding
the smallest element of a distributed array (the source array).
A minimum value schedule is described by a
collective object with local components of class {\tt Minval}.
The public interface of the {\tt Minval} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class Minval {
  public :
    Minval(const DAD* src) ;

    void execute(T* res, T* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
Minval(const DAD* src)
\end{verbatim}
The source array is described by the DAD {\tt *src}.  It will have
elements of type {\tt T}.

\paragraph{Type restrictions:}
{\tt T} should be a POD type.  Conventional
binary comparision operators, {\tt >} and {\tt <}, must be defined for
objects of type {\tt T}, and a function {\tt mostpos} must be
overloaded with the entry point
\small
\begin{verbatim}
  void mostpos(T* res) ;
\end{verbatim}
\normalsize
which sets {\tt *res} to the largest allowed value of type {\tt T}.
The Adlib header files define {\tt mostpos} for all the standard
arithmetic types of C++, so these types satisfy all the
requirements for {\tt T}.

\paragraph{Accessibility restrictions:}
The source array must be accessible (see section
\ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt src} argument is stored in the schedule as a
reference.  The associated object must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* res, T* srcDat)
\end{verbatim}
The arguments are the address to which the result should be written and
the base address of the local segment of the source array.  The latter
should point to a vector of the locally held elements.

\paragraph{Effect:}
Executing the schedule finds the smallest element of the array.
The minimum value, written to {\tt *res}, is broadcast to all members
of the active process group.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values for
particular elements are generally taken from the nearest copy.  The
definition of ``nearest'' is implementation dependent.

\newpage

\section{class {\tt MinvalMsk}}

A {\em masked minimum schedule} is a communication schedule for
finding the smallest element of a distributed array (the source array)
under the control of a mask array.
A masked minimum schedule is described by a
collective object with local components of class {\tt MinvalMsk}.
The public interface of the {\tt MinvalMsk} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class MinvalMsk {
  public :
    MinvalMsk(const DAD* src, const DAD* msk) ;

    void execute(T* res, T* srcDat, int* mskDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
MinvalMsk(const DAD* src, const DAD* msk)
\end{verbatim}
The source array is described by the DAD {\tt *src}.  It will have
elements of type {\tt T}.
The mask array is described by the DAD {\tt *msk}.

\paragraph{Type restrictions:}
{\tt T} should be a POD type.  Conventional
binary comparision operators, {\tt >} and {\tt <}, must be defined for
objects of type {\tt T}, and a function {\tt mostpos} must be
overloaded with the entry point
\small
\begin{verbatim}
  void mostpos(T* res) ;
\end{verbatim}
\normalsize
which sets {\tt *res} to the largest allowed value of type {\tt T}.
The Adlib header files define {\tt mostpos} for all the standard
arithmetic types of C++, so these types satisfy all the
requirements for {\tt T}.

\paragraph{Shape restrictions:}
The mask array must have the same shape as the source array (see section
\ref{shape}).

\paragraph{Alignment restrictions:}
The mask array {\em must be aligned with} the source array
(see section \ref{alignment}).

\paragraph{Accessibility restrictions:}
The source array and the mask array must be accessible.
(see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt src} and {\tt msk} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* res, T* srcDat, int* mskDat)
\end{verbatim}
The arguments are the address to which the result should be
written and the base addresses of
the local segments of the source and mask arrays.  The latter should
point to vectors of the locally held elements.

\paragraph{Effect:}
Executing the schedule finds the smallest element of the array for
which the corresponding element of the mask array is non-zero.
The minimum value,
written to {\tt *res}, is broadcast to all members of the active
process group.

\paragraph{Replicated data:} 
If the source or mask array has replicated mapping, values for
particular elements are generally taken from the nearest copy.  The
definition of ``nearest'' is implementation dependent.

\newpage

\section{class {\tt All}}

A {\em all schedule} is a communication schedule for computing the
logical conjunction of the elements of a distributed array
of boolean values (the source array).  An all schedule is described by a
collective object with local components of class {\tt All}.
The public interface of the {\tt All} class is
\small
\begin{verbatim}
  class DAD ;

  class All {
  public :
    All(const DAD* src) ;

    void execute(int* res, int* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
All(const DAD* src)
\end{verbatim}
The source array is described by the DAD {\tt *src}.  It will have
elements of type {\tt int}.

\paragraph{Accessibility restrictions:}
The source array must be accessible (see section
\ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt src} argument is stored in the schedule as a
reference.  The associated object must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(int* res, int* srcDat)
\end{verbatim}
The arguments are the address to which the result should be written and
the base address of the local segment of the source array.  The latter
should point to a vector of the locally held elements.

\paragraph{Effect:}
Executing the schedule forms the logical conjunction (boolean {\em
and}) of the elements of the array.  The result value, written to {\tt
*res}, is broadcast to all members of the active process group.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values for
particular elements are generally taken from the nearest copy.  The
definition of ``nearest'' is implementation dependent.

\newpage

\section{class {\tt Any}}

A {\em any schedule} is a communication schedule for computing the
logical disjunction of the elements of a distributed array
of boolean values (the source array).  An any schedule is described by a
collective object with local components of class {\tt Any}.
The public interface of the {\tt Any} class is
\small
\begin{verbatim}
  class DAD ;

  class Any {
  public :
    Any(const DAD* src) ;

    void execute(int* res, int* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
Any(const DAD* src)
\end{verbatim}
The source array is described by the DAD {\tt *src}.  It will have
elements of type {\tt int}.

\paragraph{Accessibility restrictions:}
The source array must be accessible (see section
\ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt src} argument is stored in the schedule as a
reference.  The associated object must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(int* res, int* srcDat)
\end{verbatim}
The arguments are the address to which the result should be written and
the base address of the local segment of the source array.  The latter
should point to a vector of the locally held elements.

\paragraph{Effect:}
Executing the schedule forms the logical disjunction (boolean {\em
or}) of the elements of the array.  The result value, written to {\tt
*res}, is broadcast to all members of the active process group.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values for
particular elements are generally taken from the nearest copy.  The
definition of ``nearest'' is implementation dependent.

\newpage

\section{class {\tt Count}}

A {\em count schedule} is a communication schedule for counting the
number of true elements in a distributed array
of boolean values (the source array).  A count schedule is described by a
collective object with local components of class {\tt Count}.
The public interface of the {\tt Count} class is
\small
\begin{verbatim}
  class DAD ;

  class Count {
  public :
    Count(const DAD* src) ;

    void execute(int* res, int* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
Count(const DAD* src)
\end{verbatim}
The source array is described by the DAD {\tt *src}.  It will have
elements of type {\tt int}.

\paragraph{Accessibility restrictions:}
The source array must be accessible (see section
\ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt src} argument is stored in the schedule as a
reference.  The associated object must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(int* res, int* srcDat)
\end{verbatim}
The arguments are the address to which the result should be written and
the base address of the local segment of the source array.  The latter
should point to a vector of the locally held elements.

\paragraph{Effect:}
Executing the schedule returns the number of true (non-zero) 
elements of the array.  The result value, written to {\tt
*res}, is broadcast to all members of the active process group.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values for
particular elements are generally taken from the nearest copy.  The
definition of ``nearest'' is implementation dependent.

\newpage

\section{class {\tt DotProduct}}

A {\em dot product schedule} is a communication schedule for computing
the dot product of two distributed arrays (the source arrays).
A dot product schedule is described by a
collective object with local components of class {\tt DotProduct}.
The public interface of the {\tt DotProduct} class is
\small
\begin{verbatim}
  class DAD ;

  template<class S, class T, class U>
  class DotProduct {
  public :
    DotProduct(const DAD* src1, const DAD* src2) ;

    void execute(S* res, T* src1Dat, U* src2Dat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
DotProduct(const DAD* src1, const DAD* src2)
\end{verbatim}
The source arrays is described by the DADs {\tt *src1} and {\tt *src2}.
They will have elements of type {\tt T} and {\tt U} respectively.
The result will have type {\tt S}.

\paragraph{Type restrictions:}
{\tt S} should be a POD type (see section
\ref{POD}).  A conventional binary multiplication operator, {\tt *},
must be defined to multiply objects of type {\tt T} with objects of
type {\tt U}.  The assignment operator {\tt +=} must be defined on
objects of type {\tt S}.  This operator must be able to accept an RHS
operand of type {\tt S}, and must also be able to accept an operand
produced by multiplying together {\tt T} and {\tt U} (if this is has
type different to {\tt S}).  The symbol 0 must be convertible to type
{\tt S}, yielding a unit of the addition operation.

All standard arithmetic types of C++ satisfy these requirements,
provided the product of a {\tt T} with a {\tt U} is convertible to an
{\tt S}.

\paragraph{Shape restrictions:}
The two source arrays must have the same shape (see section
\ref{shape}).

\paragraph{Alignment restrictions:}
The source arrays must be aligned with one another
(see section \ref{alignment}).

\paragraph{Accessibility restrictions:}
The source arrays must be accessible (see section
\ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt src1} and {\tt src2} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
void execute(S* res, T* src1Dat, U* src2Dat) ;
\end{verbatim}
The arguments are the address to which the result should be written and
the base addresses of the local segments of the source arrays.  The latter
should point to vectors of the locally held elements.

\paragraph{Effect:}
Executing the schedule multiplies together corresponding elements of
the source arrays, in pairs, then adds together all pairwise
products.  The addition occurs in an unspecified order.  The result
value, written to {\tt *res}, is broadcast to all members of the active
process group.

\paragraph{Replicated data:} 
If the source arrays have replicated mapping, values for
particular elements are generally taken from the nearest copy.  The
definition of ``nearest'' is implementation dependent.

\newpage

\section{class {\tt BoolDotProduct}}

A {\em boolean dot product schedule} is a communication schedule for computing
the boolean dot product of two distributed arrays of boolean values
(the source arrays).  A boolean dot product schedule is described by a
collective object with local components of class {\tt BoolDotProduct}.
The public interface of the {\tt BoolDotProduct} class is
\small
\begin{verbatim}
  class DAD ;

  class BoolDotProduct {
  public :
    BoolDotProduct(const DAD* src1, const DAD* src2) ;

    void execute(int* res, int* src1Dat, int* src2Dat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
BoolDotProduct(const DAD* src1, const DAD* src2)
\end{verbatim}
The source arrays is described by the DADs {\tt *src1} and {\tt *src2}.

\paragraph{Shape restrictions:}
The two source arrays must have the same shape (see section
\ref{shape}).

\paragraph{Alignment restrictions:}
The source arrays must be aligned with one another
(see section \ref{alignment}).

\paragraph{Accessibility restrictions:}
The source arrays must be accessible (see section
\ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt src1} and {\tt src2} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
void execute(int* res, int* src1Dat, int* src2Dat) ;
\end{verbatim}
The arguments are the address to which the result should be written and
the base addresses of the local segments of the source arrays.  The latter
should point to vectors of the locally held elements.

\paragraph{Effect:}
Executing the schedule computes logical {\em and} of corresponding
elements of the source arrays, in pairs, then computes logical {\em or}
of all the pairwise conjunctions.  The result value, written to {\tt
*res}, is broadcast to all members of the active process group.

\paragraph{Replicated data:} 
If the source arrays have replicated mapping, values for
particular elements are generally taken from the nearest copy.  The
definition of ``nearest'' is implementation dependent.

\newpage


\section{class {\tt Maxloc}}

A {\em maximum location schedule} is a communication schedule for finding
the location of the largest element of a distributed array.
A maximum location schedule is described by a
collective object with local components of class {\tt Maxloc}.
The public interface of the {\tt Maxloc} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class Maxloc {
  public :
    Maxloc(const DAD* src) ;

    void execute(T* val, int pos [], T* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
Maxloc(const DAD* src)
\end{verbatim}
The source array is described by the DAD {\tt *src}.  It will have
elements of type {\tt T}.

\paragraph{Type restrictions:}
{\tt T} should be a POD type.  Conventional
binary comparision operators, {\tt >} and {\tt <}, must be defined for
objects of type {\tt T}, and a function {\tt mostneg} must be
overloaded with the entry point
\small
\begin{verbatim}
  void mostneg(T* res) ;
\end{verbatim}
\normalsize
which sets {\tt *res} to the smallest allowed value of type {\tt T}.
The Adlib header files define {\tt mostneg} for all the standard
arithmetic types of C++, so these types satisfy all the
requirements for {\tt T}.

\paragraph{Accessibility restrictions:}
The source array must be accessible.
(see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt src} argument is stored in the schedule as a
reference.  The associated object must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* val, int pos [], T* srcDat)
\end{verbatim}
The arguments are the addresses to which the result value and location
should be written, and the base address of the local segment of the source
array.  The latter should point to a vector of the locally held
elements.

The size of the {\tt pos} vector must be equal to the rank of the source
array.

\paragraph{Effect:}
The value of largest element in the array is written to {\tt *val}.
The global subscripts of the first occurrence of this element are written
to the vector {\tt pos}.  If the maximum value occurs more than once in
the array, ``first occurence'' is defined by ordering the set of global
subscripts with first subscript {\em least} significant (Fortran-like
array-element ordering).

The result values written to {\tt *val} and {\tt pos} are broadcast
to all members of the active process group.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values for a
particular element are generally taken from the nearest copy.  The
definition of ``nearest'' is implementation dependent.

\newpage

\section{class {\tt MaxlocMsk}}

A {\em masked maximum location schedule} is a communication schedule for finding
the location of the largest element of a distributed array, under the
control of a mask array.
A masked maximum location schedule is described by a
collective object with local components of class {\tt MaxlocMsk}.
The public interface of the {\tt MaxlocMsk} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class MaxlocMsk {
  public :
    Maxloc(const DAD* src, const DAD* msk) ;

    void execute(T* val, int pos [], T* srcDat, int* mskDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
MaxlocMsk(const DAD* src, const DAD* msk)
\end{verbatim}
The source array is described by the DAD {\tt *src}.  It will have
elements of type {\tt T}.
The mask array is described by the DAD {\tt *msk}.

\paragraph{Type restrictions:}
{\tt T} should be a POD type.  Conventional
binary comparision operators, {\tt >} and {\tt <}, must be defined for
objects of type {\tt T}, and a function {\tt mostneg} must be
overloaded with the entry point
\small
\begin{verbatim}
  void mostneg(T* res) ;
\end{verbatim}
\normalsize
which sets {\tt *res} to the smallest allowed value of type {\tt T}.
The Adlib header files define {\tt mostneg} for all the standard
arithmetic types of C++, so these types satisfy all the
requirements for {\tt T}.

\paragraph{Shape restrictions:}
The mask array must have the same shape as the source array (see section
\ref{shape}).

\paragraph{Alignment restrictions:}
The mask array {\em must be aligned with} the source array
(see section \ref{alignment}).

\paragraph{Accessibility restrictions:}
The source array and the mask array must be accessible.
(see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt src} and {\tt msk} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* val, int pos [], T* srcDat, int* mskDat)
\end{verbatim}
The arguments are the addresses to which the result value and location
should be written, and the base addresses of the local segments of the source
and mask arrays.  The latter should point to vectors of the locally held
elements.

The size of the {\tt pos} vector must be equal to the rank of the source
array.

\paragraph{Effect:}
The value of largest element in the array for which the corresponding
element of the mask array is non-zero is written to {\tt *val}.  The
global subscripts of the first occurrence of this element are written to
the vector {\tt pos}.  If the maximum value occurs more than once in
the unmasked part of the array, ``first occurence'' is defined by
ordering the set of global subscripts with first subscript {\em least}
significant (Fortran-like array-element ordering).

The result values written to {\tt *val} and {\tt pos} are broadcast
to all members of the active process group.

\paragraph{Replicated data:} 
If the source or mask array has replicated mapping, values for a
particular element are generally taken from the nearest copy.  The
definition of ``nearest'' is implementation dependent.

\newpage

\section{class {\tt Minloc}}

A {\em minimum location schedule} is a communication schedule for finding
the location of the smallest element of a distributed array.
A minimum location schedule is described by a
collective object with local components of class {\tt Minloc}.
The public interface of the {\tt Minloc} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class Minloc {
  public :
    Minloc(const DAD* src) ;

    void execute(T* val, int pos [], T* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
Minloc(const DAD* src)
\end{verbatim}
The source array is described by the DAD {\tt *src}.  It will have
elements of type {\tt T}.

\paragraph{Type restrictions:}
{\tt T} should be a POD type.  Conventional
binary comparision operators, {\tt >} and {\tt <}, must be defined for
objects of type {\tt T}, and a function {\tt mostpos} must be
overloaded with the entry point
\small
\begin{verbatim}
  void mostpos(T* res) ;
\end{verbatim}
\normalsize
which sets {\tt *res} to the largest allowed value of type {\tt T}.
The Adlib header files define {\tt mostpos} for all the standard
arithmetic types of C++, so these types satisfy all the
requirements for {\tt T}.

\paragraph{Accessibility restrictions:}
The source array must be accessible.
(see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt src} argument is stored in the schedule as a
reference.  The associated object must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* val, int pos [], T* srcDat)
\end{verbatim}
The arguments are the addresses to which the result value and location
should be written, and the base address of the local segment of the source
array.  The latter should point to a vector of the locally held
elements.

The size of the {\tt pos} vector must be equal to the rank of the source
array.

\paragraph{Effect:}
The value of smallest element in the array is written to {\tt *val}.
The global subscripts of the first occurrence of this element are written
to the vector {\tt pos}.  If the minimum value occurs more than once in
the array, ``first occurence'' is defined by ordering the set of global
subscripts with first subscript {\em least} significant (Fortran-like
array-element ordering).

The result values written to {\tt *val} and {\tt pos} are broadcast
to all members of the active process group.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values for a
particular element are generally taken from the nearest copy.  The
definition of ``nearest'' is implementation dependent.

\newpage

\section{class {\tt MinlocMsk}}

A {\em masked minimum location schedule} is a communication schedule for finding
the location of the smallest element of a distributed array, under the
control of a mask array.
A masked minimum location schedule is described by a
collective object with local components of class {\tt MinlocMsk}.
The public interface of the {\tt MinlocMsk} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class MinlocMsk {
  public :
    Minloc(const DAD* src, const DAD* msk) ;

    void execute(T* val, int pos [], T* srcDat, int* mskDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
MinlocMsk(const DAD* src, const DAD* msk)
\end{verbatim}
The source array is described by the DAD {\tt *src}.  It will have
elements of type {\tt T}.
The mask array is described by the DAD {\tt *msk}.

\paragraph{Type restrictions:}
{\tt T} should be a POD type.  Conventional
binary comparision operators, {\tt >} and {\tt <}, must be defined for
objects of type {\tt T}, and a function {\tt mostpos} must be
overloaded with the entry point
\small
\begin{verbatim}
  void mostpos(T* res) ;
\end{verbatim}
\normalsize
which sets {\tt *res} to the largest allowed value of type {\tt T}.
The Adlib header files define {\tt mostpos} for all the standard
arithmetic types of C++, so these types satisfy all the
requirements for {\tt T}.

\paragraph{Shape restrictions:}
The mask array must have the same shape as the source array (see section
\ref{shape}).

\paragraph{Alignment restrictions:}
The mask array {\em must be aligned with} the source array
(see section \ref{alignment}).

\paragraph{Accessibility restrictions:}
The source array and the mask array must be accessible.
(see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt src} and {\tt msk} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* val, int pos [], T* srcDat, int* mskDat)
\end{verbatim}
The arguments are the addresses to which the result value and location
should be written, and the base addresses of the local segments of the source
and mask arrays.  The latter should point to vectors of the locally held
elements.

The size of the {\tt pos} vector must be equal to the rank of the source
array.

\paragraph{Effect:}
The value of smallest element in the array for which the corresponding
element of the mask array is non-zero is written to {\tt *val}.  The
global subscripts of the first occurrence of this element are written to
the vector {\tt pos}.  If the minimum value occurs more than once in
the unmasked part of the array, ``first occurence'' is defined by
ordering the set of global subscripts with first subscript {\em least}
significant (Fortran-like array-element ordering).

The result values written to {\tt *val} and {\tt pos} are broadcast
to all members of the active process group.

\paragraph{Replicated data:} 
If the source or mask array has replicated mapping, values for a
particular element are generally taken from the nearest copy.  The
definition of ``nearest'' is implementation dependent.

\newpage

\section{class {\tt SumDim}}

A {\em dimension sum schedule} is a communication schedule for summing
the elements of a distributed array along one of its
dimensions, yielding a reduced array with rank one less than
the source.

A dimension sum schedule is described by a
collective object with local components of class {\tt SumDim}.
The public interface of the {\tt SumDim} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class SumDim {
  public :
    SumDim(const DAD* res, const DAD* src, const int dim) ;

    void execute(T* resDat, T* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
SumDim(const DAD* res, const DAD* src, const int dim)
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
result array is described by the DAD {\tt *res}.  They will both have
elements of type {\tt T}.  The reduction occurs in dimension {\tt dim}.

\paragraph{Value restrictions:}
The value of {\tt dim} must be in the range $0, \ldots, R - 1$ where
$R$ is the rank of the source array.

\paragraph{Type restrictions:}
{\tt T} should be a POD type (see section \ref{POD}).  A conventional
binary addition operator, {\tt +}, must be defined for objects of type
{\tt T}, the assignment operator {\tt +=} must operate in
a compatible way, and the symbol 0 must be convertible to type {\tt T},
yielding a zero of the addition operation.

All standard arithmetic types of C++ satisfy these requirements
for {\tt T}.

\paragraph{Shape restrictions:}
The shape of the result array must be obtained from the
shape of the source array by deleting dimension {\tt dim}
(see section \ref{shape}).

\paragraph{Alignment restrictions:}
The result array must be aligned to the source array, {\em with
replicated alignment in dimension {\tt dim}} (see section
\ref{alignment}).

\paragraph{Accessibility restrictions:}
The source array and the result array
must be accessible (see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt res} and {\tt src} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* resDat, T* srcDat)
\end{verbatim}
Arguments are the base addresses for local segments of the
result and source arrays.  They should point to vectors of
the locally held elements.

\paragraph{Effect:}
On exit, the value of
\small
\begin{tabbing}
\verb$  res [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim+1}},
                    \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is
\small
\begin{displaymath}
\sum_{x_{\mbox{\scriptsize \tt dim}} = 0}^{N - 1} \mbox{\tt src [} x_0, \ldots,
x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim}}, x_{\mbox{\tt dim+1}},
\ldots, x_{R - 1} \mbox{\tt ]}
\end{displaymath}
\normalsize
where $N$ is the extent of the source array in dimension {\tt dim}.
The sums are performed in an unspecified order.

As implied by the replicated alignment of the result array,
results are broadcast in the process dimension associated with 
dimension {\tt dim} of the source array.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values for particular
contributions to the sums are generally taken from the nearest copy of
the source element.  The definition of ``nearest'' is implementation
dependent.  Consistent replication of copies in the result array relies
on consistency of copies in the source array.

\paragraph{Overlap restrictions:} In-place updates are not allowed.  The
pairs {\tt *res}, {\tt resDat} and {\tt *src}, {\tt srcDat} must define
non-overlapping arrays.

\newpage

\section{class {\tt SumDimMsk}}

A {\em masked dimension sum schedule} is a communication schedule for summing,
under the control of mask,
the elements of a distributed array along one of its
dimensions, yielding a reduced array with rank one less than
the source.

A masked dimension sum schedule is described by a
collective object with local components of class {\tt SumDimMsk}.
The public interface of the {\tt SumDimMsk} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class SumDimMsk {
  public :
    SumDimMsk(const DAD* res, const DAD* src, const int dim,
              const DAD* msk) ;

    void execute(T* resDat, T* srcDat, int* mskDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
SumDimMsk(const DAD* res, const DAD* src, const int dim,
          const DAD* msk)
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
result array is described by the DAD {\tt *res}.  They will both have
elements of type {\tt T}.  The reduction occurs in dimension {\tt dim}.
The mask array is described by the DAD {\tt *msk}.

\paragraph{Value restrictions:}
The value of {\tt dim} must be in the range $0, \ldots, R - 1$ where
$R$ is the rank of the source array.

\paragraph{Type restrictions:}
{\tt T} should be a POD type (see section \ref{POD}).  A conventional
binary addition operator, {\tt +}, must be defined for objects of type
{\tt T}, the assignment operator {\tt +=} must operate in
a compatible way, and the symbol 0 must be convertible to type {\tt T},
yielding a zero of the addition operation.

All standard arithmetic types of C++ satisfy these requirements
for {\tt T}.

\paragraph{Shape restrictions:}
The mask array must be the same shape as the source array.
The shape of the result array must be obtained from the
shape of the source array by deleting dimension {\tt dim}
(see section \ref{shape}).

\paragraph{Alignment restrictions:}
The mask array must be aligned with the source array.
The result array must be aligned to the source array, {\em with
replicated alignment in dimension {\tt dim}} (see section
\ref{alignment}).

\paragraph{Accessibility restrictions:}
The source and mask arrays and the result array
must be accessible (see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt res}, {\tt src} and {\tt msk} arguments are stored in the
schedule as references.  The associated objects must persist for the
lifetime of the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* resDat, T* srcDat, int* mskDat)
\end{verbatim}
Arguments are the base addresses for local segments of the
result, source and mask arrays.  They should point to vectors of
the locally held elements.

\paragraph{Effect:}
On exit, the value of
\small
\begin{tabbing}
\verb$  res [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim+1}},
                    \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is
\small
\begin{displaymath}
\sum_{\begin{array}{c}
      x_{\mbox{\scriptsize \tt dim}} = 0 \\
      \mbox{\scriptsize \tt msk [} x_0, \ldots,
         x_{\mbox{\scriptsize \tt dim-1}},
         x_{\mbox{\scriptsize \tt dim}}, \\
         \quad \quad \quad  x_{\mbox{\scriptsize \tt dim+1}}, \ldots,
         x_{R - 1} \mbox{\scriptsize \tt ]} \neq 0
      \end{array}}^{N - 1} \mbox{\tt src [} x_0, \ldots,
x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim}}, x_{\mbox{\tt dim+1}},
\ldots, x_{R - 1} \mbox{\tt ]}
\end{displaymath}
\normalsize
where $N$ is the extent of the source array in dimension {\tt dim}.
The sum is performed in an unspecified order.

As implied by the replicated alignment of the result array,
results are broadcast in the process dimension associated with 
dimension {\tt dim} of the source array.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values for particular
contributions to the sums are generally taken from the nearest copy of
the source element.  The definition of ``nearest'' is implementation
dependent.  Consistent replication of copies in the result array relies
on consistency of copies in the source array.

\paragraph{Overlap restrictions:} In-place updates are not allowed.  The
pair {\tt *res}, {\tt resDat} must define an array that has no overlap
with the arrays defined by either of the pairs {\tt *src}, {\tt srcDat}
and {\tt *msk}, {\tt mskDat}

\newpage

\section{class {\tt ProductDim}}

A {\em dimension product schedule} is a communication schedule for
multiplying together the elements of a distributed array along one of
its dimensions, yielding a reduced array with rank one less than the
source.

A dimension product schedule is described by a
collective object with local components of class {\tt ProductDim}.
The public interface of the {\tt ProductDim} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class ProductDim {
  public :
    ProductDim(const DAD* res, const DAD* src, const int dim) ;

    void execute(T* resDat, T* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
ProductDim(const DAD* res, const DAD* src, const int dim)
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
result array is described by the DAD {\tt *res}.  They will both have
elements of type {\tt T}.  The reduction occurs in dimension {\tt dim}.

\paragraph{Value restrictions:}
The value of {\tt dim} must be in the range $0, \ldots, R - 1$ where
$R$ is the rank of the source array.

\paragraph{Type restrictions:}
{\tt T} should be a POD type (see section \ref{POD}).  A conventional
binary multiplication operator, {\tt *}, must be defined for objects of type
{\tt T}, the assignment operator {\tt *=} must operate in
a compatible way, and the symbol 1 must be convertible to type {\tt T},
yielding a unit of the multiplication operation.

All standard arithmetic types of C++ satisfy these requirements
for {\tt T}.

\paragraph{Shape restrictions:}
The shape of the result array must be obtained from the
shape of the source array by deleting dimension {\tt dim}
(see section \ref{shape}).

\paragraph{Alignment restrictions:}
The result array must be aligned to the source array, {\em with
replicated alignment in dimension {\tt dim}} (see section
\ref{alignment}).

\paragraph{Accessibility restrictions:}
The source array and the result array
must be accessible (see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt res} and {\tt src} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* resDat, T* srcDat)
\end{verbatim}
Arguments are the base addresses for local segments of the
result and source arrays.  They should point to vectors of
the locally held elements.

\paragraph{Effect:}
On exit, the value of
\small
\begin{tabbing}
\verb$  res [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim+1}},
                    \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is
\small
\begin{displaymath}
\prod_{x_{\mbox{\scriptsize \tt dim}} = 0}^{N - 1} \mbox{\tt src [} x_0, \ldots,
x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim}}, x_{\mbox{\tt dim+1}},
\ldots, x_{R - 1} \mbox{\tt ]}
\end{displaymath}
\normalsize
where $N$ is the extent of the source array in dimension {\tt dim}.
The product is computed in an unspecified order.

As implied by the replicated alignment of the result array,
results are broadcast in the process dimension associated with 
dimension {\tt dim} of the source array.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values for particular
contributions to the product are generally taken from the nearest copy of
the source element.  The definition of ``nearest'' is implementation
dependent.  Consistent replication of copies in the result array relies
on consistency of copies in the source array.

\paragraph{Overlap restrictions:} In-place updates are not allowed.  The
pairs {\tt *res}, {\tt resDat} and {\tt *src}, {\tt srcDat} must define
non-overlapping arrays.

\newpage

\section{class {\tt ProductDimMsk}}

A {\em masked dimension product schedule} is a communication schedule
for multiplying together, under the control of mask, the elements of a
distributed array along one of its dimensions, yielding a reduced array
with rank one less than the source.

A masked dimension product schedule is described by a
collective object with local components of class {\tt ProductDimMsk}.
The public interface of the {\tt ProductDimMsk} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class ProductDimMsk {
  public :
    ProductDimMsk(const DAD* res, const DAD* src, const int dim,
                  const DAD* msk) ;

    void execute(T* resDat, T* srcDat, int* mskDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
ProductDimMsk(const DAD* res, const DAD* src, const int dim,
          const DAD* msk)
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
result array is described by the DAD {\tt *res}.  They will both have
elements of type {\tt T}.  The reduction occurs in dimension {\tt dim}.
The mask array is described by the DAD {\tt *msk}.

\paragraph{Value restrictions:}
The value of {\tt dim} must be in the range $0, \ldots, R - 1$ where
$R$ is the rank of the source array.

\paragraph{Type restrictions:}
{\tt T} should be a POD type (see section \ref{POD}).  A conventional
binary multiplication operator, {\tt *}, must be defined for objects of type
{\tt T}, the assignment operator {\tt *=} must operate in
a compatible way, and the symbol 1 must be convertible to type {\tt T},
yielding a unit of the multiplication operation.

All standard arithmetic types of C++ satisfy these requirements
for {\tt T}.

\paragraph{Shape restrictions:}
The mask array must be the same shape as the source array.
The shape of the result array must be obtained from the
shape of the source array by deleting dimension {\tt dim}
(see section \ref{shape}).

\paragraph{Alignment restrictions:}
The mask array must be aligned with the source array.
The result array must be aligned to the source array, {\em with
replicated alignment in dimension {\tt dim}} (see section
\ref{alignment}).

\paragraph{Accessibility restrictions:}
The source and mask arrays and the result array
must be accessible (see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt res}, {\tt src} and {\tt msk} arguments are stored in the
schedule as references.  The associated objects must persist for the
lifetime of the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* resDat, T* srcDat, int* mskDat)
\end{verbatim}
Arguments are the base addresses for local segments of the
result, source and mask arrays.  They should point to vectors of
the locally held elements.

\paragraph{Effect:}
On exit, the value of
\small
\begin{tabbing}
\verb$  res [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim+1}},
                    \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is
\small
\begin{displaymath}
\prod_{\begin{array}{c}
      x_{\mbox{\scriptsize \tt dim}} = 0 \\
      \mbox{\scriptsize \tt msk [} x_0, \ldots,
         x_{\mbox{\scriptsize \tt dim-1}},
         x_{\mbox{\scriptsize \tt dim}}, \\
         \quad \quad \quad  x_{\mbox{\scriptsize \tt dim+1}}, \ldots,
         x_{R - 1} \mbox{\scriptsize \tt ]} \neq 0
      \end{array}}^{N - 1} \mbox{\tt src [} x_0, \ldots,
x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim}}, x_{\mbox{\tt dim+1}},
\ldots, x_{R - 1} \mbox{\tt ]}
\end{displaymath}
\normalsize
where $N$ is the extent of the source array in dimension {\tt dim}.
The product is computed in an unspecified order.

As implied by the replicated alignment of the result array,
results are broadcast in the process dimension associated with 
dimension {\tt dim} of the source array.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values for particular
contributions to the product are generally taken from the nearest copy of
the source element.  The definition of ``nearest'' is implementation
dependent.  Consistent replication of copies in the result array relies
on consistency of copies in the source array.

\paragraph{Overlap restrictions:} In-place updates are not allowed.  The
pair {\tt *res}, {\tt resDat} must define an array that has no overlap
with the arrays defined by either of the pairs {\tt *src}, {\tt srcDat}
and {\tt *msk}, {\tt mskDat}

\newpage

\section{class {\tt MaxvalDim}}

A {\em dimension maximum value schedule} is a communication schedule for
finding the largest elements of a distributed array along one of its
dimensions, yielding a reduced array with rank one less than
the source.

A dimension maximum value schedule is described by a
collective object with local components of class {\tt MaxvalDim}.
The public interface of the {\tt MaxvalDim} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class MaxvalDim {
  public :
    MaxvalDim(const DAD* res, const DAD* src, const int dim) ;

    void execute(T* resDat, T* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
MaxvalDim(const DAD* res, const DAD* src, const int dim)
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
result array is described by the DAD {\tt *res}.  They will both have
elements of type {\tt T}.  The reduction occurs in dimension {\tt dim}.

\paragraph{Value restrictions:}
The value of {\tt dim} must be in the range $0, \ldots, R - 1$ where
$R$ is the rank of the source array.

\paragraph{Type restrictions:}
{\tt T} should be a POD type.  Conventional
binary comparision operators, {\tt >} and {\tt <}, must be defined for
objects of type {\tt T}, and a function {\tt mostneg} must be
overloaded with the entry point
\small
\begin{verbatim}
  void mostneg(T* res) ;
\end{verbatim}
\normalsize
which sets {\tt *res} to the smallest allowed value of type {\tt T}.
The Adlib header files define {\tt mostneg} for all the standard
arithmetic types of C++, so these types satisfy all the
requirements for {\tt T}.

\paragraph{Shape restrictions:}
The shape of the result array must be obtained from the
shape of the source array by deleting dimension {\tt dim}
(see section \ref{shape}).

\paragraph{Alignment restrictions:}
The result array must be aligned to the source array, {\em with
replicated alignment in dimension {\tt dim}} (see section
\ref{alignment}).

\paragraph{Accessibility restrictions:}
The source array and the result array
must be accessible (see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt res} and {\tt src} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* resDat, T* srcDat)
\end{verbatim}
Arguments are the base addresses for local segments of the
result and source arrays.  They should point to vectors of
the locally held elements.

\paragraph{Effect:}
On exit, the value of
\small
\begin{tabbing}
\verb$  res [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim+1}},
                    \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is the maximum value of
\small
\begin{tabbing}
\verb$  src [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim}},
                    x_{\mbox{\tt dim+1}}, \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
across allowed values of $x_{\mbox{\tt dim}}$.

As implied by the replicated alignment of the result array,
the results are broadcast in the process dimension associated with 
dimension {\tt dim} of the source array.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values of particular
elements for comparision are generally taken from the nearest copy of
the source element.  The definition of ``nearest'' is implementation
dependent.  Consistent replication of copies in the result array relies
on consistency of copies in the source array.

\paragraph{Overlap restrictions:} In-place updates are not allowed.  The
pairs {\tt *res}, {\tt resDat} and {\tt *src}, {\tt srcDat} must define
non-overlapping arrays.

\newpage

\section{class {\tt MaxvalDimMsk}}

A {\em masked dimension maximum value schedule} is a communication
schedule for finding, under the control of mask, the largest elements
of a distributed array along one of its dimensions, yielding a reduced
array with rank one less than the source.

A masked dimension maximum value schedule is described by a
collective object with local components of class {\tt MaxvalDimMsk}.
The public interface of the {\tt MaxvalDimMsk} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class MaxvalDimMsk {
  public :
    MaxvalDimMsk(const DAD* res, const DAD* src, const int dim,
                 const DAD* msk) ;

    void execute(T* resDat, T* srcDat, int* mskDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
MaxvalDimMsk(const DAD* res, const DAD* src, const int dim,
          const DAD* msk)
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
result array is described by the DAD {\tt *res}.  They will both have
elements of type {\tt T}.  The reduction occurs in dimension {\tt dim}.
The mask array is described by the DAD {\tt *msk}.

\paragraph{Value restrictions:}
The value of {\tt dim} must be in the range $0, \ldots, R - 1$ where
$R$ is the rank of the source array.

\paragraph{Type restrictions:}
{\tt T} should be a POD type.  Conventional
binary comparision operators, {\tt >} and {\tt <}, must be defined for
objects of type {\tt T}, and a function {\tt mostneg} must be
overloaded with the entry point
\small
\begin{verbatim}
  void mostneg(T* res) ;
\end{verbatim}
\normalsize
which sets {\tt *res} to the smallest allowed value of type {\tt T}.
The Adlib header files define {\tt mostneg} for all the standard
arithmetic types of C++, so these types satisfy all the
requirements for {\tt T}.

\paragraph{Shape restrictions:}
The mask array must be the same shape as the source array.
The shape of the result array must be obtained from the
shape of the source array by deleting dimension {\tt dim}
(see section \ref{shape}).

\paragraph{Alignment restrictions:}
The mask array must be aligned with the source array.
The result array must be aligned to the source array, {\em with
replicated alignment in dimension {\tt dim}} (see section
\ref{alignment}).

\paragraph{Accessibility restrictions:}
The source and mask arrays and the result array
must be accessible (see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt res}, {\tt src} and {\tt msk} arguments are stored in the
schedule as references.  The associated objects must persist for the
lifetime of the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* resDat, T* srcDat, int* mskDat)
\end{verbatim}
Arguments are the base addresses for local segments of the
result, source and mask arrays.  They should point to vectors of
the locally held elements.

\paragraph{Effect:}
On exit, the value of
\small
\begin{tabbing}
\verb$  res [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim+1}},
                    \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is the maximum value of
\small
\begin{tabbing}
\verb$  src [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim}},
                    x_{\mbox{\tt dim+1}}, \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
for which
\small
\begin{displaymath}
\mbox{\tt msk [} x_0, \ldots,
x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim}}, x_{\mbox{\tt dim+1}},
\ldots, x_{R - 1} \mbox{\tt ]} \neq 0
\end{displaymath}
\normalsize
over the allowed values of $x_{\mbox{\tt dim}}$.

As implied by the replicated alignment of the result array,
the results are broadcast in the process dimension associated with 
dimension {\tt dim} of the source array.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values for particular
elements for comparision are generally taken from the nearest copy of
the source element.  The definition of ``nearest'' is implementation
dependent.  Consistent replication of copies in the result array relies
on consistency of copies in the source array.

\paragraph{Overlap restrictions:} In-place updates are not allowed.  The
pair {\tt *res}, {\tt resDat} must define an array that has no overlap
with the arrays defined by either of the pairs {\tt *src}, {\tt srcDat}
and {\tt *msk}, {\tt mskDat}

\newpage

\section{class {\tt MinvalDim}}

A {\em dimension minimum value schedule} is a communication schedule for
finding the smallest elements of a distributed array along one of its
dimensions, yielding a reduced array with rank one less than
the source.

A dimension minimum value schedule is described by a
collective object with local components of class {\tt MinvalDim}.
The public interface of the {\tt MinvalDim} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class MinvalDim {
  public :
    MinvalDim(const DAD* res, const DAD* src, const int dim) ;

    void execute(T* resDat, T* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
MinvalDim(const DAD* res, const DAD* src, const int dim)
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
result array is described by the DAD {\tt *res}.  They will both have
elements of type {\tt T}.  The reduction occurs in dimension {\tt dim}.

\paragraph{Value restrictions:}
The value of {\tt dim} must be in the range $0, \ldots, R - 1$ where
$R$ is the rank of the source array.

\paragraph{Type restrictions:}
{\tt T} should be a POD type.  Conventional
binary comparision operators, {\tt >} and {\tt <}, must be defined for
objects of type {\tt T}, and a function {\tt mostpos} must be
overloaded with the entry point
\small
\begin{verbatim}
  void mostpos(T* res) ;
\end{verbatim}
\normalsize
which sets {\tt *res} to the largest allowed value of type {\tt T}.
The Adlib header files define {\tt mostpos} for all the standard
arithmetic types of C++, so these types satisfy all the
requirements for {\tt T}.

\paragraph{Shape restrictions:}
The shape of the result array must be obtained from the
shape of the source array by deleting dimension {\tt dim}
(see section \ref{shape}).

\paragraph{Alignment restrictions:}
The result array must be aligned to the source array, {\em with
replicated alignment in dimension {\tt dim}} (see section
\ref{alignment}).

\paragraph{Accessibility restrictions:}
The source array and the result array
must be accessible (see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt res} and {\tt src} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* resDat, T* srcDat)
\end{verbatim}
Arguments are the base addresses for local segments of the
result and source arrays.  They should point to vectors of
the locally held elements.

\paragraph{Effect:}
On exit, the value of
\small
\begin{tabbing}
\verb$  res [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim+1}},
                    \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is the minimum value of
\small
\begin{tabbing}
\verb$  src [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim}},
                    x_{\mbox{\tt dim+1}}, \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
across allowed values of $x_{\mbox{\tt dim}}$.

As implied by the replicated alignment of the result array,
the results are broadcast in the process dimension associated with 
dimension {\tt dim} of the source array.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values of particular
elements for comparision are generally taken from the nearest copy of
the source element.  The definition of ``nearest'' is implementation
dependent.  Consistent replication of copies in the result array relies
on consistency of copies in the source array.

\paragraph{Overlap restrictions:} In-place updates are not allowed.  The
pairs {\tt *res}, {\tt resDat} and {\tt *src}, {\tt srcDat} must define
non-overlapping arrays.

\newpage

\section{class {\tt MinvalDimMsk}}

A {\em masked dimension minimum value schedule} is a communication
schedule for finding, under the control of mask, the smallest elements
of a distributed array along one of its dimensions, yielding a reduced
array with rank one less than the source.

A masked dimension minimum value schedule is described by a
collective object with local components of class {\tt MinvalDimMsk}.
The public interface of the {\tt MinvalDimMsk} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class MinvalDimMsk {
  public :
    MinvalDimMsk(const DAD* res, const DAD* src, const int dim,
                 const DAD* msk) ;

    void execute(T* resDat, T* srcDat, int* mskDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
MinvalDimMsk(const DAD* res, const DAD* src, const int dim,
             const DAD* msk)
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
result array is described by the DAD {\tt *res}.  They will both have
elements of type {\tt T}.  The reduction occurs in dimension {\tt dim}.
The mask array is described by the DAD {\tt *msk}.

\paragraph{Value restrictions:}
The value of {\tt dim} must be in the range $0, \ldots, R - 1$ where
$R$ is the rank of the source array.

\paragraph{Type restrictions:}
{\tt T} should be a POD type.  Conventional
binary comparision operators, {\tt >} and {\tt <}, must be defined for
objects of type {\tt T}, and a function {\tt mostpos} must be
overloaded with the entry point
\small
\begin{verbatim}
  void mostpos(T* res) ;
\end{verbatim}
\normalsize
which sets {\tt *res} to the largest allowed value of type {\tt T}.
The Adlib header files define {\tt mostpos} for all the standard
arithmetic types of C++, so these types satisfy all the
requirements for {\tt T}.

\paragraph{Shape restrictions:}
The mask array must be the same shape as the source array.
The shape of the result array must be obtained from the
shape of the source array by deleting dimension {\tt dim}
(see section \ref{shape}).

\paragraph{Alignment restrictions:}
The mask array must be aligned with the source array.
The result array must be aligned to the source array, {\em with
replicated alignment in dimension {\tt dim}} (see section
\ref{alignment}).

\paragraph{Accessibility restrictions:}
The source and mask arrays and the result array
must be accessible (see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt res}, {\tt src} and {\tt msk} arguments are stored in the
schedule as references.  The associated objects must persist for the
lifetime of the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* resDat, T* srcDat, int* mskDat)
\end{verbatim}
Arguments are the base addresses for local segments of the
result, source and mask arrays.  They should point to vectors of
the locally held elements.

\paragraph{Effect:}
On exit, the value of
\small
\begin{tabbing}
\verb$  res [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim+1}},
                    \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is the minimum value of
\small
\begin{tabbing}
\verb$  src [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim}},
                    x_{\mbox{\tt dim+1}}, \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
for which
\small
\begin{displaymath}
\mbox{\tt msk [} x_0, \ldots,
x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim}}, x_{\mbox{\tt dim+1}},
\ldots, x_{R - 1} \mbox{\tt ]} \neq 0
\end{displaymath}
\normalsize
over the allowed values of $x_{\mbox{\tt dim}}$.

As implied by the replicated alignment of the result array,
the results are broadcast in the process dimension associated with 
dimension {\tt dim} of the source array.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values for particular
elements for comparision are generally taken from the nearest copy of
the source element.  The definition of ``nearest'' is implementation
dependent.  Consistent replication of copies in the result array relies
on consistency of copies in the source array.

\paragraph{Overlap restrictions:} In-place updates are not allowed.  The
pair {\tt *res}, {\tt resDat} must define an array that has no overlap
with the arrays defined by either of the pairs {\tt *src}, {\tt srcDat}
and {\tt *msk}, {\tt mskDat}

\newpage

\section{class {\tt AllDim}}

A {\em dimension all schedule} is a communication schedule for
computing the logical conjunction of the elements of a distributed
array of boolean along one of its dimensions, yielding a reduced array
with rank one less than the source.

A dimension all schedule is described by a
collective object with local components of class {\tt AllDim}.
The public interface of the {\tt AllDim} class is
\small
\begin{verbatim}
  class DAD ;

  class AllDim {
  public :
    AllDim(const DAD* res, const DAD* src, const int dim) ;

    void execute(int* resDat, int* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
AllDim(const DAD* res, const DAD* src, const int dim)
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
result array is described by the DAD {\tt *res}.  They will both have
elements of type {\tt int}.  The reduction occurs in dimension {\tt dim}.

\paragraph{Value restrictions:}
The value of {\tt dim} must be in the range $0, \ldots, R - 1$ where
$R$ is the rank of the source array.

\paragraph{Shape restrictions:}
The shape of the result array must be obtained from the
shape of the source array by deleting dimension {\tt dim}
(see section \ref{shape}).

\paragraph{Alignment restrictions:}
The result array must be aligned to the source array, {\em with
replicated alignment in dimension {\tt dim}} (see section
\ref{alignment}).

\paragraph{Accessibility restrictions:}
The source array and the result array
must be accessible (see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt res} and {\tt src} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(int* resDat, int* srcDat)
\end{verbatim}
Arguments are the base addresses for local segments of the
result and source arrays.  They should point to vectors of
the locally held elements.

\paragraph{Effect:}
On exit, the value of
\small
\begin{tabbing}
\verb$  res [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim+1}},
                    \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is true if
\small
\begin{tabbing}
\verb$  src [$$x_0, \ldots,
             x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim}}, x_{\mbox{\tt dim+1}},
                    \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is true (non-zero) for {\em all} allowed values of $x_{\mbox{\tt dim}}$.

As implied by the replicated alignment of the result array,
results are broadcast in the process dimension associated with 
dimension {\tt dim} of the source array.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values for particular
contributions to the conjunctions are generally taken from the nearest copy of
the source element.  The definition of ``nearest'' is implementation
dependent.  Consistent replication of copies in the result array relies
on consistency of copies in the source array.

\paragraph{Overlap restrictions:} In-place updates are not allowed.  The
pairs {\tt *res}, {\tt resDat} and {\tt *src}, {\tt srcDat} must define
non-overlapping arrays.

\newpage

\section{class {\tt AnyDim}}

A {\em dimension any schedule} is a communication schedule for
computing the logical disjunction of the elements of a distributed
array of boolean values along one of its dimensions, yielding a reduced
array with rank one less than the source.

A dimension any schedule is described by a
collective object with local components of class {\tt AnyDim}.
The public interface of the {\tt AnyDim} class is
\small
\begin{verbatim}
  class DAD ;

  class AnyDim {
  public :
    AnyDim(const DAD* res, const DAD* src, const int dim) ;

    void execute(int* resDat, int* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
AnyDim(const DAD* res, const DAD* src, const int dim)
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
result array is described by the DAD {\tt *res}.  They will both have
elements of type {\tt int}.  The reduction occurs in dimension {\tt dim}.

\paragraph{Value restrictions:}
The value of {\tt dim} must be in the range $0, \ldots, R - 1$ where
$R$ is the rank of the source array.

\paragraph{Shape restrictions:}
The shape of the result array must be obtained from the
shape of the source array by deleting dimension {\tt dim}
(see section \ref{shape}).

\paragraph{Alignment restrictions:}
The result array must be aligned to the source array, {\em with
replicated alignment in dimension {\tt dim}} (see section
\ref{alignment}).

\paragraph{Accessibility restrictions:}
The source array and the result array
must be accessible (see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt res} and {\tt src} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(int* resDat, int* srcDat)
\end{verbatim}
Arguments are the base addresses for local segments of the
result and source arrays.  They should point to vectors of
the locally held elements.

\paragraph{Effect:}
On exit, the value of
\small
\begin{tabbing}
\verb$  res [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim+1}},
                    \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is true if
\small
\begin{tabbing}
\verb$  src [$$x_0, \ldots,
             x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim}}, x_{\mbox{\tt dim+1}},
                    \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is true (non-zero) for {\em any} allowed values of $x_{\mbox{\tt dim}}$.

As implied by the replicated alignment of the result array,
results are broadcast in the process dimension associated with 
dimension {\tt dim} of the source array.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values for particular
contributions to the disjunctions are generally taken from the nearest copy of
the source element.  The definition of ``nearest'' is implementation
dependent.  Consistent replication of copies in the result array relies
on consistency of copies in the source array.

\paragraph{Overlap restrictions:} In-place updates are not allowed.  The
pairs {\tt *res}, {\tt resDat} and {\tt *src}, {\tt srcDat} must define
non-overlapping arrays.

\newpage

\section{class {\tt CountDim}}

A {\em dimension count schedule} is a communication schedule for
counting the number of true elements of a distributed array of boolean
values along one of its dimensions, yielding a reduced array with rank
one less than the source.

A dimension count schedule is described by a
collective object with local components of class {\tt CountDim}.
The public interface of the {\tt CountDim} class is
\small
\begin{verbatim}
  class DAD ;

  class CountDim {
  public :
    CountDim(const DAD* res, const DAD* src, const int dim) ;

    void execute(int* resDat, int* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
CountDim(const DAD* res, const DAD* src, const int dim)
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
result array is described by the DAD {\tt *res}.  They will both have
elements of type {\tt int}.  The reduction occurs in dimension {\tt dim}.

\paragraph{Value restrictions:}
The value of {\tt dim} must be in the range $0, \ldots, R - 1$ where
$R$ is the rank of the source array.

\paragraph{Shape restrictions:}
The shape of the result array must be obtained from the
shape of the source array by deleting dimension {\tt dim}
(see section \ref{shape}).

\paragraph{Alignment restrictions:}
The result array must be aligned to the source array, {\em with
replicated alignment in dimension {\tt dim}} (see section
\ref{alignment}).

\paragraph{Accessibility restrictions:}
The source array and the result array
must be accessible (see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt res} and {\tt src} arguments are stored in the schedule as
references.  The associated objects must persist for the lifetime of
the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(int* resDat, int* srcDat)
\end{verbatim}
Arguments are the base addresses for local segments of the
result and source arrays.  They should point to vectors of
the locally held elements.

\paragraph{Effect:}
On exit, the value of
\small
\begin{tabbing}
\verb$  res [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim+1}},
                    \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is the number of true (non-zero) elements
\small
\begin{tabbing}
\verb$  src [$$x_0, \ldots,
             x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim}}, x_{\mbox{\tt dim+1}},
                    \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
over allowed values of $x_{\mbox{\tt dim}}$.

As implied by the replicated alignment of the result array,
results are broadcast in the process dimension associated with 
dimension {\tt dim} of the source array.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values for particular
contributions to the count are generally taken from the nearest copy of
the source element.  The definition of ``nearest'' is implementation
dependent.  Consistent replication of copies in the result array relies
on consistency of copies in the source array.

\paragraph{Overlap restrictions:} In-place updates are not allowed.  The
pairs {\tt *res}, {\tt resDat} and {\tt *src}, {\tt srcDat} must define
non-overlapping arrays.

\newpage

\section{class {\tt MaxlocDim}}

A {\em dimension maximum location schedule} is a communication schedule
for searching for the largest elements of a distributed array along one
of its dimensions, yielding a reduced array with rank one less than the
source.

A dimension maximum location schedule is described by a
collective object with local components of class {\tt MaxlocDim}.
The public interface of the {\tt MaxlocDim} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class MaxlocDim {
  public :
    MaxlocDim(const DAD* val, const DAD* pos,
              const DAD* src, const int dim) ;

    void execute(T* valDat, int* posDat, T* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
MaxlocDim(const DAD* val, const DAD* pos,
          const DAD* src, const int dim)
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
array of maximum values is described by the DAD {\tt *val}.  They will
both have elements of type {\tt T}.  The array of maximum locations is
described by the DAD {\tt *pos}.
The search occurs in dimension {\tt dim}.

\paragraph{Value restrictions:}
The value of {\tt dim} must be in the range $0, \ldots, R - 1$ where
$R$ is the rank of the source array.

\paragraph{Type restrictions:}
{\tt T} should be a POD type.  Conventional
binary comparision operators, {\tt >} and {\tt <}, must be defined for
objects of type {\tt T}, and a function {\tt mostneg} must be
overloaded with the entry point
\small
\begin{verbatim}
  void mostneg(T* res) ;
\end{verbatim}
\normalsize
which sets {\tt *res} to the smallest allowed value of type {\tt T}.
The Adlib header files define {\tt mostneg} for all the standard
arithmetic types of C++, so these types satisfy all the
requirements for {\tt T}.

\paragraph{Shape restrictions:}
The shape of the two result arrays ({\tt *val} and {\tt *pos}) must be
must be obtained from the shape of the source array by deleting
dimension {\tt dim} (see section \ref{shape}).

\paragraph{Alignment restrictions:}
The two result arrays ({\tt *val} and {\tt *pos}) must be aligned to
the source array, {\em with replicated alignment in dimension {\tt
dim}} (see section \ref{alignment}).

\paragraph{Accessibility restrictions:}
The source array and the result arrays
must be accessible (see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt val}, {\tt loc} and {\tt src} arguments are stored in the
schedule as references.  The associated objects must persist for the
lifetime of the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* valDat, int* posDat, T* srcDat)
\end{verbatim}
Arguments are the base addresses for local segments of the result
value, result position, and source arrays.  They should point to
vectors of the locally held elements.

\paragraph{Effect:}
On exit, the value of
\small
\begin{tabbing}
\verb$  val [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim+1}},
                    \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is the maximum value of
\small
\begin{tabbing}
\verb$  src [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim}},
                    x_{\mbox{\tt dim+1}}, \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
across allowed values of $x_{\mbox{\tt dim}}$.  The value of
\small
\begin{tabbing}
\verb$  pos [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim+1}},
                    \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is the smallest $x_{\mbox{\tt dim}}$ value at which this maximum
occurs.

As implied by the replicated alignment of the result arrays,
the results are broadcast in the process dimension associated with 
dimension {\tt dim} of the source array.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values of particular
elements for comparision are generally taken from the nearest copy of
the source element.  The definition of ``nearest'' is implementation
dependent.  Consistent replication of copies in the result array relies
on consistency of copies in the source array.

\paragraph{Overlap restrictions:} In-place updates are not allowed.
Neither of the arrays defined by the pairs {\tt *val}, {\tt valDat} or
{\tt *pos}, {\tt posDat} may have any overlap with
the array defined by the pair {\tt *src}, {\tt srcDat}.

\newpage

\section{class {\tt MaxlocDimMsk}}

A {\em masked dimension maximum location schedule} is a communication
schedule for searching, under the control of a mask, for the largest
elements of a distributed array along one of its dimensions, yielding a
reduced array with rank one less than the source.

A masked dimension maximum location schedule is described by a
collective object with local components of class {\tt MaxlocDimMsk}.
The public interface of the {\tt MaxlocDimMsk} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class MaxlocDimMsk {
  public :
    MaxlocDimMsk(const DAD* val, const DAD* pos,
                 const DAD* src, const int dim, const DAD* msk) ;

    void execute(T* valDat, int* posDat, T* srcDat, int* mskDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
MaxlocDimMsk(const DAD* val, const DAD* pos,
             const DAD* src, const int dim,
             const DAD* msk)
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
array of maximum values is described by the DAD {\tt *val}.  They will
both have elements of type {\tt T}.  The array of maximum locations is
described by the DAD {\tt *pos}.
The search occurs in dimension {\tt dim}.
The mask array is described by the DAD {\tt *msk}.

\paragraph{Value restrictions:}
The value of {\tt dim} must be in the range $0, \ldots, R - 1$ where
$R$ is the rank of the source array.

\paragraph{Type restrictions:}
{\tt T} should be a POD type.  Conventional
binary comparision operators, {\tt >} and {\tt <}, must be defined for
objects of type {\tt T}, and a function {\tt mostneg} must be
overloaded with the entry point
\small
\begin{verbatim}
  void mostneg(T* res) ;
\end{verbatim}
\normalsize
which sets {\tt *res} to the smallest allowed value of type {\tt T}.
The Adlib header files define {\tt mostneg} for all the standard
arithmetic types of C++, so these types satisfy all the
requirements for {\tt T}.

\paragraph{Shape restrictions:}
The shape of the two result arrays ({\tt *val} and {\tt *pos}) must be
must be obtained from the shape of the source array by deleting
dimension {\tt dim}.
The mask array must be the same shape as the source array
(see section \ref{shape}).

\paragraph{Alignment restrictions:}
The two result arrays ({\tt *val} and {\tt *pos}) must be aligned to
the source array, {\em with replicated alignment in dimension {\tt
dim}}.  The mask array must be aligned with the source
array (see section \ref{alignment}).

\paragraph{Accessibility restrictions:}
The source and mask arrays and the result arrays
must be accessible (see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt val}, {\tt loc}, {\tt src} and {\tt msk} arguments are stored
in the schedule as references.  The associated objects must persist for
the lifetime of the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* valDat, int* posDat, T* srcDat, int* mskDat)
\end{verbatim}
Arguments are the base addresses for local segments of the result
value, result position, source, and mask arrays.  They should point to
vectors of the locally held elements.

\paragraph{Effect:}
On exit, the value of
\small
\begin{tabbing}
\verb$  val [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim+1}},
                    \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is the maximum value of
\small
\begin{tabbing}
\verb$  src [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim}},
                    x_{\mbox{\tt dim+1}}, \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
for which
\small
\begin{displaymath}
\mbox{\tt msk [} x_0, \ldots,
x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim}}, x_{\mbox{\tt dim+1}},
\ldots, x_{R - 1} \mbox{\tt ]} \neq 0
\end{displaymath}
\normalsize
over the allowed values of $x_{\mbox{\tt dim}}$.  The value of
\small
\begin{tabbing}
\verb$  pos [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim+1}},
                    \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is the smallest $x_{\mbox{\tt dim}}$ value at which this maximum
occurs.

As implied by the replicated alignment of the result arrays,
the results are broadcast in the process dimension associated with 
dimension {\tt dim} of the source array.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values for particular
elements for comparision are generally taken from the nearest copy of
the source element.  The definition of ``nearest'' is implementation
dependent.  Consistent replication of copies in the result array relies
on consistency of copies in the source array.

\paragraph{Overlap restrictions:} In-place updates are not allowed.
Neither of the arrays defined by the pairs {\tt *val}, {\tt valDat} or
{\tt *pos}, {\tt posDat} may have any overlap with either of the arrays
defined by the pairs {\tt *src}, {\tt srcDat} and {\tt *msk}, {\tt
mskDat}

\newpage

\section{class {\tt MinlocDim}}

A {\em dimension minimum location schedule} is a communication schedule
for searching for the smallest elements of a distributed array along one
of its dimensions, yielding a reduced array with rank one less than the
source.

A dimension minimum location schedule is described by a
collective object with local components of class {\tt MinlocDim}.
The public interface of the {\tt MinlocDim} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class MinlocDim {
  public :
    MinlocDim(const DAD* val, const DAD* pos,
              const DAD* src, const int dim) ;

    void execute(T* valDat, int* posDat, T* srcDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
MinlocDim(const DAD* val, const DAD* pos,
          const DAD* src, const int dim)
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
array of minimum values is described by the DAD {\tt *val}.  They will
both have elements of type {\tt T}.  The array of minimum locations is
described by the DAD {\tt *pos}.
The search occurs in dimension {\tt dim}.

\paragraph{Value restrictions:}
The value of {\tt dim} must be in the range $0, \ldots, R - 1$ where
$R$ is the rank of the source array.

\paragraph{Type restrictions:}
{\tt T} should be a POD type.  Conventional
binary comparision operators, {\tt >} and {\tt <}, must be defined for
objects of type {\tt T}, and a function {\tt mostpos} must be
overloaded with the entry point
\small
\begin{verbatim}
  void mostpos(T* res) ;
\end{verbatim}
\normalsize
which sets {\tt *res} to the largest allowed value of type {\tt T}.
The Adlib header files define {\tt mostpos} for all the standard
arithmetic types of C++, so these types satisfy all the
requirements for {\tt T}.

\paragraph{Shape restrictions:}
The shape of the two result arrays ({\tt *val} and {\tt *pos}) must be
must be obtained from the shape of the source array by deleting
dimension {\tt dim} (see section \ref{shape}).

\paragraph{Alignment restrictions:}
The two result arrays ({\tt *val} and {\tt *pos}) must be aligned to
the source array, {\em with replicated alignment in dimension {\tt
dim}} (see section \ref{alignment}).

\paragraph{Accessibility restrictions:}
The source array and the result arrays
must be accessible (see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt val}, {\tt loc} and {\tt src} arguments are stored in the
schedule as references.  The associated objects must persist for the
lifetime of the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* valDat, int* posDat, T* srcDat)
\end{verbatim}
Arguments are the base addresses for local segments of the result
value, result position, and source arrays.  They should point to
vectors of the locally held elements.

\paragraph{Effect:}
On exit, the value of
\small
\begin{tabbing}
\verb$  val [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim+1}},
                    \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is the minimum value of
\small
\begin{tabbing}
\verb$  src [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim}},
                    x_{\mbox{\tt dim+1}}, \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
across allowed values of $x_{\mbox{\tt dim}}$.  The value of
\small
\begin{tabbing}
\verb$  pos [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim+1}},
                    \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is the smallest $x_{\mbox{\tt dim}}$ value at which this minimum
occurs.

As implied by the replicated alignment of the result arrays,
the results are broadcast in the process dimension associated with 
dimension {\tt dim} of the source array.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values of particular
elements for comparision are generally taken from the nearest copy of
the source element.  The definition of ``nearest'' is implementation
dependent.  Consistent replication of copies in the result array relies
on consistency of copies in the source array.

\paragraph{Overlap restrictions:} In-place updates are not allowed.
Neither of the arrays defined by the pairs {\tt *val}, {\tt valDat} or
{\tt *pos}, {\tt posDat} may have any overlap with
the array defined by the pair {\tt *src}, {\tt srcDat}.

\newpage

\section{class {\tt MinlocDimMsk}}

A {\em masked dimension minimum location schedule} is a communication
schedule for searching, under the control of a mask, for the smallest
elements of a distributed array along one of its dimensions, yielding a
reduced array with rank one less than the source.

A masked dimension minimum location schedule is described by a
collective object with local components of class {\tt MinlocDimMsk}.
The public interface of the {\tt MinlocDimMsk} class is
\small
\begin{verbatim}
  class DAD ;

  template<class T>
  class MinlocDimMsk {
  public :
    MinlocDimMsk(const DAD* val, const DAD* pos,
                 const DAD* src, const int dim, const DAD* msk) ;

    void execute(T* valDat, int* posDat, T* srcDat, int* mskDat) ;
  private :
    ...
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
MinlocDimMsk(const DAD* val, const DAD* pos,
             const DAD* src, const int dim,
             const DAD* msk)
\end{verbatim}
The source array is described by the DAD {\tt *src} and the
array of minimum values is described by the DAD {\tt *val}.  They will
both have elements of type {\tt T}.  The array of minimum locations is
described by the DAD {\tt *pos}.
The search occurs in dimension {\tt dim}.
The mask array is described by the DAD {\tt *msk}.

\paragraph{Value restrictions:}
The value of {\tt dim} must be in the range $0, \ldots, R - 1$ where
$R$ is the rank of the source array.

\paragraph{Type restrictions:}
{\tt T} should be a POD type.  Conventional
binary comparision operators, {\tt >} and {\tt <}, must be defined for
objects of type {\tt T}, and a function {\tt mostpos} must be
overloaded with the entry point
\small
\begin{verbatim}
  void mostpos(T* res) ;
\end{verbatim}
\normalsize
which sets {\tt *res} to the largest allowed value of type {\tt T}.
The Adlib header files define {\tt mostpos} for all the standard
arithmetic types of C++, so these types satisfy all the
requirements for {\tt T}.

\paragraph{Shape restrictions:}
The shape of the two result arrays ({\tt *val} and {\tt *pos}) must be
must be obtained from the shape of the source array by deleting
dimension {\tt dim}.
The mask array must be the same shape as the source array
(see section \ref{shape}).

\paragraph{Alignment restrictions:}
The two result arrays ({\tt *val} and {\tt *pos}) must be aligned to
the source array, {\em with replicated alignment in dimension {\tt
dim}}.  The mask array must be aligned with the source
array (see section \ref{alignment}).

\paragraph{Accessibility restrictions:}
The source and mask arrays and the result arrays
must be accessible (see section \ref{accessibility}).

\paragraph{Argument lifetime:}
The {\tt val}, {\tt loc}, {\tt src} and {\tt msk} arguments are stored
in the schedule as references.  The associated objects must persist for
the lifetime of the constructed schedule.

\subsection{Method}

\begin{verbatim}
execute(T* valDat, int* posDat, T* srcDat, int* mskDat)
\end{verbatim}
Arguments are the base addresses for local segments of the result
value, result position, source, and mask arrays.  They should point to
vectors of the locally held elements.

\paragraph{Effect:}
On exit, the value of
\small
\begin{tabbing}
\verb$  val [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim+1}},
                    \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is the minimum value of
\small
\begin{tabbing}
\verb$  src [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim}},
                    x_{\mbox{\tt dim+1}}, \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
for which
\small
\begin{displaymath}
\mbox{\tt msk [} x_0, \ldots,
x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim}}, x_{\mbox{\tt dim+1}},
\ldots, x_{R - 1} \mbox{\tt ]} \neq 0
\end{displaymath}
\normalsize
over the allowed values of $x_{\mbox{\tt dim}}$.  The value of
\small
\begin{tabbing}
\verb$  pos [$$x_0, \ldots, x_{\mbox{\tt dim-1}}, x_{\mbox{\tt dim+1}},
                    \ldots, x_{R - 1}${\tt ]}
\end{tabbing}
\normalsize
is the smallest $x_{\mbox{\tt dim}}$ value at which this minimum
occurs.

As implied by the replicated alignment of the result arrays,
the results are broadcast in the process dimension associated with 
dimension {\tt dim} of the source array.

\paragraph{Replicated data:} 
If the source array has replicated mapping, values for particular
elements for comparision are generally taken from the nearest copy of
the source element.  The definition of ``nearest'' is implementation
dependent.  Consistent replication of copies in the result array relies
on consistency of copies in the source array.

\paragraph{Overlap restrictions:} In-place updates are not allowed.
Neither of the arrays defined by the pairs {\tt *val}, {\tt valDat} or
{\tt *pos}, {\tt posDat} may have any overlap with either of the arrays
defined by the pairs {\tt *src}, {\tt srcDat} and {\tt *msk}, {\tt
mskDat}

\newpage

\chapter{The ad++ interface\label{ad++}}

\chapter{Distributed loops\label{loops}}

In this chapter we discuss various ways to use the Adlib run-time
technology in translation of distributed loops---loops whose
ranges is partitioned across the active process group.  Typically
such loops are used to access and modify the data in distributed
arrays.  For definiteness, we work in the context of the {\em ad++}
interface.  The techniques can be adapted to other interfaces to the
kernel library.

In ad++, the general {\em overall} construct is a distributed, parallel loop.
It is parametrized by an {\tt Index} object which maintains local
{\em loop state}.
If {\tt x} is a range the {\em overall} construct has the syntax.
\small
\begin{verbatim}
  Index i(x) ;
  OVERALL(i) {
    ...
  } ALLOVER(i) ;
\end{verbatim}
\normalsize
If {\tt x} has extent {\tt N}, this construct can be compared to the
sequential loop
\small
\begin{verbatim}
  int i ;
  for(i = 0 ; i < N ; i++) {
    ...
  }
\end{verbatim}
\normalsize
The difference is that in the {\em overall} construct the
{\tt N} instances of the body of the loop will be partitioned across
the set of active processes, following the mapping of {\tt x}.

The {\tt Index} class is a subclass of {\tt Location}.  Within an {\em overall}
construct parametrized by an {\tt Index} {\tt i}, the {\tt Subcript} component
of {\tt i} is set to the local subscript for the current iteration.
So {\tt i} can be used as an array subscript, as in
\small
\begin{verbatim}
  Array1<float> c(x) ;

  Index i(x) ;
  OVERALL(i) {
    c(i) = ...
  } ALLOVER(i) ;
\end{verbatim}
\normalsize

The general {\em overall} construct has an effect on the active process
group as described in
section \ref{apg}.  If a construct parametrized by {\tt i} appears in
the context of an active process group {\tt p}, the body of the
construct executes in the context of an active process group {\tt p / i}
(recall that {\tt Index} is a subclass of {\tt Location},
so this expression is well-formed.)
The parent range of {\tt i} must be distributed over a dimension
of {\tt p}.

Combining these features, we can give a more complete example
\small
\begin{verbatim}
  Array2<float> a(x, y) ;
  Array1<float> b(y) ;
  ...
  Index i(x), j(y) ;
  OVERALL(i) {
    OVERALL(j) {
      a(i, j) = 2 * b(j) + x.idx(i) ;
    } ALLOVER(j) ;
  } ALLOVER(i) ;
\end{verbatim}
\normalsize
To each element of {\tt a}, this assigns an expression computed from the
aligned value of {\tt b} and the global subscript of {\tt x} (obtained
through {\tt x.idx(i)}.
%\footnote{Sometimes it is necessary
%to know the global subscript of the iteration relative to some parent
%range of {\tt x} (some range of which {\tt x} is a subrange).  This
%value be expressed in terms of {\tt (int) i} using the alignment
%parameters of {\tt x} relative to the parent.  Earlier specifications
%of the library provided special syntax and computational support for
%obtaining parent global subscripts, but this now seems like an
%unnecessary complication.}
All data accesses through legal
subscripting operations are {\em local}.  If a non-local array element
was required, it would take a specific call to a member of the
communication library to access it.

The remainder of this chapter discusses several schemes for translating
the distributed loop.  The first scheme uses the Adlib {\tt Index}
class directly.  The ``translation'' is the trivial one, using only
the C macro preprocessor to replace the {\tt OVERALL} and {\tt ALLOVER}
``keywords''.  The second scheme uses another auxilliary (iterator)
class from the library---{\tt LocBlocksIndex}.  The translation is still
relatively straightforward and has the advantage of being independent
of the level of the parametric range.  The {\tt LocBlocksIndex} mechanism
is quite efficient, and is used extensively in the implementation of
the Adlib communication library.  Finally we describe a scheme which
works directly in terms of the members of {\tt Range} class, without
introducing any auxilliary iterator class.

\clearpage

\section{class {\tt Index}\label{indexes}}

An iterator class, maintaining loop state for simple enumerations
of the elements of a range.

The {\tt Index} class is derived from the {\tt LocBlocksIndex} class
(see section \ref{blockIndex}) which is in turn derived from {\tt Location}.
These classes are used extensively in
Adlib code that has to deal with ranges whose level is not known in advance.
Their use can be avoided if the level of the ranges is
known at compile time, using code transformations described in section
\ref{transKernel}.

The public interface of the {\tt Index} class is
\small
\begin{verbatim}
  class Index : public LocBlocksIndex {
  public :
    Index(Range x) ;

    void begin() ;
    void next() ;
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
Index(Range x)
\end{verbatim}
Create an index object for enumerating the elements of range {\tt x}.

\subsection{Methods}

\begin{verbatim}
begin()
\end{verbatim}
Used to implement the general {\em overall construct}---a distributed
loop.  Begins an enumeration of the elements of the range mapped to the
local process.  On exit from this member, the {\tt Location} component
of the index represents the first element of the local segment of the
range\footnote{Here ``first element'' simply means first in the enumeration.
It {\em does not} necessarily mean the local element with the smallest global
subscript.}.

If {\tt i} is the loop index, the idiom for the loop is
\small
\begin{verbatim}
  for(i.begin() ; i.test() ; i.next())
    S
\end{verbatim}
\normalsize
The member {\tt test()} is inherited from {\tt LocBlocksIndex}
(see section \ref{blockIndex}).

\begin{verbatim}
next()
\end{verbatim}
Move to next element in enumeration.

\subsection{Translation of {\em overall} construct by macro expansion}

The most naive translation of the {\em overall} construct is by using the
standard C preprocessor to expand the macros
\small
\begin{verbatim}
  #define OVERALL(i) for(apgStack.push(&apg), apg.restrict(i.dim), \
                         i.begin() ; i.test() ; i.next())

  #define ALLOVER(i) apgStack.pop(&apg)
\end{verbatim}
\normalsize
Effectively, the loop
\small
\begin{verbatim}
  OVERALL(i) {
    ...
  } ALLOVER(i) ;
\end{verbatim}
\normalsize
becomes
\small
\begin{verbatim}
  apgStack.push(&apg) ;
  apg.restrict(i.dim) ;
  for(i.begin() ; i.test() ; i.next()) {
    ...
  }
  apgStack.pop(&apg) ;
\end{verbatim}
\normalsize
We moved the {\tt apg} manipulations (see section \ref{apg}) outside
the {\em for} construct to improve readability.  The {\tt begin()},
{\tt test()} and {\tt next()} members of {\tt Index} are used in the
{\em for} loop to enumerate the local elements of the range.

This translation is trivial to implement, but it is very inefficient.
First we have the overhead of the calls to the iterator members of {\tt
Index} in every iteration.  Secondly (probably even more seriously)
every array or range subscripting operation in the body of the loop
involves calls to member functions.  The overhead of all these library
calls can easily downgrade performance by an order of magnitude or more
relative to a comparable sequential {\em for} loop.

\clearpage

\section{class {\tt LocBlocksIndex}\label{blockIndex}}

An iterator class, maintaining loop state for enumerations
of the locally held blocks of a range.

The public interface of the {\tt LocBlocksIndex} class is
\small
\begin{verbatim}
  class LocBlocksIndex : public Location, public Block {
  public :
    LocBlocksIndex(Range _x) ;

    void beginLocBlk() ;
    void nextLocBlk() ;

    int test() ;
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
LocBlocksIndex(Range x)
\end{verbatim}
Create an index object for enumerating the local blocks of range {\tt x}.

\subsection{Methods}

\begin{verbatim}
beginLocBlk()
\end{verbatim}
Begins an enumeration of the blocks of the range mapped to the local
process.  On exit from this member, the {\tt Block} componenent of the
{\tt Index} contains the parameters of the first (non-empty) block of
the locally held segment of the range, and the {\tt Location} component
represents the first element (smallest global subscript) in that
block.  ``First block'' simply means first in the enumeration---it does
not guarantee that the block contains smaller subscripts than later
blocks.

If {\tt i} is the loop index, the idiom for the loop is
\small
\begin{verbatim}
  for(i.beginLocBlk() ; i.test() ; i.nextLocBlk())
    S
\end{verbatim}
\normalsize

\begin{verbatim}
nextLocBlk()
\end{verbatim}
Move to next (non-empty) block in the enumeration, updating the {\tt Block} and
{\tt Location} components.
Usage is illustrated in the idiomatic example above.

\begin{verbatim}
test()
\end{verbatim}
After an initial call to {\tt beginLocBlock} and zero or more subsequent
calls to {\tt nextLocBlock}, result of this member is non-zero if there
are still blocks waiting to be enumerated.
Usage is illustrated in the idiomatic example above.

\subsection{Translation of {\em overall} construct using {\tt LocBlocksIndex}}

The class {\tt LocBlocksIndex} is a superclass of {\tt Index} that provides
members to enumerate local {\em blocks} of a range, rather than
individual local elements.  Library functions return
base addresses of the array sections associated with these blocks.
Elements within the block are then enumerated with a simple,
efficient {\em for} loop, computing offsets from base addresses using
linear expressions.  The performance-critical inner loops can be
compiled with high efficiency.  If the block size is large enough,
most of the cost of the library calls is amortized.

{\tt LocBlocksIndex} is a subclass of {\tt Location} {\em and} of {\tt Block}.
The outer level in the translation of a {\em overall} construct
now looks something like
\small
\begin{verbatim}
  LocBlocksIndex i(x) ;

  apgStack.push(&apg) ;
  apg.restrict(i.dim) ;
  for(i.beginLocBlk() ; i.test() ; i.nextLocBlk()) {
    ... deal with block `i'
  }
  apgStack.pop(&apg) ;
\end{verbatim}
\normalsize
In this translation scheme we have an outer loop enumerating the
locally held blocks of the range.  In general this loop is needed
because Adlib supports higher-level distribution
formats like {\em block-cyclic}.  These allow multiple blocks of a
single range to reside on the same processor.  In a context where it is known
in advance that the local process holds a single block (for example, if
the range involved has level 1), the translation scheme given in
the next section allows further optimizations.

In general code to ``deal with block {\tt i}'', takes the form
\small
\begin{verbatim}
    ... precompute some bases and increments for block

    for(int l = 0 ; l < i.count ; l++) {
      ...
    }
\end{verbatim}
\normalsize
Before filling the details of this code, we need
to put the source code into a normalized form.
The body of a {\em overall} construct parametrized by an index {\tt i}
may use {\tt i} in several contexts:
\begin{enumerate}
\item
As a subscript in a local subscripting operation.
\item
In an expression such as {\tt x.idx(i)} used to obtain the global subscript of
the current iteration relative to the index range.
\item
In an expression such as {\tt y.idx(i)} used to obtain the global subscript of
the current iteration relative to some super-range of the index range.
\item
As a scalar subscript in a section subscripting operation.
\item
In a group restriction operation of the form {\tt p / i},
where {\tt p} is some group.
\end{enumerate}
As described in chapter \ref{arrays}, subscripting operations
on arrays can be replaced with lower-level operations on the {\tt Map}
and {\tt Group} classes.  For example, if {\tt a} is an array of {\tt float},
the reference
\small
\begin{verbatim}
  ... a(i, j) ...
\end{verbatim}
\normalsize
can be replaced with
\small
\begin{verbatim}
  float* a_dat  = a.dat() ;
  
  ... a_dat [a.map(0).offset(i) + a.map(1).offset(j)] ...
\end{verbatim}
\normalsize
Of course the inquiries {\tt dat()} and {\tt map()} can be lifted outside
any loop.  Similarly, the section construction
\small
\begin{verbatim}
  ... a.sect(i, y) ...
\end{verbatim}
\normalsize
can be replaced with
\small
\begin{verbatim}
  float* a_dat  = a.dat() ;

  ... Section1<float>(y, a.grp() / i,
                      a.map(1), a_dat + a.map(0).offset(i)) ...
\end{verbatim}
\normalsize
By applying these transformations, and replacing expression of the
form {\tt y.idx(i)} by linear expressions in the template global
subscript {\tt i.tem}, the set of
uses of {\tt i} inside the loop can be reduced to four cases
\begin{enumerate}
\item
As an argument of {\tt Map :: offset}.
\item
In {\tt x.idx(i)}, yielding the global subscript.
\item
In {\tt i.tem}, yielding the template global subscript.
\item
In a group restriction operation of the form {\tt p / i}.
\end{enumerate}
We will deal with these cases in turn.
{\em [Replace follwing enumeration and associated figures with
straight descriptive text.]}

\begin{figure}[p]
{\bf SOURCE:}
\small
\begin{verbatim}
  Range x ;
  Map   u ;

  Index i(x) ;
  OVERALL(i) {
    ... u.offset(i) ...
  } ALLOVER(i) ;
\end{verbatim}
\normalsize
{\bf OUTPUT:}
\small
\begin{verbatim}
  Range x ;
  Map   u ;

  LocBlocksIndex i(x) ;

  apgStack.push(&apg) ;
  apg.restrict(i.dim) ;
  for(i.beginLocBlk() ; i.test() ; i.nextLocBlk()) {
    int u_bas = u.offset(i) ;
    int u_stp = u.step(i.sub_stp) ;

    for(int l = 0 ; l < i.count ; l++) {
      ... u_bas + u_stp * l ...
    }
  }
  apgStack.pop(&apg) ;
\end{verbatim}
\normalsize
\caption{\label{blocksIndexOffset}Translation of offset computation.}
\end{figure}

\begin{figure}[p]
{\bf SOURCE:}
\small
\begin{verbatim}
  Range x ;

  Index i(x) ;
  OVERALL(i) {
    ... x.idx(i) ...
  } ALLOVER(i) ;
\end{verbatim}
\normalsize
{\bf OUTPUT:}
\small
\begin{verbatim}
  Range x ;

  LocBlocksIndex i(x) ;

  apgStack.push(&apg) ;
  apg.restrict(i.dim) ;
  for(i.beginLocBlk() ; i.test() ; i.nextLocBlk()) {
    for(int l = 0 ; l < i.count ; l++) {
      ... i.glb_bas + i.glb_stp * l ...
    }
  }
  apgStack.pop(&apg) ;
\end{verbatim}
\normalsize
\caption{\label{blocksIndexGlobal}Translation of global subscript computation.}
\end{figure}

\begin{figure}[p]
{\bf SOURCE:}
\small
\begin{verbatim}
  Range x ;

  Index i(x) ;
  OVERALL(i) {
    ... p / i ...
  } ALLOVER(i) ;
\end{verbatim}
\normalsize
{\bf OUTPUT:}
\small
\begin{verbatim}
  Range x ;

  LocBlocksIndex i(x) ;

  apgStack.push(&apg) ;
  apg.restrict(i.dim) ;
  for(i.beginLocBlk() ; i.test() ; i.nextLocBlk()) {
    for(int l = 0 ; l < i.count ; l++) {
      ... p / i ...
    }
  }
  apgStack.pop(&apg) ;
\end{verbatim}
\normalsize
\caption{\label{blocksIndexGroup}Translation for computation of group
restriction.}
\end{figure}

\begin{description}

\item{\bf Offset computation.}
Within a particular block the expression {\tt u.offset(i)} can be
rewritten as a linear function of the inner induction variable.
The base for this function is given by the value of {\tt offset}
for the first {\tt Location} of the range, which is the
{\tt Location} component of {\tt i}.  Its increment is returned by the
member {\tt Map :: step}.
Figure \ref{blocksIndexOffset} illustrates the translation.
The call to {\tt offset} has been removed from the inner loop.
A good compiler will generate very efficient code for the linear
expression that replaces it.

\item{\bf Global subscript computation}
is slightly simpler.
The base and increment for this expression are already
contained in the {\tt Block} component of {\tt i}, computed by its
iterator members.
Figure \ref{blocksIndexGlobal} illustrates the translation.

\item{\bf Group restriction} is translated trivially,
as illustrated in figure \ref{blocksIndexGroup}.

\end{description}
Now, consider this example from the preamble to this chapter:
\small
\begin{verbatim}
  Array2<float> a(x, y) ;
  Array1<float> b(y) ;
  ...
  Index i(x), j(y) ;
  OVERALL(i) {
    OVERALL(j) {
      a(i, j) = 2 * b(j) + i ;
    } ALLOVER(j) ;
  } ALLOVER(i) ;
\end{verbatim}
\normalsize
It can be normalized to the form
\small
\begin{verbatim}
  Array2<float> a(x, y) ;
  Array1<float> b(y) ;
  ...
  float* a_dat = a.dat() ;

  float* b_dat = b.dat() ;

  Index i(x), j(y) ;
  OVERALL(i) {
    OVERALL(j) {
      a_dat [a.map(0).offset(i) + a.map(1).offset(j)] =
          b_dat [b.map(0).offset(j)] + x.idx(i) ;
    } ALLOVER(j) ;
  } ALLOVER(i) ;
\end{verbatim}
\normalsize
A translation of the loop nest is given in figure \ref{blocksIndexExample}.

\begin{figure}[p]
\scriptsize
\begin{verbatim}
  LocBlocksIndex i(x), j(y) ;

  apgStack.push(&apg) ;
  apg.restrict(i.dim) ;
  for(i.beginLocBlk() ; i.test() ; i.nextLocBlk()) {
    int a_off0_bas = a.map(0).offset(i) ;
    int a_off0_stp = a.map(0).step(i.sub_stp) ;

    for(int l = 0 ; l < i.count ; l++) {
      apgStack.push(&apg) ;
      apg.restrict(j.dim) ;
      for(j.beginLocBlk() ; j.test() ; j.nextLocBlk()) {
        int a_off1_bas = a.map(1).offset(j) ;
        int a_off1_stp = a.map(1).step(j.sub_stp) ;

        int b_off0_bas = b.map(0).offset(j) ;
        int b_off0_stp = b.map(0).step(j.sub_stp) ;

        for(int m = 0 ; m < j.count ; m++) {
          a_dat [a_off0_bas + a_off0_stp * l +
                 a_off1_bas + a_off1_stp * m] =
                    b_dat [b_off0_bas + b_off0_stp * m] +
                    i.glb_bas + i.glb_stp * l ;
        }
      }
      apgStack.pop(&apg) ;
    }
  }
  apgStack.pop(&apg) ;
\end{verbatim}
\normalsize
\caption{\label{blocksIndexExample}Translation of example.}
\end{figure}

Note that in this example the manipulations of {\tt apg} could have
been omitted, because there are no collective operations inside the
loop that depend on the state of {\tt apg}.

As a final straightforward optimization, when we have perfectly nested
{\em overall} constructs, the loop nesting can be changed to put
all intra-block loops innermost.  In that case the inner loops become
\small
\begin{verbatim}
      for(int l = 0 ; l < i.count ; l++) {
        for(int m = 0 ; m < j.count ; m++) {
          a_dat [a_off0_bas + a_off0_stp * l +
                 a_off1_bas + a_off1_stp * m] =
                    b_dat [b_off0_bas + b_off0_stp * m] +
                    i.glb_bas + i.glb_stp * l ;
        }
      }
\end{verbatim}
\normalsize
All subscript expressions are linear in the loop induction variables,
and we expect very good code generation from these loops.

The translation scheme described in this section is summarized in figure
\ref{blocksIndexSummary}.

\begin{figure}[p]

{\bf SOURCE:}
\small
\begin{verbatim}
  Range x ;
  Map   u ;
  Group p ;

  Index i(x) ;
  OVERALL(i) {
    ... u.offset(i) ...
        x.idx(i) ...
        i.tem ...
        p / i ...
  } ALLOVER(i) ;
\end{verbatim}
\normalsize
{\bf OUTPUT:}
\small
\begin{verbatim}
  Range x ;
  Map   u ;
  Group p ;

  LocBlocksIndex i(x) ;

  apgStack.push(&apg) ;
  apg.restrict(i.dim) ;
  for(i.beginLocBlk() ; i.test() ; i.nextLocBlk()) {
    int u_bas = u.offset(i) ;
    int u_stp = u.step(i.sub_stp) ;

    for(int l = 0 ; l < i.count ; l++) {
      ... u_bas + u_stp * l ...
          i.glb_bas + i.glb_stp * l ...
          i.tem_bas + i.tem_stp * l ...
          p / i ...
    }
  }
  apgStack.pop(&apg) ;
\end{verbatim}
\normalsize

\caption{\label{blocksIndexSummary}Summary of
{\tt LocBlocksIndex}-based translation scheme for {\em overall} construct.}
\end{figure}

\clearpage

\section{Translation using the kernel range\label{transKernel}}

Internally, all the iterator classes depend on the {\tt block} member of
the kernel range.  In this section we show how to use this member
directly for translation of {\em overall} constructs.  The scheme given
here effectively inlines the iterator members used in the previous
translations.  It also inlines the {\tt offset} member of the {\tt Map}
class, in terms of lower level {\tt disp} and {\tt step} members.

To apply the translation scheme described in this section we need some
compile-time knowledge about the level of the range involved.  The scheme
works recursively by expanding a {\em overall} construct in the source
program in terms of a {\em overall} construct for a range one level
lower.  The procedure can (if desired) be continued recursively.  After
one or two stages we get down to a {\em overall} construct for a
level-0 range.  This base case has a different, simpler translation.
For this scheme to be effective we must at least know in advance if the
original parametric range has level 0 (ie, it already represents the
base case).  Ideally we should know the exact level, as a compile-time
constant.

Before applying the translation proper, the input program should be
normalized as discussed in the previous section.
Rather than discuss translation of the three uses of {\tt Index}
individually, we will go straight to the combined summary form,
in the style of figure \ref{blocksIndexSummary}.
For a parametric range of level greater than zero, the translation
summary is given in figure \ref{kernelNon0Summary}.

\begin{figure}[btp]
{\bf SOURCE:}
\small
\begin{verbatim}
  Range x ;
  Map   u ;
  Group p ;

  Index i(x) ;
  OVERALL(i) {
    ... u.offset(i) ...
        x.idx(i) ...
        i.tem ...
        p / i ...
  } ALLOVER(i) ;
\end{verbatim}
\normalsize
{\bf OUTPUT:}
\small
\begin{verbatim}
  Range x ;
  Map   u ;
  Group p ;

  Index i1(x.ker()) ;
  OVERALL(i1) {
    Block i ;
    x.block(i1.tem, &i) ;

    int u_bas = u.disp(i.sub_bas) + u.ker().offset(i1) ;
    int u_stp = u.step(i.sub_stp) ;

    for(int l = 0 ; l < i_count ; l++) {
      ... u_bas + u_stp * l ...
          i.glb_bas + i.glb_stp * l ...
          i.tem_bas + i.tem_stp * l ...
          p / i1 ...
    }
  } ALLOVER(i1) ;
\end{verbatim}
\normalsize

\caption{\label{kernelNon0Summary}Summary of recursive translation
scheme for {\em overall} construct with level greater than 0.}
\end{figure}

The outer loop is a {\em overall} construct parametrized by {\tt
x.ker()}.  The {\tt block} member of {\tt x}
initialize variables describing the block selected by the current
value of the kernel subscript.  These variables correspond exactly with
the fields of the {\tt Block} component of {\tt LocBlocksIndex} (and, of
course, this is exactly how they are computed in the implementation of
that class).

The {\tt offset} operation is expanded in terms of {\tt disp} and
{\tt step} operations, and an {\tt offset} for a kernel
range.  If necessary the transformation can be applied recursively
to eliminate the {\tt offset} function altogether.

The rest of the translation closely follows that of the previous section.

If the parametric range has level 0 (it is a process dimension, or a
subrange of a process dimension) the summary is given in figure
\ref{kernel0Summary}.
%This based on the primitive where construct
%of section \ref{apg}, except that we allow for the fact that
%{\tt x} may be a subrange.

\begin{figure}[btp]
{\bf SOURCE:}
\small
\begin{verbatim}
  Range x ;
  Map   u ;
  Group p ;

  Index i(x) ;
  OVERALL(i) {
    ... u.offset(i) ...
        x.idx(i) ...
        i.tem ...
        p / i ...
  } ALLOVER(i) ;
\end{verbatim}
\normalsize
{\bf OUTPUT:}
\small
\begin{verbatim}
  Range x ;
  Map   u ;
  Group p ;

  Dimension d = x.dim() ;

  apgStack.push(&apg) ;
  apg.restrict(d) ;

  int glb ;
  if(x.local(&glb)) {
    ... 0 ...
        glb ...
        d.crd() ...
        p.restrict(d) ...
  }

  apgStack.pop(&apg) ;
\end{verbatim}
\normalsize

\caption{\label{kernel0Summary}Summary of translation
for {\em overall} construct of level 0.}
\end{figure}

One stage of recursion applied to the example of the previous section
gives the translation in figure \ref{recursiveExample1}.  If ranges
{\tt x} and {\tt y} both have level 1 application of the rule for
translating level 0 constructs then gives the translation in figure
\ref{recursiveExample2}.  Finally, figure \ref{recursiveExampleOpt}
gives an optimized form on the assumption that the original ranges
were level 1.  We can remove the {\tt local} conditional because every
active process must contain an element of the kernel, and replace the
value {\tt i1} initialized by {\tt local} with {\tt d.crd()}.
Three other optimizations do not depend on the assumption of
simplicity: additions of 0 are constant-folded away,
{\tt x.ker().dim()} is replaced with {\tt x.dim()}, and the {\tt apg}
manipulations are removed, because the loop body contains no calls to
collective operations.

\begin{figure}[p]
\scriptsize
\begin{verbatim}
  Index i1(x.ker()), j1(y.ker()) ;
  OVERALL(i1) {
    Block i ;
    x.block(i1.tem, &i) ;

    int a_off0_bas = a.map(0).disp(i.sub_bas) + a.map(0).ker().offset(i1) ;
    int a_off0_stp = a.map(0).step(i.sub_stp) ;

    for(int l = 0 ; l < i.count ; l++) {
      OVERALL(j1) {
        Block j ;
        y.block(j1.tem, &j) ;

        int a_off1_bas = a.map(1).disp(j.sub_bas) + a.map(0).ker().offset(j1) ;
        int a_off1_stp = a.map(1).step(j.sub_stp) ;

        int b_off0_bas = b.map(0).disp(i.sub_bas) + b.map(0).ker().offset(i1) ;
        int b_off0_stp = b.map(0).step(i.sub_stp) ;

        for(int m = 0 ; m < j.count ; m++) {
          a_dat [a_off0_bas + a_off0_stp * l +
                 a_off1_bas + a_off1_stp * m] =
                    b_dat [b_off0_bas + b_off0_stp * m] +
                    i.glb_bas + i.glb_stp * l ;
        }
      } ALLOVER(j1) ;
    }
  } ALLOVER(i1) ;
\end{verbatim}
\normalsize
\caption{\label{recursiveExample1}Translation of example.
Pass 1, assuming ranges {\tt x} and {\tt y}
have level greater than zero.}
\end{figure}

\begin{figure}[p]
\scriptsize
\begin{verbatim}
  Dimension d = x.ker().dim() ;
  apgStack.push(&apg) ;
  apg.restrict(d) ;

  int i1 ;
  if(x.ker().local(&i1) {
    Block i ;
    x.block(i1.tem, &i) ;

    int a_off0_bas = a.map(0).disp(i.sub_bas) + 0 ;
    int a_off0_stp = a.map(0).step(i.sub_stp) ;

    for(int l = 0 ; l < i.count ; l++) {
      Dimension e = y.ker().dim() ;
      apgStack.push(&apg) ;
      apg.restrict(e) ;

      int j1 ;
      if(y.ker().local(&j1) {
        Block j ;
        y.block(j1.tem, &j) ;

        int a_off1_bas = a.map(1).disp(j.sub_bas) + 0 ;
        int a_off1_stp = a.map(1).step(j.sub_stp) ;

        int b_off0_bas = b.map(0).disp(i.sub_bas) + 0 ;
        int b_off0_stp = b.map(0).step(i.sub_stp) ;

        for(int m = 0 ; m < j.count ; m++) {
          a_dat [a_off0_bas + a_off0_stp * l +
                 a_off1_bas + a_off1_stp * m] =
                    b_dat [b_off0_bas + b_off0_stp * m] +
                    i.glb_bas + i.glb_stp * l ;
        }
      }
      apgStack.pop(&apg) ;
    }
  }
  apgStack.pop(&apg) ;
\end{verbatim}
\normalsize
\caption{\label{recursiveExample2}Translation of example.
Pass 2, assuming ranges {\tt x} and {\tt y} have
level 1, so their kernels are level 0.}
\end{figure}

\begin{figure}[p]
\scriptsize
\begin{verbatim}
  Dimension d = x.dim() ;

  Block i ;
  x.block(d.crd(), &i) ;

  int a_off0_bas = a.map(0).disp(i.sub_bas) ;
  int a_off0_stp = a.map(0).step(i.sub_stp) ;

  Dimension e = y.dim() ;

  Block j ;
  y.block(e.crd(), &j) ;

  int a_off1_bas = a.map(1).disp(j.sub_bas) ;
  int a_off1_stp = a.map(1).step(j.sub_stp) ;

  int b_off0_bas = b.map(0).disp(i.sub_bas) ;
  int b_off0_stp = b.map(0).step(i.sub_stp) ;

  for(int l = 0 ; l < i.count ; l++) {
    for(int m = 0 ; m < j.count ; m++) {
      a_dat [a_off0_bas + a_off0_stp * l + a_off1_bas + a_off1_stp * m] =
                b_dat [b_off0_bas + b_off0_stp * m] +
                i.glb_bas + i.glb_stp * l ;
    }
  }
\end{verbatim}
\normalsize
\caption{\label{recursiveExampleOpt}Translation of example.
Optimizations assuming ranges {\tt x} and {\tt y} are level 1.}
\end{figure}

Because level 1 ranges are an important case, figure
\ref{simpleSummary} summarizes the translation of the overall construct
for level 1 parametric ranges.

\begin{figure}[btp]
{\bf SOURCE:}
\small
\begin{verbatim}
  Range x ;
  Map   u ;
  Group p ;

  Index i(x) ;
  OVERALL(i) {
    ... u.offset(i) ...
        x.idx(i) ...
        i.tem ...
        p / i ...
  } ALLOVER(i) ;
\end{verbatim}
\normalsize
{\bf OUTPUT:}
\small
\begin{verbatim}
  Range x ;
  Map   u ;
  Group p ;

  Dimension d = x.dim() ;
  apgStack.push(&apg) ;
  apg.restrict(d) ;

  Block i ;
  x.block(d.crd(), &i) ;

  int u_bas = u.disp(i.sub_bas) ;
  int u_stp = u.step(i.sub_stp) ;

  for(int l = 0 ; l < i.count ; l++) {
    ... u_bas + u_stp * l ...
        i.glb_bas + i.glb_stp * l ...
        i.tem_bas + i.tem_stp * l ...
        p.restrict(d) ...
  }

  apgStack.pop(&apg) ;
\end{verbatim}
\normalsize

\caption{\label{simpleSummary}Summary of translation
for {\em overall} construct with level 1 {\tt x}.}
\end{figure}

\clearpage

\section{Translation using the subkernel range}

{\em [Make this a subsection of the previous section.]}

Occasionally an effective optimization to the translation scheme of the
last section is to use the {\em subkernel} instead of the kernel for
outer loops.  If the parametric range is a small subrange of its parent
template, covering only a small part of its kernel, using the
subkernel may avoid the overhead of inspecting many empty blocks.
See figures \ref{blocksubs} and \ref{cyclicsubs}.

\begin{figure}[bp]
\centerline{\psfig{figure=blocksubker.eps,height=2in}}
\caption{\label{blocksubker}Possible definition of the subkernel
for the range of figure \ref{blocksubs}.}
\end{figure}

\begin{figure}[btp]
\centerline{\psfig{figure=cyclicsubker.eps,height=2in}}
\caption{\label{cyclicsubker}Possible definition of the subkernel
for the range of figure \ref{cyclicsubs}.}
\end{figure}

For a parametric range of level greater than zero, the translation
summary is given in figure \ref{subkernelSummary}.  The kernel
index {\tt j} is now parametrized by {\tt x.subker()} rather than
{\tt x.ker()}.

In practise this optimization is more important in the global block
enumerations of section \ref{allBlocks} than in distributed loops.
As well as providing a useful optimization to this enumeration, the
subkernel imposes an ordering on block enumeration which is important in
certain communication operations (specifically, {\tt remap}).
If the alignment stride of the parent range is negative, the
result for {\tt subker().str()} is also negative.

\begin{figure}[btp]
{\bf SOURCE:}
\small
\begin{verbatim}
  Range x ;
  Map   u ;
  Group p ;

  Index i(x) ;
  OVERALL(i) {
    ... u.offset(i) ...
        x.idx(i) ...
        i.tem ...
        p / i ...
  } ALLOVER(i) ;
\end{verbatim}
\normalsize
{\bf OUTPUT:}
\small
\begin{verbatim}
  Range x ;
  Map   u ;
  Group p ;

  Index i1(x.subker()) ;
  OVERALL(i1) {
    Block i ;
    x.block(i1.tem, &i) ;

    int u_bas = u.disp(i.sub_bas) + u.ker().offset(i1) ;
    int u_stp = u.step(i.sub_stp) ;

    for(int l = 0 ; l < i.count ; l++) {
      ... u_bas + u_stp * l ...
          i.glb_bas + i.glb_stp * l ...
          i.tem_bas + i.tem_stp * l ...
          p / i1 ...
    }
  } ALLOVER(i1) ;
\end{verbatim}
\normalsize

\caption{\label{subkernelSummary}Summary of subkernel-based translation
scheme for {\em overall} construct with level greater than 0.}
\end{figure}

\clearpage

\section{Access to ghost regions}

If an array appearing in a {\em overall} construct has ghost regions,
the subscripts of the array may be shifted by some amount without
violating the restriction that all array element accesses are local.
In ad++ this can be expressed by an idiom like
\small
\begin{verbatim}
  Array1<float> b(x), c(x) ;

  Index i(x) ;
  OVERALL(i) {
    b(i) = c(i + 1) + c(i - 1) ;
  } ALLOVER(i) ;
\end{verbatim}
\normalsize
This assumes that the array {\tt c} has ghost regions of extent
one or more on both sides of its ``physical'' segments.
The particular usage illustrated here is very useful in ``stencil''
computations.  The addition and subtraction operators must be
overloaded on the {\tt Location} class to support this usage.
Possible definitions are
\small
\begin{verbatim}
  inline Location operator+(const Location& i, const int shift) {
    Location shifted(i) ;
    shifted.sub -= shift ;
    return shifted ;
  }

  inline Location operator-(const Location& i, const int shift) {
    Location shifted(i) ;
    shifted.sub += shift ;
    return shifted ;
  }
\end{verbatim}
\normalsize

For definiteness, the translation scheme in figure \ref{shiftOffset}
uses the {\tt blocksIndex}-based style of translation, but the same
techniques can be carried over directly to the recursive style.

A subtle point to note in the definition of the overloaded {\tt +}
and {\tt -} operators is that the shift amount is measured relative to
the underlying {\em template} range.  This is slightly inconvenient if
the array range has a non-trivial alignment stride.  Because this is assumed
to be unusual in typical stencil updates, and because alternatives that
automatically take account of the alignment stride add complexity, the current
definition of the shift was adopted as a pragmatic compromise.  The problem
can be overcome by using the {\tt str} inquiry, if necessary.  If {\tt
x} (ie, {\tt c.rng()}) may have a non-unit alignment stride, the
assignment in the fragment above should be replaced by
\small
\begin{verbatim}
    b(i) = c(i + x.str()) + c(i - x.str()) ;
\end{verbatim}
\normalsize

\begin{figure}[p]
{\bf SOURCE:}
\small
\begin{verbatim}
  Range x ;
  Map   u ;

  Index i(x) ;
  OVERALL(i) {
    ... u.offset(i + s) ...
  } ALLOVER(i) ;
\end{verbatim}
\normalsize
{\bf OUTPUT:}
\small
\begin{verbatim}
  Range x ;
  Map   u ;

  LocBlocksIndex i(x) ;

  apgStack.push(&apg) ;
  apg.restrict(i.dim) ;
  for(i.beginLocBlk() ; i.test() ; i.nextLocBlk()) {
    int u_bas = u.offset(i) + s * u.str() ;
    int u_stp = u.step(i.sub_stp) ;

    for(int l = 0 ; l < i.count ; l++) {
      ... u_bas + u_stp * l ...
    }
  }
  apgStack.pop(&apg) ;
\end{verbatim}
\normalsize
\caption{\label{shiftOffset}Translation of (constant) shifted offset
computation.}
\end{figure}

\clearpage

\section{class {\tt AllBlocksIndex}\label{allBlocks}}

An iterator class, maintaining loop state for enumerations
of all the blocks of a range.

The public interface of the {\tt AllBlocksIndex} class is
\small
\begin{verbatim}
  class AllBlocksIndex : public LocBlocksIndex {
  public :
    AllBlocksIndex(Range _x) ;

    void beginAllBlk() ;
    void nextAllBlk() ;
  } ;
\end{verbatim}
\normalsize

\subsection{Constructor}

\begin{verbatim}
AllBlocksIndex(Range x)
\end{verbatim}
Create an index object for enumerating all blocks of range {\tt x}.

\subsection{Methods}

\begin{verbatim}
beginAllBlk()
\end{verbatim}
Begins an enumeration of all blocks of the range.  On exit from this
member, the {\tt Block} componenent of the {\tt Index} contains the
parameters of the first (non-empty) block of the range, and the {\tt
Location} component represents the first element (smallest global
subscript) in that block.  ``First block'' simply means first in the
enumeration---it does not guarantee that the block contains smaller
subscripts than later blocks.

If {\tt i} is the loop index, the idiom for the loop is
\small
\begin{verbatim}
  for(i.beginAllBlk() ; i.test() ; i.nextAllBlk())
    S
\end{verbatim}
\normalsize
The member {\tt test()} is inherited from {\tt LocBlocksIndex}
(see section \ref{blockIndex}).

\begin{verbatim}
nextAllBlk()
\end{verbatim}
Move to next (non-empty) block in the enumeration, updating the {\tt Block} and
{\tt Location} components.

\subsection{Use of {\tt AllBlocksIndex} in the communication library}

The run-time technology introduced in this chapter for translation of
distributed loops is used extensively in the implementation of the collective
communication library.  In that context, blocks of ranges are usually
more important than individual elements, so use of the {\tt
LocBlocksIndex} iterator is common.

Besides enumeration of locally held blocks, it is sometimes necessary
to enumerate {\em all} blocks of a range---local and non-local.
For example, a data remapping operation defines a map between the
elements of two ranges with different distribution formats.  A local
block in one range maps to a specific subrange of the other.  But
in general this subrange does not correspond to a single block of
the target range---it may be distributed over several processes,
divided into a number of blocks.  If the original block of data is
to be moved to the target array, it must be split into a corresponding
number of data blocks, each sent to the appropriate destination.

{\em All blocks} enumeration resembles the local blocks
enumeration given in section \ref{blockIndex}, but the loop is
started using the {\tt beginAllBlk()} member of {\tt AllBlocksIndex}.
\small
\begin{verbatim}
  AllBlocksIndex i(x) ;
  ...
  for(i.beginAllBlk() ; i.test() ; i.nextAllBlk()) {
    ...
  }
\end{verbatim}
\normalsize
In each iteration, the {\tt crd} field inherited from the {\tt
Location} component of {\tt i} gives the process coordinate of the
remote block, while the fields of the {\tt Block} component define the
subscript range.  If it is necessary to compute memory offsets in the
remote process, this can be done using {\tt offset} and related members
of {\tt Map} in exactly the same way as for a local block.

There is no guarantee that enumeration of the blocks occurs in an
obvious sequential order.  It {\em is} guaranteed that the subsequence
of blocks associated with a single process is enumerated in the same
order as for {\em local blocks} enumeration using {\tt
LocBlocksIndex}---this guarantee is often exploited to ensure message
blocks are sent and received in the same order {\em [need clarification
on this point of ordering]}.

\chapter{Implementation of the communication schedules}

\printindex

\end{document}

% Things to do:
%

