\documentstyle{csart}

\newenvironment{linear}{\\ \begin{minipage}[t]{\textwidth}}{\end{minipage}}
% Prevents body from being split between pages.  Can't be used at start
% of a paragraph, irritatingly.

\begin{document}

\sloppy

\pagestyle{empty}

%\title{"Level-I" communication library}

%\author{D.B. Carpenter}
%\address{Department of Electronics and Computer Science, \\
%         Southampton University, \\
%         Southampton, S09 5NH} 

%\maketitle

%\newpage

%\tableofcontents
%\listoftables

%\newpage

\setcounter{page}{1}
\pagestyle{plain}


%\section*{``Level-I'' communication library}

\section{Interworker Operations}

     Two basic classes of interworker operation will be
provided---``polymorphic'', pure communication routines, and global
arithmetic operations.

\subsection{Polymorphic routines}

\subsubsection{Broadcast}

     Broadcast is the most primitive operation capable of
copying values to lower rank structures.  Because values
can be assigned directly to higher rank structures through
\verb$WHERE$ constructs, {\em all} communication patterns
{\em can} be expressed (inefficiently) in terms of $broadcast$.
\begin{linear}
\begin{verbatim}

    PROC broadcast ([] INDEX x, RANK R TYPE T A,
                                VAL {x} + R T B, VAL INT src)

      -- Broadcast `B' from site "x = src" to all sites - result
      -- in `A'.

\end{verbatim}
\end{linear}

\subsubsection{The Permutation-Relation Family}

     The simplest form of permutation provided is straightforward
rotation.
\begin{linear}
\begin{verbatim}

    PROC rotate     ([] INDEX x, {x} + RANK R TYPE T A,
                                       VAL {x} + R T B, VAL INT shift)

      -- Rotate data in `B' `shift' sites in `x' direction - result
      -- in `A'.

\end{verbatim}
\end{linear}
Two useful generalisations of $rotate$ are
\begin{linear}
\begin{verbatim}

    PROC rotate.var ([] INDEX x,
                      {x} INT A.len, {x} + RANK R [] TYPE T A,
                  VAL {x} INT B.len,       VAL {x} + R [] T B,
                      VAL INT shift)

\end{verbatim}
\end{linear}
and
\begin{linear}
\begin{verbatim}

    PROC rotate.fix ([] INDEX x,
                  VAL {x} INT A.len, {x} + RANK R [] TYPE T A,
                  VAL {x} INT B.len,       VAL {x} + R [] T B,
                      VAL INT shift)
\end{verbatim}
\verb$      -- Precondition:$\\
\verb$      --    $ $\forall_x (A.len_{x + shift} = B.len_x)$\\
\verb$      -- where quantification is over the coordinate values associated$
\verb$      -- with `x', and addition is modulo SIZE x.$\\

\end{linear}
$rotate.var$ behaves exactly like $rotate$, except that the elements
of $A$ and $B$ are sequential arrays, and the number of elements
of these arrays to be sent from each site are specified in $A.len$.
The number of elements arriving at each site is returned in
$B.len$ (this is similar to a ``counted array'' communication in {\em occam}).
$rotate.fix$ is identical except that $A.len$ is an input to the
procedure---if the precondition isn't satisfied an error will occur.
Note that $rotate.var$ can be built from $rotate$ (acting on the
lengths) and $rotate.fix$.

     The precondition on $rotate.fix$ is the first example of a
non-local condition on input data.  Several of the remaining routines
in this section have similar preconditions.  In some cases verifying such a
predicate may be as complex as, or more complex than, the
actual operation to be performed.  For efficiency, run-time checking of
such conditions is therefore unlikely to be incorporated in the
library routines.  In general the routines with such requirements
should be treated with due caution---depending on the implementation
they may actually introduce deadlocks if abused.

     In conjunction with use of multi-dimensional ranks,
and some of the procedures in \ref{arithmetic}, we suspect that
$broadcast$ and $rotate$ should suffice for most purposes (in programs suited
to expression in our framework). 
The remaining routines in this section are provided
for completeness.  The permutations would be useful, for example, in
implementing generic hypercube-oriented algorithms.  The relations
are provided as an ultimate catch-all---any program using these operations
extensively would probably be better coded in an explicit message-passing (or
shared-memory?) style.

     Two procedures for general permutation are
\begin{linear}
\begin{verbatim}

    PROC permute.non ([] INDEX x,
                       {x} INT src, {x} + RANK R TYPE T A,
                   VAL {x} INT dst,       VAL {x} + R T B)

      -- Permute elements of `B' to sites defined by coordinates in
      -- array `dst' - result in `A'.
\end{verbatim}
\verb$      -- Precondition:$\\
\verb$      --    $ $\forall_{x, x'} (dst_x = dst_{x'} \Rightarrow x = x')$\\
\verb$      -- (and all elements of `dst' are in the range of possible$\\
\verb$      -- `x' coordinates)$\\

\end{linear}
and
\begin{linear}
\begin{verbatim}

    PROC permute.det ([] INDEX x,
                   VAL {x} INT src, {x} + RANK R TYPE T A,
                   VAL {x} INT dst,       VAL {x} + R T B)
\end{verbatim}
\verb$      -- Precondition:$\\
\verb$      --    (precondition for `permute.non')$ $\land$\\
\verb$      --    $ $\forall_x (src_{dst_x} = x)$\\

\end{linear}
$permute.non$ behaves in an obvious way.  The output $src$ contains the
coordinate of the source site for the data just obtained.  $permute.det$
is identical, except that the source sites must be provided as inputs.
The name postfixes are short for ``non-deterministic'' and ``deterministic'',
referring to the underlying implementations---the former would involve
``alternative'' input.  Notice that this means that the first routine
may be much less efficient than the second, which can operate through
committed input.  Notice also though that the second form may suffer less
easily trappable deadlocks if the precondition is not respected!

     The last pair of routines in this section are the general ``relations''.
\begin{linear}
\begin{verbatim}

    PROC relate.non ([] INDEX x,
           {x} INT src.len,     {x} [] INT src, {x} + RANK R [] TYPE T A,
       VAL {x} INT dst.len, VAL {x} [] INT dst,       VAL {x} + R [] T B)

      -- Send `dst.len' messages in `B' to destinations in `dst' -
      -- result in `A'.

\end{verbatim}
\end{linear}
and
\begin{linear}
\begin{verbatim}

    PROC relate.det ([] INDEX x,
       VAL {x} INT src.len, VAL {x} [] INT src, {x} + RANK R [] TYPE T A,
       VAL {x} INT dst.len, VAL {x} [] INT dst,       VAL {x} + R [] T B)
\end{verbatim}
\verb$      -- Precondition:$\\
\verb$      --    $ $\forall_{x, x'}(|\{j:src_{x'}[j]=x\}| = |\{i:dst_x[i]=x'\}|)$\\
\verb$      -- where the range of `i' (`j') is 0..dst.len_x-1 (0..src.len_x'-1)$\\

\end{linear}
$relate.non$ delivers a specified number of messages from each site
to an unrestricted set of destinations (the elements of the array of
destinations in $dst$ and of values in $B$ should be in one-to-one
correspondence).  The values returned in $A$ will likewise be
in one-to-one corresponce with their sources returned in $src$ (and 
the total number arriving at each site is returned in $src.len$).
In general an implementation will not guarantee any ordering of the
returned set of arriving messages---this routine may be truly
non-deterministic.

     $relate.det$ is identical, except that it is provided with
a list of sources from which the messages will arrive.  The elaborate
precondition guarantees that the number of messages between any two
points defined in $src$ agrees with that defined in $dst$.  Where
more than one message passes between the same two points the implementation can
easily guarantee that their order in $A$ will correspond
to their order in $B$.

     Implementation of $relate.non$ is seriously inefficient unless the
number of messages to be delivered is large---a global
synchronisation is needed to detect that all messages have arrived.
On the other hand, use of $relate.det$ requires extreme caution to
guarantee the complicated precondition, required for deadlock freedom.

     Incidentally, there is a weak analogy between the $var$ and $fix$
postfixing of $rotate$, and the $non$ and $det$ postfixes on
$permute$ and $relate$.  We did not exploit that analogy to add uniformity
to the naming conventions, because it is possible that a comprehensive
library would provide $var$ and $fix$ forms of all four $permute$ and
$relate$ procedures---these attributes are really quite orthogonal.

\subsubsection{Miscellany}

     In some sense the routines described in this subsection are less
fundamental than those of the previous two, but they are useful
and occur commonly.

     First a trivial derivative of $rotate$, which returns its
result ``in situ'' in the original array
\begin{linear}
\begin{verbatim}

    PROC rotate.in  ([] INDEX x, {x} + RANK R TYPE T A, VAL INT shift)

      -- Rotate data in `A' `shift' sites in `x' direction - result
      -- in `A'.

\end{verbatim}
\end{linear}

     Secondly, without giving the full interface, a
derivative of $permute.fix$ which implemented the permutation
\begin{displaymath}
dst_x = src_x = \left\{
                        \begin{array}{ll}
                         x \oplus 2^b & \mbox{if $x \oplus 2^b < n$} \\
                         x            & \mbox{otherwise}
                        \end{array}
                \right. ,
\end{displaymath}
where $\oplus$ is bitwise exclusive or, and $n = $ \verb$SIZE$ $x$, would
be extremely useful for hypercube-oriented algorithms.  The same
variants available for $rotate$ could be provided for this routine.

     Thirdly, routines for performing ``small'' permutations in situ
could be useful for some purposes.  Suppose we just want to exchange
two elements of a distribution; setting up the whole source and
destination distributions would be rather inefficient.  Instead
a procedure should be provided which takes a globally defined small 
permutation and applies it efficiently to distributed data (in complexity
terms, we define a {\em small} permutation to be one which affects
{\em constant} number of sites).  We could provide a routine which
effected an arbitrary small permutation.  On the grounds of simplifying
the interface we propose restricting to cyclic permutations (observing,
with one's complexity hat on,
that any {\em constant} sized permutation can then be expressed in terms of
a {\em constant} number of small cyclic permutations).  This motivates
the interface
\begin{linear}
\begin{verbatim}

    PROC cycle      ([] INDEX x, {x} + RANK R TYPE T A,
                                       VAL {x} + R T B, VAL [] INT cyc)

      -- Permute elements of `B' to sites defined by cycle in `cyc' -
      -- result in `A'.
\end{verbatim}
\verb$      -- Precondition:$\\
\verb$      --    $ $\forall_{i, i'} (cyc[i] = cyc[i'] \Rightarrow i = i')$\\
\verb$      -- and all elements of `cyc' are in the range of possible$\\
\verb$      -- `x' coordinates$\\

\end{linear}
For uniformity, the same set of variants provided for $rotate$ could also be
provided for $cycle$ (and probably the only useful form would be
$cycle.in$).

      One or two additional routines for common operations, such as
transposing two dimensional distributions, might also be provided---but
probably only in ``level II'' implementations.

\subsection{Global Arithmetic}

     The only family of global arithmetic we propose providing at level I is
a series of partial prefix operations.  The family is large because
of the large number of types and arithmetic operations that have to
be catered for.  Generically the interface is
\begin{linear}
\begin{verbatim}

    PROC prefix.<op>.<type> ([] INDEX x, {x} <type> prefix, VAL {x} <type> A)

      -- `<op>' is an associative binary operation applicable to type
      -- `<type>'.

\end{verbatim}
\end{linear}
The family includes
\begin{verbatim}

    prefix.add.INT            -- +
    prefix.pls.INT            -- modulo addition
    prefix.mul.INT            -- *
    prefix.tim.INT            -- modulo multiplication
    prefix.or.INT             -- \/
    prefix.and.INT            -- /\
    prefix.xor.INT            -- ><
    prefix.max.INT            -- maximum
    prefix.min.INT            -- minimum

    prefix.add.INT16          -- +
    prefix.pls.INT16          -- modulo addition
    prefix.mul.INT16          -- *
    prefix.tim.INT16          -- modulo multiplication
    prefix.or.INT16           -- \/
    prefix.and.INT16          -- /\
    prefix.xor.INT16          -- ><
    prefix.max.INT16          -- maximum
    prefix.min.INT16          -- minimum

    prefix.add.INT32          -- +
    prefix.pls.INT32          -- modulo addition
    prefix.mul.INT32          -- *
    prefix.tim.INT32          -- modulo multiplication
    prefix.or.INT32           -- \/
    prefix.and.INT32          -- /\
    prefix.xor.INT32          -- ><
    prefix.max.INT32          -- maximum
    prefix.min.INT32          -- minimum

    prefix.add.INT64          -- +
    prefix.pls.INT64          -- modulo addition
    prefix.mul.INT64          -- *
    prefix.tim.INT64          -- modulo multiplication
    prefix.or.INT64           -- \/
    prefix.and.INT64          -- /\
    prefix.xor.INT64          -- ><
    prefix.max.INT64          -- maximum
    prefix.min.INT64          -- minimum

    prefix.add.REAL32         -- +
    prefix.mul.REAL32         -- *
    prefix.max.REAL32         -- maximum
    prefix.min.REAL32         -- minimum

    prefix.add.REAL64         -- +
    prefix.mul.REAL64         -- *
    prefix.max.REAL64         -- maximum
    prefix.min.REAL64         -- minimum

    prefix.or.BOOL            -- OR
    prefix.and.BOOL           -- AND
    prefix.xor.BOOL           -- <>
\end{verbatim}
~
\begin{linear}
\begin{verbatim}
    prefix.mul.complex.<scalar.type>  
                              -- complex multiplication -
                              -- <scalar.type> ::=
                              -- INT | INT16 | INT32 | INT64 | REAL32 |
                              -- REAL64

    prefix.mul.mat.<type>     -- matrix multiplication - <type> ::=
                              -- INT | INT16 | INT32 | INT64 | REAL32 |
                              -- REAL64 | complex.<scalar.type>

\end{verbatim}
\end{linear}
This proliferation of routines is slightly absurd---the problem is,
of course, that {\em occam} doesn't permit passing functions as
parameters to procedures.
Arguably simple global ``accumulation'' versions should be provided, but
these can be expressed with approximately optimal efficiency
in terms of $prefix$ and $broadcast$.  There is a case for providing
vector versions of all these routines.  Also they could be promoted
to operate on distributions of ``$\{x\} + R$'' rank.  Level II
implementations would probably provide versions that operated on
sub-ranges of distributions.

\section{Input and Output}

     Input or output is performed on logical occam channels (the
implementation of a channel will be some complicated distributed
structure akin to an index).  The most straightforward routines
communicate whole distributions sequentially on these global channels.
\begin{linear}
\begin{verbatim}

    PROC input    (CHAN OF TYPE T in, T A)

    PROC input.1  (CHAN OF TYPE T in, [] INDEX x, {x} T A)

    PROC input.2  (CHAN OF TYPE T in, [] INDEX x, y, {x, y} T A)

    PROC input.3  (CHAN OF TYPE T in, [] INDEX x, y, z, {x, y, z} T A)

\end{verbatim}
\end{linear}
etc, and
\begin{linear}
\begin{verbatim}

    PROC output   (CHAN OF TYPE T out, T A)

    PROC output.1 (CHAN OF TYPE T out, [] INDEX x, {x} T A)

    PROC output.2 (CHAN OF TYPE T out, [] INDEX x, y, {x, y} T A)

    PROC output.3 (CHAN OF TYPE T out, [] INDEX x, y, z, {x, y, z} T A)

\end{verbatim}
\end{linear}
etc.  The protocol on the logical channel presents some problems---for
correct channel usage the stream of \verb$TYPE$ $T$ data to be output
by the library routine
needs to go on a channel of the appropriate type, most naturally
a channel with a simple protocol of $T$.  But certainly in the course
of a program we will want to output stream of more than one type
on given channels, suggesting a variant protocol; of course
the library routine won't know the about the user's variant protocol.

     We have a neat solution to this problem, which involves a natural
generalisation of occam variant protocols to provide arbitrary
nesting of protocols.  A very small modification to the occam
input/output syntax allows some child protocol to be selected
from a parent protocol within some lexical scope. 
The effect is that at different
points in the program the protocol on a channel can change, and
in particular we can extract a simple protocol such as $T$ from
a more elaborate variant, then call the
above procedures.  This is not the place to describe this
extension in detail---for purposes of implementing the {\em occam}
communication library we will simply use the \verb$ANY$ protocol.

\end{document}
