
\documentstyle{article}

\input{psfig} 

\begin{document}

\sloppy

\pagestyle{plain}

\title{{\em Adlib} Reference Manual}

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

\date{\em [In preparation]}

\maketitle

\newpage

\tableofcontents

\newpage

\section{The Range class}

\subsection{Default constructors and copying}

\begin{verbatim}
  Range() ;

  Range(const Range& x) ;

  Range& operator=(const Range& x) ;

  Range :: clone(const Range&) ;

  ~Range() ;
\end{verbatim}
The \verb$Range$ class is implemented as a handle class.  A
\verb$Range$ object contains a single word which is a pointer to a
representation object of type \verb$RangeRep$.

The default constructor for the \verb$Range$ class creates an object
containing a null pointer.

The copy constructor copies the pointer in the parent object to the new
object, and increments a reference count in the representation object.

The assignment operator behaves in a similar way, but also decrements the
reference count of (and deletes, if necessary) any representation object
referenced by the assignment variable prior to the assignment.  The
assignment then overwrites that reference.

The \verb$clone$ member allocates a new representation object and
copies all fields of the parent object into the new object.

The destructor \verb$~Range$ decrements the reference count of (and
deletes, if necessary) any representation object referenced by the
\verb$Range$ object.

\subsection{\label{RangeConstructors}Proper constructors}

\begin{verbatim}
  Range(const int extent) ;

  Range(const int extent, Dimension dim, const Format fmt) ;

  Range(const int extent, Dimension dim, const Format fmt,
        const int blockSize, const int layout = ADLIB) ;

  Range(const int extent, const int base, const int stride,
        Range parent) ;

  Range(const int extent, const int base, Range parent) ;
\end{verbatim}
These functions all create new representation objects and initialise
handle objects referencing them.  In all cases the first
argument is the extent of the range.  The remaining arguments

The first constructor creates a ``collapsed'' range.
The whole of the range is mapped into the local address space.

The second constructor create a range with block or simple cyclic or
``stepped'' block distribution format.  The \verb$fmt$ argument takes one of
the values \verb$BLK$, \verb$CYC$ or \verb$STP$.  Suppose the extent
of the range is \verb$n$ and the extent of the process dimension is
\verb$p$\footnote{In the current implementation, {\tt p} is the {\em
physical} number of processors in the process dimension.  This may or
may not be equal to the extent specified in the {\tt Procs} declaration
that originally created the dimension.  If the specified size of the
process array is larger than the number of active processes, the
actual value of {\tt p} may be smaller than the specified extent.}.

\begin{figure}[btp]
\centerline{\psfig{figure=distribution.eps,height=4in}}
\caption{\label{distribution}Example distribution formats.}
\end{figure}

In {\em block} distribution contiguous blocks of the range of size
\verb$b = [(n + p - 1) / p]$ are allocated to processes, starting from the
first.  When fewer than \verb$b$ elements of the range remain, the
residue is allocated to the current process.  Any further processes
receive no elements.  This distribution format is illustrated for
\verb$n = 17$, \verb$p = 4$ in figure \ref{distribution}(a).  The
constructor call is
\small
\begin{verbatim}
  Range(17, d, BLK)
\end{verbatim}
\normalsize
assuming \verb$d$ is a process dimension of extent 4.

In simple {\em cyclic} distribution, the elements of the range are
allocated one per process, and the range wraps around when all
processes have received an element.  This distribution format is
illustrated in figure \ref{distribution}(b) for the case
\small
\begin{verbatim}
  Range(17, d, CYC)
\end{verbatim}
\normalsize


In {\em stepped} block distribution the first \verb$n mod p$ processes
are assigned \verb$b + 1$ range elements and the remaining processes
are assigned $b$ elements, where \verb$b = [n / p]$ .  This
distribution format is illustrated in figure \ref{distribution}(c)
for the case
\small
\begin{verbatim}
  Range(17, d, STP)
\end{verbatim}
\normalsize

The third constructor creates a range with block or block cyclic
(according to the value of \verb$fmt$)
distribution format, and a user-specified block size.  The
ranges constructed by
\small
\begin{verbatim}
  Range(17, d, BLK, 6)
\end{verbatim}
\normalsize
and
\small
\begin{verbatim}
  Range(17, d, CYC, 3)
\end{verbatim}
\normalsize
are illustrated in figures \ref{distribution}(d) and
\ref{distribution}(e), assuming \verb$d$ is a process dimension of
extent 4.

The optional \verb$layout$ parameter of the last constructor affects the
mapping of array elements into memory.  It will be discussed later.

The final two forms of the \verb$Range$ constructor are used for
constructing derived ranges.  Base and stride are specified for
alignment to some parent range.  In the second form the \verb$stride$
parameter is omitted and it defaults to 1.

Derived ranges can be aligned to parent ranges of any distribution
format.  This is a fundamental requirement for consistency of the
library.  If a new distribution format is to be implemented, one must
also implement ``affine'' alignment to the new distribution format.

\subsection{General inquiry functions}

\begin{verbatim}
  int size() ;

  Dimension dim() ;

  Range prm() ;
\end{verbatim}
The member \verb$size$ returns the extent of the range.  The member
\verb$dim$ returns (a handle object for) the process dimension over
which the range is distributed.  This will be a null handle for
collapsed ranges.  The member \verb$prm$ returns (a copy of) the primitive range
structure from which this range was derived.

\subsection{The {\tt Subscript} record}

\begin{verbatim}
  struct Subscript : public Coord {
    int blk ;
    int sub ;
  } ;
\end{verbatim}
A \verb$Subscript$ is implemented as a simple record containing two
publically accessible data members in addition to the members of
\verb$Coord$.
\verb$blk$ and \verb$sub$ are components of a local subscript.
Their precise interpretation depends on the
implementation of the parent range, and is not strictly prescribed by the
general Adlib framework.  The {\em expected} use is as follows.
\begin{itemize}
\item
A \verb$Subscript$ always defines a location within a parent primitive
range (in HPF terms, it is a subscript into a template).
\item
\verb$sub$ is an offset within a local block---for simple distribution
formats it is ``the'' local subscript.
\item
\verb$blk$ is intended for use in
``multi-block'' distribution formats such as {\em block cyclic}
distribution.  It identifies a particular local block, of which there
may be several.  For simple distribution formats with only a single
block per process, the \verb$blk$ field is unused.
\end{itemize}


%The members \verb$at$ and \verb$ta$ are used to implement the
%Adlib {\em at} construct through the idiom
%\small
%\begin{verbatim}
%  if(s.at()) {
%    ...
%  } s.ta()
%\end{verbatim}
%\normalsize
%Their implementation is
%\small
%\begin{verbatim}
%  inline int Subscript :: at() {
%    if(dim) {
%      apg->where(dim) ;
%      return dim->crd() == crd ;
%    }
%    else return 1 ;
%  }
%
%  inline void Subscript :: ta() {
%    if(dim)
%      apg->erewh(dim) ;
%  }
%\end{verbatim}
%\normalsize
%[THIS WILL PROBABLY CHANGE WHEN THE PROCESS GROUP INTERFACE IS
%DOCUMENTED]

A subscript record will normally be initialised by a member
of the \verb$Range$ class.  Although its fields are publically
accessible, it is not normally necessary to read or write
them directly.

\subsection{\label{rangeSubs}Subscripting a {\tt Range} object}

\begin{verbatim}
  int operator()(Subscript& s) ;

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

The operator \verb$operator()(Subscript& s)$ takes a local subscript
and returns the corresponding global subscript into this range.
Its argument must be aligned to an element of the range for this
operation to be legal.  Typically, the argument was originally
created from this range, or from some range derived from this range.

The \verb$operator()(const int i)$ takes a global subscript into this
range, and returns a reference to a correponding local subscript.
For collapsed distribution formats the \verb$dim$ field in the returned
subscript is null.
Because the result of this call is a reference, there is an issue about
persistence of the referenced object.  In fact there is a
\verb$Subscript$ object inside the representation of every \verb$Range$
object.  The subscripting call modifies this object and returns a
reference to it.  The reference remains valid until the next
operation which might change the internal state of the range used to
construct it---a subsequent subscripting operation or one of the
iterator operations described in the following sections.

In normal usage the transitory nature of the returned reference does
not seem to cause problems, and we avoid the overhead of allocating a
new record whenever a local subscript is computed in an expression.  If
a persistent local subscript object is required, use the \verb$Subscript$
copy constructor explicitly to create one.

\subsection{High level {\em where} iterators}

\begin{verbatim}
  void where() ;
  int  test()  ;
  void next()  ;
  void erewh() ;

  operator int() ;
  operator Subscript&() ;
\end{verbatim}
The four members \verb$where$, \verb$test$, \verb$next$ and \verb$erewh$
are intended for use in the idiom
\small
\begin{verbatim}
  for(x.where() ; x.test() ; x.next()) {
    ...
  } x.erewh() ;
\end{verbatim}
\normalsize
or in some strictly equivalent looping construct.  Between the
calls to \verb$where()$ and \verb$erewh()$ the range \verb$x$
is ``activated as an iterator''.

     The semantics of the {\em where} construct has been explained
in the introductory section of this document.  In summary
\begin{itemize}
\item
A {\em where} loop over \verb$x$ can be executed provided \verb$x$ is
distributed over a dimension of the active process group, \verb$p$.
\item
The body of the loop executes once for every element of the range held
on the local processor.
\item
While a range is activated as a {\em where} iterator, the type
conversions \verb$operator int()$ and \verb$operator Subscript&()$
allow the range to be coerced to the global or local subscript
associated with the current iteration.  As a rule the {\em only}
appearance of a loop range inside the loop body will be in coercions.
\item
During an iteration of the loop, the active process group is
reduced to \verb$p / x$, assuming the coercion from range to
\verb$Subscript$ described above.
\end{itemize}

     Two common ambiguities associated with range-to-subscript cooercions
need to be resolved.
\begin{itemize}
\item
{\em If a range activated as an iterator is passed as an argument
to a section constructor, it will, in effect, be cooerced to
a local subscript.}

The alternative would be to intepret the range ``uncoerced''.  This
would construct a section whose a process group includes the dimension
over which \verb$x$ is distributed.  That violates the constraint that
the process group of a newly created section must be contained in the
active process group, because this dimension is deleted from the
active process group inside the loop.

\item
{\em If a range activated as an iterator is passed to a subscripting
operation on another range, it will, in effect, be cooerced to
a local subscript.}

It will occasionally be necessary to subscript a range \verb$y$
inside the where construct.
There is an ambiguity in the subscripting operations of the previous
section.  The operation
\small
\begin{verbatim}
  y(x)
\end{verbatim}
\normalsize
could be interpretted as
\small
\begin{verbatim}
  y((Subscript&) x)
\end{verbatim}
\normalsize
or as
\small
\begin{verbatim}
  y((int) x)
\end{verbatim}
\normalsize
The first interpretation is legal if \verb$y$ is a parent range of
\verb$x$; it yields the global subscript in \verb$y$ associated with
the current iteration of the loop.  This is a likely requirement,
because often we often need to perform a distributed loop over some
subrange, and may want to access the global index values of the parent
range.  The second interpretation is legal, but less obviously useful.
So the first interpretation is the default.
\end{itemize}

\subsection{\label{lowLoops}Lower level iterators}

\begin{verbatim}
  int blockLo()   ;
  int blockHi()   ;
  int blockStep() ;

  int blockCount() ;

  void locBlocksEnum() ;
  int  locBlocksTest() ;
  void locBlocksNext() ;

  void allBlocksEnum() ;
  int  allBlocksTest() ;
  void allBlocksNext() ;

  void blockNext() ;

  int  at() ;
  void ta() ;

  int step(Range x) ;
\end{verbatim}
These operations are used for optimizing \verb$where$ constructs,
and in the implementation of various collective communication operaitons.

Discussion will be deferred to section \ref{optimization}.

\subsection{Support for array construction}

\subsection{Support for section construction}

\begin{verbatim}
  Range operator()(const int extent, const int base,
                   const int stride) ;
  Range operator()(const int extent, const int base) ;

  Range(const Subscript& i) ;

  int isScalar() ;
\end{verbatim}
The first two operators simply provide syntactic sugar for construction
of derived ranges.  The expressions
\small
\begin{verbatim}
  x(e, b, s)

  x(e, b)
\end{verbatim}
\normalsize
are equivalent to
\small
\begin{verbatim}
  Range(e, b, s, x)

  Range(e, b, x)
\end{verbatim}
\normalsize
They provide a convenient syntax for ``triplet subscripts'' of
array sections.

The third function is a new constructor, used to implement a type
conversion which ``wraps up'' a \verb$Subscript$ as a \verb$Range$.  This
is purely a device to allow scalar subscripts to be passed to the
section constructor functions.  These functions expect \verb$Range$
structures as arguments.

A \verb$Range$ object created in this way has very limited functionality.
The only member functions that can meaningfully applied to it are
\verb$isScalar$ and coercion back to a \verb$Subscript$.

The member \verb$isScalar$ is used inside section constructor
functions to determine whether a subscript argument (formally
a \verb$Range$) is to be treated as a proper range,
or as a scalar subscript.  The two cases in which it should
coerced to a \verb$Subscript$ are:
\begin{enumerate}
\item
The original argument really was a \verb$Subscript$, wrapped up in the way
described in the preceding paragraphs.
\item
The argument was a range structure activated as an iterator.
\end{enumerate}
In these two situations \verb$isScalar$ returns a non-zero value.
Otherwise it returns zero.

\section{The {\tt Stride} class}

     This section describes the public interface of the \verb$Stride$
class.

     The \verb$Stride$ is a support class for construction of distributed
arrays.  It provides a mapping from local subscripts within a range to
offsets in memory.  The most primitive distributed array---a distributed
vector---can be parameterized by three entities
\begin{enumerate}
\item
A \verb$Range$ object, describing the range of subscripts for the vector.
\item
A base address in memory
\item
A \verb$Stride$ object, describing the layout of array elements in memory.
\end{enumerate}

     A \verb$Stride$ object typically has a rather simple
structure---for some kinds of array range it may contain a single
integer---the physical memory displacement between consecutive array
elements.  In general, for multi-block array ranges or array ranges
with strided alignments, it may involve a few more parameters.

     It follows that the representation of a \verb$Stride$ object
depends on the representation of the associated \verb$Range$ object for
the array.

\subsection{Default constructors and copying}
\begin{verbatim}
  Stride() ;

  Stride(const Stride& x) ;

  Stride& operator=(const Stride& x) ;

  ~Stride() ;
\end{verbatim}
The \verb$Stride$ class is implemented as a handle class.  A
\verb$Stride$ object contains a single word which is a pointer to a
representation object of type \verb$StrideRep$.  The \verb$StrideRep$
class is at the base of a hierarchy of representations.  In general
each subclass of \verb$RangeRep$ may be associated with its own variant
of \verb$StrideRep$.

The default constructor for the \verb$Stride$ class creates an object
containing a null pointer.

The copy constructor copies the pointer in the parent object to the new
object, and increments a reference count in the representation object.

The assignemnt operator behaves similarly, but will also decrement the
reference count of (and delete, if necessary) any representation object
referenced by the assignment variable prior to the assignment.  The
assignment then overwrites that reference.

The destructor \verb$~Stride$ decrements the reference count of (and
deletes, if necessary) any representation object referenced by the
\verb$Range$ object.

\subsection{Proper constructors}

\begin{verbatim}
  Stride Range :: vector(int* dataLen) ;

  Stride Range :: promote(const int oldStr) ;
\end{verbatim}
(These ``constructors'' are implemented as member functions of the
\verb$Range$ class; logically they are constructors for the
\verb$Stride$ class.)  The first constructor is the ``normal''
constructor for a \verb$Stride$ object.  Its parameter is a
``value-result'' argument.  Before the call the integer referenced by
\verb$dataLen$ should be set to the size of a individual item or
element in the vector to be parameterized.  On exit, it is overwritten
with the total amount of space which must be allocated locally to hold
the vector, in the same units as the input value.

The \verb$vector$ constructor does not, and can not, sensibly, allocate
any memory for the array.  However it {\em does} define how much memory
is to be allocated.  An important property of the constructor is that
it should direct every processor to allocate the same amount of space.
Some processors may hold fewer elements from the index range, but all
processors allocate space enough to hold the maximum possible of number
of elements.

This has a couple of useful consequences, one being that all processes
holding portions of a multi-dimensional distributed array contain
identical stride structures.  This facilitates access to remotely
held array elements.

A typical usage of the constructor is in defining the layout for a
multi-dimensional array of rank \verb$rank$ and type \verb$T$.  Suppose the
ranges for the array are defined in a vector of \verb$Range$ structures
called \verb$rngs$.  We need to initialize a corresponding vector of
\verb$Stride$ structures called \verb$strs$, then allocate space for
the elements in a \verb$char*$ variable called \verb$data$.  This could
be done as
follows
\small
\begin{verbatim}
  int size = sizeof(T) ;
  for(int i = 0 ; i < rank ; i++)
    strs [i] = (rngs [i]).vector(&size) ;
  data = new char [size] ;
\end{verbatim}
\normalsize
This leads to a layout in which the first dimension is
``most-rapidly-varying'' in memory (as in Fortran).  The reverse
convention can be obtained by reversing the order of the calls to the
constructor.

The second constructor, \verb$promote$, is more specialized.  It is
used in array promotions which give a distributed view of replicated,
sequential arrays.  The argument is the memory stride of the original
sequential array.

[MOVE (PART OF) THE ABOVE INTO THE SECTION ABOUT `Range' SUPPORT FOR
CONSTRUCTION OF ARRAYS].

\subsection{Memory offsets}

\begin{verbatim}
  int offset(Subscript& subs) ;

  int step(Range x) ;
\end{verbatim}
The principal operation on a \verb$Stride$ object, apart from its
constructor, is the computation of the memory offset for a given
\verb$Subscript$.  The argument of \verb$offset$ must be aligned with
some element of the range used to construct the stride.  Its result
is the memory offset generated by the subscript, in the same units
used for the \verb$dataLen$ argument of the constructor.

The \verb$step$ member is akin to the \verb$step$ member of the
\verb$Range$ class.  It is designed for the optimisation of {\em where}
constructs.  We will give a small example of manipulation of a
distributed vector in a {\em where} construct.

Suppose we create a vector parametrised by range \verb$x$, stride
\verb$vec$ and base address \verb$data$ as follows
\small
\begin{verbatim}
    float* data ;
    int size = 1 ;
    Stride vec = x.vector(&size) ;
    data = new float [size] ;
\end{verbatim}
\normalsize
This vector might be initialised in the following {\em where} construct
\small
\begin{verbatim}
    for(x.where() ; x.test() ; x.next()) {
      data [vec.offset(x)] = x * x ;
    } x.erewh() ;
\end{verbatim}
\normalsize
We want to optimise this loop along the lines described in section
\ref{lowLoops}.  The first stage is to transform the loop to
\small
\begin{verbatim}
    x.at() ;
    for(x.locBlocksEnum() ; x.locBlocksTest() ; x.locBlocksNext()) {
      const int l = x.blockLo() ;
      const int u = x.blockHi()  ;
      const int s = x.blockStep()  ;
      int i ;
      for(i = l ; i <= u ; i += s) {
        data [vec.offset(x)] = i * i ;
        x.blockNext() ;
      }
    }
    x.ta() ;
\end{verbatim}
\normalsize
Now, using the \verb$Stride :: step$ member and the fact that the coercion
of \verb$x$ to an integer will just yield \verb$i$, the inner loop can
be optimized to
\small
\begin{verbatim}
      int data_vec = data + vec.offset(x) ;
      const int step_vec = vec.step(x) ;
      for(i = l ; i <= u ; i += s) {
        *data_vec = i * i ;
        data_vec += step_vec ;
      }
\end{verbatim}
\normalsize
The call to \verb$x.blockNext()$ was eliminated; \verb$x$ is no longer
used inside the loop and its state needn't be updated.  The outer calls
to \verb$at$ and \verb$ta$ can also be eliminated, because there are no
function calls in the loop which could depend on the state of the
active process group.

Note that in normal usage {\em the iterator argument of \verb$step$ is
identical to, or is a range derived from} the range used to construct
the subscripted \verb$Stride$.

\section{The {\tt RangeRep} class}

The \verb$Range$ class contains just one data member---a pointer to a
representation object from the class \verb$RangeRep$.  Most of the
member functions of \verb$Range$ are inline functions which
dispatch the required operation to the representation object.
The definition of the \verb$Range$ class looks something like this:
\small
\begin{verbatim}
  class Range {
  public :
    ... constructors
  
    // Inquiries
  
    int size() {return rep->size() ;}
  
    Dimension* dim() {return rep->dim() ; }
  
    // Subscripting
  
    int operator()(Subscript& s) {
      return rep->subs(&s) ;
    }
  
    Subscript& operator()(const int i) {
      return *rep->subs(i) ;
    }
  
    operator int() {return rep->subs() ; }
    operator Subscript&() {return *rep ; }
  
    // `where' iterators
  
    void where() {rep->where() ; }
    int  test()  {return rep->test() ; }
    void next()  {rep->next() ; }
    void erewh() {rep->erewh() ; }
  
    // Lower level iterations...
  
    void locBlocksEnum() {rep->locBlocksEnum() ; }
    int  locBlocksTest() {return rep->locBlocksTest() ; }
    void locBlocksNext() {rep->locBlocksNext() ; }
  
    void allBlocksEnum() {rep->allBlocksEnum() ; }
    int  allBlocksTest() {return rep->allBlocksTest() ; }
    void allBlocksNext() {rep->allBlocksNext() ; }
  
    int blockBase() {return rep->blockLo() ; }
    int blockCount() {return rep->blockCount() ; }
    int blockLo() {return rep->blockLo() ; }
    int blockHi() {return rep->blockHi() ; }
    int blockStep() {return rep->blockStep() ; }

    void blockNext() {rep->blockNext() ; }
  
    int step(Range x) {return rep->step(x.rep) ; }
  
    int at() {return rep->at() ; }
    void ta() {rep->ta() ; }
  
    int isScalar() {return rep->isScalar() ; }
  
    ...
  private :
    RangeRep* rep ;
  } ;
\end{verbatim}
\normalsize

The class \verb$RangeRep$ is an abstract class at the base of a
hierarchy.  Its concrete subclasses realise the various distribution
and alignment formats supported for Adlib \verb$Range$ objects.
The \verb$Range$ constructors, omitted above, will invoke constructors for
the derived classes.

Several of the member functions of \verb$RangeRep$ are defined as
(inline) functions on the base class.  These include the inquiry
functions and the {\em where} iterators.  The remaining functions
are virtual; they must be defined within the concrete subclasses.

The definition of the \verb$RangeRep$ base class looks something
like this:
\small
\begin{verbatim}
  class RangeRep : public Subscript {
  friend class Range ;
  friend class DerivedStrideRep ;          // Accesses `count'
  public :
    RangeRep() : scalar(0) {}
    RangeRep(const Subscript& i) : Subscript(i), scalar(1) {}
  
    virtual ~RangeRep() {}
  
    int size() const {return extent ; }
  
    int subs() const {return i ; }
    int isScalar() const {return scalar ; }
  
    // `where' iterators
  
    void where() ;
    int  test()  ;
    void next()  ;
    void erewh() ;
  
    int at() ;
    void ta() ;
  
    ... virtual functions
  protected :
    int extent ;
  private :
    int i ;
    int scalar ;
  
    int count ;
  } ;
\end{verbatim}
\normalsize
As promised, the representation of a range includes a subscript
record---\verb$RangeRep$ is derived from \verb$Subscript$ (this
explains why the coercion operator
\verb$operator Range :: Subscript&()$ just returns a reference to the
representation object).

The value of the private member \verb$scalar$ defines the result of
\verb$isScalar$.  The private member \verb$i$ is updated by the
{\em where} iterators, and defines the result of the coercion
\verb$operator Range :: int()$ throug \verb$RangeRep :: subs()$.  The
private member \verb$count$ is a reference count for the representation
object: it is updated by the constructor and destructor members of the
handle class.

The member functions \verb$at$ and \verb$ta$ are defined by
\small
\begin{verbatim}
  inline int RangeRep :: at() {
    scalar = 1 ;
    return Subscript :: at() ;
  }
  
  inline void RangeRep :: ta() {
    Subscript :: ta() ;
    scalar = 0 ;
  }
\end{verbatim}
\normalsize
and the {\em where} iterators by
\small
\begin{verbatim}
  inline void RangeRep :: where() {
    at() ;
    locBlocksEnum() ;
    i = blockLo() ;
  }
  
  inline int RangeRep :: test() {
    return locBlocksTest() ;
  }
  
  inline void RangeRep :: next() {
    blockNext() ;
    i += blockStep() ;
    if(i > blockHi()) {
      locBlocksNext() ;
      i = blockLo() ;
    }
  }
  
  inline void RangeRep :: erewh() {
    ta() ;
  }
\end{verbatim}
\normalsize

The only data member of \verb$RangeRep$ relevant or accessible to
derived classes is the protected member \verb$extent$, the extent of
the range.

The remainder of this section describes the virtual members of
\verb$RangeRep$, which must be defined in the derived classes.

\subsection{Subscripting a {\tt RangeRep} object}

\begin{verbatim}
  virtual Subscript* subs(const int i) ;

  virtual int subs(Subscript* s) ;
\end{verbatim}
These are the implementation-level counterparts of the address-translation
operators on the \verb$Range$ class.  The convert a global index
to a \verb$Subscript$ and vice versa.

\subsection{Lower level iterators}

\begin{verbatim}
  virtual int blockLo()   ;
  virtual int blockHi()   ;
  virtual int blockStep() ;

  virtual int blockCount() ;

  virtual void locBlocksEnum() ;
  virtual int  locBlocksTest() ;
  virtual void locBlocksNext() ;

  virtual void allBlocksEnum() ;
  virtual int  allBlocksTest() ;
  virtual void allBlocksNext() ;

  virtual void blockNext() ;

  virtual void blockStepPrim() ;

  virtual int step(RangeRep* x) ;
\end{verbatim}
These are the implementation-level counterparts of the ``lower level
iterator'' functions on the \verb$Range$ class.

     The function \verb$blockStepPrim$ has no counterpart in
the higher level \verb$Range$ class.  It is similar to \verb$blockStep$
but returns the step in the {\em primitive} range.  In other words
satisfies
\small
\begin{verbatim}
  blockStepPrim() == s * blockStep()
\end{verbatim}
\normalsize
where \verb$s$ is the alignment stride of the range, or one for a
primitive range.  This function is needed to implement the \verb$step$
members of \verb$RangeRep$ and \verb$StrideRep$.  We could have
provided an inquiry function to return the alignment stride of a range,
and used the above formula directly.  It happens that the strides of
external ranges are only ever used in this combination, so we save a
function call by putting this computation inside \verb$blockStepPrim$.

     As an example, the implementation of \verb$step$ on a concrete
\verb$RangeRep$ class describing a primitive range is invariably just
\small
\begin{verbatim}
  int step(RangeRep* x) {
    return x->blockStepPrim() ;
  }
\end{verbatim}
\normalsize
whereas on a \verb$RangeRep$ which has an alignment stride
\verb$stride$ it is
\small
\begin{verbatim}
  int step(RangeRep* x) {
    return x->blockStepPrim() / stride ;
  }
\end{verbatim}
\normalsize
Remember that the iterator argument of \verb$step$ is normally a
subrange of the subscripted range.  Consequently \verb$x.stride$ is a
multiple of \verb$stride$.  Since \verb$x->blockStepPrim()$ is
certainly a multiple of \verb$x.stride$, the division above yields a
whole-number result.

\subsection{Miscellaneous constructor functions}

\begin{verbatim}
  virtual RangeRep* alignedRangeRep(const int extent,
                                    const int base,
                                    const int stride) ;

  virtual StrideRep* vector(int* dataLen) ;
\end{verbatim}
The function \verb$alignedRangeRep$ creates a derived range.
The implementation of the \verb$Range$ constructor for a derived
range is just
\small
\begin{verbatim}
  Range(const int extent, const int base, const int stride,
        Range parent) {
    rep = parent.rep->alignedRangeRep(extent, base, stride) ;
    rep->count = 1 ;
  }
\end{verbatim}
\normalsize
(As well as creating the \verb$RangeRep$ object, this constructor
initializes its reference count).

The function \verb$vector$ is the representation-level counterpart of
the \verb$Range :: vector$.  It creates a \verb$StrideRep$ object
to describe the memory layout of a vector distributed over the range.

\subsection{The {\tt RangeRep} hierarchy}

The \verb$RangeRep$ hierarchy as currently implemented is illustrated
in figure \ref{RangeRep}.

\begin{figure}[btp]
\centerline{\psfig{figure=RangeRep.eps,height=6in}}
\caption{\label{RangeRep}The {\tt RangeRep} hierarchy.}
\end{figure}

\verb$RangeRep$ base class is a degenerate case.  Its only direct use
(other than as a base class) is to implement the \verb$Range$ wrapper
for subscripts, returned by the promotion from \verb$Subscript$ to
\verb$Range$.  This conversion is provided to support scalar
subscripting in array sections.

The five immediate subclasses of \verb$RangeRep$ represent the five
distribution formats described in section \ref{RangeConstructors}.
Each of these classes in turn has a subclass representing
a range aligned to the directly distributed ranges.

Finally, the subclass \verb$BlockCyclicAlignedRangeRep$ has a further
subclass: \verb$ADAPTRangeRep$.  This subclass is used in the the SHPF
translation system.  The ADAPT translation tool lays out memory for
aligned block-cyclic arrays in a slightly different way to the default
Adlib scheme.  The new subclass overrides the \verb$vector$ member,
which defines this memory arrangement.  This example illustrates how
one can sometimes use inheritance to tailor Adlib to different
applications.  The \verb$StepRangeRep$ branch is another example---it
was introduced to support a \verb$C*$ translator.

\section{The {\tt StrideRep} class}

The \verb$Stride$ class contains just one data member---a pointer to a
representation object from the class \verb$StrideRep$.
The member functions of \verb$Stride$ are inline functions which
dispatch the required operation to the representation object.
The definition of the \verb$Stride$ class looks like this:
\small
\begin{verbatim}
  class Stride {
  public :
    Stride() : rep(0) {}

    ... copy constructor, assignment, destructor

    int offset(Subscript& subs) {
      return rep ? rep->offset(&subs) : 0 ;
    }
    int step(Range x) {
      return rep ? rep->step(x.rep) : 0 ;
    }
  private :
    StrideRep* rep ;
  } ;
\end{verbatim}
\normalsize
The default constructor creates a null stride.  The \verb$offset$
member returns 0 for a null stride, or dispatches the call to
the representation object of type \verb$StrideRep$ for a non-null stride.
Non-null strides are created by members of the \verb$Range$
class with which the stride is associated.

Null strides are used in certain array promotions, to simulate
replication of values in particular dimensions.

\subsection{Memory offsets}

\begin{verbatim}
  int offset(Subscript* subs) ;

  int step(RangeRep* x) ;
\end{verbatim}
These are representation-level counterparts of the \verb$offset$
and \verb$step$ members of the \verb$Stride$ class.

\subsection{The {\tt StrideRep} hierarchy}

The \verb$StrideRep$ hierarchy as currently implemented is illustrated
in figure \ref{StrideRep}.

\begin{figure}[btp]
\centerline{\psfig{figure=StrideRep.eps,height=6in}}
\caption{\label{StrideRep}The {\tt StrideRep} hierarchy.}
\end{figure}

There is a \verb$StrideRep$ subclass associated most (but not all)
of the \verb$RangeRep$ subclasses (in some cases the \verb$StrideRep$
associated with a parent \verb$RangeRep$ may be adequate).

\verb$PromoteStrideRep$ is a special case.  It is the representation
object for a stride returned by the \verb$Range :: promote$
``constructor''.

\section{Optimization}

All supported distribution formats have the property that the local
segment of a range consists of zero or more blocks of elements.
A block contains a set of regularly spaced global index values.
If a ``current block'' is defined (see below), the members
\verb$blockLo$, \verb$blockHi$ and \verb$blockStep$ define
the global index sub-range for this block, as follows.  Suppose
\small
\begin{verbatim}
  l = x.blockLo()
  u = x.blockHi()
  s = x.blockStep()
\end{verbatim}
\normalsize
then the global index values in the current block of \verb$x$ are
\small
\begin{verbatim}
  l, l + s, l + 2s, ..., u
\end{verbatim}
\normalsize
The function \verb$blockCount$ will returns the value \verb$(u - l)/s + 1$.

The result of \verb$blockCount()$ is always {\em greater than zero}.
If a particular processor contains no elements from a range, this is
flagged by the absence of blocks from the processor, not by the
presence of empty blocks.

There are two sets of iterator functions for enumerating the blocks
of a range: the ``\verb$locBlock$'' iterators and the ``\verb$allBlock$''
iterators.  As the names suggest, the \verb$locBlock$ functions
enumerate all locally held blocks of a range.  The \verb$allBlock$
functions enumerate {\em all} blocks of a range, including blocks held
non-locally.  They are intended for use in the idioms
\small
\begin{verbatim}
  for(x.locBlocksEnum() ; x.locBlocksTest() ; x.locBlocksNext()) {
    ...
  }

  for(x.allBlocksEnum() ; x.allBlocksTest() ; x.allBlocksNext()) {
    ...
  }
\end{verbatim}
\normalsize
or in some strictly equivalent looping constructs.  During an iteration
of the loops, one particular block is current.  Its parameters can be
determined by the inquiry functions introduced above.

The iterator functions set the \verb$Subscript$ record in the range
representation to point to the first element of the block.  A coercion
of the range to a \verb$Subscript&$ returns this value unless it is
explicitly changed inside the loop body.  To support implementation
of {\em where} iterators the function \verb$blockNext$ shifts
internal \verb$Subscript$ state one place up in the block.

Note that the coercion of a \verb$Range$ to an \verb$int$ is not
defined inside the low-level iterators.  Definition of this
coercion is peculiar to {\em where} iterators.

Two guarantees are provided on the order of enumeration of blocks:
\begin{enumerate}
\item
For a particular range structure, \verb$allBlocks$ loops
enumerate blocks in the same order on every processor.
\item
The blocks for an individual processor are interleaved in a
\verb$allBlocks$ enumeration in the same order in which they are
appear in a \verb$locBlocks$ enumeration on that processor.
\end{enumerate}
The second guarantee {\em does not} require that the blocks for a single
processor are consecutive in a \verb$allBlocks$ enumeration.
Also note that this guarantee is only contentful for multi-block
distribution formats---ie formats where a single processor may contain
more than one block

The \verb$locBlocks$ iterators enable optimisation of \verb$where$
constructs.  The fragment
\small
\begin{verbatim}
  for(x.where() ; x.test() ; x.next()) {
    ...
  } x.erewh() ;
\end{verbatim}
\normalsize
can be replaced by
\small
\begin{verbatim}
  x.at() ;
  for(x.locBlocksEnum() ; x.locBlocksTest() ; x.locBlocksNext()) {
    const int l = x.blockLo()   ;
    const int u = x.blockHi()   ;
    const int s = x.blockStep() ;
    for(int i = l ; i <= u ; i += s) {
      ...
      x.blockNext() ;
    }
  }
  x.ta() ;
\end{verbatim}
\normalsize
This transformation only requires one change in the elided code.
Because the low-level iterators do not define the coercion of
the range to \verb$int$, any such coercion should be replaced
by the value \verb$i$ of the inner loop index.

The \verb$at$ and \verb$ta$ members effect the changes on the active
process group necessary to implement a \verb$where$ construct properly,
and the other operations have been described above.

This is still not a fully optimized translation approach.  More
substantial gains are possible by further alterations to the body of
the loop.  Coercions to \verb$Subscript$ can be eliminated according to
context.  As a simple example suppose the body of the loop contains the
expression \verb$y(x)$, where \verb$y$ is some parent range of
\verb$x$.  The member function \verb$step$ returns the step of global
index values for this range associated with the current block of
\verb$y$.  So the inner loop can be replaced by
\small
\begin{verbatim}
    int i_y = y(x) ;
    const int step_y = y.step(x) ;
    for(i = b, j = 0 ; j < e ; i += s, j++) {
      ...
      i_y += step_y ;
      x.blockNext() ;
    }
\end{verbatim}
\normalsize
with appearances of \verb$y(x)$ in the elided code replaced by just
\verb$i_y$.

We note that in normal usage {\em the iterator argument of
\verb$step$ is a range derived from} the subscripted range.

In later sections similar techniques will be introduced to eliminate
{\em all} explicit uses of \verb$Subscript$ in the inner loop, enabling
highly efficient translation of the \verb$where$ construct.

Other optimisations are possible:
\begin{itemize}
\item
If it is known that a particular range does not have a multi-block
distribution, the enumeration of the local blocks can be simplified
to
\small
\begin{verbatim}
  x.locBlocksEnum() ;
  if(x.locBlocksTest()) {
    ...
  }
\end{verbatim}
\normalsize
This saves at most one call to \verb$locBlocksNext$ and one call to
\verb$locBlocksTest$.  The conditional is still required to allow for
the case where the local processor holds no blocks.  This optimization
may be sensible in automatically generated code.
\item
If the body of the loop contains no call to functions
which might access the active process group descriptor, the calls
to the \verb$at$ and \verb$ta$ members can be omitted.
\end{itemize}
\end{document}


Changes to existing interface

12) `ADAPTRangeRep' is not documented correctly.  [It doesn't even
    exist any more.]

15) A thought: `x.locBlocksTest()' could be defined as `x.blockCount()'
    if the latter returns zero when there is no block remaining.

16) Replacement of constructors for derived ranges with `sub' member.

17) Replace section constructors by `sect' member.


