\begin{slide}{}

\begin{center}
{\Large An Outline Proposal for the PCRC Library Interface}
\end{center}

\begin{center}
D.B. Carpenter \\
{\bf Northeast Parallel Architectures Center} \\
{\bf Syracuse University } \\
{\bf 111 College Place } \\
{\bf Syracuse NY 13244-4100 }
\end{center}

\end{slide}




\begin{slide}{Introduction}

\begin{center}
\bf Introduction
\end{center}

Will sketch a possible interface to the PCRC run-time library.

Give concrete procedure interfaces in C.

``Concrete syntax'' will change later (eg, need systematic naming
convention for the routines).  For now, important agree on the
underlying semantics of the library

\end{slide}


\begin{slide}{Structure of the library}

The library contains two types of routine.
\begin{itemize}
\item
``Housekeeping'' routines: local procedures for
address translation, enumeration of local subranges, etc.
\item
Collective operations: collective communications, and collective
arithmetic operations.  
\end{itemize}

\end{slide}

\begin{slide}{Process coordinates}

\begin{center}
\bf Process coordinates
\end{center}

There are two important run-time operations associated with process
arrays (processor arrangements).

\begin{enumerate}
\item
Determine if {\em this} processor
holds {\em any} element of of the logical process array, and
\item
Determine the position (the {\em process coordinates}) of this
processor within the process array.  (Assumes max one logical
process/processor)
\end{enumerate}

\end{slide}

\begin{slide}{Process coordinate routines}

\begin{verbatim}
  int procs(int rank, int* shape) ;

  int on(int procsHandle) ;

  void crds(int* coords, int procsHandle) ;
\end{verbatim}
\verb$procs$ returns an integer handle to a process array.
\verb$on$ return a non-zero value if local processor holds
any element of the process array.
\verb$crds$ returns coordinates of local process in vector \verb$coord$.

\end{slide}


\begin{slide}{Address translation}

\begin{center}
\bf Address translation
\end{center}

Routines define mapping between HPF-program-level global subscripts
and pairs of the form
\begin{verbatim}
  (coord, l_i)
\end{verbatim}
\verb$l_i$ a local index, \verb$coord$ is a process coordinate

\end{slide}

\begin{slide}{Address translation interfaces}

Primitive conversion routines
\begin{verbatim}
  void globToLoc(int* coord, int* l_i, int g_i,
    int g_lb, int g_ub, int offset, int stride,
    int t_lb, int t_ub, int distCode, int numProcs) ;

  void locToGlob(int* g_i, int coord, int l_i,
    int g_lb, int g_ub, int offset, int stride,
    int t_lb, int t_ub, int distCode, int numProcs) ;
\end{verbatim}
The procedure \verb$globToLoc$ takes \verb$g_i$ and returns
\verb$*coord$ and \verb$*l_i$.  \verb$locToGlob$ does reverse
translation.

\end{slide}

\begin{slide}{Address translation convenient}

More convenient interfaces are
\begin{verbatim}
  void globToLoc(int* coord, int* l_i, int g_i,
                 DIM* range) ;

  void locToGlob(int* g_i, int coord, int l_i,
                 DIM* range) ;
\end{verbatim}
Work in terms of the \verb$DIM$ structure in the DAD.

\end{slide}

\begin{slide}{Address translation example}

The HPF fragment
\begin{verbatim}
  a(i) = 27
\end{verbatim}
could be translated (to C) as
\begin{verbatim}
  globToLoc(&coord, &l_i, i, a_DAD.axes) ;

  if(coord == locCoord)
    a_LOC [l_i - 1] = 27 ;
\end{verbatim}
\verb$locCoord$ is the coordinate of the local processor,
\verb$a_LOC$ is the C array holding the local segment of \verb$a$.

\end{slide}

\begin{slide}{Parallel iteration}


\begin{center}
\bf Parallel iteration
\end{center}

\begin{verbatim}
  void locBlock(int* l_lb, int* l_ub, int* l_stride,
    int g_lb, int g_ub, int offset, int stride,
    int t_lb, int t_ub, int distCode, int numProcs,
    int coord) ;
\end{verbatim}
computes the parameters \verb$l_lb$, \verb$l_ub$ and \verb$l_stride$
of segment of array held on processor with coordinate \verb$coord$.
A more convenient interface is
\begin{verbatim}
  void locBlock(int* l_lb, int* l_ub, int* l_stride,
                DIM* range, int coord) ;
\end{verbatim}

\end{slide}

\begin{slide}{locBlock example 1}

\tiny

\begin{verbatim}
BLOCK, numProcs 5, t_lb 1, t_ub 32, g_lb 8, g_ub 15, offset 4, stride 3

     coord      l_lb      l_ub  l_stride
         0         5         5         3
         1         1         7         3
         2         3         6         3
         3         2         5         3
         4         1        -2         3

l_i\coord    0       1       2       3       4

   1         -       9       -       -       -

   2         -       -       -      14       -

   3         -       -      12       -       -

   4         -      10       -       -       -

   5         8       -       -      15       -

   6         -       -      13       -       -

   7         -      11       -       -       -
\end{verbatim}

\end{slide}

\begin{slide}{locBlock example 2}

\tiny

\begin{verbatim}
CYCLIC, numProcs 6, t_lb 1, t_ub 42, g_lb 1, g_ub 10, offset 40, stride -4

     coord      l_lb      l_ub  l_stride
         0         3         7         2
         1         1         0         1
         2         2         6         2
         3         1         0         1
         4         1         7         2
         5         1         0         1

l_i\coord    0       1       2       3       4       5

   1         -       -       -       -      10       -

   2         -       -       9       -       -       -

   3         8       -       -       -       7       -

   4         -       -       6       -       -       -

   5         5       -       -       -       4       -

   6         -       -       3       -       -       -

   7         2       -       -       -       1       -
\end{verbatim}

\end{slide}


\begin{slide}{Parallel iteration example}

\verb$locBlock$ used to initialise the \verb$l_lb$
and \verb$l_ub$ fields in the DAD, or used directly
to translate parallel loops.  Will use the example
\begin{verbatim}
  FORALL (i = l : u : s)
    a(i) = ...
  END FORALL
\end{verbatim}

\end{slide}

\begin{slide}{Parallel iteration translation 1}

First translation:
\begin{verbatim}
  DIM* j = a_DAD.axes ;
  locBlock(&l_lb, &l_ub, &l_stride,
      l, u,
      offset + (l - j->g_lb) * j->stride, s * j->stride,
      j->t_lb, j->t_ub, j->distCode, j->numProcs,
      locCoord) ;
  for(l_i = l_lb ; l_i <= l_ub ; l_i += l_stride)
    a_LOC [l_i - 1] = ...
\end{verbatim}

\end{slide}

\begin{slide}{Parallel iteration translation 2}

Second translation:
\begin{verbatim}
  DIM i ;
  rangeSection(&i, a_DAD.axes, l, u, s, locCoord) ;
  locBlock(&l_lb, &l_ub, &l_stride, &i, locCoord) ;
  for(l_i = l_lb ; l_i <= l_ub ; l_i += l_stride)
    a_LOC [l_i - 1] = ...
\end{verbatim}
where introduced new constructor function
\begin{verbatim}
  void rangeSection(DIM* range, DIM* parent,
               int l, int u, int s, int locCoord) ;
\end{verbatim}

\end{slide}

\begin{slide}{Parallel iteration translation 3}

Third translation:
\begin{verbatim}
  DIM i ;
  rangeSection(&i, a_DAD.axes, l, u, s) ;
  for(l_i = i.l_lb ; l_i <= i.l_ub ; l_i += i.l_stride)
    a_LOC [l_i - 1] = ...
\end{verbatim}
Depends on to extensions to the DAD (add \verb$locCoord$ and
\verb$l_stride$ fields to \verb$DIM$.  Removed redundant
last argument of constructor \verb$rangeSection$.)

Assumes constructor intialises \verb$l_i$, etc.

\end{slide}

\begin{slide}{Miscellaneous constructors}

\begin{center}
\bf Miscellaneous constructors
\end{center}

Constructors are functions that initialise fields of a
data structure, eg \verb$rangeSection$.

Another \verb$DIM$ constructor,
\begin{verbatim}
  void range(DIM* range,
    int g_lb, int g_ub, int offset, int stride,
    int t_lb, int t_ub, int distCode,
    int numProcs, int locCoord) ;
\end{verbatim}
which initialises all fields of a \verb$DIM$ structure.
Calls \verb$locBlock$ internally to initialise
the \verb$l_lb$, \verb$l_lu$ fields.

\end{slide}

\begin{slide}{DAD constructors}

DAD constructors also needed.  Eg, copy constructor.  Also, section
constructor:
\begin{verbatim}
  void arraySection(DAD* array, DAD* parent, 
                    int l1, int u1, int s1,
                    int l2, int u2, int s2,
                    ...)
\end{verbatim}
New DAD describes the section
\begin{verbatim}
  a (l1 : u1 : s1, l2 : u2 : s2, ...)
\end{verbatim}

\end{slide}

\begin{slide}{Collective operations}

\begin{center}
\bf Collective operations
\end{center}

Three broad categories
\begin{itemize}
\item
Operations that copy data held in regular sections
to other regular sections with different mapping.
Eg shifts, transpose, broadcast.
\item
Gather or scatter operations.
Eg array assignments with vector subscript, forall with
non-linear subscripts.
\item
Collective arithmetic operations.  Eg reductions,
matrix arithmetic.
\end{itemize}

\end{slide}

\begin{slide}{Regular data remapping}

\begin{center}
\bf Regular data remapping
\end{center}

Prototype operation in this category
\begin{verbatim}
  void remap(DAD* dst, DAD* src) ;
\end{verbatim}
Copies the values in the array described by \verb$*src$
to the array described by \verb$dst$.

\end{slide}

\begin{slide}{Remap example}

Example
\begin{verbatim}
  FORALL (i = l : u : s)
    a(i) = b(i) + ...
  END FORALL
\end{verbatim}
where \verb$a$ and \verb$b$ have unrelated mappings.

\end{slide}

\begin{slide}{Remap example translation}

Translation:
\begin{verbatim}
  arraySection(&bSect_DAD, &b_DAD, l, u, s) ;
  arraySection(&tmpSect_DAD, &tmp_DAD, l, u, s) ;

  remap(&tmpSect_DAD, &bSect_DAD) ;

  DIM* i = tmpSect_DAD.axes ;
  for(l_i = i->l_lb ; l_i < i->l_ub ;
                             l_i += i->l_stride)
    a_LOC [l_i - 1] = tmp_LOC [l_i - 1] + ...
\end{verbatim}
Compiler sets up \verb$tmp$ with same mapping as \verb$a$.

\end{slide}

\begin{slide}{broadcast}

Because no replicated alignments, \verb$remap$ does not directly
implement broadcast operations.

An array element can be broadcast by
\begin{verbatim}
  void broadcast(void* dst, DAD* src,
                 int i1, int i2, ...) ;
\end{verbatim}
\verb$i1$, \verb$i2$, \ldots are global subscripts.

May or may not be necessary to provide lower-level operation
which broadcasts arbitrary datum from specified processor.

\end{slide}

\begin{slide}{remapShift}

Streamlined versions of \verb$remap$ can be provided for special
cases, eg
\begin{verbatim}
  void remapShift(DAD* dst, DAD* src, int dim) ;
\end{verbatim}
\verb$dst$ and \verb$src$ have
identical alignments except in dimension
\verb$dim$.  In this dimension alignments only
differ in their offset.

Also provide F90 intrinsics \verb$CSHIFT$, \verb$EOSHIFT$,
\verb$TRANSPOSE$, \verb$SPREAD$, etc.

\end{slide}

\begin{slide}{Gather and scatter operations}

\begin{center}
\bf Gather and scatter operations
\end{center}

Implement parallel assignments with irregular patterns
of subscripting.

Eg \verb$a$ is an \verb$n$-element array, \verb$b$ is a rank-2
array:
\begin{verbatim}
  FORALL (i = 1 : n)
    a(i) = b(f(i), g(i))
  END FORALL
\end{verbatim}
\verb$f$ and \verb$g$ are arbitrary functions.

\end{slide}

\begin{slide}{Gather example translation}

Translation:
\begin{verbatim}
  DIM* i = a_DAD.axes ;

  /* Compute subscript arrays, `tmp1', `tmp2' */
  for(l_i = i->l_lb ; l_i < i->l_ub ; l_i += i->l_stride) {
    int g_i ;
    locToGlob(&g_i, locCoord, l_i, i) ;

    tmp1_LOC [l_i - 1] = f(g_i) ;
    tmp2_LOC [l_i - 1] = g(g_i) ;
  }
  ...
\end{verbatim}

\end{slide}

\begin{slide}{Gather example translation continued}

Translation (continued):
\begin{verbatim}
  DAD* subs [2] ;
  ...

  /* gather data */
  subs [0] = &tmp1_DAD ;
  subs [2] = &tmp2_DAD ;
  gather(a, b, subs) ;
\end{verbatim}

\end{slide}

\begin{slide}{Gather, scatter interfaces}

The general \verb$gather$ operation has interface
\begin{verbatim}
  void gather(DAD* gath, DAD* scat, DAD* [] subs) ;
\end{verbatim}
Subscript arrays have same shape and mapping as {\em gathered data}.
Number of subscripts equal to rank of {\em scattered data}.

Similarly
\begin{verbatim}
  void scatter(DAD* gath, DAD* scat, DAD* [] subs) ;
\end{verbatim}

\end{slide}

\begin{slide}{Collective arithmetic operations}

\begin{center}
\bf Collective arithmetic operations
\end{center}

Reduction operations and matrix arithmetic operations (and other
operations in the HPF library) can be implemented directly.

Eg, F90 \verb$MATMUL$ function supported through
the procedure
\begin{verbatim}
  void matmul(DAD* result, DAD* a, DAD* b) ;
\end{verbatim}
Mappings of the three arguments unrelated.

\end{slide}

\begin{slide}{Problems with the DAD}

\begin{center}
\bf Problems with the DAD
\end{center}

\begin{itemize}
\item
Does not distinguish triplet subscripts of extent one from
scalar subscripts.
\item
Includes non-default lower bounds on global indices.
Causes problems at procedure boundaries, where lower bounds
change.
\item
\verb$DIM$ does not have a \verb$l_stride$ field.
\item
\verb$DIM$ does not have a \verb$locCoord$ field.
\end{itemize}

\end{slide}

