\section{Conclusion}
\label{section:conclusion}

Tuning for dataflow execution (either by the programmer or compiler)
requires techniques which are different from tuning on conventional
architectures.  In this paper, we have characterized some of the overheads
of dataflow execution on Monsoon, focusing on loops and using an example of
a preconditioned conjugate gradient algorithm (PCG).  Our performance
measured by {\it cycles executed per required floating point operation} is
comparable to a production version of the algorithm running on the CM-5.

Much of the overhead comes from the dataflow switch and fork instructions,
as well as bubbles which result from fine-grained synchronization on
Monsoon.  Part of this overhead could be eliminated by architectural
changes -- for instance, the EM-4 \cite{EM4a} architecture uses essentially
the same dataflow-style synchronization mechanism as Monsoon, but does not
incur a bubble because the synchronization and execution units are
decoupled.  In addition, due to some hardware limitations, some idle cycles
on Monsoon are the result of network access contention, rather than being
fundamentally associated with dataflow architectures.  The fork overhead is
eliminated in the Epsilon dataflow architecture \cite{Grafe88a} with a {\it
copy} instruction which can send values to multiple instructions --
however, the {\it copy} instruction reduces instruction count, but does not
reduce cycle count.

Some overhead is the result of the $k$-bounded loop scheme, which has
proven to be difficult to use for the programmer as well as incurring
significant execution overhead.  Setting $k$ for the $k$-bounded loop is a
non-trivial task, and does not lend itself easily to compiler analysis.
Whereas $k$-bounding assumes an eager model of parallelism exposure,
run-time, demand-based approaches such as lazy task creation \cite{Mohr91}
or guided self-scheduling \cite{Poly87} may prove more effective, as well
as easier to program -- however, in general, these techniques are difficult
to implement on Monsoon because it is almost impossible to determine when a
Monsoon processor is idle because of the deeply-pipelined,
heavily-interleaved model of execution.  Again, this is not an inherent
feature of dataflow architectures, but an oversight in the hardware design
of Monsoon.

Language definition and compiler optimization also affect performance.
Id's policy of array extents being defined only at run-time inhibits some
standard loop optimizations, and may be changed by either changing the
language or adding pragmas.  Some compiler loop optimizations for
conventional architectures may not be effective for Monsoon because the
addition of induction variables is very expensive for the dataflow loop
schemas.  However, some other loop optimizations may be more effective for
Monsoon than conventional architectures because of the high overhead of
dataflow loop execution.

The programmer plays a large part in attaining good performance.  Loop
schemas and $k$-bounds should be chosen to expose just enough parallelism
to keep the machine busy.  Changes to the algorithm in order to take
advantage of complete loop unfolding, such as the hybrid version of the
PCG, can also improve performance in non-intuitive ways.

In related work, Arvind, et.al.~\cite{Arvind88b} gives a more detailed
analysis of the overheads of dataflow execution.  Hicks,
et.al.~\cite{id-performance} describes performance of several smaller
benchmarks on Monsoon.  Yeung and Agarwal \cite{Yeung93} discuss the
importance of language support for the expression of fine-grained
parallelism using preconditioned conjugate gradient (primarily the
preconditioning step, which is significantly different from ours) on
Alewife.  Sur and Bohm \cite{Sur94} have performed many performance
analyses of scientific codes in Id on Monsoon, primarily focusing on
language features and their impact on performance.

Although it is unlikely that dataflow architectures (as they exist today)
will be viable commercially in the near future, multithreading techniques
and parallelism are playing an increasingly important role in the design of
commercial systems.  The synchronization and control overheads we encounter
in dataflow computing are inherent to fine-grained parallel multithreaded
execution, and these overheads change the relative importance of program
optimizations, motivating increases in sizes of basic blocks through
inlining, loop unrolling, and program structuring.  The higher overhead of
control instructions also motivates decreases in the sizes of basic block
interfaces, even when the size of the basic block may be decreased by
adding a basic block interface.
