\documentstyle[psfig]{article}

\begin{document}

\sloppy

\pagestyle{plain}


\title{{\em PCRC Distributed Data Descriptor Abstract Specification} \vspace{0.25in} \\
        DRAFT}

\author{Bryan Carpenter, Don Leskiw and Xiaoming Li \\ 
        \em Northeast Parallel Architectures Centre, \\
        \em Syracuse University, \\
        \em Syracuse, New York\vspace{0.25in} \\
        James Cowie \\ 
        \em Cooperating Systems Corporation, \\
        \em Chestnut Hill, Massachusetts\vspace{0.35in} \\
        \em With contributions from\vspace{0.15in}: \\
        Denis Gannon et al\\ 
        \em Department of Computer Science \& CICA, \\
        \em Indiana University, \\
        \em Bloomington, Indiana
} 

\date{November, 1996.  Revised June, 1997}

\maketitle

%\tableofcontents

\newpage

\section{Introduction}

Currently, high performance parallel architectures do not have standard
methods to access and manipulate distributed data structures such
as arrays and pointer-linked trees.  Research groups and commercial
vendors often reinvent the tools and functions required for distributed
data structures for each source-language, machine architecture, and
run-time system.

The purpose of this document is to propose a simple and compact
model for creating and accessing regular distributed data
in a parallel environment.  This document is {\em not} intended to be
an application program interface (API) for a user-level library.  While
part of the specification may be visible at the source code level, the
intent is that the specification provides a standard model for
low-level compiler-generated code, run-time systems, and parallel
toolkits capable of interoperating and sharing implementation layers.

\section{Definitions}

\begin{description}
\item{Context:}
An address space.  A SMP UNIX process represents a single context.
Lightweight threads executing ith the address space would share
the single context.  A machine such as the SP2 or Paragon can support
several contexts per node.  The terms ``context'' and ``process''
will be used interchangeably in this document.
\item{Local segment:}  The set of local elements for a given context.
\item{Distribution Target:}  The set of processes or contexts
across which an aggregate is distributed.
\item{Process grid:}  A set of processes or contexts
labelled by a tuple of {\em process coordinates}.
\item{Global subscript:}  A subscript into a distributed array,
viewed as a global entity.
\item{Local subscript:}  A subscript into a local segment of a
distributed array.  In the specific array model presented in the
following section, a local subscript is a subscript into the local
segment of an abstract index space or {\em template}.  This may or may
not require
some translation before being used as a subscript into the physical
local array segment---see section \ref{strides}.
\end{description}

\section{PCRC DAD Specification}

This section describes that basic design of the Distributed Array
Descriptor (DAD).  The design
description is necessarily somewhat abstract, since the DAD must
transcend linguistic, programming model, and architectural boundaries.
We have avoided language-specific bindings.

The model presented here is restricted to distributed multidimensional
{\em arrays}: aggregates of elements of the same type, indexed over a
fixed Cartesian product of integer intervals.  The ultimate scope of an
extended descriptor may be broader, covering, for example, distributed
recursive data structures such as lists and trees.


\subsection{Overview of the Data Representation}

There are three kinds of information in the distributed array
descriptor:
\begin{itemize}
\item
``Type'' information.  This is the kind of information a compiler
would use in static type-checking.  In general this information
must also be passed to the run-time system.  It includes some description
of the type of the elements, and the rank of the array.
\item
Information on the global shape and distribution of the array.
This includes a description of the group of processes over which
the data is distributed and of the mapping of elements of the 
array to those processes.
This information is needed, in particular, in translation of a
set of global array subscripts to a set of process grid coordinates
and a set of local subscript.
\item
Information on the layout of the local elements of the array.
This information is needed in translation from a set of local subscripts
to an address in local memory.
\end{itemize}
These domains are further divided into pairs of
components: a scalar component, containing information pertinent to
the whole array, and a vectorial component, containing additional
information on a
per-dimension basis.  As illustrated in figure \ref{sixcomp}, this
yields 6 logical components:
\begin{figure}[btp]
\centerline{\psfig{figure=6comp.eps,height=2.5in}}
\caption{\label{sixcomp}Structure of the array descriptor.}
\end{figure}
\begin{enumerate}
\item
Element type information.
\item
Rank or dimensionality of the array---an integer \verb$R$.
\item
Distribution target---the {\em group} structure.
\item
Information on the bounds and distribution of index ranges---a vector of
\verb$R$ {\em range} structures.
\item
A base address in local memory---a pointer.
\item
Information on layout of elements in local memory---a vector of \verb$R$
{\em stride} structures.
\end{enumerate}
This organization has been developed to maximize the potential for
sharing of components by similar arrays.  Two arrays which share the
extent and alignment of a particular dimension will have identical range
structures for the dimension concerned.  Two sections of a common
parent array will share strides inheritted from the parent.

The remainder of this section reviews the content of the six
components in turn

\subsection{Element type information}

An array element can have any type representable as a contiguous group
of bytes.  All elements of the array have the same type.

The type information in the descriptor consists of the element length
in bytes and an integer tag field optionally used to provide more
detailed information about the type.  The tag field could be
used by arithmetic array operations accepting arguments whose elements
have any one of specified set of primitive arithmetic types.

\subsection{Rank}

The rank is a simple integer---the number of dimensions of an array.
The rank may be zero.  This allows the descriptor to describe a scalar
variable which is localized to a particular process or group of processes.

\subsection{Distribution target}

An array is distributed over a particular group of processes, or
contexts.  This may be the whole set of processes actively executing
the program, or some subset of those processes\footnote{The DAD does
{\em not} directly provide mapping of multiple {\em abstract processors}
(in the HPF sense) into
a single address space.  The higher levels of language specific
run-time support could provide such mapping, if it was needed (in some
cases that may depend on extensions to the supported distribution
formats, described in the next section).}.

The model supports groups which are multidimensional grids of
proceses, mapped into the active process set.  It also supports groups
which are regular subsets of other groups, obtained by restricting some
of the grid dimensions to particular coordinates.  These options
are illustrated in figure \ref{embedding}.
\begin{figure}[btp]
\centerline{\psfig{figure=embedding.eps,height=3in}}
\caption{\label{embedding}Examples of process groups over which an array
could be distributed (shaded processes).}
\end{figure}

Operations supported by the group structure include
\begin{itemize}
\item
Creation of a group structure representing a process grid.
\item
Creation of a group structure representing a subgrid by restriction
a dimension of an existing group.
\item
Provision of an inquiry function which determines whether the local
process is a member of the group concerned, and (assuming that to be
the case),
\item
Inquiry functions which return coordinates of the local
process relative to the grid-dimensions of the group.
\end{itemize}
Additional lower-level group operations may include
\begin{itemize}
\item
Conversion of grid coordinates to physical process identifiers
\item
Enumeration of all processes in a group
\item
Construction of spanning tree covering a group.
\end{itemize}
Such functions will certainly be needed within the run-time,
but may not be required directly by an application or compiler
generated code.

\subsection{Index ranges}

In the DAD, the extent of an array dimension and the mapping of its
global subscripts into a process dimension is parametrized by a {\em
range} structure.  In languages that provide two-level mapping, with
alignment of arrays to abstract index spaces (templates), the extent
and mapping of a {\em template} dimension can also be described by a
DAD range structure.

An essential r\"{o}le of the range structure is to provide a map
from global subscripts to local subscripts.  This point of view is
illustrated in figure \ref{range}.  The map is visualized as a
function from global subscripts to pairs consisting of a process
coordinate and a local subscript.
\begin{figure}[btp]
\centerline{\psfig{figure=range.eps,height=3in}}
\caption{\label{range}The range structure viewed as a map from global
to local subscripts.  The range has extent 10 and is distributed
blockwise over a grid-dimension of extent 4.  The arrows represent the
mappings $1 \rightarrow (0, 1)$, $6 \rightarrow (2, 0)$, $3\rightarrow
(3, 0)$.} \end{figure}

The global subscript associated with an array dimension takes values in
the range \verb$0, ..., n - 1$, where \verb$n$ is the {\em extent} of the
array in the dimension concerned.  Where the source language allows
lower bounds other than zero for array subscripts the compiler (or the
language-specific layer of the run-time) is responsible for normalizing
the subscript so that it ``starts at'' zero before passing it to the
kernel run-time.

A {\em primitive range} is one that is mapped directly to a process
grid dimension.  Template dimensions are represented by primitive
ranges.  A primitive range is effectively parametrized by its extent,
its target processor dimension, and a distribution format.  A primitive
range may have one of a number of supported distribution formats,
including ``block'' or ``cyclic'' distributions.  Different source
languages often require different distribution formats, therefore this
part of the interface and its associated implementation code are
organized to make addition of new formats as straightforward as
practical\footnote{In the NPAC/Adlib implementation each distribution
format is represented by a different subclass of a common ``range''
base class, and, within certain constraints, new distribution formats
can be added by extending the inheritance hierarchy with new
subclasses.}.

Besides primitive ranges the DAD supports {\em aligned ranges} (also
called {\em subranges}).  An aligned range is effectively parametrized by its
extent, a parent primitive range, an alignment offset, and an alignment
stride.

Operations supported by the range structure include
\begin{itemize}
\item
Mapping from global to local subscripts, as discussed above
\item
The reverse mapping, from local to global subscripts
\item
Inquiry functions returning extent and mapping information
\item
Construction of aligned subranges
\item
Operations to support enumeration of the locally held block(s) of
subscript values.
\item
Operations to support enumeration of the global set of subscript blocks
defined my the mapping of the range.
\end{itemize}

\subsection{Base address}

The base address is a pointer to base of a local array which holds
the elements, or a pointer into heap memory.

\subsection{\label{strides}Strides}

%{\em [From the HPCC glossary at
%http://nhse.npac.syr.edu/hpccgloss/hpccgloss.html.  Need a better
%citation.  DBC]}
\begin{quote}
{\bf stride (n.)} a term derived from the concept of walking or striding
through data from one location to the next. [\ldots]
\end{quote}
A local subscript defines a local element of a primitive range or
template.  A local subscript does not {\em directly} encode information
about the spread of array elements in physical memory.  The mapping
from local subscript to memory offset is embodied in the {\em stride}.
\begin{figure}[btp]
\centerline{\psfig{figure=stride.eps,height=3in}}
\caption{\label{stride}A pair of stride structures map a two-dimensional
array segment into a section of local memory.}
\end{figure}

In the simplest case a memory stride is a single integer:
if the local subscripts are
\begin{verbatim}
  l_0, l_1, ...
\end{verbatim}
and the memory strides are
\begin{verbatim}
  str_0, str_1, ...
\end{verbatim}
then the offset of the element from the base of the local array
segment is
\begin{verbatim}
  (str_0 * l_0) + (str_1 * l_1) + ...
\end{verbatim}

Different {\em packing strategies} may be supported, requiring more
general mappings from local subscript to offset.  These may require
extensions of the stride structure beyond a simple integer.  For
example, if an array is declared with an alignment stride\footnote{Of
course the alignment stride and memory stride are two quite different
concepts.} of {\em s} then it is wasteful of memory to create an array
segment as large as the template because only one in {\em s} elements
are ever used.  This can be avoided if the local subscript is divided
by {\em s} before subscripting the array.  The value of the divisor
{\em s} could be stored in the generalized stride structure.

\subsection{Further notes on the DAD}

The DAD represents replication of data over any or all grid dimensions
simply by distributing the array over a group containing the dimensions
concerned, without specifying any index ranges distributed over those
dimensions.

%{\em [Notes on the representation of array sections, and embedded
%alignments.]}

\section{Language Bindings}

The exposition given here is intentionally language-independent.
Several bindings of the interface to specific programming languages
(Fortran 77, C, C++, Java) will be presented in accompanying
documents.

%\appendix

%\section{A Tabular Reference Implementation}

%{\em [Xiaoming's $7 \times N$ table]}

\end{document}

