% What do I want to talk about in this paper:
%
%   (0) Sequential loops has traditionally not received very
% 	much attention.  Reasons: (1) assumed that most loops
%	will be executed in parallel; (2) efficiency (as measured
%	by overhead incurred) was not given very much attention.
%
%   (1) Present the 2 sequential loop schemas:
%	 (a) self-gating sequential loop schema as a cheap
%	     way of implementing sequential loops in the pure
%	     dynamic dataflow model.
%	 (b) the fbv sequential loop schema as a further 
%	     improvements on multi-threaded machines.
%
%   (2) The overheads of dataflow execution:
%        (a) matching bubbles.
% 	 (b) fanouts
%	 (c) switching
%	 (d) extraneous synchronization. (for resource reuse)
%
%   (3) Overcoming these overheads is needed if we want to
%	execute code efficiently.  The 2 sequential loop
%	schemata illustrate this.  Strictness information plays
%	a large role in making this possible.  General partitioning
%	and threading will reap us even greater benefits.
%
%   (4) Crucial remaining low level issue with respect to supporting 
%	efficient execution: memory hierarchy.  Registers may not
%    	be the correct answer to our the needs of multi-threading
%	as values in general need to cross thread boundary.  
%
% Message:
%   (1) Instruction level parallelism exploited in the dynamic 
%	dataflow manner is expensive.  It incurs processor cycles
%	as overhead.  It also requires fast access to a large
%	token-store memory, or at least a memory hierarchy that 
%	gives such an illusion, e.g. a cache.  It is however not
%	clear that a cache is effective in such an environment.
%   
%	A better means of exploiting instruction level parallelism
%	is to use superscaler hardware, and either pack instructions
%	for superscaler issue, or even use hardware mechanisms like
%	Tomasulo's algorithm to exploit such parallelism.
%
%	This will not be able to exploit inter-thread parallelism
%	in the same cycle on the same processor.  
%	(Processor coupling, Steve's stuff, tries to address this.)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentstyle[empty]{fpca93}


%%% Figure environment for this document.
%%% Usage:  \begin{fig}{LABEL}{CAPTION}
\newenvironment{fig-top}[2]
  {\begin{figure}[t]%
   \def\figlabel{#1}%
   \def\figcaption{#2}%
   \hrule width\linewidth height1pt%
   \vskip \fboxsep}%
  {\caption{\label{\figlabel}\figcaption}%
   \vskip \fboxsep
   \hrule width\linewidth height1pt%
   \end{figure}}

\input{fig}

\input{acaro-macro}
\def\illustrationfileprefix{/bk/hahaha/research/docs/papers/FPCA-93/pics/}

\def\illustrationfilesuffix{.ps}

\def\illustrationtx#1#2{
{\leavevmode
 \epsfxsize=#1
 \epsffile{\illustrationfileprefix#2\illustrationfilesuffix}}
}

\newcounter {example-counter}[subsection]

\newenvironment{fig-no-boarder}[2]
  {\begin{figure}%
   \def\figlabel{#1}%
   \def\figcaption{#2}%
%   \hrule width\linewidth height1pt%
   \vskip \fboxsep}%
  {\caption{\label{\figlabel}\figcaption}%
   \vskip \fboxsep
%   \hrule width\linewidth height1pt%
   \end{figure}}

%\def\example#1{
%\noindent {\bf \underline{Example
%\stepcounter{example-counter}\arabic{example-counter}: #1}}
%}
\def\example#1{
\stepcounter{example-counter}
\subsubsection {\underline{Example
\arabic{example-counter}: #1}}
}

\begin{document}
\bibliographystyle{plain}
\title{Efficient Implementation of Sequential Loops in Dataflow
Computation}
\author{Boon Seong Ang \\
\\ NE43-205, Laboratory for Computer Science, 
\\ Massachusetts Institute of Technology,
Cambridge, MA 02139. 
\\ hahaha@abp.lcs.mit.edu}
\maketitle

\begin{abstract}

The implementation of sequential loops in dataflow computation had
traditionally not received very much attention as it was assumed that
most loops would be executed in parallel.  This assumption was valid
for earlier dataflow machines such as the MIT Tagged Token Dataflow
Architecture (TTDA)\cite{TTDA90}, Sigma-1\cite{sigma-1-87} but not for
the newest generation of dataflow machines including
Monsoon\cite{Culler-greg90}, EM-4\cite{em-4-90} and
Epsilon-2\cite{Grafe90}.  On the latter machines, sequential loops use
less memory, and can execute in fewer instructions, albeit with lower
parallelism than the parallel versions.  This characterisation of
sequential and parallel loops suggests that programs should have
parallel outer loops and sequential inner loops.  The run time of
sequential loops therefore become significant in the overall run time.
We also found that previous implementations of sequential loops can
incur fairly high overheads.  In this paper, we present two new ways
of implementing sequential loops that have lower overhead then
previous methods.  We studied this problem in the context of compiling
Id\cite{id90,id-implicit-parallelism} for Monsoon.  


%Run time
%statistics comparing the execution time of benchmark programs compiled
%using different sequential loop schemata are presented.  We conclude
%with a brief discussion of some of the inefficiencies of dynamic
%dataflow execution that became evident during the course of this work.

\end{abstract}

\section{Introduction}

Loops executing on dataflow machines can be classified into three
categories according to the amount of inter-iteration parallelism
allowed.  At one extreme is an {\em unbounded} loop, where there is no
artificial bound on the number of concurrent iterations.  Such a
loop is compiled into a recursive procedure which together with
non-strict procedure call convention lead to unrestrained unraveling
of the loop.  Next, we have what is often referred to as {\em
k-bounded} loops\cite{Culler89}, where the number of iterations
executing concurrently is bounded to a value $k$ which can be computed
at run time.  Finally, a {\em sequential} loop is one where one
iteration of the loop has to complete before the next one executes.

The implementation of sequential loops in dataflow computation had
traditionally not received much attention as it was assumed that most
loops would execute in parallel, predominantly as k-bounded loops.
This assumption was valid for earlier dataflow machines such as the
MIT Tagged Token Dataflow Architecture (TTDA)\cite{TTDA90} and
Sigma-1\cite{sigma-1-87} where the per-iteration cycle cost of
executing a loop is the same whether the loop is k-bounded or
sequential.  The consumption of resources, in the form of token
``tags'' is also the same for both cases.  For these machines, it is
natural to execute loops in parallel to reap full benefit of parallel
processing.

With the newest generation of dataflow machines (e.g.
Monsoon\cite{monsoon-book,Culler-greg90}, EM-4\cite{em-4-90} and the
Epsilon-2\cite{Grafe90}) the situation is different.  These machines
use {\em frame memory} on each processor to implement
token-matching(see Section~\ref{sec:matching}).  This has two
consequences for loops: (i) every {\em concurrent} iteration needs its
own frame; (ii) sending data between two iterations that do not share
(in a time multiplexed way) the same frame requires communication
through the interconnection network.  The former means that memory
usage is lower for sequential loops while the latter suggests that
they can execute in fewer cycles.  Additional saving comes from fewer
frame allocations and deallocations.  The benefits come, however, at
the expense of reduced parallelism.  Thus there is a place for both
k-bounded and sequential loops.  Outer loops should be k-bounded for
parallelism, while inner loops should be made sequential for
efficiency reasons.  Such a strategy places great important on the
efficiency of sequential loops as the run time of inner loops often
dominates the overall run time of programs.


Much as sequential loops can potentially be cheap, past
implementations\cite{Hicks90,Culler89} have not achieved the goal of
keeping the costs down.  In this work, we present two new ways of
implementing sequential loops that incur less overhead then previous
methods.  We studied this problem in the context of compiling
Id\cite{id90,id-implicit-parallelism}, a non-strict, inherently
parallel language, for
Monsoon\cite{Culler-greg90,monsoon-book}.  The two
implementations use slightly different execution models which are
discussed in the paper.

We start by providing some background in Section~\ref{sec:background}
and proceed to describe some of the past approaches to implementing
sequential loops in Section~\ref{sec:past-implementations}.  In
Section~\ref{sec:self-gating}, we present a new implementation, the
{\em self-gating} sequential loop schema, which implements a
sequential loop in the pure dataflow model.  We improve upon this
schema by adopting a mixed dataflow-von Neumann execution model to
produce the {\em frame-based-variable} sequential loop schema.  This
is presented in Section~\ref{sec:fbv}.  Run time statistics of Id code
compiled using the different implementation strategies are presented
in Section~\ref{sec:run-time-stats}.  Conclusion follows in
Section~\ref{sec:insights-etc}.

% with a discussion of some of the
%inefficiencies of dynamic dataflow execution that became evident
%during the course of this work.

\section{Background}
\label{sec:background}


%% * matching and frames; how about Monsoon tokens?
%% * Dataflow graphs?  -- I think we can assume people knows this.

 This section provides a brief introduction to dataflow computation
with emphasis on explaining loops. Dataflow computation orders
instruction execution according to the availability of data.  A
dataflow computer continuously processes {\em tokens} that deliver
data to the instructions.  On Monsoon, each token contains: (1) a {\em
value}; (2) an {\em ip}, pointer to the destination instruction; (3) a
{\em port}, specifying left or right input; and (4) an {\em fp}, the
frame pointer.  An instruction is executed during the processing of a
token if that token delivers the last piece of input data needed by
the instruction.  When an instruction executes, zero or more tokens
are produced.  Program execution starts with the injection of tokens
carrying the arguments and ends when there is no more token to be
processed.



\subsection{Matching and Frames}
\label{sec:matching}

 Central to this execution model is keeping track of which input
tokens have arrived at each instruction, and the values carried on
these tokens.  The process of grouping together all the input operands
of a particular instruction, which then enables the instruction for
execution is called {\em matching}.  We will further assume that there
are at most two inputs to each instruction\footnote{The exception to
this is a signal-tree which we will see later.}.


% Matching is initiated when a token is processed.  

A matching mechanism needs to have the following two features: (1) a
way of finding out whether the other operand has arrived and if so,
fetch that operand; (2) a place for storing the first operand that
arrives.  In order to support re-entrant code, the mechanism must
distinguish between tokens belonging to different invocations of the
same piece of code.

 On Monsoon, matching is achieved by using {\em frame} memory which is
local to each processing element (PE).  Each instruction that requires
matching\footnote{Not all instructions need matching.  Unary
operations, for example, have only one input and do not require
matching.} is assigned a unique slot of frame memory which has two
fields: (1) a {\em presence bits} field indicating the presence or
absence of each operand; and (2) a {\em data} field.  The former keeps
track of whether any one of the operands has arrived, while the latter
provides the space for storing the operand that arrives first.  

%This operand can be fetched later when processing of the second token
%occurs.

 In compiling Id code for Monsoon, we group instructions belonging to
the same procedure into a {\em code block}.  The matching slots of
instructions belonging to the same code block are assigned
contiguous frame memory locations which are collectively called a {\em
frame}.  During the processing of a token, the {\em fp} (base pointer
to a frame) on the token and the offset encoded in the destination
instruction allows the matching frame slot to be determined.  Matching
then proceeds according to the state of the presence bits at the frame
slot.

%One can think of a frame as analogous to an activation frame in
%conventional stack-oriented languages.

% For each instruction that requires matching, the offset of its
%matching frame slot relative to the base of the frame is determined at
%compile time and encoded in the instruction.  The {\em tag} field of a
%Monsoon token is actually the frame base pointer, also called the
%frame pointer or {\em fp}.  When a token is processed on Monsoon, the
%machine first fetches the destination instruction specified in the
%token's {\em ip} field.  Once this instruction is fetched and decoded,
%the matching location is determined by adding the {\em fp} of the
%token to the offset encoded in the instruction.  Matching then
%proceeds according to the state of the presence bits at the
%instruction's frame slot.

 Monsoon supports re-entrant procedure invocation by allocating a new
frame for each procedure call\cite{Derek-ms}.  By so doing, tokens
from different invocations will have different {\em fp}'s and hence
matching under the scheme described above will be able to distinguish
them.

\begin{figure}
\hrule
\begin{verbatim}
       def sum_1_to n = {s = 0;
                         in
                            {for i <- 1 to n do
                                (next s) = i+s;
                             finally s}};
\end{verbatim}
\hrule
\caption{An Id procedure that computes $\sum_{i=1}^{n} i$ when called with $n$.}\label{fig:sum-1-n-code}
\end{figure}

\subsection{Loops in Id}

We start by introducing the syntax with an example that computes
$\sum_{i=1}^{n} i$ when called with \verb|n|.  The code is shown in
Figure~\ref{fig:sum-1-n-code}.  This procedure starts by initializing
\verb|s| to 0 and then iterates through a loop \verb|n| times.  During
each iteration, it ``updates'' \verb|s| by adding the current value of
\verb|i| to the value of \verb|s|.  Updating a variable presents a
problem in Id because Id is basically a functional language.
%\footnote{Extensions have been made to Id to accommodate
%mutable data-structures\cite{barth91}, but scalar variables are still
%functional.} To overcome this problem, Id has a special class of
%variables known as {\em nextified variables}.  
In our example, \verb|s| is a {\em nextified variable} of the
\verb|for| loop with an assignment made to \verb|(next s)| during each
iteration of the loop.  In the same iteration, \verb|s| and
\verb|(next s)| are different identifiers.  However, the \verb|(next
s)| computed in an iteration automatically becomes the value of
\verb|s| in the next iteration.  The scope of a nextified variable
extends to the
\verb|finally| part of the loop.  Thus the \verb|for| loop in the
example returns the value of \verb|(next s)| computed during the last
iteration of the loop.

\section{Past Implementations of Sequential Loops}
\label{sec:past-implementations}

Implementing sequential loops on Monsoon turns out to be very tricky
because by using only one frame to execute the entire loop, the {\em
fp} is the {\em same} for tokens belonging to different iterations.
Loops in general have to be re-entrant but the default way of allowing
re-entrant code on Monsoon requires using a new frame for each
iteration.  With only one frame, unless the compiler compiles in
mechanisms to separate tokens belonging to different iterations of the
loop, tokens from different iterations destined for the same
instruction can erroneously meet under the hardware matching scheme.
We call such an event, a {\em conflict}.

%Tokens belonging to neighboring iterations tend to run into such
%problems. 

In this section, we describe past attempts at solving this problem.
We begin with an ``obvious'' implementation that uses a barrier at the
end of each iteration.  This is, unfortunately, incorrect.  We next
look at a straight forward fix which we call the brute-force 2-barrier
approach.  Finally, we look at a schema found in Culler\cite{Culler89}
which was the previous best schema.

\subsection{An Incorrect, One-barrier Sequential Loop Schema} 
\label{sec:incorrect-1-barrier-seq-loop}

\begin{fig}{fig:naive-fib-seq-loop}
{An incorrect implementation of the sequential loop in \protect
\verb|fib| using the one-barrier approach.  Under certain execution
order, two tokens may end up on the value-input arc (shaded) of
\protect \verb|(next p)|'s gate at the same time.}
\illustrationx{2.2in}{this-fib-loop}
\end{fig}

A first attempt at solving the conflict problem has the compiler
insert a {\em barrier} at the end of each iteration.  The barrier
separates the current iteration from the next one and ensures that the
next iteration does not begin execution until the current one has
completed.  Such a barrier can be implemented as shown at the bottom
of Figure~\ref{fig:naive-fib-seq-loop}.

\begin{figure}[t]
\bigskip
\hrule
\begin{verbatim}
       def fib n = if (n==0) then 0
                   else
                       {p = 0;  c = 1;
                        in
                          {for i <- 2 to n do
                              (next c) = c+p;
                              (next p) = c;
                           finally c}};
\end{verbatim}
\hrule
\caption{{\tt fib} computes the $n^{th}$ Fibonacci number.}\label{fig:fib-code} 
\end{figure}

Figure~\ref{fig:naive-fib-seq-loop} is the dataflow diagram for the
code in Figure~\ref{fig:fib-code} which computes the $n^{th}$
Fibonacci number.  We can discern four regions in the dataflow
diagram. At the top is a shaded oval blob labeled ``Loop Predicate'',
which computes a boolean value indicating whether another iteration
should be executed.  Below this blob is a row of ovals, each with a
``T'' and an ``F'' output.  Each oval is a switch that directs the
value coming in on top to either the ``T'' or ``F'' output depending
on the boolean value that comes in by the side.  Next comes a big grey
region labeled ``loop body'' where the bulk of the computation of each
iteration is carried out.  At the bottom is the barrier which consists
of two parts: (1) A {\em signal tree} (the iteration termination
signal tree) that collects the {\tt next} values of the nextified
variables.  This produces an output token when all the inputs have
arrived.  The actual value on the token is unimportant as the token is
only used to signal an event.  (2) A row of {\em gate} instructions
(represented as bow-ties), one for the {\tt next} value of each
nextified variable.  Each gate, triggered by the output of the signal
tree, is placed just before the {\tt next} value is ``circulated
back'' to the next iteration.  A gate instruction takes a value input
at the top, and a trigger input on the side.  When both input tokens
have arrived, a gate produces an output token carrying the same value
as that on the value input.  Computation that needs the output of a
gate instruction is therefore guaranteed not to occur before the
trigger is available.

This set of signal tree and gates implements a barrier as no value can
cross the array of gates until every value has arrived at the barrier.
Because the {\tt next} values of nextified variables are the only
input tokens to the next iteration, the next iteration cannot start
until the current one finishes.  There is one last symbol used in the
dataflow diagram, a circle with a cross inside.  This is a {\em merge}
which has two inputs and one output.  A merge is not a real
instruction executed at run time.  The simplest way to think about a
merge is that the token that emerges from its output can come from
either one of its inputs, and no matching of inputs occurs.

While the one-barrier approach may look deceivingly correct, tokens
from two iterations {\em can} conflict for some loops, such as the
\verb|fib| loop.  On a dataflow graph, conflicts between tokens from
different iterations is indicated by either two or more tokens ending
up on the same arc at the same time, or two tokens from different
iterations matching at an instruction.  Having two tokens on the same
arc is a problem on Monsoon as that requires storing two values on the
same frame slot when we only have space for one.  Even if we could
store more than one value on a frame slot, we would not know which
value to use for matching when a token subsequently arrives at the
other input of the same instruction.

In the dataflow graph of Figure~\ref{fig:naive-fib-seq-loop}, two
tokens carrying \verb|(next p)| from neighboring iterations can end up
on the shaded value-input arc of \verb|(next p)|'s gate at the same
time.  This happens if at the end of iteration $i$, after tokens
carrying \verb|(next i)|, \verb|(next c)| and \verb|(next p)| have
arrived at the barrier, the tokens carrying \verb|(next i)|,
\verb|(next c)| {\em and} values produced by them including those in
iteration $(i+1)$ are processed before \verb|(next p)| of iteration
$i$ is processed.  Processing of the token carrying
\verb|(next c)| of iteration $i$ results in several tokens in
iteration $(i+1)$ including one which carries \verb|(next p)| of
iteration $(i+1)$.  This is sent to \verb|(next p)|'s gate while
\verb|(next p)| from iteration $i$ is still waiting on the same input
arc!

The problem with the naive one-barrier implementation of sequential
loop is that the resources that we are reusing include the frame
slots used by the array of gates in the barrier. The signal tree of
the barrier, on the other hand, does not include completion of usage
of these frame slots.  Thus the signal from this signal-tree is not a
good enough indication that the next iteration can start.

\subsection{A Brute-force, Two-barrier Sequential Loop Schema} 

 A brute force fix for the incorrect one-barrier approach uses two
barriers as shown in Figure~\ref{fig:brute-force-2-barrier-seq-loop}.
The signal tree of barrier 2 indicates not only that computation has
finished within the loop body itself, but that the frame slots
belonging to the gates in barrier 1 can be reused.  As every output
from barrier 2 is recirculated back, the signal tree of barrier 1
cannot signal completion until every output of barrier 2 has left the
barrier.  This makes it safe to reuse the frame slots used by barrier
2's gates when the signal tree of barrier 1 signals completion.

\begin{fig}{fig:brute-force-2-barrier-seq-loop}
{Brute force implementation of sequential loop with two
barriers at the end of each iteration.  This implementation is correct
but very expensive.}
\illustrationx{1.9in}{brute-force-2-barriers-seq-loop}
\end{fig}

 Although the two-barrier approach is correct, it is very expensive.
On Monsoon, each barrier costs approximately $4n$ cycles where $n$ is
the number of nextified variables.  The total cost of using the
two-barrier approach is then $8n$ cycles.  This is a huge overhead!
Consider the loop of \verb|fib| for example.  The overhead will be
about 24 cycles when the ``useful work'' done each iteration is only 3
to 4 cycles.  RISC code implementing the same loop will only take 4
cycles each iteration!

\subsection{Culler's Sequential Loop Schema}

Culler\cite{Culler89} describes another correct implementation of
sequential loops which is less costly than the two-barrier approach.
The schema is shown in Figure~\ref{fig:culler-seq-loop}.  One can
still discern parts of two barriers, but the two parts of each
barrier, signal tree and array of gates, have been pulled apart.  In
addition, the schema cleverly avoids one array of gates by instead
using the array of switches and gating the predicate input to the
switches.  The reader is referred to
\cite{Culler89} for a correctness proof of this schema.

\begin{fig-top}{fig:culler-seq-loop}
{Culler's sequential loop schema.}
\illustrationx{2.5in}{culler-seq-loop}
\end{fig-top}

Culler's schema is less costly then the two-barrier approach.  On
Monsoon, the overhead for a sequential loop with $n$ nextified
variable is approximately $6n$ cycles per iteration, a significant
saving compared to $8n$ cycles for the two-barrier approach. This was
the best implementation we had before the current work, and was used
in the Id compiler.  However, $6n$ cycles per iteration is still a
hefty overhead.  For \verb|fib|, this still means 18 cycles of
overhead.  We will next present new sequential loop schemata that have
much lower overhead costs.

\section{Self-gating Sequential Loop Schema}
\label{sec:self-gating}

The self-gating sequential loop schema is motivated by an optimized
version of the one-barrier approach of
Section~\ref{sec:incorrect-1-barrier-seq-loop}.  In the optimized
version, we use the same clever trick that is used in Culler's
sequential loop schema to avoid an array of gates by making use of the
switches at the iteration boundary.  This still-incorrect schema is
shown in Figure~\ref{fig:fib-still-broken} for the {\tt fib} code.
The schema has very little overhead.  In terms of our cost measure,
the overhead is approximately $n+2$ cycles where $n$ is again the
number of nextified variables.  However, it suffers from the same
problem as the one-barrier approach.

\begin{fig}{fig:fib-still-broken}	
{\protect \verb|fib| wired up under the improved the one-barrier
sequential loop schema. Note how conflict can still occur at the
value-input to \protect \verb|p|'s switch.}
\illustrationx{1.9in}{fib-still-broken}
\end{fig}

The schema has no problem with conflicts within the loop-body
because of the signal tree and gating of the predicate into the
switches.  The setup ensures that tokens for the next iteration are
prevented from passing the row of switches until all tokens of the
previous iteration have cleared out of the loop-body.
There is also no problem with conflict within the loop-predicate
region if we ensure that the output of the loop-predicate region is
only produced when all computations inside the loop-predicate region
have completed.  This can be ensured locally within the loop-predicate
block.

The problem with the optimized one-barrier schema lies in the part of
the loop outside the loop-body and loop-predicate blocks.  In
particular, the trouble spots are the ``loop-back'' arcs that
recirculate the nextified variables produced in the loop-body back to
the switches.  Looking at Figure~\ref{fig:fib-still-broken}, we find
that once again, if the tokens of \verb|(next i)| and \verb|(next c)|
are processed before that of \verb|(next p)|, a fast recirculating
\verb|(next c)| from iteration $i$ can get into the next iteration,
become \verb|(next p)| of iteration $(i+1)$ which recirculates back to
the switch for \verb|p| and conflicts with the \verb|(next p)| of
iteration $i$ which is still there.

Culler's schema removes such conflicts by holding the nextified values
behind the row of gates outside the loop-body until all the nextified
values from the previous iteration have passed through the switches.
(See Figure~\ref{fig:culler-seq-loop}.)  We can, however, do better.
Careful examination of the optimized one-barrier schema shows that we
only need to hold {\em each} nextified value behind a gate until {\em
its} previous nextified value has gone through its switch.  This alone
will ensure that no conflict can occur at the input to each switch.
While we still need an array of gates to hold back the {\tt next}
values, each gate is triggered by a token carrying the current value
of the corresponding nextified variable.
Figure~\ref{fig:fib-self-gating-loop} illustrates this schema with the
{\tt fib} code.  The reader should check that no conflict can arise at
the input to \verb|p|'s switch as \verb|(next p)| of the $(i+1)^{th}$
iteration is held behind the gate labeled {\tt g1} in the figure until
\verb|(next p)| of the $i^{th}$ iteration has moved through its
switch.  We call this gating of the {\tt next} value of each nextified
value with its current value {\em self-gating}.  A formal correctness
proof of this schema is given in~\cite{Ang-ms92}.  This schema avoids
one of the signal trees in Culler's schema.  We will also see in
Section~\ref{sec:self-gating-opt} that it is easy to optimize the
self-gating schema.

\begin{fig}{fig:fib-self-gating-loop}
{The loop in \protect \verb|fib| wired up under the self-gating
sequential loop schema.}
\illustrationx{2.0in}{fib-self-gating-loop}
\end{fig}

The self-gating sequential loop schema incurs an overhead of
approximately $4n + 2$ cycles per iteration where n is the number of
nextified variables.  This is, approximately, a 33\% savings over the
$6n +2$ overhead of Culler's schema.  Further improvement is possible,
and we will see them next.

\subsection{Optimization of the Self-gating Sequential Loop Schema}
\label{sec:self-gating-opt}

The self-gating sequential loop schema has another big advantage over
Culler's schema in that in most cases, it can easily be optimized.
Self-gating is not always necessary and it is not difficult to
determine this at compile time.  Strictness information plays a
crucial role in the optimization.

\subsubsection{Removing Redundant Self-gates}

The self-gating of each nextified variable serves to ensure that
during each iteration, the {\tt next} value of a nextified variable
does not recirculate back to its switch until its current value has
passed through the switch.  For most nextified variables, there is
data-dependence between the current value and the {\tt next} value
such that the {\tt next} value cannot be produced until the current
value is available in the loop-body.  In such cases, the role
performed by self-gating is inherent in the code of loop-body itself,
so there is no need to add the self-gating.  Another way to look at
the data-dependence between the current and {\tt next} values of the
nextified variable is that the computation of the {\tt next} value is
strict in the current value.  This information can be gathered easily
by strictness analysis.

In the loop of \verb|fib| for example, the value of \verb|(next i)| is
strict in the value of \verb|i|.  Similarly for \verb|(next c)| and
\verb|c|.  There is therefore no need to self-gate either of these
nextified variables.  The resulting dataflow graph, together with the
optimization described in the next section, is shown in
Figure~\ref{fig:fully-optimized-fib-loop}.

\begin{fig}{fig:fully-optimized-fib-loop}
{The loop in \protect \verb|fib| wired up under the fully optimized
self-gating sequential loop schema.} 
\illustrationx{1.9in}{fully-optimized-fib-loops}
\end{fig}

\subsubsection{Reducing Iteration Termination Signal Tree Size}

A second optimization is to reduce the number of inputs to the
iteration termination signal tree.  Again, we make use of
data-dependence that is already present in the code to achieve this.
Nextified variables are included in the iteration termination signal
tree so that we do not let the loop predicate value get past gate {\tt
g2} in Figure~\ref{fig:fib-self-gating-loop} until all the {\tt next}
are available.  But if the predicate computed by the loop-predicate
block is strict in the {\tt next} value of a particular nextified
variable, we do not need to include that nextified variable in the
iteration termination signal tree.  In the \verb|fib| example, {\tt
(next i)} is required before the predicate \fbox{\verb|<=n|} can
execute.  There is therefore no need to include it in the iteration
termination signal tree.  The dataflow diagram of the {\tt fib} loop
including this optimization is shown in
Figure~\ref{fig:fully-optimized-fib-loop}


For a loop with $n$ nextified variables, $m$ of which need
self-gating, and $p$ of which need to be included in the iteration
termination signal tree, the overhead introduced by the sequential
loop schema is approximate $(p + 3m)$.  Usually, $m$ is much smaller
than $n$ and frequently 0, while $p$ is smaller than, but closed to
$n$.  Overall, this results in very low overhead for the sequential
loops.  In the {\tt fib} example, the overhead is only 5 cycles per
iteration, barely 30\% of the 18 cycles overhead incurred under
Culler's schema.

\section{Frame-based-variable (fbv) Sequential Loop Schema}
\label{sec:fbv}

While the self-gating sequential loop schema is a big improvement over
Culler's sequential loop schema, sequential loops are still fairly
expensive in Id.  Consider again the example that computes
$\sum_{i=1}^{n} i$ (Figure~\ref{fig:sum-1-n-code}).
Figure~\ref{fig:sum-loop-sgo} shows its implementation in the
optimized self-gating schema.

\begin{fig}{fig:sum-loop-sgo}
{The loop of $\sum_{i=1}^{n}$ wired up under the
optimized self-gating sequential loop schema.}
\illustrationx{1.9in}{sum-loop-sgo}
\end{fig}

The loop in \verb|sum_1_to| actually incurs very little overhead that
is directly attributed to the sequential loop schema.  No self-gating
is needed and {\tt (next i)} does not need to be included in the
iteration termination signal tree because the loop-predicate blocks's
output is strict in it.  Despite all these favorable conditions,
Monsoon takes 12 cycles
%\footnote{The 12 cycles only
%include those cycles that the Monsoon processor actually spends
%processing tokens belonging to the loop.  Because of Monsoon's
%interleaved pipeline, the actual latency for executing each iteration
%of the loop is longer.} 
to execute one iteration of this loop.  A
typical piece of RISC code performing the same task takes only 4
cycles.  Further improvement is needed and we begin this effort by
identifying the sources of inefficiency.

\subsection{Remaining Sources of Overhead in Sequential Loops}
\label{sec:remaining-overheads}

An examination of Figure~\ref{fig:sum-loop-sgo} shows that processor
cycles are incurred by the following that are not present in RISC
code: (1) switching, (2) fanout, and (3) matching bubbles.
%\begin{itemize}
%\item{switching,}
%\item{fanout, and}
%\item{matching bubbles.}
%\end{itemize}

{\em Switching} refers to the fine-grain switching at loop iteration
boundary.  This mechanism determines if the {\tt next} values of
nextified values go to the next iteration or exit the loop.  Each
nextified variable is switched individually.

{\em Fanout} are needed due to architectural constraints.  On Monsoon, each
instruction can have at most two destinations while some are
restricted to only one.  If a value is needed at more destinations
than the instruction producing it can cope with, we need to use {\em
fanout} instructions to supply the value to all the places where it is
needed.  A fanout instruction takes an input token and produces two
tokens carrying the same value.  In general, a tree of fanout
instructions is used to duplicate a value sufficiently many times to
supply all its destinations.

{\em Bubbles} are caused by matching.  During matching of two tokens,
the first token to arrive does not result in actual execution of an
instruction.  Nevertheless, Monsoon takes one cycle to process the
token.  As the ALU part of the pipeline is not used during this cycle,
the cycle is known as a {\em matching bubble} or bubble in short.
Thus, each binary operation takes at least two cycles to execute with
the first one a bubble.

All the features listed above are needed to support fine-grain
parallel execution in the pure-dataflow model.  Fanout overhead can be
reduced slightly with better architectural support such as the
``repeat'' feature found on the Epsilon-2 machine\cite{Grafe90}.  But
as long as each operand value is distributed on a token in the
conventional dataflow model, switching and matching bubble cycles are
inevitable.  They are deeply tied to pure-dataflow's model of data
transfer and instruction execution.

The analysis yields some good news and some bad ones.  The bad news
is: if we insist on staying within the pure-dataflow model, there is
little we can do to improve the efficiency of loops except perhaps add
hardware to perform fanout and matching without using the main
processor pipeline.  It is not clear how much is gained through such
hardware solutions when the cost of hardware is taken into account.
On the other hand, if we are willing to go beyond the pure-dataflow
model by adopting some elements of von Neumann style execution, we can
improve the efficiency of most sequential loops through a different
compilation strategy.  This is the basis of our next approach.

\subsection{The Frame-based-variable (Fbv) Approach}

This new implementation of sequential loops is motivated by the
observation that sequential loops {\em must} synchronize at the loop
boundary.  The presence of this synchronization makes some of the
matching in the loop-body itself redundant.

Specifically, all the {\tt next} values of nextified variables are
synchronized at the end of each iteration.  When these values cross
over to the next iteration, they become the current values of the
nextified variables.  Thus, by the time the next iteration starts
executing, we already know that the current values of nextified
variables are available, and there should be no need to
synchronize(match) before their uses.  If we can somehow harness this
property, we should be able to reduce the number of matching bubbles.

There is also no point in switching each nextified value individually.
Fine-grain switching is done so that computations needing only the
switched value can proceed as soon as possible.  However, due to the
barrier at iteration boundary, we are not making use of this benefit
of fine-grain switching at all.  As fine-grain switching is fairly
expensive, it will be a great saving if we can get rid of them or
reduce their number.

\subsubsection{A Mixed Dataflow-von Neumann Execution Model}

In order to reap the benefits outlined above, we need an execution
style with ``von Neumann'' flavors: the values of nextified variables
are passed {\em via frame memory locations} instead of on tokens.
{\tt Next} values are stored directly into frame memory locations, and
uses of a nextified variable simply read from these locations.  The
approach shares some similarities with multithreading described
in~\cite{KP-multithread91}.  With such an approach, we only need to
retain one nextified variable that is passed via tokens and switched
at the iteration boundary to initiate each iteration.  As most
nextified variables are stored explicitly in frame slots, this
approach is called the {\em frame-based-variable (fbv)} sequential
loop schema.

Ideally, we would like the operations that use nextified variables to
read the frame memory locations directly, and those that produce the
{\tt next} values to store them into frame memory directly.
Unfortunately, this requires a frame-memory to frame-memory 3-address
instruction set that is not supported by Monsoon.  It is also doubtful
whether such instructions can be supported efficiently on real
machines.  Memory hierarchy to support efficient fine-grain execution
is an interesting and important topic but is unfortunately beyond the
scope of this work.

 Coming back to Monsoon, storing into frame memory has to be done via
an explicit store instruction.  For reads, however, we can at times
avoid identity instructions, which are Monsoon's equivalent of
explicit load instructions.  Monsoon supports a one-address
accumulator style code.  In the case where a nextified variable is
used in a binary operation which has a token input as the other
operand, Monsoon is able to read the value of the nextified variable
from memory directly.  In cases where both inputs of an instruction
are from frame memory, we need to insert an identity instruction that
fetches one of the operands explicitly.  The identity instruction will
have to be {\em triggered}, i.e. have a trigger input, as the arrival
of a token is the only way to initiate execution on Monsoon.  A
trigger in this case is similar to a trigger to a gate instruction in
that the token is merely used to enable an operation.

\begin{fig}{fig:first-broken-fbv-loop}
{The skeleton of the frame-based-variable (fbv) sequential loop
schema.  This is not complete.  Additional mechanisms is needed to
prevent WAR hazards.}
\illustrationx{2.1in}{first-broken-fbv-loop}
\end{fig}

The general fbv sequential loop schema is shown in
Figure~\ref{fig:first-broken-fbv-loop}.  Self-gating of the switched
nextified variable can be optimized out as usual if the
data-dependence check allows it.  As before, we need to collect an
iteration termination signal.  For nextified variables that are not
switched, the signal outputs of the store instructions are fed into
the iteration termination signal tree.  We cannot optimize any of
these out on the ground that the loop-predicate is strict in that
nextified variable.  This optimization only apply to switched
nextified variables.

{\tt Next} values that are used in the loop-predicate block are still
supplied via tokens.  That accounts for the re-circulation arcs, but
there are usually relatively few of them as nextified variables not
used in the loop-predicate block are not recirculated.  The initial
values of the nextified variables have to be stored before the loop
can start execution.  This is done by the row of store instructions at
the top of Figure~\ref{fig:first-broken-fbv-loop}.  Lastly, the final
values returned by the loop need to be fetched explicitly.  

\subsection{Data Hazards in the Frame-based-variables Approach}  

The fbv sequential loop schema described in the last section suffers
from a major complication arising from the parallel execution of code
{\em within} the loop-body.  The body of each iteration is executed in
parallel in a sequential loop, even though the iterations of the loop
are executed one at a time.  Under the fbv approach, each frame slot
used to store a nextified variable is both read from and written into
every iteration.  For correctness, we have to make sure that every use
of a nextified variable reads the current value and not the {\tt next}
value.  But because of parallel execution in the loop-body, this is
not guaranteed automatically and it is possible to have {\em Write
After Read (WAR) hazards}\footnote{Write After Read hazard is a term
used in RISC literature to refer to incorrect ordering of memory
operations where a write that should occur after a read from the same
location is allowed to occur before the read.  The read ends up
reading a newer value stored to that location.} where the update
occurs too soon.

A nextified variable suffers from WAR hazard if there is a use of the
nextified variable that is {\em not} guaranteed to occur before the
{\tt next} value of the nextified variable is computed.  A use is
guaranteed to occur first if it is strict for the computation of the
{\tt next} value.  There are several ways to deal with this problem;
we explored two general solutions: (1) delay the store of the {\tt
next} value until it is safe to perform the store; (2) use two frame
slots for each nextified variables, one for reads, one for the write,
moving the value from the write slot to the read slot at the iteration
boundary.

\subsubsection{Fbv hazard solution 1: Delaying the Store}

We can avoid WAR hazards by delaying the store of each {\tt next}
value with a suitably triggered gate, i.e. insert a gate instruction
on the arc supplying the value to be stored.  We call each gate
instruction used this way a {\em store-gate}, and this solution, the
{\em gated-store approach}. The trigger input to each store-gate
is carefully chosen so that its availability signals the completion of
all the reads from the corresponding frame slot, making it safe for
the store to proceed.  

 For a nextified variable \verb|x| that suffers WAR hazard, the most
straight forward way to obtain a trigger for its store-gate is to
perform an explicit fetch of \verb|x| from its frame slot.  The output
of this fetch is supplied to all the uses of \verb|x| that are not
strict for \verb|(next x)|, and also used to trigger the store-gate of
\verb|x|.  This ensures that the store will never occur until all
reads from \verb|x|'s frame location are done.
Figure~\ref{fig:fbv-naive-trigger} shows the fbv sequential loop
schema with this approach to handle WAR hazards.  Storage of the
initial values of nextified variables is left out in the figure to
avoid clutter.

\begin{fig}{fig:fbv-naive-trigger}
{The frame-based-variable sequential loop schema with the 
gated-store, explicit fetch, approach to dealing with WAR hazards.}
\illustrationx{2.15in}{fbv-naive-trigger}
\end{fig}

 The gated-store solution described above can be optimized.  The
gated-store solution inserts an explicit fetch for each nextified
variable that has a hazard problem.  Each of these fetches is
triggered with an input that initiates the fetch.  By using the output
of a fetch to trigger another fetch and carefully ordering the
fetches, we can add data-dependence between uses of nextified
variables and their respective {\tt next} values without changing the
overall semantics of the program.  Such added data-dependences can
remove some of the WAR hazards.

\begin{fig-top}{fig:fib-gs}
{{\tt fib} wired under the fbv sequential loop schema with the 
general gated-store, explicit fetch, approach to dealing with WAR
hazards. The dataflow graph on the left is without optimization while
the one on the right optimizes the triggering order.}
\begin{tabular}{l r}
\illustrationtx{1.6in}{fib-gs} &
\illustrationtx{1.6in}{fib-gs-o2} \\
\end{tabular}
\end{fig-top}

Figure~\ref{fig:fib-gs} show how this is applied to the loop in {\tt
fib}.  The left side of the figure shows the loop without this
optimization.  As both {\tt p} and {\tt c} have uses that are not
strict for {\tt (next p)} and {\tt (next c)} respectively, they need
store-gates as shown.  With clever choice of triggers for the fetches,
however, we can trigger the fetch of {\tt c} with the output from the
fetch of {\tt p}.  As {\tt (next p)} is dependent on the output of
this fetch of {\tt c}, this choice of fetch triggers effective makes
{\tt (next p)} dependent on the only use of {\tt p}, making it
unnecessary to gate the store of {\tt (next p)}.  The resulting
dataflow graph is shown on the right side of Figure~\ref{fig:fib-gs}.

\subsubsection{Fbv hazard solution 2: Using 2 frame slots.}

The second solution to the hazard problem uses 2 frame slots for each
nextified variable.  In the loop-body, we always read from one
location and store into the other.  At the end of each iteration, we
move the values from the store-locations to the read-locations before
allowing the next iteration to start.
Figure~\ref{fig:fbv-2-slot-loop} shows the resulting fbv sequential
loop schema.  We will refer to this solution as the {\em 2-slot
approach}.

\begin{fig}{fig:fbv-2-slot-loop}
{The frame-based-variable sequential loop schema with the 
2-frame-slot-per-nextified variable approach to take care of 
WAR hazards.}
\illustrationx{2.25in}{fbv-2-slot-loop}
\end{fig}

This solution is very simple in that the compiler needs to do almost
no analysis to implement it.  Surprisingly, even though a move from
one frame memory location to another takes two instructions on
Monsoon, the solution is still fairly efficient as there is no gating
whatsoever.  

 The one drawback of this schema is that the string of fetch-store
instructions performing the moves in-between iterations can result in
rather long latency.  This is particularly bad for Monsoon which is
very sensitive to a single long thread.  Unlike most pipelined RISC
processors, each Monsoon processor interleaves eight independent
thread of computation, such that a single thread will only occupy one
out of every eight cycles.  Latency of an $n$ instruction thread is
therefore $(8\times n)$.  In addition, eight-fold parallelism is
needed on each processor to keep it busy.  By linearizing work into a
thread, the 2-slot approach reduces parallelism.  We will see some of
these effects in the next section when we present some run time
statistics.

%\subsubsection{Comparison of Estimated Overhead}
%
%We end this section with a very rough analytical comparison of the
%self-gating sequential loop schema and the two fbv sequential loop
%schemata: self-gating with explicit fetches, and the 2-slot fbv.  We
%will consider the cost per iteration for a nextified variable.  The
%cost measure that we employ here is slightly different from the one we
%used when discussing the self-gating sequential loop schema as we want
%to include the cost of supplying the nextified variables on tokens.
%We will therefore include all the cycles when tokens carrying
%nextified variable values, whether current or {\tt next} values, are
%processed.
%
%For self-gating, there are four situations depending on whether the
%nextified variable needs self-gating and whether it is to be included
%in iteration termination signal.  The cases are:
%\begin{center}
%\begin{tabular}{c c c}
%\hline
%Self-gating & Included in iteration & cycles  \\
% &  termination signal & \\
%\hline
%No & No & 4 \\
%No & Yes & 6 \\
%Yes & No & 7 \\
%Yes & Yes & 8 \\
%\hline
%\end{tabular}
%\end{center}
%We expect most nextified variables to fall under the second case.  
%
%With the general gated-store fbv sequential loop schema there are three
%possible cases.  
%\begin{center}
%\begin{tabular}{c c c}
%\hline
%Gating of the store & Explicit fetch & cycles \\
%\hline
%No & No  & 2 \\
%No & Yes & 5 \\
%Yes & Yes & 7 \\
%\hline
%\end{tabular}
%\end{center}
%It is more difficult to tell which category nextified variables will
%fall under as it is highly dependent on the code in rather complicated
%ways.  
%
%Finally, with the 2-slot fbv schema, there are two cases:
%\begin{center}
%\begin{tabular}{c c}
%\hline
%Explicit fetch & cycles \\
%\hline
%No & 4 \\
%Yes & 7 \\
%\hline
%\end{tabular}
%\end{center}
%
%While it is difficult to make an absolute analytical comparison
%because the different cases in each schema arise under conditions that
%do not have direct correspondence, it seems highly likely that for
%most sequential loops, one of the two fbv schemata is superior to the
%self-gating schema.  The next section supports this conclusion with
%actual run time results.

\section{Run Time Statistics on Monsoon}
\label{sec:run-time-stats}

In this section, we present the run time statistics of eight programs
compiled using four different sequential loop schemata: Culler's
schema, self-gating schema, gated-store-fbv and 2-slot-fbv.  The
programs are run on a Monsoon configured with one processing element
(PE) and one I-Structure (IS) board.  The statistics are gathered with
hardware support and is non-intrusive to the first
order\cite{monitoring-monsoon,Venkat-92}.  We will first briefly
describe the eight programs before examining the statistics.

\subsection{The Benchmarks}
\label{sec:seq-loop-benchmarks}

The following benchmarks are used to compare the different sequential
loop schemata.  Each has a sequential loop as its innermost loop.
\begin{enumerate}
\item {\sc Matrix Multiply} creates two $n \times n$ double-precision
floating point matrices, computes their product matrix and returns the
sum of the elements of the product matrix as its result.  The
multiplication of matrices is coded up as straight-forward, triply
nested loops with the innermost loop computing a dot-product.  

%The algorithm runs in O($n^3$) time.

\item {\sc Blocked MM} is similar to {\sc Matrix
Multiply} except that it is blocked so that each iteration of the
innermost loop computes the inner-product of a $4 \times 4$ block of
the result matrix.

\item {\sc Simple}\cite{simple} is a hydrodynamics and heat conduction
simulation program.  
%The Simple document, along with the associated
%Fortran program, was developed as an unclassified
%benchmark\cite{simple} to evaluate various high performance machines
%and compilers.  
It uses a Lagrangian formulation of equations to
simulate the behavior of fluid in a sphere.  Unlike the other
benchmarks described here, this is a sizable program and is
representative of a class of numerical programs.

% \cite{paraffins}
\item {\sc Paraffins} enumerates all the distinct
isomers of every paraffin\footnote{Paraffins are molecules with
chemical formula $C_{n}H_{2n+2}$, where C and H stand for carbon and
hydrogen atoms, respectively, and $n > 0$.} with $n$ or fewer Carbon
atoms.
%The algorithm is $O(e^n)$.  
The program generates lists of paraffins and finally returns an array
filled with the number of distinct paraffins of each size up to and
including the maximum size specified by the user.

\item {\sc Fib} computes the $n^{th}$ Fibonacci number.  The code is
listed in Section~\ref{sec:incorrect-1-barrier-seq-loop} and does the
computation with a sequential loop.  It runs in O($n$) time.

\item {\sc Merge Sort} generates an array of $n$ random
numbers and then proceeds to sort it using the merge sort algorithm.
The program is recursive but uses a loop to perform merging.  

%The algorithm does O($n \log n$) work and has at most O($\log n$) fold
%parallelism.

\item {\sc Stats} generates an array of size $n$, fills it with random
numbers and then finds the minimum, maximum, and average of the values
in the array.  

%This takes O($n$) time.

\item {\sc FFT} computes the Fast Fourier Transform of a degree $n$
polynomial.  It takes O($n \log n$) time.
\end{enumerate}


\subsection{The Results}
\label{sec:stats-def}

 Table~\ref{tab:seq-loop-comparison} shows the results.  Due to the
lack of space,the data is highly compressed.  For each program, three
pairs of normalized numbers, each corresponding to using a new
sequential loop schema during compilation, are reported.  The two
numbers in each pair are separated by a slash ``/''.  The first, {\em
token-count}, corresponds to the total number of tokens processed by
the Monsoon processor and can be thought of as the useful work done.
The second corresponds to the elapsed time for running the program,
and is call the {\em critical path length}.  The difference between
the two numbers is due to Monsoon's 8-way interleaved pipeline which
requires eight fold parallelism at any time to keep a processor busy.
When there is not enough parallelism, idle cycles are incurred, which
are included in the critical path length but not the token-count.  All
the numbers are normalized, using the token-count and critical path
length of the same program compiled with Culler's schema as basis.


%\begin{table*}
%\begin{center}
%\begin{tabular}{|l|c|c|c|c|}
%\hline
%Program                                   & Culler's & Self-gating 
%					  & Gated-store-Fbv & 2-slot-Fbv \\ 
%                & ($\times 10^3$ cycles) 
%                & ($\times 10^3$ cycles) 
%                & ($\times 10^3$ cycles) & ($\times 10^3$ cycles) \\\hline
%\hline
%{\sc Matrix Multiply}(n = 100)     & 32434/35480
%				   & 22217/25195
%				   & 17105/19668
%				   & 17105/19669 \\\hline
%{\sc Blocked MM}(n = 100)          & 18172/19053
%				   & 12469/13373
%				   & 9264/10080
%				   & 9264/10078 \\\hline
%{\sc Simple}(25 $\times$ 25, 25 cycles)
%                                   & 107350/114084
%                                   & 102842/109533
%                                   & 101381/108005
%                                   & 102598/109213 \\\hline
%{\sc Paraffins} (n = 19)           & 26204/27119
%			           & 23086/24051
%				   & 23399/24413
%				   & 23040/24097 \\\hline
%{\sc Fib} (n = 100)		   & 3.369/8.861     & 2.379/6.683 
%				   & 1.181/7.093     & 1.382/9.386\\\hline
%{\sc Merge-sort} (n = 500)	   & 758.9/911.7     & 700.2/854.7
%	 			   & 669.8/829.3     & 693.0/858.2\\\hline
%{\sc Stats} (n = 1000)		   & 99.35/132.4     & 78.44/108.9
%	 			   & 65.95/97.38     & 65.95/99.34\\\hline
%{\sc FFT} (n = 256)		   & 195.1/215.2     & 176.0/197.9 
%				   & 170.4/191.4     & 172.5/195.3\\\hline
%\end{tabular}
%\end{center}
%\caption{Comparison of various Sequential Loop Schema. Each box
%contains 2 numbers: token-count/critical path length.}
%\label{tab:seq-loop-comparison}

%\begin{table*}
%\begin{center}
%\begin{tabular}{|l|c|c|c|c|}
%\hline
%Program                                   & Culler's & Self-gating 
%					  & Gated-store-Fbv & 2-slot-Fbv \\ 
%%                & ($\times 10^3$ cycles) 
%%                & ($\times 10^3$ cycles) 
%%                & ($\times 10^3$ cycles) & ($\times 10^3$ cycles) \\
%\hline
%\hline
%{\sc Matrix Multiply}(n = 100)     & 1.00/1.00
%				   & 0.68/0.71
%				   & 0.53/0.55
%				   & 0.53/0.55 \\\hline
%{\sc Blocked MM}(n = 100)          & 1.00/1.00
%				   & 0.69/0.70
%				   & 0.51/0.53
%				   & 0.51/0.53 \\\hline
%{\sc Simple}(25 $\times$ 25, 25 cycles)
%                                   & 1.00/1.00
%                                   & 0.96/0.96
%                                   & 0.94/0.95
%                                   & 0.96/0.96 \\\hline
%{\sc Paraffins} (n = 19)           & 1.00/1.00
%			           & 0.88/0.89
%				   & 0.89/0.90
%				   & 0.88/0.89 \\\hline
%{\sc Fib} (n = 100)		   & 1.00/1.00     & 0.71/0.75
%				   & 0.35/0.80     & 0.41/1.06 \\\hline
%{\sc Merge-sort} (n = 500)	   & 1.00/1.00     & 0.92/0.93
%	 			   & 0.88/0.91     & 0.91/0.94\\\hline
%{\sc Stats} (n = 1000)		   & 1.00/1.00     & 0.79/0.82
%	 			   & 0.66/0.74     & 0.66/0.75\\\hline
%{\sc FFT} (n = 256)		   & 1.00/1.00     & 0.90/0.92
%				   & 0.87/0.89     & 0.88/0.91\\\hline
%\end{tabular}
%\end{center}
%\caption{Comparison of various Sequential Loop Schema. Each box
%contains 2 numbers: normalized token-count/critical path length.}
%\label{tab:seq-loop-comparison}
%\end{table*}
%
\begin{table}
\begin{center}
\begin{tabular}{|l|c|c|c|}
\hline
Program                                   & Self-gating 
					  & Gated- & 2-slot-Fbv \\ 
& & store-Fbv & \\
\hline
\hline
{\sc Matrix Multiply}              & 0.68/0.71
				   & 0.53/0.55
				   & 0.53/0.55 \\\hline
{\sc Blocked MM}                   & 0.69/0.70
				   & 0.51/0.53
				   & 0.51/0.53 \\\hline
{\sc Simple}                       & 0.96/0.96
                                   & 0.94/0.95
                                   & 0.96/0.96 \\\hline
{\sc Paraffins}                    & 0.88/0.89
				   & 0.89/0.90
				   & 0.88/0.89 \\\hline
{\sc Fib}  			   & 0.71/0.75
				   & 0.35/0.80     & 0.41/1.06 \\\hline
{\sc Merge-sort}		   & 0.92/0.93
	 			   & 0.88/0.91     & 0.91/0.94\\\hline
{\sc Stats} 			   & 0.79/0.82
	 			   & 0.66/0.74     & 0.66/0.75\\\hline
{\sc FFT} 			   & 0.90/0.92
				   & 0.87/0.89     & 0.88/0.91\\\hline
\end{tabular}
\end{center}
\caption{Comparison of various Sequential Loop Schema. Each box
contains 2 numbers: normalized token-count/ critical path length.
Normalization is with respect to the run time of the respective
programs compiled with Culler's schema.}
\label{tab:seq-loop-comparison}
\end{table}

%\begin{fig-no-boarder}{tab:seq-loop-comparison}
%{Comparison of various Sequential Loop Schema. Each box contains 2
%numbers: token-count/critical path length.}
%\illustrationx{6.2in}{seq-loop-raw-results-table}
%\end{fig-no-boarder}

While critical path length is important if we are interested in how
fast each program runs on its own, the token-count matters more here
as most of these benchmarks are small toy routines that we expect to
find as inner loops of larger programs.  Real programs are expected to
be larger and have several instances of the inner-loops executing at
the same time which together provide the required parallelism.  We
should, nevertheless, try to keep the critical path lengths closed to
the token-counts so that the amount of parallelism that has to be
provided by other code running at the same time is kept low.

The token-count of every program is lower when compiled with any of
the three new sequential loop schemata than with Culler's schema.  In
addition, the fbv schema with gated-stores gives the best run time in
almost every cases.  Improvements ranges from 6\% to 65\%.  The low
improvement for {\sc Simple} can be explained by noting that {\sc
Simple} contains loops with very few nextified variables, and also
fairly large loop bodies.  This means that the loop overhead was
relatively small to start with, and hence there is little scope for
improvements. 

The critical path length of the benchmark programs shows similar
improvement.  The only exception is {\sc Fib} compiled under the
2-slot fbv schema where the critical path is actually {\em longer}
than the same program compiled under Culler's schema.  This example
illustrates the short-coming of the 2-slot fbv schema that we
mentioned earlier, namely that of a long single thread where data is
move between the write and read slots.  Gated-store fbv is still the
best in most cases.  In other cases it is also not too far off from
the best timing.

%\begin{figure*}
%\begin{tabular}{l r}
%\illustrationtx{2.5in}{mm-loop-schemas} &
%\illustrationtx{2.5in}{bmm-loop-schemas} \\
%\\ \\
%\illustrationtx{2.5in}{simple-loop-schemas} &
%\illustrationtx{2.5in}{paraf-loop-schemas} \\
%\end{tabular}
%\caption{Run time of the benchmark programs under the 4 different
%sequential loop schemas.}
%\label{fig:seq-loop-stats-a}
%\end{figure*}
%
%\begin{figure*}
%\begin{tabular}{l r}
%\illustrationtx{2.5in}{fib-loop-schemas} &
%\illustrationtx{2.5in}{ms-loop-schemas} \\ 
%\\ \\
%\illustrationtx{2.5in}{stats-loop-schemas} &
%\illustrationtx{2.5in}{fft-loop-schemas} \\
%\end{tabular}
%\caption{Run time of the benchmark programs under the 4 different
%sequential loop schemas.}
%\label{fig:seq-loop-stats-b}
%\end{figure*}
%
%
%\begin{figure*}
%\begin{tabular}{l l l l l}
%\illustrationtx{1.45in}{mm-loop-schemas} &
%\illustrationtx{1.45in}{bmm-loop-schemas} &
%\illustrationtx{1.45in}{simple-loop-schemas} &
%\illustrationtx{1.45in}{paraf-loop-schemas} \\
%\\ \\
%\illustrationtx{1.45in}{fib-loop-schemas} & 
%\illustrationtx{1.45in}{ms-loop-schemas} & 
%\illustrationtx{1.45in}{stats-loop-schemas} & 
%\illustrationtx{1.45in}{fft-loop-schemas} \\
%\end{tabular}
%\caption{Run time of the benchmark programs under the 4 different
%sequential loop schemata.}
%\label{fig:seq-loop-stats}
%\end{figure*}

%\begin{table*}
%\begin{center}
%\begin{tabular}{|l|c|c|c|}
%\hline
%Program                           & Self-gating & Gated-store-Fbv & 2-slot-Fbv \\ \hline
%\hline
%Matrix-Multiply (n = 100)	  & 31.50\%/28.99\% & 47.26\%/44.57\% & 47.26\%/44.56\% \\\hline
%Blocked-Matrix-Multiply (n = 100) & 31.38\%/29.81\% & 49.02\%/47.09\% & 49.02\%/47.11\% \\\hline
%Paraffins (n = 19)	          & 11.90\%/11.31\% & 10.70\%/9.98\%  & 12.07\%/11.14\% \\\hline
%Fib (n = 100)		          & 29.39\%/24.58\% & 64.95\%/19.95\% & 58.98\%/-5.92\% \\\hline
%Merge-Sort (n = 500) 		  & 7.73\%/6.25\%   & 11.74\%/9.04\%  & 8.68\%/5.87\% \\\hline
%Stats (n = 1000)	  	  & 21.05\%/17.75\% & 33.62\%/26.45\% & 33.62\%/24.97\% \\\hline
%FFT (n = 256)			  & 9.79\%/8.04\%   & 12.66\%/11.06\% & 11.58\%/9.25\% \\\hline
%\end{tabular}
%\end{center}
%\caption{Percentage improvement over Culler's schema.}
%\label{tab:seq-loop-improvement}
%\end{table*}

%\begin{table*}
%\begin{center}
%\begin{tabular}{|l|r|r|r|}
%\hline
%Program                           & Self-gating & Gated-store-Fbv & 2-slot-Fbv \\ \hline
%\hline
%{\sc Matrix Multiply} (n = 100)	  & 31.50\% & * 47.26\% & * 47.26\% \\\hline
%{\sc Blocked Matrix Multiply} (n = 100) & 31.38\% & * 49.02\% & * 49.02\%
%\\\hline
%{\sc Simple} (25 $\times$ 25, 25 cycles)& 4.20\%  & * 5.56\% & 4.43\% \\\hline
%{\sc Paraffins} (n = 19)          & 11.90\% & 10.70\%   & * 12.07\% \\\hline
%{\sc Fib} (n = 100)	          & 29.39\% & * 64.95\% & 58.98\%  \\\hline
%{\sc Merge-Sort} (n = 500) 	  & 7.73\%  & * 11.74\% & 8.68\%   \\\hline
%{\sc Stats} (n = 1000)	  	  & 21.05\% & * 33.62\% & * 33.62\% \\\hline
%{\sc FFT} (n = 256)		  & 9.79\%  & * 12.66\% & 11.58\% \\\hline
%\end{tabular}
%\end{center}
%\caption{Percentage improvement of token-count over Culler's schema.}
%\label{tab:seq-loop-improvement-tc}
%\end{table*}



%\begin{table*}
%\begin{center}
%\begin{tabular}{|l|r|r|r|}
%\hline
%Program                           & Self-gating & Gated-store-Fbv & 2-slot-Fbv \\ \hline
%\hline
%{\sc Matrix Multiply} (n = 100)	  & 28.99\%   & * 44.57\% & 44.56\% \\\hline
%{\sc Blocked Matrix Multiply} (n = 100) & 29.81\%   & 47.09\%   & * 47.11\% \\\hline
%{\sc Simple} (25 $\times$ 25, 25 cycles)& 4.00\%  & * 5.33\% & 4.27\% \\\hline
%{\sc Paraffins} (n = 19)          & * 11.31\% & 9.98\%    & 11.14\% \\\hline
%{\sc Fib} (n = 100)	          & * 24.58\% & 19.95\%   & -5.92\% \\\hline
%{\sc Merge-Sort} (n = 500) 	  & 6.25\%    & * 9.04\%  & 5.87\% \\\hline
%{\sc Stats} (n = 1000)	  	  & 17.75\%   & * 26.45\% & 24.97\% \\\hline
%{\sc FFT} (n = 256)		  & 8.04\%    & * 11.06\% & 9.25\% \\\hline
%\end{tabular}
%\end{center}
%\caption{Precentage improvement of critical path length over Culler's schema.}
%\label{tab:seq-loop-improvement-cpl}
%\end{table*}

Based on the run time for our benchmarks, the gated-store fbv
sequential loop schema emerges as the best sequential loop schema
among those that we have studied, having both low token-counts and
critical path lengths.  

%\section{Inefficiencies of Pure Dataflow Execution}
\section{Conclusion and Future Directions}
\label{sec:insights-etc}

We explored various ways of implementing sequential loops efficiently
on dynamic dataflow machines that perform matching with frame memory.
Several other good schemata were not examined due to lack of space.
We will quickly point out a few of them, although we believe that what
we have presented in this paper are at least as good.  One way of
reducing the sequential loop overhead of the 2-barrier approach is to
use 2 copies of code, with a barrier between each copy.  In addition,
the gates in the barriers can be removed by simply gating the switch
predicate instead.  We believe that the self-gating sequential loop
schema is as efficient as this schema for most cases, given that most
nextified variables are strict in their current values.  By using the
self-gating schema, we avoid the increases in code and frame sizes
that accompany duplication of code.  The 2-slot fbv can also be
improved by duplicating code.  This avoids the explicit moves between
the two slots by having each copy use opposite slots for reading and
writing.\footnote{I would like to thank one of the referees for
pointing out these possibilities.}

This work also pointed out very clearly the shortcomings of pure
dataflow execution.  The comparison of pure dataflow execution with
RISC style code in Section~\ref{sec:remaining-overheads} is applicable
to dataflow execution in general.  The overheads of switching, fanout
and matching bubbles is {\em inherent} in the pure dataflow execution
model.  These problems have already been noted by other researchers,
and means of overcoming them have been suggested by
Iannucci\cite{Iannucci90}, Culler\cite{schauser91}, Traub and
Papadoupolos\cite{KP-multithread91,Kt-partitioning92}.  In general, a
fundamental change in the way data is communicated, from {\em only}
via tokens to using memory as well is needed.  This together with {\em
threading} by the compiler allows redundant synchronization to be
removed.

The *T project\cite{Start92}, jointly undertaken by our research group
at MIT and Motorola, will be investigating and testing these
approaches on a real machine.  Some interesting open questions remain,
including what sort of memory hierarchy, instruction set and
scheduling will efficiently support this style of execution.  It
appears doubtful that the traditional RISC style three-address
register-to-register instruction sets with generic general-purpose
registers is a good match for this style of execution due to the
expected high frequency of thread switch.
%Various researchers\cite{Aga90,Nuth91,Vijay92} are investigating
%different aspects of this problem, which will be another key issue to
%study in the *T project.

\smallskip
\noindent{\bf Acknowledgements}

Funding is provided in part by the Advanced
Research Projects Agency of the Department of Defence under Office of
Naval Research contract N00014-89-J-1988.

\bibliography{abbrevs,thesis}

\end{document}

Space allocation: (The hard fact is that we only have 10 pages.)

 amount 	use		remaining

    1 	    bibliography  	    9
    1	 	intro		    8
    1	     background		    7
    1	    stats & result	    6
   1/2	     conclusion		   5 1/2
    1	   other schemata	   4 1/2
    2	     self gating	   2 1/2
  2 1/2		fbv		    0


* Remove Comparison of Estimated Overhead?
* Remove bar-charts? 