% Section on analysis of requirements for MPA's

\section{Fundamental Problems in an MPA}

\label{sec-analysis}

A general purpose Massively Parallel Architecture (MPA) consists of a
collection of nodes that communicate using a pipelined,
message based interconnection network (see Figure
\ref{fig-analysis-mpa}).
\begin{figure}[htbp]
  \hdivider \\
  \illustration{fig-analysis-mpa}{1 true in}
  \caption{%
     \label{fig-analysis-mpa}
     Structure of a massively parallel architecture.
          }
  \hdivider
\end{figure}
Each node contains a processor and some local memory.  Given a node N,
we refer to its own memory as {\em local memory\/} and to other
memories as {\em remote memories\/}.

A consequence of message based communication is that remote accesses
must be structured as {\em split transactions\/}.  If node N1 wants to
read the contents of location A in node N2, it involves two messages:
a request message from N1 to N2 carrying the address A and a return
address identifying N1, followed by a response message from N2 to N1
carrying the contents of location A.

{\em Memory addressing\/}: although we believe it is important, we do
not consider here the issue of whether the memories in the different
nodes belong to a single, global address space or whether the memory
in each node has its own local address space.  We also do not consider
here the issue of virtual memory.

{\em Locality and memory latencies\/}: In an MPA, the latencies of
local {\vs} remote memory accesses typically vary by orders of
magnitude.  Further, remote memory latencies grow with machine size---
the best-case scenario is that remote access time will vary with $\log
N$, where $N$ is the number of nodes.

We now present two problems which, we hope the reader will agree, a
general purpose MPA must solve efficiently in order to have good
performance over a wide variety of applications \cite{Arvind87c}.

\subsection{The Latency of Remote Loads}

The remote load situation is illustrated in Figure
\ref{fig-analysis-rload-problem}.
\begin{figure}[htbp]
  \hdivider \\
  \illustration{fig-analysis-rload-problem}{1.6 true in}
  \caption{%
     \label{fig-analysis-rload-problem}
     The remote load problem: Node N1 to compute difference of variables in nodes N2 and N3
          }
  \hdivider
\end{figure}
Variables {\cf A} and {\cf B} are located on nodes N2 and N3,
respectively, and need to be brought to node N1 in order to compute
the difference {\cf A-B} in variable {\cf C}.  The basic intent of the
computation is expressed by the following statement sequence
executing on N1:
\beginid
    vA = rload pA
    vB = rload pB
    C = vA - vB
\endid
where {\cf pA} and {\cf pB} are pointers to {\cf A} and {\cf
B}, respectively.  The first two statements perform remote loads,
copying values from {\cf A} and {\cf B} into {\cf vA} and {\cf vB},
respectively.  The last statement computes the difference and stores
it in {\cf C}.

The figure also shows a variable {\cf CTXT}, which is the {\em
context\/} of the computation on N1.  It could be, for example, a
stack pointer, a frame pointer, a ``current-object'' pointer in an
object-oriented system, a process identifier, {\etc} In general,
variable names like {\cf vA}, {\cf vB} and {\cf C} are interpreted
relative to {\cf CTXT}.

The key issue in remote loads is how to deal with the long latencies
in the communication system, \ie\ how to avoid idling N1's processor
during the remote load operations.  Note that in most architectures,
these latencies are predictable because they depend mainly on the
distance between the nodes.

\subsection{Idling due to Synchronizing Loads}

We extend the remote load problem by now assuming that {\cf A} and
{\cf B} are computed by concurrent processes, and we are not sure
exactly when they will be ready for node N1 to read.  We need some
form of synchronization to ensure that the remote loads from N1 read
the values only after they have been produced.  This is an example of
producer-consumer parallelism.

Unlike the remote load problem, the latency here is not just an
architectural property--- it also depends on scheduling, and the time
it takes to compute {\cf A} and {\cf B}, which may be much longer than
the transit latency.  In particular, the unpredictable latencies of
synchronizing loads are a problem {\em even when they are local.}

% ----------------------------------------------------------------
