
\documentstyle{article}

\input{psfig} 

\begin{document}

\sloppy

\pagestyle{plain}

\title{\em An Outline Proposal for the PCRC Library Interface}

\author{D.B. Carpenter \vspace{0.25in} \\ 
        \em Northeast Parallel Architectures Centre, \\
        \em Syracuse University, \\
        \em 111 College Place, \\
        \em Syracuse, New York 13244-410} 

\date{DRAFT}

\maketitle

\tableofcontents

\newpage

\section{Introduction}

This document sketches a possible interface to the PCRC run-time
library.  The text includes various concrete procedure interfaces in
C.  This ``concrete syntax'' will definitely change later.  For now the
important thing is to define the underlying semantics of the
library\footnote{So, for example, this text does not to adopt a
systematic naming convention for the routines, such as pre-pending {\tt
PCRC} to the name of every procedure, and it sometimes slips into
C++-style overloading of names.}.

The library contains two types of routine.
\begin{itemize}
\item
``Housekeeping'' routines: local procedures used for operations
such as translation between
global indices and local indices, enumeration of local subranges,
and initialising DAD records.
\item
Collective operations: collective communications, and collective
arithmetic operations.  
\end{itemize}
Section \ref{housekeeping} outlines a possible set of routines in the
first category.  Section \ref{collective} gives examples of routines in
the second category.  Eventually this category will include support for
all the array intrinsic functions of Fortran 90 and HPF.

The text of this paper includes possible translations of various HPF
fragments to C.  A preliminary glossary of C function interfaces is
collected in the appendix.  Once the principles of the library are
agreed, Fortran interfaces can also be defined.

The appendix also discusses some problems we have encounterd with the
{\em Distributed Array Descriptor} (DAD) defined in \cite{DAD}.
Some improvements are suggested.


\section{\label{housekeeping}Local housekeeping}

This section proposes ``top-level'' routines to perform various
housekeeping operations.  It is presumed that an optimising compiler
will often place the implementations of lightweight operations
(such as these) in-line in the generated code.

\subsection{\label{process}Process coordinates.}

HPF has an idea of processor arrangements, which are multi-dimensional
arrays of logical processes.

There are two important run-time operations associated with process
arrays.
\begin{enumerate}
\item
determine if {\em this} processor
holds {\em any} element of of the logical process array
(example: the processor arrangement may be scalar, in which
case only the host or root processor typically holds any data
distributed over it), and
\item
determine the position (the {\em process coordinates}) of this
processor within the process array.
\end{enumerate}
The second function tacitly assumes that there is at most one logical
process mapped to each physical processor, an implementation
restriction permitted by the HPF 1.0 definition.

It is proposed that each process array has an integer {\em handle}
associated with it.  This allows process arrays to be referenced
uniquely.  A handle is returned by the ``constructor'' function
\begin{verbatim}
  int procs(int rank, int* shape) ;
\end{verbatim}
\verb$rank$ is the rank of the arrangement (0 for a scalar array,
1 for a 1-dimensional array, etc) and \verb$shape$ is a vector of
extents (sizes of individual dimensions).  \verb$procs$ will always
return different handles for process arrays of different shapes {\em
and always return the same handle for process arrays of the same
shape}.

The two functions described earlier are provided through
\begin{verbatim}
  int on(int procsHandle) ;
\end{verbatim}
which returns a non-zero value if the local processor holds
any element of the process array, and
\begin{verbatim}
  void crds(int* coords, int procsHandle) ;
\end{verbatim}
which return coordinates in the vector \verb$coord$.  The length of
this vector should be the rank of the process array.  An individual
coordinate is in the range $0, \ldots, p - 1$, where $p$ is the extent
of the process array in the associated dimension.


\subsection{\label{addressTranslation}Address translation.}

A {\em global subscript} is an HPF-program-level index into a distributed
array.  A {\em local subscript} is an index into the locally held segment of
the distributed array.

Following the proposal in \cite{DAD}, the local
segments of an aligned array are allocated {\em as if} the array has
the shape of its template.  If the array is aligned to just a section
of its template, elements of the allocated array outside the alignment
section remain unused.

A {\em template subscript} is a global index into a template.

Address translation has two components.  There is a mapping
from global subscript to template subscript---this part of the
mapping depends on on the alignment parameters of the array.  Then
there is a mapping between template subscripts and
pairs of the form
\begin{verbatim}
  (coord, l_i)
\end{verbatim}
where \verb$l_i$ is a local index and \verb$coord$ is a process
coordinate---this part of the mapping depends only on the size and
distribution format of the template.

The primitive routines
for converting between global an local indices are
\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 a global subscript \verb$g_i$
and returns a coordinate and local subscript pair \verb$*coord$
and \verb$*l_i$.  The procedure \verb$locToGlob$ performs the
reverse translation.  The remaining parameters are fields in
the DAD describing the mapping of an individual array dimension.

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}
which work in terms of the \verb$DIM$ structure in the DAD.
This \verb$DIM$ structure can be extracted directly from the DAD.
For example, if \verb$a_DAD$ is the DAD of some array, a
pointer to the \verb$DIM$ structure for the \verb$d$th dimension
is given by
\begin{verbatim}
  a_DAD.axes + d ;
\end{verbatim}
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}
assuming \verb$locCoord$ is the coordinate of the local processor
in the relevant process dimension, and \verb$a_LOC$ is the C array
holding the local segment of the HPF array.

\subsection{\label{iteration}Parallel iteration}

The function
\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 the segment of an array held on a process with coordinate \verb$coord$.
In the simplest case,
where the alignment is trivial,
and the template extent divides the process extent exactly, the values
of the three returned parameters are just
\begin{verbatim}
  *l_lb     = 1
  *l_ub     = t_blockSize
  *l_stride = 1
\end{verbatim}
\verb$t_blockSize$ being the extent of a local segment.
In general the local lower bound, upper bound and stride have
non-trivial value.  The returned value \verb$*l_stride$ is always
positive, even if \verb$stride$ is negative.  A couple of
examples are given in figures \ref{eg1} and \ref{eg2}.
\begin{figure}[btp]
\centerline{\psfig{figure=eg1.eps,height=3in}}
\caption{\label{eg1}
Output of {\tt locBlock} for {\tt distCode} = 1, {\tt numProcs} = 5,
{\tt t\_lb} = 1, {\tt t\_ub} = 32, {\tt g\_lb} = 8, {\tt g\_ub} = 15,
{\tt offset} = 4, {\tt stride} = 3}
\end{figure}
\begin{figure}[btp]
\centerline{\psfig{figure=eg2.eps,height=3in}}
\caption{\label{eg2}
Output of {\tt locBlock} for {\tt distCode} = 2, {\tt numProcs} = 6,
{\tt t\_lb} = 1, {\tt t\_ub} = 42, {\tt g\_lb} = 1, {\tt g\_ub} = 10,
{\tt offset} = 40, {\tt stride} = -4}
\end{figure}

A more convenient interface is
\begin{verbatim}
  void locBlock(int* l_lb, int* l_ub, int* l_stride,
                DIM* range, int coord) ;
\end{verbatim}

The procedure \verb$locBlock$ is used to initialise the \verb$l_lb$
and \verb$l_ub$ fields in the DAD, or it could be used directly
to translate parallel loops.  For example
\begin{verbatim}
  FORALL (i = l : u : s)
    a(i) = ...
  END FORALL
\end{verbatim}
could be translated by
\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}
If the RHS of the forall assignment involves the value \verb$i$ in some
functional context (eg, \verb$SIN(q * i)$) the value of the global
index can be recovered from \verb$l_i$ by using the \verb$locToGlob$
address translation function introduced in section
\ref{addressTranslation} (see section \ref{gatherScatter} for
an example).

The more compact second form of the \verb$locBlock$ interface can
be used in this translation if we introduce an additional function
\begin{verbatim}
  void rangeSection(DIM* range, DIM* parent,
                    int l, int u, int s, int coord) ;
\end{verbatim}
This initialises a new \verb$DIM$ structure aligned with the
original one through the triplet \verb$l : u : s$.
Then the opaque fragment 
\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) ;
\end{verbatim}
can be replaced by the more concise
\begin{verbatim}
  DIM i ;
  rangeSection(&i, a_DAD.axes, l, u, s, locCoord) ;
  locBlock(&l_lb, &l_ub, &l_stride, &i, locCoord) ;
\end{verbatim}
The \verb$rangeSection$ function can also be used to initialise
the \verb$DIM$ fields in a DAD describing a Fortran 90 regular
section of some parent array.

[{\em Aside}: the \verb$coord$ parameter to \verb$rangeSection$ is
needed so that the fields \verb$l_lb$, \verb$l_ub$ {\em within} that
structure can be initialised.  If the \verb$DIM$ structure was extended
to include a \verb$locCoord$ field, this parameter could be omitted,
because its value could be taken from the parent structure.]

[{\em Aside}: if, additionally the \verb$DIM$ structure was extended to
include the \verb$l_stride$ field, the whole translation of the
original HPF fragment could be simplified to
\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}
because we would expect the \verb$rangeSection$ operation to
initialise the fields \verb$l_lb$, \verb$l_ub$ and \verb$l_stride$
of \verb$i$, by calling \verb$locBlock$ internally.]

\subsection{\label{constructors}Miscellaneous constructors}

In this context a {\em constructor} means
a function which initialises the fields of a data structure.
The relevant data structures here are the \verb$DAD$ structure
itself and the \verb$DIM$ structure.

One example of a \verb$DIM$ constructor,
is the function \verb$rangeSection$.  Another useful example is
\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
(it will probably call \verb$locBlock$ internally to initialise
the \verb$l_lb$, \verb$l_lu$ fields).

DAD constructors will also be useful.  For example a
{\em section} constructor could have the interface
\begin{verbatim}
  void arraySection(DAD* array, DAD* parent, 
                    int l1, int u1, int s1,
                    int l2, int u2, int s2,
                    ...)
\end{verbatim}
If \verb$*parent$ describes an array \verb$a$, the result \verb$*array$
describes the section
\begin{verbatim}
  a (l1 : u1 : s1, l2 : u2 : s2, ...)
\end{verbatim}
This interface needs some further elaboration; a mechanism is needed
to allow simple subscripts (as well as subscript triplets) to be
represented.

The \verb$DAD$ constructor \verb$arraySection$ will probably call
the \verb$DIM$ constructor \verb$rangeSection$ internally.


\section{\label{collective}Collective operations}

Collective operations can be divided into three broad categories
\begin{itemize}
\item
Operations which take data held in regular sections of one distributed
array, and copy the values into regular sections of another distributed
or sequential array.  Familar examples are shifts, transposes and
broadcasts.
\item
Operations which gather or scatter data using more general patterns of
subscripting.  In Fortran 90, a familar example is an array assignment
using a vector subscript; in HPF or Fortran 95, another example is a
forall assignment where the subscript expression are non-linear
functions of the forall indices.  More esoteric examples include the
{\em combining scatter} functions in the HPF library.
\item
Collective arithmetic operations on regular data.  These include reduction
operations operations and matrix arithmetic.
\end{itemize}

\subsection{Regular data remapping}

The majority of operations in this class can be reduced to HPF
array assignments in which a regular section of one array is
assigned to a regular section of another.  Broadcasts fall into
this category if we regard an array element as a rank-0 section
of an array.

As the prototype operation in this category we propose
\begin{verbatim}
  void remap(DAD* dst, DAD* src) ;
\end{verbatim}
which simply copies the values in the array described by \verb$*src$
to the array described by \verb$dst$.

A construct such as
\begin{verbatim}
  FORALL (i = l : u : s)
    a(i) = b(i) + ...
  END FORALL
\end{verbatim}
in which \verb$a$ and \verb$b$ may have unrelated distribution
formats, might be translated by
\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}
This is very similar to the example in section \ref{housekeeping}, but
now the selected section of array \verb$b$ needs to be remapped to a
section of a temporary aligned with \verb$a$ before the computation can
proceed.  We assume that \verb$tmp$ has been set up by the compiler
with the same mapping parameters as \verb$a$.  The section constructors
introduced in section \ref{constructors} are called to build DADs
for the sections of \verb$b$ and \verb$tmp$ which will be referenced
in the loop.  Then the \verb$remap$ operation is invoked to perform
the communication.

Because the PCRC distributed data model is proposed not to support
replicated alignments, the \verb$remap$ operation 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}
Here \verb$i1$, \verb$i2$, \ldots are the global subscripts
for the element.
It may or may not be necessary to provide a lower-level operation
which broadcasts an arbitrary datum from a specified processor.

Due to its generality, some compromises with efficiency will be
required in implementing \verb$remap$.  Therefore less general
variants which impose restrictions on the alignments of their
arguments may be provided.  One which has been mooted is
\begin{verbatim}
  void remapShift(DAD* dst, DAD* src, int dim) ;
\end{verbatim}
This variant assumes \verb$dst$ and \verb$src$ have
identical alignments except in the dimension selected by
\verb$dim$, and in this dimension their alignments only
differ in their offset.  If the compiler establishes such a
relationship between alignments, this streamlined routine can be
called.

The \verb$remap$ operation is already very general, but there are some
common situations which it does not cover.  For example it cannot
implement the F90 \verb$TRANPOSE$ intrinsic, and (again because the PCRC
distributed data model is proposed to not support replicated alignments) it
cannot implement the \verb$SPREAD$ intrinsic.  So we propose a
slightly more general operation
\begin{verbatim}
  void promote(DAD* dst, DAD* src, int* injection) ;
\end{verbatim}
The rank of the array described by \verb$*dst$ is greater than
or equal to the rank of the array described by \verb$*src$.
The length of the \verb$injection$ vector the rank of the
{\em source} array; its elements are distinct values in
the range $0, \ldots, r - 1$, where $r$ is the rank of the
{\em destination} array.  Values in the source array are copied
to the destination, mapping dimensions of the source to dimensions
of the destination according to the injection vector.  The
values are replicated in any dimension of the destination
not selected by an element of the injection vector.
For example, if \verb$a$ and \verb$b$ are both rank 2 arrays,
the operation
\begin{verbatim}
  inj [0] = 1 ; inj [1] = 0 ;
  promote(&b_DAD, &a_DAD, inj) ;
\end{verbatim}
implements a transpose.  If \verb$a$ is rank 1 and \verb$b$ is
rank 2, the operation
\begin{verbatim}
  inj [0] = 0 ;
  promote(&b_DAD, &a_DAD, inj) ;
\end{verbatim}
copies the values in \verb$a$ into \verb$b$, replicating them
in the second dimension of \verb$a$.  It implements a ``spread''
operation.

The general procedures described above may be supplemented by
additional entry points which directly support intrinsic operations
such as \verb$CSHIFT$ and \verb$EOSHIFT$.


\subsection{\label{gatherScatter}Gather and scatter operations}

To implement parallel assignments with irregular patterns
of subscripting we need gather and scatter operations.

Suppose \verb$a$ is an \verb$n$-element array and \verb$b$ is a rank-2
array.  The fragment
\begin{verbatim}
  FORALL (i = 1 : n)
    a(i) = b(f(i), g(i))
  END FORALL
\end{verbatim}
where \verb$f$ and \verb$g$ are arbitrary functions, can be translated
in two steps.  First arrays of subscript values are computed,
then a {\em gather} operation is invoked.
\begin{verbatim}
  DIM* i = a_DAD.axes ;
  DAD* subs [2] ;

  /* 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) - 1 ;
    tmp2_LOC [l_i - 1] = g(g_i) - 1 ;
  }

  /* gather data */
  subs [0] = &tmp1_DAD ;
  subs [1] = &tmp2_DAD ;
  gather(a_DAD, b_DAD, subs) ;
\end{verbatim}
This assumes the compiler has set up \verb$tmp1$ and \verb$tmp2$ with
the same alignment parameters as \verb$a$.

The general \verb$gather$ operation has interface
\begin{verbatim}
  void gather(DAD* gath, DAD* scat, DAD* [] subs) ;
\end{verbatim}
Here \verb$gath$ describes the {\em gathered data} and \verb$scat$ describes the {\em
scattered data}.  These is followed followed by a vector of DADs describing
the subscript arrays, which are
integer arrays with the same shape and mapping as the {\em gathered
data}.  The number of subscript arrays should be equal to the rank of the
scattered data, and the values of their elements should lie in the
ranges expected for subscripts of that array.  Data is copied from
\verb$scat$ to \verb$gath$ with the specified subscripting pattern.

A completely analogous primitive \verb$scatter$ copies data from
\verb$gath$ to \verb$scat$:
\begin{verbatim}
  void scatter(DAD* gath, DAD* scat, DAD* [] subs) ;
\end{verbatim}

% [FOLLOWING DOESN'T WORK BECAUSE WE DON'T HAVE REPLICATED ALIGNMENTS
% FOR THE SUBSCRIPT VECTORS]
%
%These operations are unnecesarily general if it is only required to
%implement the patterns of access in Fortran 90 array syntax.
%Vector subscripts can be handled by the simpler primitives
%\begin{verbatim}
%  void vecGather(DAD& gath, DAD& scat, DAD* [] subs) ;
%  void vecScatter(DAD& gath, DAD& scat, DAD* [] subs) ;
%\end{verbatim}
%where now \verb$a$ and \verb$b$ have the same rank, and the subscripts
%are rank-1 arrays, whose individual ranges are the same as the
%corresponding to range of \verb$b$.  If any subscript element is a
%null pointer it is assumed that the gathered and scattered
%data have the same extent in the associated dimension, and the
%operation behaves like a regular array assignment with respect to that
%dimension.  If \verb$a$ and \verb$b$ are rank-2 arrays and \verb$v$ is
%an integer vector, the HPF statement

The F90 \verb$reshape$ intrinsic can be implemented by a
\verb$gather$ operation, but in practise an extra library operation may
be provided to implement this function directly.

\subsection{Collective arithmetic operations}

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

For example the F90 \verb$MATMUL$ function can be supported through
the procedure
\begin{verbatim}
  void matmul(DAD* result, DAD* a, DAD* b) ;
\end{verbatim}
The mappings of the three arguments need not be related.

\newpage

\appendix

\section{Glossary of Function Interfaces}

\begin{figure}[hp]
\begin{verbatim}
  int procs(int rank, int* shape) ;

  int on(int procsHandle) ;
  void crds(int* coords, int procsHandle) ;
\end{verbatim}
%\caption{Process coordinates, see section \ref{process}.}
\caption{Process coordinates, see section 2.1.}
\end{figure}

\begin{figure}[hp]
\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) ;

  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}
%\caption{Address translation, see section \ref{addressTranslation}.}
\caption{Address translation, see section 2.2.}
\end{figure}

\begin{figure}[hp]
\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) ;

  void locBlock(int* l_lb, int* l_ub, int* l_stride,
                DIM* range, int coord) ;
\end{verbatim}
%\caption{Parallel iteration, see section \ref{iteration}.}
\caption{Parallel iteration, see section 2.3.}
\end{figure}

\begin{figure}[hp]
\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) ;

  void rangeSection(DIM* range, DIM* parent,
                    int l, int u, int s, int coord) ;

  void arraySection(DAD* array, DAD* parent, 
                    int l1, int u1, int s1,
                    int l2, int u2, int s2,
                    ...)
\end{verbatim}
%\caption{Constructors, see section \ref{constructors}.}
\caption{Constructors, see section 2.4.}
\end{figure}

\begin{figure}[hp]
\begin{verbatim}
  void remap(DAD* dst, DAD* src) ;
  void promote(DAD* dst, DAD* src, int* injection) ;
  void broadcast(void* dst, DAD* src, int i1, int i2, ...) ;
  void remapShift(DAD* dst, DAD* src, int dim) ;

  void gather(DAD& gath, DAD& scat, DAD* [] subs) ;
  void scatter(DAD& gath, DAD& scat, DAD* [] subs) ;

  void matmul(DAD* result, DAD* a, DAD* b) ;
\end{verbatim}
%\caption{Collective operations, see section \ref{collective}.}
\caption{Collective operations, see section 3.}
\end{figure}

\newpage

\section{Remarks on the DAD}

\subsection{Some shortcomings of the current definitiion}

There are a few problems with the DAD, as defined in \cite{DAD}.
\begin{enumerate}
\item
The DAD does not distinguish triplet subscripts of extent one from
scalar subscripts.  This causes problems with operations
that depend on absolute dimension values.

For example the \verb$DIM$ parameter of \verb$CSHIFT$ selects a
dimension in its array (section) argument, {\em not} the template.  If
the array (section) happens to have some dimensions of extent 1, the
DAD does not define a unique mapping from array (section) dimension
to template dimension.

\item
The DAD includes non-default lower bounds on global indices.  This
causes problems at the procedure boundary, where lower bounds generally
change.  Lower bounds are not intrinsic properties of array
objects in Fortran.  They are associated with array variable
{\em names}, not the data themselves.  So it is not really appropriate
to have these bounds in the data representation.

It would be preferable to standardize on zero for the base subscript of
all arrays.  (Of course this standard only applies in the run-time
representation.  The language compiler is free to emit subscript
expressions implementing any lower bound for a given variable.)

\item
The DAD does not have a \verb$l_stride$ field (see section \ref{iteration}).
This is not a bug, but it is inconvenient to have \verb$l_lb$ and
\verb$l_ub$ but {\em not} \verb$l_stride$.

\item
The DAD does not have a \verb$locCoord$ field.  This is not a bug, but it is
inconvenient to have \verb$numProcs$ but {\em not} \verb$locCoord$.
\end{enumerate}

\subsection{An improved definition}

A proposed revision of the DAD, to fix these problems:

The fields in \verb$DIM$ are changed to
\begin{verbatim}
  g_extent        Global extent of section dimension.
  l_lb            As existing definition, but
                             in range 0, ..., t_blockSize - 1.
  l_ub             "     "         "       "
                              "    "       "       "
  l_stride        Stride of local segment in local index space.

  offset          As existing definition
  stride                 "         "

  distCode               "         "
  numProcs               "         "
  locCoord        local process coord
                             in range 0, ..., numProcs - 1
  
  t_extent        Global extent of template dimension
  t_blockSize     Size of local block of template
\end{verbatim}
If the template dimension is scalar-subscripted, the information 
in \verb$DIM$ should be 
\begin{verbatim}
  l_i             Location of section in local index space.
  coord           Process coord at which section is held.

  distCode        As above
  numProcs         "   "
  locCoord         "   "
  
  t_extent         "   "
  t_blockSize      "   "
\end{verbatim}
A flag should be added to distinguish these two cases.  To avoid using
unions, which may cause problems in Fortran, the second case can
be encoded by storing, say, \verb$l_i$ in \verb$l_lb$, and \verb$coord$
in \verb$l_ub$.

\subsection{The data model}

Apparently HPFF has now downgraded {\em Kernel HPF}
to a set of recommendations on programming style.  The
data model of the HPF 2.0 language will probably include 
the full HPF 1.0 model.

We should consider reinstating the remaining omitted
features of the HPF 1.0 model.

The absence of replicated alignments is a particular case.
Several simplifications to the RTL interface could be achieved
if we were supporting this feature.

\begin{thebibliography}{9}

\bibitem{DAD}{\em The Distributed Array Descriptor for a PCRC HPF Compiler},
PCRC working paper, February 1996.

\end{thebibliography}


\end{document}

