%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Monsoon: a Proof-of-Concept Dataflow Machine}
%----------------------------------------------------------------------------
\label{sec:monsoon}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%Outline:
%
%1. At the first order, works fine
%   - existence proof
%   - good performance
%2. Weaknesses
%   - single threaded
%      - implementation not arch (Alewife?)
%   - instruction set
%      - EM-4

Monsoon\cite{Culler-greg90,Greg-monsoon,Traub91} is an existence proof
that dataflow hardware is buildable.  It incorporates both fast
messaging and fast context switching as well as supports fast
synchronization, all deemed desirable for fine-grain parallel codes.
Monsoon was designed at MIT and built by Motorola.  It was designed to
run pure dynamic dataflow code, such as Id\cite{Id} programs compiled
in that style.  It is based on an eight-stage pipelined processing
node running at ten MHz (see Figure~\ref{fig:monsoon}).  Monsoon's
pipeline stages are interleaved like the Denelcor HEP\cite{HEP} --- a
single thread can only execute during one out of every eight cycles.
The global memory in Monsoon is supported in the form of I-structure
boards, each of which contains four million 64-bit words.  In
addition, presence bits are associated with each word of I-structure
memory.  The I-structure boards perform the necessary manipulation of
presence bits, including the ``deferred list''
management\cite{Culler-greg90}.  Monsoon processors and I-structure
boards are connected by a 100 MBytes/second/port network built out of
PaRC switches.  The largest configuration built contains eight Monsoon
processing elements and eight I-structure boards each.  One such
system is located at MIT and the other at Los Alamos National
Laboratory.

\begin{figure}
\illustrationpercent{jpdc-monsoon-pipe}{50}
\caption{A Monsoon node (taken from \protect{\cite{Culler-greg90}})}
\label{fig:monsoon}
\end{figure}

Monsoon demonstrates the feasibility of dataflow architectures as
discussed in the previous section.  Our performance studies to date
show good speedups and cycle counts.  For up to the largest machine
configuration of 8 processors, Monsoon is able to achieve linear
speedup for most programs (see Figure~\ref{tab:speedup}). We are able
to explain the causes for less than perfect
speedup\cite{monsoon-perf93}.  Also, cycle counts of programs executed
on Monsoon are only 3 times that of corresponding fully optimized
C/Fortran programs executed on a typical RISC processor (see
Figure~\ref{tab:mips}).  This demonstrates that with the proper
architecture, it is possible to take advantage of fine-grain
parallelism without paying an unduly high price.  


%%%%
% these tables from /bk/derek/research/papers/per/016/scalibility.tex         
%               and /bk/derek/research/papers/per/016/baseline.tex         
%%%%
\begin{figure}
\begin{center}
\begin{tabular}{|l||l|l||l|l||l|l||l|l|}
\hline
\hfill Configuration  & \multicolumn{2}{c||}{1 PE} & \multicolumn{2}{c||}{2 PE} & \multicolumn{2}{c||}{4 PE}  & \multicolumn{2}{c|}{8 PE} \\ \cline{2-9}
  &  & $\times10^6$ &  & $\times10^6$ &  & $\times10^6$ &  & $\times10^6$\\
Program  & $\frac{1 PE}{1 PE}$ & critical  & $\frac{1 PE}{2 PE}$ & critical &
$\frac{1 PE}{4 PE}$ & critical & $\frac{1 PE}{8 PE}$ & critical\\
  & & path  &  & path &  & path &  & path\\\hline
\hline
$4 \times 4$ Blocked-MM      & 1   & 1057   & 1.99  & 531   & 3.90  & 271   & 7.74  &137 \\
$500\times 500$         &     &         &       &        &       &        &       &\\\hline
Gamteb-2c       & 1   & 590     & 1.95  & 303    & 3.81  & 155   & 7.35  &80.3 \\
40000 particles &     &         &       &        &       &        &       &\\\hline
Simple          & 1   & 4681   & 1.86  & 2518  & 3.45  & 1355  & 6.27
& 747 \\
100 iters, $100 \times 100$&   &         &       &        &       &        &       &\\\hline
Paraffins       & 1   & 322    & 1.99  & 162   & 3.92  & 82.2  & 7.25  &44.4 \\
n = 22          &     &         &       &        &       &        &       &\\\hline
\end{tabular}
\end{center}
\caption{Speedup Results: Id on Monsoon (taken from \protect{\cite{monsoon-perf93}})}\label{tab:speedup}
\end{figure}

\begin{figure}
\begin{center}
\begin{tabular}{|l|c|c||c|c|}
\hline
Program         & \multicolumn{2}{c||}{MIPS R3000 (25 MHz)}          
                & \multicolumn{2}{c|}{1PE Monsoon (10 MHz)} \\
\cline {2-5}
                & ($\times10^6$ cycles) & seconds 
                & ($\times10^6$ cycles) & seconds \\ 
\hline
\hline
Matrix-Multiply, $500\times 500$        &       & & & \\
\hspace{.25in} double precision         & 1198  & 202.3  & 1768 & 176.8 \\
\hspace{.25in} single precision         &  915  & 153.1  & -- & --\\\hline
$4 \times 4$ Blocked-MM, $500\times 500$ &      & & & \\
\hspace{.25in} double precision         & 954   & 61.4 & 1058 & 105.8 \\
\hspace{.25in} single precision         & 741   & 44.9 & -- & -- \\\hline
Gamteb-2c                               & 265   & 11.1 & 590 & 59.0  \\
\hspace{.25in} 40000 particles          &       & & & \\\hline
Simple, 100 iters, $100\times 100$      &       & & & \\
\hspace{.25in} double precision         & 1787  & 86.5 & 4682 & 468.2 \\
\hspace{.25in} single precision         & 1745  & 84.1 & -- & --\\\hline
Paraffins                               & 102   & 12.0 & 322 & 32.2 \\
\hspace{.25in} n = 22                   &       & & & \\\hline
\end{tabular}
\end{center}
\caption{Performance of Fortran/C on the MIPS R3000 verses Id on 1
processor Monsoon (taken from \protect{\cite{monsoon-perf93}})}\label{tab:mips}
\end{figure}

\subsection{Where Monsoon Succeeded}
Since Monsoon was designed to execute dataflow code, its performance
doing that is excellent.  Monsoon's strengths can be categorized
as follows:

\paragraph{1. Excellent Processor/Network Interface Integration:}
Monsoon is capable of sending a message to the network in a single
instruction.  There are many variations of the send instruction.  The
basic send instruction takes a {\em token} which is a tuple containing
a continuation (instruction pointer and global frame pointer) and a
value.  The message is sent to the specified processor and, when
scheduled, results in the execution of the continuation specified in
the message.  Variants of the send instruction allow us to encode
operations, such as remote fetch, into a single instruction.  For more
complicated continuation manipulation, a specific functional unit
(called the pointer increment unit) is available.  Monsoon's
functional unit and token formation unit were optimized for the
message operations that would be most common in compiled Id code.

\paragraph{2. Implicit Forks:}
In order to expose parallelism to keep its pipelines busy and to
tolerate latency, Monsoon must be able to fork off work.  It does so
by allowing instructions to produce up to two tokens in the last stage
of the pipeline.  This feature allows parallelism to expand quickly,
with little added overhead.  Since only one token can reenter the
pipeline, one token is designated to be inserted into a token queue.
The designation is encoded into the instruction being executed.  

\paragraph{3. Fast Hardware Synchronization:}
Frequent use of cheap messaging and forking requires cheap
synchronization.  Monsoon has specialized hardware support for
synchronization which consists of two components: a few bits of state
(called presence bits) associated with each word of memory and a stage
of the processor pipeline dedicated to synchronization.  Instruction
execution can be made conditional upon the presence bits of a memory
location referenced by the instruction.  Instructions can also alter
the presence bits based on the previous values of these bits.  For
example, if synchronization fails, the presence bits are set and a
{\em bubble} ({\ie} a {\nop}) is sent down the rest of the pipeline.
If synchronization succeeds, the presence bits are cleared and the
operation is continued down the pipeline.  Bubbles affect performance,
but are much more efficient means of synchronization than if the
operation was simulated with a sequence of RISC style instructions.

How instructions react to specific presence bit states and how they
mutate that state can be changed by a system programmer.  Monsoon's
instruction set is modifiable because it uses loadable microcode.  The
microcode is the instruction decode tables for the processor pipeline.
See \cite{Papadopoulos89} for more details.

\paragraph{4. Fast Context Switch:}
Monsoon is able to support very short threads because it is able to
switch contexts very quickly.  Monsoon performs context switching at
two levels.  First, its interleaved pipeline switches context every
cycle, interleaving eight threads at a time, making these context
switches free.  Tokens that produce result tokens are generally
allowed to put one result token back into the pipeline as soon as it
is produced, allowing threading.  If the current thread does not
produce any other tokens, effectively terminating the thread, a token
is taken automatically from the token queue for execution.  Incoming
network tokens are allowed to enter the pipeline at regular intervals,
taking advantage of the fact that there is no cost to do so.

Associated with each of the eight threads is an extremely lightweight
context, consisting of a single accumulator value (the value carried
on the token being processed) and 3 registers.  The second level of
context switching occurs when a thread ends.  If there are useful
values in the registers, they have to be explicitly stored away by the
thread.  This context switch is not free, unlike the cycle-by-cycle
interleaving, but the small context makes the switch very cheap
nevertheless.  Pure dataflow code does not make use of the temporary
registers at all; it uses only single-instruction threads.
While this means that context switching is free, this style of
execution fails to exploit the advantages of state that may
be passed through the registers.

\paragraph{5. Hardware Managed Token Queues:}

Monsoon has hardware managed token queues to store additional tokens
that cannot be executed immediately in the pipeline.  Additional
tokens are produced since an instruction can produce up to two tokens
and only one can reenter the pipeline.  Also, if the pipeline is
completely full, the network is allowed to occasionally interrupt the
processor, forcing the executing token to be pushed onto the token
queue.  There are two queues available which can be accessed in either
FIFO or LIFO mode.

\paragraph{6. Support for Global Shared Memory:}
Global shared memory is supported by split-phase operations which are
implemented by fast messaging, fast context switching, and fast
synchronization.  Split-phase operations are implemented as
specialized send instructions, which automatically set the instruction
pointer to point to the correct handler.  The fast synchronization
mechanism of Monsoon quickly integrates the returned value into the
computation.  Since the messaging and synchronization mechanisms were
designed with split-phase operations in mind, they implement the
necessary functionality very efficiently and are extremely tolerant of
memory latency.

\subsection{Where Monsoon Failed}

Though Monsoon showed that architectures that run dataflow code well
can be built, it has several weaknesses that prevent it from being a
truly practical architecture.  Many of these defects were intended to
simplify implementation and are not fundamental in nature.  The
weaknesses are described below.


\paragraph{Poor Single Threaded Performance:}

Monsoon's single thread performance was poor.  There are two basic
reasons for the poor performance: an interleaved pipeline and a weak
instruction set.  Each is described more fully below.
\begin{itemize}
\item {{\bf Interleaved Pipeline:}}
The latency incurred by any specific thread is eight times the number
of instructions to execute.  Execution of two contiguous instructions
in a thread are separated by 7 cycles where instructions from other
threads can be executed.  If there is sufficient parallelism in the
machine during this time, the overall performance of the machine is
not degraded.  In most programs, however, there are critical sections
where shared resources are accessed.  This happens within the run-time
system, for instance, and can occur in user code as well.  The extra
thread latency can constrict the expansion of parallelism since the
available parallelism is sequentialized through an expanded critical
section.  This problem can increase the total run time of a program.
It can also increase the processor resources and parallelism required
by a program, since 8 threads needs to be active to keep the machine
busy.  

The interleaving used by Monsoon was expedient, as it simplified the
pipeline.  There is no reason why an aggressive implementation could
not have a normal, non-interleaved pipeline and yet have the context
switching capabilities of Monsoon.

\item{{\bf Weak Instruction Set:}}
There are several problems with Monsoon's instruction set, which can
be divided between those that are specific implementation problems
and those that arise out of more fundamental architectural decisions.

Among the implementation problems are Monsoon's instruction encoding,
particularly its memory addressing modes.  These are weak and
inflexible, requiring address computation to be done separately from
reads and requiring indirect reads to take two cycles.  RISC-like
3-address instruction sets are more powerful, as they can specify more
general arguments and more general destinations.  In fact, the
EM-4\cite{sakai89} has exactly that sort of instruction set.  Monsoon
is also capable of such instructions, but its instruction set is
inherently limited in power because the number of registers is very
small (3 per thread), and the local memory is not addressable via
these registers.

A more fundamental problem with the instruction set is the coupling of
both synchronization and data delivery in the form of a token.  This
issue is related to the assumption about the frequency of
synchronization which will be discussed in the next section.  The
immediate effect of this duality of token is that it makes it
difficult for the compiler to perform certain types of optimizations.
For example, if the compiler is able to determine that some
synchronization is redundant, it is some times not able to optimize
these synchronizations out because the data still needs to be
delivered.
\end{itemize}

\paragraph{Optimized for Synchronization:}

Monsoon's architecture was optimized for synchronization.  Most
instructions were expected to synchronize, and thus context switches
were expected to be very frequent.  This assumption justifies the
automatic context switching found in Monsoon, which in turn increases
the amount of necessary synchronization.

Due to both the necessity of forking to exploit instruction-level
parallelism and the interleaved nature of the pipeline,
synchronization is required much more often than would be necessary in
a sequential processor that assumes a sequential instruction stream.
The pure dataflow model also increases the number of forks, and
subsequent synchronizations.  Conventional RISC processors, on the
other hand, exploit instruction level parallelism within a sequential
instruction stream using pipelining and superscalar organization, and
do not require explicit synchronization.  The required coordination is
managed in hardware resulting in a more efficient strategy for
exploiting instruction level parallelism.

Since the synchronization section of the pipeline is tightly coupled to
the execution units of the pipelines, a miss in the matching section
causes a bubble in the execution units.  This bubble degrades
performance; approximately 10\% to 30\% of all cycles executed bubble
the execution units.  The obvious solution of decoupling the matching
section from the execution unit is difficult, however, and can still
result in bubbles, either in the execution units or matching sections.

Moving more towards a model that has better threading support (by
increasing available state) and less support for synchronization would
probably have overall benefits.  If everything is balanced, that is
context switching and synchronization become less frequent as context
switching and synchronization costs go up, there would be no
difference in performance.  The compiler, however, is generally able
to reduce synchronization events when it is allowed to thread an
instruction stream.  This threading will benefit machines optimized
for long threads.


\paragraph{Unrealistic Memory Hierarchy:} 

Another artifact of Monsoon's full custom nature is its memory
hierarchy, which was implemented using fast static RAMs to save on
design time and complexity.  Some argue that the hierarchy is
unrealistic.  One could argue, however, that Monsoon's frame memory,
256 Kwords = 2 MBytes, is {\em smaller} than caches in modern
processors.  Monsoon's frame memory can be considered a cache.  Since
I-structure memory was not cached and resided some 30 cycles away from
the processors, it is clear from our performance studies that
multithreading allows us to tolerate latency reasonably well.

The presence bit pipeline stage, which read-modifies-writes memory on
every cycle is unconventional and may be difficult to build.  Some
modern RISC processors, however, support read-modify-write for byte
writes, proving it may be possible to implement the presence bit stage
in a fast pipeline.  Until an actual high-speed machine is built with
the support we want, it is difficult to say for sure whether
it is an obstacle to high-speed implementation.

\paragraph{Little control over thread scheduling:} In Monsoon,
token scheduling cannot really be controlled by the programmer.  The
token queues are completely hardware managed; software is not
permitted to read or write the token queue.  In general, it is a bad
idea if any significant storage in the machine is not easily
accessible by software.  The compiler can decide which token in a
two-token-producing instruction gets pushed onto the queue, but there
is no way to select the ``best'' token to execute next.  However,
executing a ``bad'' sequence of tokens could dramatically increase
run-time or resource usage of the entire program.  It would be
desirable to have more flexibility in managing the execution order,
such as the ability to examine and reorder the token queues.

\subsection{Pragmatic Issues} 
Since Monsoon is a fully custom processor, it cannot leverage
commercial processor hardware and software efforts, dooming it to
technology generations behind the current state of the art.  While
this is not a technical point, it is nevertheless an overriding
practical consideration.  Most parallel computer builders acknowledge
the need to use a commercial processor, or a commercial processor with
very simple changes, in order to be competitive in performance.  Custom
processors lag behind commercial processors in raw speed (cycle time).

It is difficult to justify the efforts involved in building
experimental machines and software systems if commercially available
sequential machines perform better.  The time spent doing even simple
support software can be substantial; Monsoon's basic software, such as
the microcode generator, client/server software and I/O took huge
amounts of effort, probably well over 10 man years.  Hence, even
though there is a greater possibility of speedup for custom
processors, their cost in terms of hardware and software development
as well as their lower clock speed make them uncompetitive.  Thus, it
was imperative that our next machine be very close to a conventional
processor, allowing us to use the basic support software and requiring
only a custom compiler and run-time system.
