\documentstyle{csart}

\title{Geometric Parallelism}
\author{D.B. Carpenter}
\address{University of Southampton}

\begin{document}

\maketitle{}

\section{Background}

     In an attempt to characterise the commonest forms of concurrency
found in MIMD programs, the three classes {\em processor farm},
{\em algorithmic} and {\em geometric} parallelism were suggested
some time ago.  The first two types, in their purest form, are
those formalised in the interleave and pipe constructs of CSP.
Geometric parallelism is to some extent captured by the many languages
which support parallel array data-structures and operations.

     The scheme described here is quite similar to that found
in such languages.
It differs in reflecting more closely typical implementations
of geometrically parallel applications on existing MIMD hardware.
In particular operations on parallel arrays are very restricted here.  For
example the simple operation of indexing into a parallel array
to obtain an element of that array is not provided as a primitive
of the language.  The reasoning is that implementation of such an
operation will typically involve (behind the scenes) moving of
data between processors.  We adopt the point of view that any
communication should be
made ``explicit'' (at least to the extent that it requires calls
to possibly predefined procedures for rearranging distributed
data). 
     
     Some people will regard this point of view as retrograde.  Part of
the reason for adopting it here is that we are using the
notations introduced as a framework for {\em describing} programs and
characterising geometric communication libraries, rather than as a
language to be compiled directly, so hiding calls to communications
routines would be self-defeating.  Beyond that our philosophy is that
(as in {\em occam}) the primitives of a language should be transparent
and capable of straightforward and efficient implementation, and adopt
the viewpoint that hidden communication does not satisfy these
criteria. 


\section{Overview}

     Data can be distributed in many ways.  The most primitive
form of distribution is over a (possibly multi-dimensional) rectangular
grid of processes, and this is the prototype which will receive most attention
here.  Even in this framework different data-structures will have
different distributions, some objects will be global, or scalar.
Some objects may be distributed over some dimensions (have different
values at different sites) but be global with respect to other
dimensions.

    The first concept we introduce to describe these circumstances
is the {\em distributed index} (which we sometimes referred to a simply
an {\em index}).
A distributed index can be thought of
a data structure which describes the decomposition of a particular
dimension in the grid upon which the user's parallel data structure
are defined.  This decomposition may be onto a physical grid-connected
array of processors, or onto some other processor configuration.
In the simplest case, a program dealing with a one-dimensional grid
problem would have one index ``in scope'', a program dealing with
a two-dimensional problem would have two indicies in scope, and so on.

    In general very few of the details of this ``data
structure'' (the index) will be visible to the user, except possibly
at some program configuration level.  It may incorporate things
like channels for communication to neighbours in the current direction
and number of sites held on each processor, etc, but the only aspect
necessarily visible to the user is the total ``size'' of the index -
the number of sites the grid has in this particular direction.

    Thus declaration of an index takes the form
\begin{verbatim}

    [n] INDEX x :

\end{verbatim}
where the count $ n $ implies that $ x $ refers to a dimension
characterised by coordinate values 0 \ldots $n - 1$.  It {\em doesn't} imply,
for example, that we are working with an $n$-dimensional grid in any sense -
any similarity to ordinary occam array syntax is ``purely coincidental''.

     The second concept we introduce is that 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 is 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{verbatim}

     RANK rxy IS {x, y} :

\end{verbatim}
where $x$ and $y$ are existing indicies.

     Our third concept is that of a {\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{verbatim}

     {x, y} INT A :

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

     rxy INT A :

\end{verbatim}
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 direct way of getting at its elements
is to execute a WHERE construct \ldots

     The third esential ingredient of our scheme is the WHERE construct.
This is a type of parallel loop, with special properties.  A WHERE loop
is executed ``over'' an index set.  Within the body of the ``loop''
the type properties of the specified indicies, and objects distributed
over them change.  An index name refers simply to an INT value, the
``position'' of the elementary process of the loop, whereas a
distribution over a specified index becomes an object of its original
type, but with this index stripped from its rank (if this index
was part of its rank).

     For example, in the body of a
\begin{verbatim}

     WHERE {x}

\end{verbatim}
loop, $x$ becomes a simple value, and $A$ becomes an object of type
\begin{verbatim}

     {y} INT A :

\end{verbatim}
and $y$ remains as an object of type ``distributed'' index.
Inside a
\begin{verbatim}

     WHERE {x, y}

\end{verbatim}
construct both $x$ and $y$ are treated as simple INT values, and
$A$ refers to an INT variable.  Thus the following programs
are legal
\begin{verbatim}

     WHERE {x, y}
       A := x * y

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

\end{verbatim}
and have identical semantics - indeed the second can be
construed as a definition of the first.  The following programs
are illegal
\begin{verbatim}

    WHERE {x}
      A := x

    WHERE {x}
      WHERE {x}
        SKIP

\end{verbatim}
the first because we are attempting to assign an integer value
to a distribution over $y$, the second, more subtly, because inside
the body of the outermost construct $x$ is simply an integer
value - and we cannot form index sets as required by the innermost
WHERE from simple integers.

     The last essential ingredient in the simplest incarnation of
our scheme is an abstraction mechanism for operations on
distributed data - in particular for ``communication'', which
typically take form of permutation and other operations on
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 unsatisfactory if a routine for transposing
a matrix (a two-dimensional distribution) had to be re-written
for every possible arithmetic data type of the elements - INT,
REAL32, BYTE, arrays thereof, etc.  The full specification of
this interface involves rank- and type- variables, and a simple
form of pattern-matching, analogous to features found in many
functional languages.  The object is to provide polymorphism but
retain the possibility of full static type-checking, as in
modern functional languages.

     Here we will just give a couple of examples of interfaces.
The full definition of the mechanism is described in section XXX.
\begin{verbatim}

    PROC rotate (VAL [] INDEX i, {i} \/ RANK r TYPE t A,
                             VAL {i} \/ r t B)

\end{verbatim}
The simplest way to explain what this means is to give an example
of the calling sequence.
\begin{verbatim}

    [5] INDEX x, y :
    {x, y} REAL32 sourc, dest :
    SEQ
      ...
      rotate (x, dest, sourc)
      ...

\end{verbatim}
On calling $rotate$, $i$ will be identified with $x$, the rank-variable
$r$ will be identified with the rank value \verb@{y}@, the type-variable
$t$ will be identified with the type value REAL32, and type-consistency
will be accepted.  The operator \verb@\/@ is meant to represent (or be
suggestive of) set union, so the rank expression \verb@{i} \/ r@ evaluates
to \verb@{x, y}@.  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
\begin{verbatim}
    
    PROC broadcast (VAL [] INDEX i, RANK r TYPE t A,
                              VAL {i} \/ r t B, VAL INT src)

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

    [5] INDEX x, y :
    {y} INT dest
    {x, y} REAL32 sourc :
    SEQ
      ...
      broadcast (y, dest, sourc, 0)
      ...

\end{verbatim}
Identifying the binding of $i$, $r$, $t$, $A$ and $B$ (and $src$) is left
as an example

\section{Primitives vs Predefines}

     We have made the point the very few operations on distributions
are provided as primitives, in the sense that special syntax is provided
for them.  Having outlined the procedure mechanism, we will attempt
some further justification for this strategy.  Our belief is that
there are simply {\em too many} candidates for primitive operations
on distributions (this translates as ``communication patterns'') to provide
syntax for a representative sample of them.  Instead we advocate providing
a powerful polymorphic procedural abstraction mechanism, and supplying
the ``primitive'' operations on distributions as libraries or
predefined procedures.

     A case could be made for supplying a few operations, such as
broadcasts, shifts and summations, as primitives, with special syntax.
But given a sufficiently powerful procedure interface this seems
redundant.  (There is quite a strong case for providing broadcasts as
primitive, since then every program could, at least in principle, be
specified without recourse to procedure calls.  Used unrestrictadly
the WHERE construct provides a natural mechanism.  But I want to
restrict WHERE to non-broadcasting usage).
\end{document}


