%\documentstyle{csart}

%\begin{document}

%\newenvironment{linear}{\\ \begin{minipage}[t]{\textwidth}}{\end{minipage}}

\section{\label{overview}Overview}

     The notations described in this document are designed to express
parallel algorithms dealing with data defined on rectangular
grids of one or more dimension.  Although many problems require
less regular parallel data structures, it is certainly true that
an important class of problems {\em do} have a rectangular grid structure.

\subsection{Defining Grids}

     The underlying model we have is of data structures whose
components can be localised at the sites of an abstract rectangular grid.
The intention is that the points of this grid will be distributed
in some way over a collection of processors, but the exact
nature of this distribution is unspecified at this stage.

     To define a grid we need a set of ``axes''.  In our notation
an axis is formalised by an object called a {\em distributed
index}, or often simply an {\em index}.  In general an index
will be implemented by a distributed data structure which might include
details of the mapping from the abstract grid to an underlying
processor network as well as communication channels between connected
processors.

     The only aspect of this structure visible in our abstract notation
is the total ``size'' of the index, that is the number of points the
grid has in the direction referred to.  The declaration of an index
takes the form
\begin{linear}
\begin{verbatim}

    [n] INDEX x :

\end{verbatim}
\end{linear}
where the count $ n $ implies that $ x $ refers to a dimension
characterised by coordinate values 0 \ldots $n - 1$.  It {\em doesn't} imply
that we are working with an $n$-dimensional grid in any sense---any
similarity to ordinary occam array syntax is largely coincidental.
In practice definition of indicies may well be a ``configuration''
issue, but more dynamic implementations are possible.

     Suppose a process has $d$ distributed indicies in scope.  The
understanding is that we then have a $d$-dimensional grid available
over which to distribute data structures.  Some items of data will
take different values at every site of the grid, some may be
``scalar'', that is to say they have a global value.  Others may
take various values over a subset of dimensions, but have values
global with respect to other dimensions.

\subsection{Rank and Distributed Data}

     To capture these possibilities we introduce the idea of {\em rank}. 
Rank is somewhat analogous to type, but describes the {\em distribution}
of an object, rather than, for example, its arithmetic properties.
Here a rank is just a set of indicies---those over which a data object
of such rank is distributed.  It's convenient to be able to name a
rank in its own right, much as it's convenient to be able to name
types.  For example
\begin{linear}
\begin{verbatim}

     RANK XY IS {x, y} :

\end{verbatim}
\end{linear}
where $x$ and $y$ are existing indicies.  A couple of simple operators
are useful for combining ranks.  Here we will only mention the union
operator \verb$\/$.  This is used for combining the indicies of two
ranks into a single rank, as in
\begin{linear}
\begin{verbatim}

    {x, y} \/ {z} = {x, y, z}

\end{verbatim}
\end{linear}
This operation is not quite analogous to set union.  In particular
it is forbidden
to combine two ranks with common indicies.  Operators like \verb$\/$
are only really provided for convenience in defining the procedure
interface---see appendix \ref{interface} for more details.

     The next concept is the {\em distribution}, which is our
formalisation of the parallel array.  For example a distribution of
integers over $x$ and $y$ can be declared by
\begin{linear}
\begin{verbatim}

     {x, y} INT A :

\end{verbatim}
\end{linear}
or, given the earlier definition of $XY$, just as
\begin{linear}
\begin{verbatim}

     XY INT A :

\end{verbatim}
\end{linear}
In these examples $A$ is similar to a two-dimensional array.  It {\em isn't}
a two-dimensional array, however.  For example, it cannot be ``indexed
into'' as an array can be.  The only way of getting at its elements
is to execute a \verb$WHERE$ construct.

     An object defined with no specified rank, or with the trivial rank,
\verb${}$, is scalar with respect to the currently scoped indicies.

\subsection{The WHERE Construct}

     In general {\em no} operations can be performed directly on distributions,
that is, objects with non-trivial rank.  But a construct is provided
which ``de-scopes'' distributed indicies, turning a distribution
over that index into a scalar, which {\em can} be operated on.  This
construct, \verb$WHERE$, can be regarded as a parallel loop.

     For example, the following program is illegal
\begin{linear}
\begin{verbatim}

     [n] INDEX x :
     {x} INT A :
     SEQ
       A := A * A

\end{verbatim}
\end{linear}
because we attempted an operation on a non-scalar object.  The correct
way to achieve what was probably intended is
\begin{linear}
\begin{verbatim}

     [n] INDEX x :
     {x} INT A :

     WHERE {x}
       A := A * A

\end{verbatim}
\end{linear}
This is legal, because inside the body of the \verb$WHERE$ construct
$A$ becomes just a scalar (its only index, $x$, is no longer in force).
The effect of the \verb$WHERE$ is to
perform the process in its body, notionally in parallel, for all values of the
``$x$-coordinate''.  Because $x$ is ``out of scope'' inside the body of
the construct, the following code-fragments are illegal
\begin{linear}
\begin{verbatim}

     WHERE {x}                  WHERE {x]
       WHERE {x}                  {x} INT B :
         ... body                 ... body

\end{verbatim}
\end{linear}
As a convenient refinement, we will modify the demand the $x$ is ``out of
scope''---instead we will just say that $x$ ceases to be a distributed index
in the body of \verb$WHERE {x}$.  Instead this name now refers to a
simple integer value.  For each parallel process this value is simply
the ``$x$-coordinate'' of that process.  The above fragments remain
illegal because, inside the body of the \verb$WHERE$, $x$ doesn't have
the correct type (an index) for the context.  But we can now write, for example
\begin{linear}
\begin{verbatim}

     WHERE {x}
       IF
         (base <= x) AND (x < (base + count))
           ... body
         TRUE
           SKIP

\end{verbatim}
\end{linear}
in which case the body is only executed for a sub-range of the
possible values of the $x$-coordinate.  A more fully developed
notation would probably provide a special syntax for this
situation.  For the present we stick with the simple syntax.

     The scheme generalises straightforwardly to the case of
multi-dimensional grids.  For example
\begin{linear}
\begin{verbatim}

     [n] INDEX x :
     [m] INDEX y :
     {x, y} INT A :
     {x}    INT b :

     WHERE {x}
       SEQ
         b := x
         WHERE {y}
           A := b * y

\end{verbatim}
\end{linear}
Inside the $x$ loop $b$ is treated as a scalar and $x$ as an
integer value, so the assignment to $b$ is legitimate.
Notice that the outermost loop has no effect on $y$, so
$A$ looses its $x$ index but remains distributed over $y$---its
type at this stage is \verb${y} INT$.  On entering
the $y$ loop $A$ and $y$ also become scalar, and the $A$
assignment is legal.

     Because nesting of \verb$WHERE$ constructs is so common
we introduce the special syntax
\begin{linear}
\begin{verbatim}

    WHERE {x, y}

\end{verbatim}
\end{linear}
to represent immediately nested \verb$WHERE {x}$ and \verb$WHERE {y}$
constructors.  More generally the \verb$WHERE$ constructor takes
an arbitrary rank-valued expression as its argument.

     Appendix \ref{where} discusses some aspects of \verb$WHERE$ usage
not entered into here.

\subsection{The Procedure Interface}

     The final essential ingredient of
our scheme is an abstraction mechanism for operations on
distributed data---in particular for ``communication'', which
typically takes the form of permutation or other operations on
elements of distributions.  This is the most complicated part of the scheme
to specify in detail, because to be truly useful the procedure
interface really needs to be ``polymorphic''.  Thus a given
routine can apply to distributions of different types.  For
example it would be unsatisfactory if a routine for transposing
a matrix (a two-dimensional distribution) had to be re-written
for every possible arithmetic data type of its elements---\verb$INT$,
\verb$REAL32$, \verb$BYTE$, arrays thereof, etc.  The full specification of
this interface involves rank- and type- variables, and a simple
form of pattern-matching.  The object is to provide polymorphism but
retain the possibility of static type-checking.

     Here we will just give a couple of examples of interfaces.
The full definition of the mechanism is described in appendix
\ref{interface}.

     An example of a possible interface for a procedure designed
to perform a ``cyclic shift'' on a distribution over a specified
index is
\begin{linear}
\begin{verbatim}

    PROC rotate ([] INDEX i, {i} \/ RANK r TYPE t A,
                             VAL {i} \/ r t B, VAL INT shift)
			     
\end{verbatim}
\end{linear}
The simplest way to explain what this interface means is to give an example
of the calling sequence.
\begin{linear}
\begin{verbatim}

    [n] INDEX x, y :
    {x, y} REAL32 data, result :
    SEQ
      ...
      rotate (x, result, data, -1)
      ...

\end{verbatim}
\end{linear}
On calling $rotate$, $i$ will be identified with $x$, $A$ will be
identified with $result$ and $B$ will be identified with $data$. 
To match the actual rank and type of $result$ the rank-variable
$r$ will be identified with the rank value \verb@{y}@ (note that the
rank expression \verb@{i} \/ r@ then evaluates correctly to \verb@{x, y}@)
and the type-variable $t$ will be identified with the type value REAL32.
The rank and type of the third formal parameter ($B$) then match
the actual parameter ($data$), so overall rank and type consistency
will be accepted.  In general a call to $rotate$ is valid so long as
its first argument is an index, and its second arguments  are of
the same rank and type, and their rank includes the first argument.

     As a second example, the procedure $broadcast$
takes data from a particular element of a distribution over
some index, and returns it in a datum global with respect to
that index.
\begin{linear}
\begin{verbatim}
    
    PROC broadcast ([] INDEX i, RANK r TYPE t A,
                              VAL {i} \/ r t B, VAL INT src)

\end{verbatim}
\end{linear}
can be legally called in the following program
\begin{linear}
\begin{verbatim}

    [n] INDEX y :
    INT result
    {y} REAL32 data :
    SEQ
      ...
      broadcast (y, result, data, 0)
      ...

\end{verbatim}
\end{linear}
Identifying the binding of $i$, $r$, $t$, $A$ and $B$ is left
as an exercise.

     Incidentally, a code fragment like
\begin{linear}
\begin{verbatim}

     WHERE {y}
       broadcast (y, result, data, 0)

\end{verbatim}
\end{linear}
is illegal, because inside a $y$-loop the symbol $y$ refers to a simple integer
value, whereas {\em broadcast} expects an \verb$INDEX$ as its first
parameter.  This is an essential feature of the scheme\ldots without
it simple deadlock-free implementations would not be possible.

%\end{document}


