
% ACL presentation for ASI meeting---outline.

%\documentstyle{csart}
\documentstyle{pumaslides}
\special{dvitops: landscape}
\def\footline{\rm Array Communication Library \hfill \thepage}

\raggedright

\title{Array Communicaton Library}
\author{Bryan Carpenter\\
University of Southampton}

\begin{document}

\maketitle

\thispagestyle{empty}

\newpage

\section*{Motivation}

Puma architecture provides efficient point-to-point communications.
In data-parallel applications many more elaborate communication patterns
recur frequently.  

Regard these as more global operations: rearrangements
of or simple arithmetic transformations on distributed data.
%
%Can be implemented in terms of message-passing,
%but better regarded as more global operations: rearrangements
%of distributed data (e.g., permutation) or simple arithmetic
%transformations (e.g., prefix) on distributed data.

\begin{itemize}
\item     ``Array'' in ACL refers to {\em process\/} array: library
operates within arbitrary-dimensional arrays of processes.
\item      Level is somewhere between low-level communication libraries and
libraries providing specialised support for particular applications,
or specific distribution strategies for data arrays.
\end{itemize}

\newpage

\section*{Process Arrays}

Each logical direction has a structure called an ``index''
associated with it, e.g., $x$, $y$ and $z$.
%     A process array is a logically multi-dimensional process configuration.
%Each direction has a structure called an ``index''
%associated with it, e.g., $x$, $y$ and $z$.

% figure `array' goes here
%\begin{figure}[h]
% magnified by 0.36 (0.3 with figure environment!)
\centerline{\psfig{figure=array.ps}}
%\end{figure}

\newpage

\section*{Interface}

\begin{itemize}
\item     Index structures are passed to communication routines in much the
same way as channels in occam.  For example
\begin{verbatim}
     PERM.SHIFT (x, result, data, 3)
\end{verbatim}
shifts the values in `data' 3 sites in the `x' direction, and returns
the shifted values in `result'.
\item     The index structure also contains the coordinate value for the
local process associated with the index direction:
\begin{verbatim}
     local_x = INDEX.coord (x)
\end{verbatim}
\end{itemize}

\newpage

\section*{Implementations}

\begin{itemize}
\item     In the occam/VCR implementation of ACL any two sites connected by
an index have a virtual channel between them.  
\item The data structure
embodying an index contains vectors of these channels.  
\item The channels
are hidden from the user of the communication library.  Thus the same
library interface can be provided in non-channel-oriented communication
environments.
\end{itemize}

\newpage

\section*{Selected Entry Points}

\begin{verbatim}
     PERM.DS            -- arbitrary permutation.
     PERM.SHIFT         -- a particular permutation.
     RELATE.DS          -- a generalised permutation.

     BROADCAST          -- and variants.

     PREFIX.REAL32.SUM  -- and other prefixes
     GLOB.REAL32.SUM    -- and other reductions.
\end{verbatim}

\newpage

\section*{Example---toy FFT}
% Notes:
%
%    twiddle (x, k, p) is x := exp (i pi k / p) * x.
%    In occam, have to retype data as [] BYTE for PERM.
%    Final assignment to `datum' won't pass usage checking.

%{\tiny
{\scriptsize
\begin{verbatim}
    SEQ b = 0 FOR d
      VAL p        IS 1 << b :
      VAL odd.site IS ((INDEX.coord (x) / p) /\ 1) = 1 :
      [2] REAL32 import :
      SEQ
        IF
          odd.site
            twiddle (datum, x \ p, p)
          TRUE
            SKIP
        PERM.XOR (x, import, datum, p)
        IF
          odd.site 
            datum := [import [0] - datum [0], import [1] - datum [1]]
          TRUE
            datum := [import [0] + datum [0], import [1] + datum [1]]
\end{verbatim}
}

\newpage

\section*{Example---optimal matrix multiplication}

% Notes:
%
%    Ask dlg about this

\begin{verbatim}
    SEQ
      INDEX.broadcast (y, a, 0)
      INDEX.broadcast (x, b, 0)
      matmul (c, a, b, m, l, n)
      MERGE.EL.REAL32.VEC.SUM (z, C, c, 0)
\end{verbatim}

\newpage


\section*{I/O}

\begin{itemize}
\item     As well as operations for communication {\em within\/} a particular
process array, the library has a sophisticated set of routines for
sequential I/O.
\item These allow a process array to talk to an external
process (e.g., a master or host process, or other process arrays---perhaps
an array of graphics processors, etc).
\item     For these purposes a second type of communication structure is
introduced---a logical ``distributed channel''.
\end{itemize}

\newpage

\section*{Mixing indices and distributed channels}

% figure `nets' goes here.
% magnified by 0.25
%\begin{figure}[h]
\centerline{\psfig{figure=nets.ps}}
%\end{figure}

\newpage

\section*{Configuration}

\begin{itemize}
%\item     The communication library was documented and put into a releasable
%form earlier this year.  Since then concentrated on dynamic configuration
%procedures for process arrays.
\item     With static process configuration the channel connectivity
of the networks is exposed to the user in the configuration file.
This is a failure of abstraction---the underlying virtual channels
are supposed to be hidden (transparent).
\item     By configuring ``procedurally''---using the dynamic features
of VCR---have possibility of hiding channels {\em completely\/}.  Also,
this run-time configuration is more flexible.
\end{itemize}

\newpage

\section*{Dynamic Configuration}

\begin{itemize}
\item     The implemented ACL primitives for dynamic configuration use the
remote procedure call, dynamic channel creation, and channel-moving
operations provided in VCR.
\item    One of the most important operations for dynamic configuration is
``channel-copying''.  Given a virtual channel connecting two processes,
the channel-copying operation creates a new, independent, virtual
channel connecting the same processes.
\end{itemize}

\newpage

\section*{Spawning of an ``All-to-All'' Network}

% figure `life' goes here.
% magnified by 0.23
%\begin{figure}[h]
\centerline{\psfig{figure=life.ps}}
%\end{figure}

\end{document}

