\Section{Introduction}

Dataflow machines have two basic types of overheads which do not exist in
sequential machines: {\it synchronization} and {\it control} overheads.
Synchronization overheads are primarily encountered within basic blocks,
and control overheads are encountered between basic blocks (on conditional,
loop, and procedure call boundaries).  These overheads are the cost of
exploiting fine-grained parallelism.  In this paper we consider tuning
techniques to alleviate these overheads for regular, {\it scientific}
applications on a dataflow computer.  These tuning techniques apply to both
compiler-directed optimizations as well as programmer-directed
optimizations.

\begin{fig}{figure:ocean}{In an ocean modeling code, the ocean is
represented by multiple three-dimensional arrays holding values for
different physical characteristics of the ocean.  Typically, a large
percentage of the geometry represents land, which is not of interest.}
\illustrationx{3.2in}{figures/ocean.eps}
\end{fig}

Many scientific applications spend much of their time in loops traversing
over large arrays which represent physical characteristics distributed over
the geometry of the problem.  One such application is the MIT ocean
circulation model GCM \cite{marshall} \cite{GCM} whose data parallel
implementation on the CM-5 has shown very good performance.  While
developing GCM for the CM-5, we also wrote a version of it in Id \cite{id}
for the Monsoon dataflow machine \cite{monsoon} \cite{CulPap90}.  Id is an
implicitly parallel language with a multithreaded implementation model, and
the GCM code allowed us to compare the execution overheads for the
multithreaded and data parallel models on an application which was
extremely well-suited for data parallel execution.  A more in-depth study
of the data parallel and multithreaded implementations of GCM is presented
in \cite{GCM}, where we compare program styles, ease of programming, and
algorithmic issues, while in this paper, we primarily discuss performance
and tuning on the dataflow platform.

Figure \ref{figure:ocean} shows a typical problem geometry -- the Pacific
ocean basin -- used in the circulation model.  A Pacific ocean state array
would typically contain 168 $\times$ 90 $\times$ 10 elements, 40\% of which
represent land, and do not contribute to the simulation.  However, unlike
some physical models, geometries used in ocean modeling are usually not
irregular enough to warrant repartitioning to eliminate land elements.

The core of GCM code is a preconditioned conjugate gradient (PCG) solver
which takes 80\% or more of the computational time of the application.  The
PCG consists of simple operations over entire state arrays which can be
described as triply-nested loops with relatively small loop bodies.  In
order to attain high performance for this application, we must execute
these loops efficiently while also distributing the work among the
processors.  Dataflow architectures differ significantly from conventional
sequential microprocessors or vector processors, so the process of tuning
these loops to obtain high performance is also quite different than tuning
loops written in conventional languages for conventional architectures.

\SubSection{Id: an implicitly parallel language}

Id is an implicitly parallel language which can express parallelism at the
instruction-, procedure-, and loop-level.  Id programs are compiled into
{\it dataflow graphs}, which are optimized, and then executed directly by
the Monsoon architecture.

\paragraph*{Instruction-level parallelism.}

\begin{fig}{figure:dataflow}{Optimized Monsoon dataflow graph for the body 
of the innermost loop of a three-dimensional inner product code.  It
directly represents instruction-level parallelism, but incurs fine-grained
synchronization costs.}
\illustrationx{2.9in}{figures/dfg-3d.ps}
\end{fig}

Dataflow graphs such as in Figure \ref{figure:dataflow} directly represent
instruction-level parallelism -- in the Monsoon architecture, such
instruction-level parallelism is only exploited within a processor.  Basic
blocks are represented by acyclic graphs such as in Figure
\ref{figure:dataflow}.  The {\it fork} operator in the figure is necessary
for sending values to more than two instruction at a time -- because of
opcode encoding limitations, most Monsoon instructions can send a value to
two destination instructions, and some instructions can send a value to
only one instruction.

Memory operations such as {\it i-fetch} are split-phase -- the initiation
and response are separate, and the latency of the response may be very
long.  Each memory operation has an implicit synchronization associated
with it so that reads which are executed before the write to the same
memory location wait for the write to occur before responding.

Compile-time constants (i.e.\ literals) and run-time constants (such as
loop constants) are represented in Figure \ref{figure:dataflow} in light
gray.  Run-time constants must be stored into local memory at run-time
using the {\it constant-store} instruction, and literals are stored into
local memory at load-time by the loader.  Both types of constants can be
accessed without synchronization overhead.

Control is implemented by using the {\it switch} operator which steers an
input value to one of two locations depending upon the value of an input
predicate.  Switch operators can be used to build conditionals or loops,
but incur high overhead because a different switch operator is needed for
each loop or conditional variable.

\paragraph*{\mbox{Procedure-level parallelism.}}

\hfill\mbox{Procedure-level} parallelism is expressed by implicitly forking
every procedure call and joining on the return value of the procedure.
Each procedure requires an {\it activation frame}, which is used to store
intermediate results and as a synchronization namespace for instructions in
the procedure.  An activation frame is roughly analagous to a stack frame
in a sequential processor.

Each procedure call requires a frame allocation and deallocation.  A frame
may be allocated on the local processor or on a remote processor to expoit
inter-processor parallelism, and frame allocation and deallocation is
handled by the run-time system.  Care has been taken to eliminate run-time
system costs, to the point where much of the run-time system is written in
assembly, and supported by special ``microcoded'' machine instructions
\cite{frame-manager}.  In the default run-time system, frame memory on each
processor is divided equally among all processors, so that each processor
manages part of the frame space of every other processor.  Frame allocation
requests are then handled locally in a round-robin fashion across all of
the processors in an attempt to provide some form of load balancing.

Despite the care taken in designing the run-time system, frame management
in this parallel environment is still more expensive than in a sequential
environment, where a simple pointer-bump can allocate or deallocate a stack
frame.  Furthermore, every argument is sent as a separate message, and
although the composition, sending and receiving of these messages are well
supported in hardware, argument-passing is still relatively more expensive
than register-style argument passing in sequential processors.  In general,
the programmer should inline most non-recursive procedures to avoid these
twin overheads of procedure calls.

\paragraph*{Loop-level parallelism.}

Loop-level parallelism can be exploited in several ways.  A direct
tail-recursive implementation of loops will use too many frame resources,
so most loops are either ``sequential'' loops or $k$-bounded loops
\cite{Culler90}.  Sequential loops execute on one processor, and only
exploit instruction-level parallelism; $k$-bounded loops execute $k$
consecutive iterations worth of parallelism either within or across
processors.

\begin{fig}{figure:dataflow-loop}{Schema for ``sequential'' dataflow loops,
which incur high fine-grained synchronization costs because of the need for
switch and fork operators.}
\illustrationx{2.9in}{figures/dataflow-loop.eps}
\end{fig}

Figure \ref{figure:dataflow-loop} shows the schema for a sequential loop
for Monsoon.  A number of input variables and loop constants are initially
fed to the loop body.  Their values for the next iteration are either fed
back into the top of the loop body, or else output to the final values.
The values are steered to their appropriate destination through the {\it
switch} dataflow instruction.  Since the switch instruction can only steer
one value to one destination at a time, an additional fork may be required
to distribute the loop test predicate value for each additional loop
variable.  Loop constants are stored into the frame before loop execution
and extracted after loop completion.

The $k$-bounded loop schema is more complicated than the sequential schema,
and employs a ring of $k$ activation frames which are allocated and linked
at the beginning of the loop and deallocated at the end of the loop.  Loop
constants must be stored into and extracted from each frame in a
$k$-bounded loop.  Induction variables are passed from iteration to
iteration like arguments are passed for procedure calls.

{\it Standard loop optimizations such as unrolling, peeling, strip-mining,
and interchange can have a larger impact on performance than for
conventional architectures because of the overhead of parallel asynchronous
execution of loop iterations in the dataflow model.}

High loop overhead for dataflow execution is exacerbated in Id because
array extents in Id, unlike Fortran, can be computed at run-time.
Consequently, to perform many loop optimizations important for performance
on scientific codes, one would need pragmas in Id to indicate static array
extents.  However, this type of overhead is due to the language, and not
dataflow execution.

\SubSection{The Monsoon dataflow machine}

\begin{fig}{figure:monsoon}{Monsoon consists of processing elements (PE's)
connected to I-structure memory modules (IS's) through a multi-stage
network.  Each PE is an eight-stage pipelined dataflow processor.}
\illustrationx{3.2in}{figures/monsoon.eps}
\end{fig}

Figure \ref{figure:monsoon} (taken from \cite{id-performance}) shows a
high-level view of the Monsoon multiprocessor.  Monsoon \cite{monsoon}
consists of eight 64-bit processing elements (PE's) and eight I-structure
memory modules (or IS's) connected via a multistage packet switch network.
Each PE is an eight-stage pipelined processor.  On each processor cycle, a
token enters the pipeline and its result is available eight cycles later.
Keeping an eight processor Monsoon busy requires at least 64-fold
parallelism because each stage of the pipeline executes a different thread.
Each PE can process ten million tokens per second and has 256K 64-bit words
of local memory on which frames are allocated.  In the memory module where
heap objects reside, word-level presence bits are implemented in hardware
to support fine-grain synchronizing data structures for global heap.  Each
IS has 4M 64-bit words of heap memory.  Monsoon's network interface with
bandwidth of 100M bytes per second can deliver a token to the network every
cycle.

Each instruction executes in one or two cycles, including floating point,
integer, memory, control, and message instructions.  Any instruction which
has two non-constant inputs must synchronize on the arrival of its two
inputs, and requires two cycles to execute, one of which is counted as a
{\it bubble}.

Every global memory access goes over the network, and all locations in the
global memory are equidistant.  The mapping of work to processors is
governed by the frame allocation policy.  Heap objects are interleaved by
hardware across the IS's and in general, data mapping has no effect on
performance.  Monsoon accesses global memory in a split-phase manner, and
can do useful work during the long-latency of a memory access.  However,
this requires additional instruction-level parallelism to keep the
processor fully utilized.  Each Monsoon processor has 16 counters which can
keep accurate counts of various types of instructions executed.
