%\documentstyle{csart}

%\begin{document}

\section{\label{static}Static Implementation}

     In this section we outline briefly an implementation scheme
for the language described in the previous section.  The implementation
is static in the sense that we assume definition of the abstract
grid (i.e. declaration of indicies) is performed once at some
configuration level of the program.  More dynamic implementations
would clearly be desirable---section \ref{dynamic} contains some
comments.

     In grid-oriented geometric decompositions, the grid upon which a
problem is defined (the {\em problem grid})
will usually be mapped onto some {\em process grid}.  The process grid
is a rectangular grid, typically of the same dimensionality as the problem
grid.  The process grid is in turn mapped onto some processor array.
The two mappings

     {\em problem grid} $\to$ {\em process grid}

     {\em process grid} $\to$ {\em processor array}\\
will both be many to one in general.  The first mapping reflects some
``domain decomposition''.  In general it will not be practical to
to provide an individual process for each element of the problem
grid for reasons of memory efficiency (every process needs its own
workspace and copy of global variables).  The second mapping reflects
process placement, and again for a variety of efficiency reasons it
may be desirable to have several processes on each processor.
Note that in general the connectivity of the process grid may be
much more general than nearest-neighbour---higher connectivity, if
available, facilitates operations such as broadcasts along directions
of the process grid.

     The abstract grid defined by the distributed indicies of a program
can be utilised in more than one way.  Most obviously it can be identified
with the problem grid, leading to an easy style of programming
in which the domain decomposition can be hidden from the programmer.
Alternatively it can be identified with the process grid, leaving the
programmer to manage the domain decomposition.  This leads to a less natural
programming style, but to easier implementation of the constructs
of the language, and provides the dedicated programmer with more freedom to
optimise codes.  The latter interpretation will be discussed first.
Section \ref{examples} provides examples of programming in both styles.
Both schemes assume the more restrictive choice of usage rule for
\verb$WHERE$ loops described in appendix \ref{where}.

\subsection{Abstract Grid as Process Grid}

     Implementation of our notations, which we will express in terms of
translation to standard {\em occam} is now almost trivial.  Any distribution
has only one element in each process (though of course these elements
may be sequential arrays---domains indeed).  

     An index $x$, say, has associated with it a ``distributed data
structure''.  On each process this structure
incorporates channels for communication with other processes
which can be reached by moving in the $x$-direction from the current
process, as well as the value of the ``$x$-coordinate'' of the current
process.  The exact connectivity depends on what the hardware can
support---though for a machine with hardware through-routing capabilities
their may as well be channels for direct communication with all
processes on the same line of the grid.  The $x$ structure will not
incorporate channels for communicating with processes on other ``lines'',
i.e., processes that have different
coordinates associated with any other axes of the grid.

     Figure \ref{x-channels} illustrates some of the channels associated
with the $x$-index in a two-dimensional example.  Communications procedures
such as $broadcast$ or $rotate$ are passed the index data structure, including
such channels, as parameters.

\begin{figure}
\centerline{\psfig{figure=x.ps,height=2.5in}}
\caption{\label{x-channels} Example channel connections associated with $x$ index}
\end{figure}

     In this case the implementation of \verb$WHERE {x}$ simply consists
of ``hiding'' the $x$ data structure by abbreviating the $x$-coordinate
(an element of the structure) as $x$.  As a mundanely concrete
example, the program
\begin{linear}
\begin{verbatim}

    PROC example ([n] INDEX x)

      {x} INT A :
      INT b :
      SEQ
        ...
        broadcast (x, b, A, 0)
        ...
        WHERE {x}
          ...
    :

\end{verbatim}
\end{linear}
could translate to the {\em occam}
\begin{linear}
\begin{verbatim}

    PROC example (VAL [] INT x)

      INT A :
      INT b :
      SEQ
        ...
        [] BYTE b RETYPES b :
        [] [SIZE b] BYTE A RETYPES A :
        broadcast (x, b, A, 0)
        ...
        SEQ
          VAL x IS position (x) :
          ...
    :

\end{verbatim}
\end{linear}
The index is implemented here by an array of integers, which will presumably
include pointers to channels.  This structure is set up at the ``configuration
level'' and accessed ultimately only by predefined procedures such as 
$broadcast$.  Its details needn't be specified here.  In the abstract,
$broadcast$ is type-polymorphic.  In a concrete translation such routines
would probably be written as procedures operating on \verb$BYTE$ arrays,
hence the 
retyping.  In the case where each element of the abstract grid has
a whole process, no details of the rank need to be passed to procedures
such as $broadcast$.  Finally, the only effect of \verb$WHERE$ is to
extract the coordinate value from the index data structure (done here
with an access function $position$).

     The configuration level of the program declares the channels,
spawns the grid of processes, sets up the index structures, and
calls the above ``user'' procedure in each process.

     Providing the above translation scheme is performed from a
``correct'' program it is reasonably
straightforward to convince oneself
{\samepage
\begin{itemize}
\item Copies of variables global with respect to particular indicies are held
redundantly across processes.  Consistency of copies is automatically
maintained.
\item At any stage in the program, {\em either} an index is in scope and
can be passed to
a communication routine (such as $broadcast$) {\em or} processes on a line
along that index can be performing independent actions, through
a \verb$WHERE$.  {\em Not} both.  So mismatched calls to communication
procedures cannot cause deadlocks.
\item No synchronisation is required for operation of \verb$WHERE$ loops
(mainly because no memory is shared).
\end{itemize}
}

\subsection{Abstract Grid as Problem Grid}

     In this implementation ``domaining'' is managed below the level
of the abstract program specification.  This approach is less amenable
to manual translation to a language like {\em occam}.  The process
grid and associated communication channels are set up in a similar
way, but now the ranges
of indicies are ``sectioned'' according to some prescription, and this
sectioning induces a natural distribution of arrays over the process
grid, generally with many elements of each array held by each process.
The index data structure will hold parameters of the sectioning.
 
    \verb$WHERE$ loops are translated to sequential loops over the
locally held section.  The local domain of a distribution is held in
an array.  But at various stages the ``active'' data of a distribution
may not be a contiguous slice of this array.  This is because a
\verb$WHERE$ construct may localise attention to, say, a particular
$y$ slice of an \verb${x, y}$ distribution, leaving a \verb${x}$
distribution.  If data is stored with $y$ ``most rapidly varying''
this \verb${x}$ distribution is not a contiguous region of memory.
Thus in general the local representation of a distribution includes
information about ``strides'' in the data array.  This information has to be
passed to procedures along with the data.  

\subsection{\label{dynamic}Less Static Implementation}

     Why demand that indicies only be declared at configuration
level?  Imagine code like
\begin{linear}
\begin{verbatim}

    [n] INDEX x :
    SEQ
      ... preamble
      [m] INDEX y :
      SEQ
        ... body

\end{verbatim}
\end{linear}
Declaration of an index actually causes spawning of processes---the
obvious implementation would be something like
\begin{linear}
\begin{verbatim}

    ... declare `x' channels
    PAR i = 0 FOR x.num.procs
      INDEX x :
      SEQ
        ... initialise `x' structure
        ... preamble
        ... declare `y' channels
        PAR j = 0 FOR y.num.procs
          INDEX y :
          SEQ
            ... initialise `y' structure
            ... body

\end{verbatim}
\end{linear}
where \verb$INDEX$ is a data-type we don't specify in full detail.
Unfortunately this doesn't work, because every process in the
second replicated \verb$PAR$ needs to have its own copy of
{\em anything} declared before the \verb$[m] INDEX y$ declaration.
In particular all the $x$ channels need replicating so that each of
the now-several $x$-lines
of processes have their own independent $x$ channel sets.
Thus simple declaration
of an \verb$INDEX$ is actually quite complicated to translate
unless all indicies are declared together at some outer level,
before data declarations start.  Implementation is not overwhelmingly
difficult, just relatively so.
 
%\end{document}


