\documentstyle[lcscover,oneinchmargins,12pt]{article}

%% \input /bk/derek/tex/macros
\input macros
\input{acaro-macro}
\input{fig}

% DEFINITIONS FOR ILLUSTRATIONS
% One of the following two lines should be commented out!!
\def\illustrationfileprefix{/bk/derek/research/papers/per/}
%% \def\illustrationfileprefix{/mcrc/u/jamey/perf/}

\setlength{\illuswidth}{\textwidth}
\addtolength{\illuswidth}{-7pt}

\def\illustrationfilesuffix{.ps}

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

\def\floatingillustration#1#2{
   \begin{figure}[htbp]
       {\illustration{#1}
          \caption{\label{#1}
               #2}
        }
    \end{figure}
}
\def\floatingillustrationsize#1#2#3{
   \begin{figure}[htbp]
       {\illustrationx{#3}{#1}
          \caption{\label{#1}
               #2}
        }
    \end{figure}
}

\def\percent#1{#1\%}

\def\hmm{\space{2 em}}

\renewcommand{\thetable}{\Roman{table}}

\begin{document}

\covertitle{Performance Studies of Id on the Monsoon Dataflow System \\}
\title{Performance Studies of Id on the Monsoon Dataflow System \\[2 ex]}
\author{James Hicks, Derek Chiou, Boon Seong Ang, and Arvind}
\coverauthor{James Hicks \\ Derek Chiou \\ Boon Seong Ang \\ Arvind}

\trnumber{CSG Memo 345-3 \\ \small (This supersedes CSG Memo 345-2)}
\researchcredit{%
This report describes research done at the Laboratory for Computer Science of
the Massachusetts Institute of Technology. Funding for the Laboratory is
provided in part by the Advanced Research Projects Agency of the Department
of Defense under the Office of Naval Research contract N00014-89-J-1988.}
\toappear{Journal of Parallel and Distributed Computing,
18(3):273-300, 1993.}

\maketitle
% \tableofcontents


\begin{abstract}

In this paper, we examine the performance of Id, an implicitly
parallel language, on Monsoon, an experimental dataflow machine.  One
of the precepts of our work is that the Id run-time system and
compiled Id programs should run on any number of Monsoon processors
without change.  Our experiments running Id programs on Monsoon show
that speedups of more than seven are easily achieved on eight
processors for most of the applications that we studied.  We explain
the sources of overhead that limit the speedup of each of our
benchmark programs.

We also compare the performance of Id on a single Monsoon processor
with C/Fortran on a DEC Station 5000 (MIPS R3000 processor), to
establish a baseline for the efficiency of Id execution on Monsoon.
We find that the execution of Id programs on one Monsoon processor
takes up to three times as many cycles as the corresponding C or
Fortran programs executing on a MIPS R3000 processor.  We identify the
sources of inefficiency on Monsoon and suggest improvements, where
possible.  In many cases, however, improving single processor
performance will reduce parallel processor performance.

\end{abstract}


\section{Introduction}
\label{sec:intro}
% this is the new intro by Arvind

The Monsoon Dataflow Multiprocessor, built jointly by MIT and Motorola, is
a small shared memory multiprocessor.  The motivation behind building
Monsoon research prototypes was to demonstrate the feasibility of general
purpose parallel computers, suitable for both numerical and symbolic
applications.  Since writing parallel programs is itself a research issue,
an inseparable part of this project was the demonstration of the implicitly
parallel programming language Id, which allows the user to write parallel
programs without worrying about the details of parallelism.  In this paper,
we evaluate the performance of Id programs running on Monsoon.

 Our goal was to show that one could easily write parallel programs in Id
and that these programs would run efficiently on Monsoon.  The first part
of this goal was fairly straightforward.  We took programs written in Id by
various people, and showed that they had parallelism on Monsoon.  It was
easy to determine how much Id programs sped up on one to eight processors,
which was the largest Monsoon configuration constructed.  Since the Monsoon
processor, like the Denelcor HEP~\cite{smith81}, consists of an eight-stage
interleaved pipeline, an 8-processor Monsoon requires at least 64-fold
parallelism to achieve \percent{100} utilization.  Thus, even experiments
on a small 8-processor configuration reveal important issues, such as the
amount of parallelism that programs are able to exploit, contention for
network and processor resources, and to a lesser degree, the issues of work
distribution, load balancing, and data structure distribution.  We have had
considerable experience with speedup studies from our experimentation with
TTDA~\cite{CSGmemo278,arvind88c}.  Not surprisingly, the results in this
area turned out to be very encouraging~--- we easily achieved speedups of
more than 7 on 8 processors for most of the benchmark programs (see
Table~\ref{tab:speedup}).

The second part of the goal~--- showing that Id programs run efficiently on
Monsoon~--- was rather daunting.  We wanted to understand {\em why programs did
not speedup perfectly}, {\em i.e.\/}, by a factor of 8 on 8 processors.
Was the limit on speedup due to a lack of parallelism in the programs?  We
thought that this limitation was highly unlikely because of the
overwhelming evidence to the contrary from the previous experiments on
TTDA.  Did a defect in the architecture or the run-time system 
prevent perfect speedups?  This paper sheds some light on the aspects of
the architecture and the run-time system that limited the achieved
speedups.

Between November, 1990 and September, 1992, we spent a lot of time
tuning the Id compiler and the Id run-time system (RTS) to improve
absolute performance and speedups.  This tuning resulted in
approximately a factor of 3 speed improvement over our first
successful execution of benchmarks on a single processor Monsoon
system (see Table~\ref{tab:1pe}).  The effort deepened our
understanding of some of the short comings of the Monsoon (or perhaps
any pure dataflow) architecture, and also illustrated the inherent
cost of asynchronous execution which underlies our compiling strategy.
It also confirmed some of the well known problems of generating
efficient code from ``non-strict''\footnote{Non-strict: The body of a
procedure can start to execute before all of its arguments have
arrive.} languages like Id. Again, the salient aspects of this effort
are documented in this paper.

Regardless of the speedups we were able to achieve, however, a skeptic
of dataflow architectures would want to know how the Monsoon
architecture compares to commercial architectures, and how Id compares
to C/Fortran.  But there are many obvious difficulties in making such
comparisons.  The development cost of Monsoon, a research project, is
minuscule in comparison with the development cost of commercial
machines.  Consequently it runs at 10 MHz, a clock speed 3 to 5 times
slower than commercial machines from the same time period.  Some
respectable computer architects hold the view that any comparison of
machines with such major differences is meaningless because
implementation limitations determine the architecture of commercial
machines.  We think otherwise~--- we think it is possible to normalize
over implementation technologies up to a point and learn about the
intrinsically good and bad properties of architectures.  The greatest
difficulty in comparing the Monsoon architecture with commercial
machine architectures, however, is not these technology issues but
software.

\floatingillustration{arvinds-cross-product}{Compilation Paths}

Consider the diagram in Figure~\ref{arvinds-cross-product} to
understand the full dimension of our problem.  One needs to run more
or less the same programs on two different machines to compare
performance.  This implies that either Id should be run on some other
parallel machine or some version of Fortran or C should be run on
Monsoon.  Both of these paths pose serious practical problems.  To
begin with, we are not aware of any compiler that takes standard
Fortran or C programs and compiles them for commercial parallel
machines with any success.  (The results published in \cite{Blume92},
for example, shows that poor speedup is achieved for most of the
programs in the Perfect Benchmarks suit when a parallelizing compiler
is used to parallelize the programs for the Alliant/FX80 system.)
Instead, every vendor has its own version of parallel extensions to
Fortran and C which allow a user to express his algorithm for a
particular architecture or a specific configuration of the machine.
In fact, the underlying architecture has such a profound influence on
the way users write parallel programs that the language choice is of
secondary importance.

The development of the data-parallel programming model offers a good
example to illustrate the above point.  The model was developed in the
context of the Connection Machine~\cite{hillis-CACM-article}, and
Thinking Machines provides data-parallel extensions for Fortran and C.
However, data-parallel programming in these extended sequential
languages does not resemble sequential programming except in some
superficial syntactic sense.  It may be possible to develop a set of
benchmark data-parallel programs to evaluate parallel machines from a
data-parallel point of view.  However, such an evaluation would not be
suitable for Monsoon which has very different goals.  The
data-parallel model is not a general-purpose model for parallel
programming, and data-parallel programming remains significantly
harder than sequential programming.  In fact, the difficulty of
writing parallel programs is the {\em raison d'etre\/} for our
approach.

Id, the language we use on Monsoon, is an {\em implicitly parallel}
language~--- the compiler merely exposes the parallelism implicit in
the program.  The programmer is not required to write his program for
a specific machine architecture or configuration.  In fact, to a
degree, the programmer does not even have to be aware of the
parallelism in his program.  Id programs on Monsoon are compiled to be
executed in parallel~--- the same object code runs on any number of
processors.  Id is a high-level declarative (functional) language with
extensions for single assignment data structures (called
I-structures~\cite{arvind87}) and for updateable data structures with
fine-grain synchronization (called
M-structures~\cite{barth91})~\cite{id90}.  Using Id, it may one day be
possible to treat high-level sequential programming as a special case
of parallel programming!

Going back to Figure~\ref{arvinds-cross-product}, another way to
establish the performance of Monsoon was to develop Id compilers for
commercial parallel machines.  Compiling Id for commercial parallel
machines, however, also had problems.  Id-like languages offer
expressivity but generally are difficult to compile efficiently for
systems based on conventional processors.  The non-strictness of Id
makes it easy to generate a multitude of parallel threads\footnote{A
thread is simply a sequential fragment of code, where each instruction
executes after the one before it.} but makes it very hard to
sequentialize these threads for efficient sequential execution (Strict
implicitly parallel languages like Sisal~\cite{Cann92}, on the other
hand, suffer from fewer compilation problems but generally exploit
less parallelism.)  Improper over-sequentialization of threads can
lead to deadlocks, while under-sequentialization of threads leads to
poor performance.  The functional languages community has made very
significant progress in the last few years in compiling non-strict
languages for conventional architectures~\cite{FPCA}.  Compilation of
Id on stock hardware has been pursued by Culler {\em et
al.}~\cite{Schauser91} and Nikhil~\cite{nikhil90}.  Results, however,
are still preliminary.  The initial performance figures of Id on CM-5
as reported by Culler~\cite{culler93}, for example, suggest that Id on
a 64-processor CM-5 may do just about as well as Id on an 8-processor
Monsoon!  Besides the fact that the Id compilers for stock hardware
are still immature and lack many optimizations, such a comparison only
points out that Monsoon has much better support for non-strictness and
parallelism than stock processors; this comparison does not help us
establish a base line performance of Monsoon.

Our final decision was to compare Id running on a single-processor Monsoon
with C or Fortran running on a standard workstation to establish some base
line performance.  Barring hand-tuned assembly code, one cannot get code
more efficient than C and Fortran programs compiled with good compilers for
conventional uniprocessors.  Though the comparison is unfair to us~--- our
software is meant to run in parallel, and thus, has overheads that
sequential C and Fortran implementations do not have~--- it gives us an
idea of the amount of overhead we incur.  We show that Id on Monsoon takes
2 to 3 times as many machine cycles as Fortran/C on MIPS R3000 (see
Table~\ref{tab:mips}), and we analyze the causes of this overhead.

Finally, the reader may wonder how well Fortran or C would run on a single
processor Monsoon.  Running sequential code efficiently was not a goal of
the Monsoon project.  For sequential programming, Monsoon instruction set
may be viewed as a single-accumulator type of instruction set (reminiscent
of the earliest von Neumann machines)~\cite{monsoon-book}.  We did not need
any experimental evidence to show that Monsoon cannot compete with a modern
RISC processor in executing Fortran or C!

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

\subsection{Overview}

%no change here yet

In Section~\ref{sec:monsoon system}, we discuss our execution model for
parallel programs, the Monsoon system, including its hardware and software,
and our implementation of Id on Monsoon.  In Section~\ref{sec:benchs}, we
describe the benchmark programs that we ran to measure performance.  The
source code for these benchmark programs are available upon request to {\tt
jamey@lcs.mit.edu}.  In Section~\ref{sec:monsoon-software}, we discuss the
ways in which the Id compiler and run-time system were improved in order to
get better performance on a single processor Monsoon. In
Section~\ref{sec:speedup}, we discuss the scalability and implicit
parallelism studies, and in Section~\ref{sec:single-processor-section}, we
establish Monsoon's baseline performance by comparing the execution
efficiency of Id running on Monsoon with that of Fortran/C running on a
MIPS~R3000.  We also discuss our comparison methods and rationales.
Finally, in Section~\ref{sec:conclusion}, we present our conclusions and
discuss some strategies for the future.

%******************************************************************
%******************************************************************

\section{Id on Monsoon} 
\label{monsoon} 
\label{sec:monsoon system} 

To understand our results, it is
necessary to understand our parallel execution model, dataflow and
split-phase transactions, the Monsoon architecture, and
the implementation of Id on Monsoon, including the resource management
issues. Each of these topics is discussed in this section.

\subsection{A Parallel Execution Model}
\label{sec:execution-model}

One often thinks of the execution of a high-level language program on
a sequential machine in terms of a {\em stack of activation frames}
and a global {\em heap of objects}.  An activation frame is allocated
when a procedure is called and reclaimed when it terminates. A data
structure resides in the heap if its life-time can be longer than the
procedure activation that creates it.  This model can easily be
generalized for parallel execution by turning the stack of activation
frames into a {\em tree of activation frames}.  A procedure may spawn
multiple procedures or loops in parallel, but the activation frames of
child procedures may not be allocated on a stack because they may
finish in an order unrelated to that in which they were invoked.  When
a procedure finishes, it is guaranteed to be a leaf in the activation
tree because all of its children must already have completed, and
thus, it is safe to remove its frame from the activation tree and
reclaim it for reuse.  This basic parallel execution model is shown in
Figure~\ref{fully-parallel}.

All of the frames (not just the leaves) in the activation tree are
potentially active.  The code associated with each frame will
generally have more than one ``thread'' of execution running
simultaneously.  There are three levels of parallelism to exploit in
this model: processor level, consisting of procedure activations on
separate processors, thread-level, consisting of multiple threads
active on each processor, and instruction-level, consisting of
instructions within a thread.  It is this last type of parallelism
that is exploited by super-scalar processors.  Dataflow computation on
the other hand tries to exploit all three types of parallelism.

\floatingillustrationsize{fully-parallel}{Fully Parallel Execution Model}{6in} 

The reader should note that this execution model has nothing in
particular to do with Id; it should be applicable to parallel
execution of just about any high-level language. However, Id exploits
this model to the fullest.  The non-strictness of Id permits the
execution of a child procedure to begin even before all of its
arguments have been computed. It also allows loops to unfold
dynamically, constrained only by data dependencies. Id, via
I-structures and M-structures, also allows very fine-grain
producer-consumer parallelism between parent and children procedures
and between sibling procedures.  In fact, because of all these
properties, Id tends to expose {\em too much} parallelism, often
exhausting machine resources, especially frame memory, if not
controlled.  A simple way to limit the amount of resources required is
{\em bounded loops}, where a bound is specified to indicate how many
loop iterations can occur in parallel.  Though currently the user must
input the loop bounds either as parameters or by computing them at run
time, we hope to greatly reduce if not eliminate that requirement
using compiler analysis and run-time system support in future.

 The execution model presented above has a natural mapping on shared memory
MIMD machines: the frames reside in the local memory of the processor where
they are assigned to execute, and the heap objects reside in the global
shared memory, which can be accessed from any processor. Since a frame is
accessed only locally, it is straightforward to cache frames. Caching of
heap store, however, raises the usual multiprocessor cache coherence
issues. To exploit parallelism effectively in this model, two architectural
issues~--- memory latency and synchronization~--- have to be
addressed~\cite{two-issues,start}.  Dataflow architectures offer a solution
to these problems as will be discussed in the next section.

Whenever a procedure is invoked, a frame or a set of frames (in case
it is a loop procedure) needs to be allocated. Since the frame store
is tied to processors, distribution of work depends upon how and where
the frame manager allocates frames which cannot migrate.  If the heap
storage has non-uniform access time, then the heap manager can try to
allocate storage to maximize locality.  Thus, the issues of resource
management and load balancing are intimately tied in such a model.

\subsection{Split-Phased Transactions and Dataflow Execution}
\label{sec:deferred}
\label{sec:dataflow}

 Interprocessor communication generally takes much longer than local
communication.  For example, fetching data from a frame usually is much
faster than fetching data from remote memory.  However, a processor may 
hide the latency of a remote request by doing other work while the request
is in progress.  In order for this latency toleration to be successful, the
processor must be able to switch between activities very quickly and it
must be able to deliver a response to the activity that made the request.
Furthermore, the program must have sufficient parallelism for the processor
always to have something to do while a request is in progress.

 In the dataflow model, remote requests are structured as {\em
split-phased\/} transactions so that multiple requests may be in
progress at one time.  An instruction issues a {\em request\/} to the
processor or memory module containing the desired data, and then
executes other instructions which do not depend upon the result of the
request in progress.  The request carries a tag, {\em continuation\/},
indicating the procedure activation and the instruction at which the
computation should be continued when the response arrives.  In our
dataflow model a tag, or {\em context}, is composed of an instruction
pointer (IP), a frame base pointer (FP), and a node number.  Since
responses to requests from a processor can be reordered due to the
network and synchronization, tags are essential to match requests and
responses correctly.

 When processors communicate, they also need to {\em synchronize} to
ensure that valid data is used and to avoid race conditions.  Id
I-structures and M-structures provide high-level semantics for fine
grain synchronization, and can be implemented efficiently by providing
a few {\em presence bits} for each word of
memory~\cite{hiraki87,smith81}.  An I-structure has the property that
a read-request that arrives before the write to that location is {\em
deferred\/} until that element has been written.  A deferred request
can be memorized simply by saving its continuation (the return-tag).
Once the value is present, it can be sent to the requesters using the
saved return-tags~\cite{arvind-nikhil-executing}.  Because of this
synchronization, the latency of a request may be much longer than the
actual network delay.  However, this synchronization allows us to
write deterministic programs, and the split-phased nature of remote
requests allows us to hide the extra latency, given enough parallelism
in the program.

In order for split-phased transactions to be effective in hiding
latency, the overhead of issuing a remote request must be very low.
Most commercial microprocessors have very poor network interfaces, and
can take hundreds of cycles just to put the message, corresponding to
the first-phase of a split-phased memory request, on the network.  On
the other hand, dataflow architectures, including Monsoon,
Sigma-1~\cite{hiraki87}, and EM-4~\cite{Sato92}, have network
interfaces that blend seamlessly with the processor pipeline, and can
produce a message for the network basically every cycle.

On a conventional processor, if some needed data is not available, the
processor must either wait for the data to arrive or switch to another
thread, occasionally polling for the data arrival or waiting for an
interrupt announcing the arrival of the data.  On a parallel computer,
more than one thread may have to be executed while a request is in
progress in order for the processor to stay busy.  This adds the
additional constraint that thread-switching must have low overhead,
and that there must be a mechanism for resuming the execution of a
thread when the required response arrives.  Commercial microprocessors
generally have very large context switching time and expensive
interrupts due to large processor state.  Dataflow architectures solve
these problems by executing all instructions in a data-driven manner,
and by making threads very light weight.  The state of a dataflow
thread is just a single {\em token}: a data value along with its
continuation.  Light-weight threads, together with hardware management
of thread queue, allows threads to be switched in a single cycle!
However, as can be expected, the small state of a thread in a pure
dataflow machines is detrimental to good sequential performance.

For split-phased transactions to work efficiently, the overhead of
synchronizing the response with the consumer must also be very low.
High-performance sequential computers make some use of split-phased
transactions by allowing a load instruction to issue a request, and
continuing execution until an instruction that makes use of the
register that was the target of the load is encountered.  In this case,
synchronization of the response and the consumer is done through the
hardware register scoreboard and is very efficient.  But these systems
typically do not allow load requests to complete out of order. 
Furthermore, these techniques are of little use when the data to be
read may be missing; the requesting task has to release the processor
to avoid deadlocks in case of a synchronizing read~\cite{start}.

Dataflow architectures employ a very general and efficient
synchronization mechanism which is used in all instructions requiring
two operands or instructions waiting for a remote fetch to complete.
In a dataflow machine, in contrast to a von Neumann machine, an
instruction is scheduled for execution when all of its operands are
available.  For example, the expression $(a + b)$ is evaluated when
the values, carried by tokens, for both $a$ and $b$ become available.
The tokens carrying $a$ and $b$ can arrive in arbitrary order, and
therefore whenever a token arrives the processor must check the
availability of its partner. If the partner has not arrived, the token
must be saved until the arrival of the
partner~\cite{arvind-nikhil-executing}. In modern dataflow machines
this type of synchronization is performed using an {\em
explicitly-addressed token store}~\cite{Culler90,sakai89}.  Tokens
synchronize at a compiler ordained offset into an activation frame.
Thus, when a token is processed, only the presence bits of the
specified memory location are examined to see if the token's partner
has already arrived.  When the second token of an add instruction
arrives, the value of the first token is fetched and the addition is
performed.  The result of $(a + b)$ is then packaged into a token and
sent to the instruction or instructions that need it.

This style of execution allows dataflow architectures to exploit all
the parallelism inherent in a particular program modulo system
software and hardware constraints. In the next section, we discuss how
all these mechanisms are implemented in Monsoon.

\subsection{Monsoon Hardware}
\label{sec:hardware}

The largest Monsoon multiprocessor constructed is made up of eight
processing elements (PE) and eight I-structure processors (IS)
connected by a two-stage, packet-switched, butterfly network composed
of $4\times4$ switches.  Each PE in the current implementation runs at
10 MHz, and is capable of processing up to ten million tokens per
second. It has 128 kilowords of instruction memory, where each
instruction word is 32 bits; 256 kilowords of frame memory, where each
data word is 64 bits, plus three presence bits and eight type bits,
the last of which are currently not used. It also has two token queues
which can hold up to 32K tokens each.  (A token is roughly twice the
size of a data word).  The current implementation of Monsoon's
processor has no caches, and thus is implemented using SRAMs
exclusively.

Global memory on Monsoon is implemented with I-structure
processors~\cite{Steele90}.  Access to global memory always occurs
over the network, and every global read or write is a {\it
split-phased} operation. A PE may also access the frame memory of
another PE by sending split-phased requests to that processor.  Global
addresses are interleaved across the IS nodes. Each IS contains 4
megawords of 64-bit data memory with associated presence and type
bits, and is implemented using DRAMs.

The network interface to each node (which is either a PE or an IS) has
a bandwidth of 100 Mbytes per second.  This translates to about four
million tokens per second for each node.  When Monsoon's network is
unloaded, a token takes about 13 cycles to go from one node to
another. Monsoon's network interface is capable of delivering a token
to the network {\em every} cycle, though the network is not capable of
delivering that many tokens at a sustained rate.  Token formation,
that is packaging up the destination and the value, is performed
automatically in most cases.  Though token formation and delivery to
the network interface is extremely efficient, compiled code rarely, if
ever, saturates the network.

\subsubsection{Monsoon's Processing Element}
\label{sec:bubbles}
\label{sec:hazard}
\label{sec:PE}

The Monsoon processor has a 8-stage pipeline as shown in
Figure~\ref{jpdc-monsoon-pipe}. It consists of an instruction fetch
stage, an effective-frame-address computation stage, a presence-bits
operation stage, a frame operation stage, a three stage ALU, and a
form token stage.  The instruction fetch, effective-frame-address, and
ALU stages perform the tasks specified by their names.  The
presence-bits operation stage can read, modify, and write presence
bits in one cycle.  The frame operation stage either reads a value
from a frame, writes a value in a frame, exchanges a value (takes 2
cycles), or does nothing.  The form-token stage generates zero, one,
or two tokens each cycle.

\floatingillustration{jpdc-monsoon-pipe}{Conceptual View of Monsoon's Pipeline}

Tokens are kept in {\em token queues} while waiting to be processed.
Each PE has two token queues one for system tokens and the other for
user tokens.  The system token queue is needed to ensure that some
critical tokens, such as a token to halt the system, can always be
processed.

During each cycle, the processor tries to execute a recirculating
token coming from the bottom of its pipeline.  If no recirculating
token was produced the last cycle, it pops a token from its own token
queues to execute.  Execution results in either zero, one, or two
tokens at the end of the eighth cycle.  These result tokens are
either: (i) circulated to the head of the pipeline; (ii) sent to the
network to be delivered to either another processor's system queue or
an I-structure board; or (iii) enqueued in either the local
processor's system or user token queue, depending on the operation.
If no token is produced, then one is taken from the system or user
queue to be executed next.  If no token is available, then the
processor {\em idles\/} for one cycle.

The eight tokens being processed at any given time are independent of
each other~--- that is, no token in the pipeline could have created
another token that exists in the pipeline at the same time.  This is
so because the ``next'' instruction is not computed until the 8th
cycle of the pipeline, Thus, keeping an eight processor Monsoon busy
(non-idle) requires at least 64-fold parallelism. 

Since Monsoon accepts only one token at a time for processing, the
first token of a 2-input instruction to arrive will cause the
execution unit of the processor to idle.  Since the second token could
not have arrived yet, there is no work for the processor to do, other
than to store away the value from the first token.  This idling of the
execution stages is called a {\em bubble} in the pipeline.  Bubbles
are unavoidable whenever synchronization is implemented as a stage of
a pipelined machine that takes only one token per cycle.

Monsoon can execute a sequential thread of instructions
which are scheduled at every 8th cycle.  Except for the first
instruction, each instruction in this sequence must take only one
input token which comes from the previous instruction in the thread
(via the recirculating path).  Furthermore, each instruction except
the last must be annotated as {\em critical}, which ensures that another
thread cannot enter the original thread's pipeline slot. In the
absence of the critical annotation on an instruction, a network token
can displace the original thread from its pipeline beat.  Such
``critical'' threads are broken by either synchronization points, trap
instructions or split-phased transactions.  An instruction in the
middle of a critical thread can produce two output tokens, but only
one of the output tokens can be critical.  The other token must be
pushed onto the token queue or sent to the network.  Only a restricted
subset of Monsoon's instruction set can be used in critical threads.

To enhance the performance of such critical sequential threads, each
Monsoon processor has eight register sets of three temporary registers
each.  Each register set is associated with one of the eight
interleaved threads.  Registers are not saved or restored implicitly,
and can only be used within an unbroken, {\em critical\/} thread of
instructions.  Currently only RTS code makes use of these registers.
Notice, if a single, sequential thread of computation is executed on
Monsoon, the pipeline utilization would be \percent{12.5}, because
seven of the eight pipeline stages would be idle. Again this $1/n$
utilization will be true for any processor pipeline design with fixed
interleaving and $n$-stages.

It is possible to simulate I-structure operations in the
Monsoon processor's frame memory because it also has presence
bits.  This allows the compiler and the run-time system to allocate some
heap objects locally.  Reading and writing to I-structures located in
processor memory requires the second phase of the split-phased transaction
to be executed on the processor containing the structure.

In addition to join, I-structure and M-structure types of
synchronization, Monsoon supports synchronization through {\em
spin-locks}.  If an instruction attempts to acquire a spin-lock on a
location which is already locked, a token to reexecute the same
instruction is {\em recirculated\/} in the pipeline until the lock is
freed.  Only the frame and heap managers spin-wait, because, if used
improperly, spin-waiting can cause deadlocks.  Eight threads
simultaneously spin-waiting on one processor will cause a live-lock in
the pipeline, because no thread will ever be able to unlock any of the
locations on which they are spinning.  However, spin-waiting in some
instances is much more efficient than M-structure synchronization.


\paragraph{A structural hazard:}

Because of limited board space and resources, Monsoon has a structural
hardware hazard that affects token movement to and from its token
queues and network interface (please refer to
Figure~\ref{pipeline.idraw}).  Essentially, the path from the token
queues to the top of the processor pipeline and the path from the
bottom of the processor pipeline to the network queues are the same
path --- the implementation uses a single bus for both paths.  If an
instruction generates two tokens, one that will recirculate and one
that goes to the network, everything is fine.  On the other hand, if
an instruction generates a single token destined for the network, it
must get a token from the token queues in order to keep the processor
busy.  Since the path to the network is the same as the path from the
token queues, the processor cannot send a message to the network while
pulling-off a token from the token queue.  The network token always
has higher priority for the shared bus, since results from the
pipeline will be lost if the network token is delayed and a token from
the queue is fetched first.  Thus, when an instruction produces a
single token which goes to the network, the pipeline must idle for one
cycle in which the token is delivered to the network interface.  A
token is then read from the token queue in the next cycle, unless the
next instruction in the pipeline also excites the hardware hazard.

The maximum number of idles that can be caused by the hardware
hazard is 50\% of the total cycles, but we have never seen any thing
close to this amount. A similar hazard exists when the network tries to
put a token into a token queue.

Most reads destined for the I-structure processors generated by the Id
compiler create a network token, but no local token, forcing the
structural hazard to insert an idle cycle in the processor pipeline.
We will see the effect of this structural hazard in the statistics
presented later.

\floatingillustration{pipeline.idraw}{Monsoon's Real Pipeline}

\subsubsection{Monsoon's Instrumentation}

Monsoon has hardware instrumentation for performance measurement.
Each processor has 64 statistics counters and each cycle of execution
on Monsoon is accounted for by incrementing one statistics counter.
The decoded instruction specifies the statistics register to be incremented.
In order to account for every cycle of execution time,
idle cycles also increment a statistics counter.

Monsoon's instrumentation also allows us to define between 1 and 64
groups of procedures, where each group is called a {\em color}.
Procedures can either be specified to be in a specific color or to
inherit the color of the procedure that called it.  Statistics for
each color are collected independently; thus, we can generate
statistics divided into separate categories for each procedure group.
More details on Monsoon's instrumentation are available
in~\cite{natarajan92,papadopoulos89a}.

%Although the instruction counts on each processor are exact, the
%resolution of multiprocessor instruction counts is limited.  The
%Monsoon processors are supported by Unix hosts that among other
%things, start and stop each Monsoon processor individually at the
%beginning and end of each run.  This can give rise to a timing skew
%between different processors, which can be up to a second in length.
%During this time, the running processors continue to count idle
%cycles.  In order to reduce the noise in the statistics we gather, we
%try to run problems that take at least a few seconds to run on 8
%processors.
%
For statistics collection, Monsoon's instructions, or rather cycles, are
divided into a small number of categories. We explain these next.

\paragraph{Monsoon Operation Categories:}

The {\em integer\/} and {\em floating-point\/} operation categories
are self-explanatory.  The {\em fetch\/} and {\em store\/} categories
refer only to the cycle in which an instruction issues
remote memory requests. {\em Tag\/} operations are instructions 
that manipulates continuations,
%\footnote{A continuation is made up of an instruction
%pointer, a node number and a frame pointer.} 
such as for sending arguments to and results from a called procedure.
{\em Identity\/} operations include moves (frame fetches and stores),
jumps, forks and joins.  {\em Miscops\/} instructions consist of
control flow, data conversion and control register operations.
The remaining cycles on Monsoon may be classified into 4 categories:
{\em idle cycles\/}, {\em bubbles\/}, {\em second-phase operations} and {\em recirculate cycles\/}.

{\em Idle} cycles occur when the first stage of the pipeline does not get a
token to execute.  They are caused either by empty token queues or by the
hardware hazard that prevents a token from entering the pipeline.

{\em Bubbles}, as described earlier in Section~\ref{sec:bubbles}, are
caused by the arrival of the first token of a dyadic operation.  The
instruction cannot execute until the second token arrives, so the
first value is stored into the frame and the rest of the pipeline does
nothing for this particular token.

{\em Second-phase} cycles are due to the handling of read and write
requests for the I-structures stored in a Monsoon processor's frame memory.
Accesses to these objects cause the second-phase of the instruction also 
to be executed on the Monsoon processor. Normally the second phase executes 
on the I-structure board.

{\em Recirculate\/} cycles are due to the spin-lock instructions.
The cycle in which the instruction acquires the lock is counted as a 
{\em fetch\/} instruction, but all the other cycles are counted as {\em
recirculate\/} cycles.  These cycles, which are devoted to ``busy waiting'',
are like idle cycles.

\subsection{Compiling Id for Monsoon}
\label{sec:compiling-id-for-monsoon}

The Id compiler for Monsoon was created by retargetting the TTDA Id
compiler \cite{traub86a,arvind-nikhil-executing} to generate Monsoon
object code.  Like the TTDA code, each procedure and loop is compiled
into a separate dataflow graph; instances of procedures are connected
together at run-time by {\em dynamic\/} dataflow arcs according to
some calling convention.  The extra step in the Monsoon compiler is
that of assigning a frame for each procedure. A frame is a contiguous
block of memory and has the matching locations used by tokens of a
particular procedure invocation.  (For people familiar with TTDA, a
frame serves the same function as a private waiting-matching store for
a procedure invocation.)  A frame is also used for storing constants
and loop invariants.\footnote{The compiler does not {\em allocate}
frames, it only decides on the structure of the frame template for a
procedure.  The frames are allocated at runtime.}

Code executing on Monsoon is divided into code-blocks corresponding to
procedure bodies or loop iterations.  The compiler may also split a
procedure into several smaller code-blocks to reduce code-block size
or ``inline'' procedures to create larger code-blocks.  All tokens
belonging to the same code-block invocation have the same frame
pointer, which is the base address of the block.  A frame always
resides in the local memory of a single processor, and thus, all
instructions belonging to a code-block invocation are executed on the
PE where the frame is allocated.

The code generator for Monsoon has to satisfy a number of constraints
imposed by the hardware.  For example, instruction fanout is limited
to two in most cases and one in the other cases.  The compiler must
add {\em fanout\/} or {\em fork\/} instructions to explicitly
distribute a value if too many instructions require the output of an
instruction.  The instruction encoding also constrains the location in
instruction memory of a destination instruction relative to its source
instruction.  A destination instruction can be at most 512
instructions away from its source instruction. For instructions that
allow two destinations, one of the destinations is further constrained
to reside at the instruction address immediately following the source
instruction.  In some cases, the compiler must insert {\em jump}
instructions to generate correct code for large procedures or loop
bodies.  The compiler also splits large code-blocks in order to
satisfy this constraint.

%*** cost of additional synch in DF code outweighs benefits of register use ***

Although the Id compiler generates dataflow-style code for Monsoon, it
is also possible to write threaded-style code for Monsoon.  This can
cut down the synchronization cost by eliminating some bubbles.  The
frame manager, for example, makes heavy use of threaded-style coding.
Threaded-code generation requires more analysis and can also make use
of Monsoon's temporary registers. However, Monsoon's instruction set
was optimized for TTDA style code and is not optimal for the threaded
style.  For a discussion of threaded execution model on Monsoon,
see~\cite{papadopoulos91b}.

%----------------------------------------------------------------
% Temporary values can also be stored
%in this frame.  For instance, imperative operations are used to store
%loop-invariants in the frame before any iteration of a loop is
%executed.  Storing loop-invariants directly into the frame allows them
%to be accessed with normal, non-synchronizing reads.

\subsection{Id Run-Time System and Resource Management for Monsoon}
\label{sec:frame-manager}

The run-time system (RTS) for Id consists of a frame manager and a
heap manager.  The frame manager allocates and deallocates the
activation frames in which code-blocks are executed, and the heap
manager allocates and deallocates dynamic storage for tuples, arrays,
and other aggregate objects.  The Id RTS for Monsoon was written from
scratch, and involved considerable research and experimentation.  On
the TTDA emulator, GITA, the Id RTS was faked by passing all the
resource management calls to the underlying Lisp system. The issues of
parallelism, efficiency, contention, the length of the critical
section, etc. were not addressed in the design of the Id RTS for TTDA.
In the following we describe the current resource managers on Monsoon.
Some more discussion of these may be found in
Section~\ref{sec:rts-improvements}.

\subsubsection{Frame Management}

When a procedure $P$ calls a child procedure $C$, the parent procedure
first executes a {\em get-context\/} instruction.  The get-context
instruction traps to an exception handler which allocates a frame,
possibly on another processor and returns a continuation consisting of
the instruction pointer (IP) of procedure C's entry point, and the
node and base pointer of the newly allocated frame~\cite{Chiou92}.  We
sometimes refer to this continuation as a {\em context}.  The frame
manager chooses the processor on which to allocate the frame, so that
the distribution of the work load does not have to be specified in the
compiled code.  The frame manager also colors the child's context for
statistics gathering before returning it to the parent procedure.
Procedure invocation then continues with the parent procedure sending
the required arguments to its child procedure using the context.  Each
argument is directed to a specific instruction by some preset
procedure calling convention.

In order to minimize external fragmentation, only a limited
number of frame sizes are provided.  For each frame requested, the smallest
available frame large enough to satisfy the request is returned.  The
current frame manager has sixteen different frame sizes, each a multiple of
64, and employs a version of the quick-fit algorithm~\cite{quick-fit}.
Each quick-list contains free frames of a specific size, linked
together through the first word of each frame.  

Besides the storage allocation algorithm, a crucial unknown parameter
in the early stages of the frame manager development was the number of 
managers needed for good performance. Should we have one frame manager
for the whole machine, or one for each processor, or have eight (one
for each pipeline beat) per processor?  More resource managers reduce
the contention between frame requests but may suffer from
fragmentation of resources. It is possible for a resource manager to
request resources from another when it runs out of resources, but this
may increase the overhead of processing each request.

After some experimentation, we settled on a single set of quick-lists
per processor.  Since Monsoon has eight-way interleaved pipeline, up
to eight independent frame requests per processor can be active at the
same time, and thus contention is possible.  Chiou investigated frame
managers that have eight sets of resources per processor, and found
that, although these frame managers rarely waited for a critical
resource, they had difficulty sharing resources between the different
sets~\cite{Chiou92}.

For maximum efficiency, the frame allocator is written in
threaded-style in Monsoon assembly language, and uses some
instructions written specifically for the frame manager.

% The total throughput is determined by the length of the
%critical sections in the frame manager code and the contention between
%frame requests running in different pipeline beats on the same
%processor.  

\paragraph{Work Distribution:}

The frame manager is also responsible for partitioning work among the
processors on a code-block granularity.  Currently, the frame manager
distributes work in a round-robin fashion.  Each processor has a set
of round-robin counters, one for each frame size, that it uses to
distribute work to other processors.  Since each processor has its own
round-robin counters, work distribution decisions can be made locally.
Such a distributed approach to load balancing does not ensure a
globally even distribution of work.  However, because many frames are
allocated during the execution of most programs and the amount of work
done in each frame is relatively small, we feel that a round-robin
scheme will balance the load reasonably well.  Our results so far have
supported this intuition.

\subsubsection{Heap Management}

Requests for heap memory, like requests for frame memory, are made by
special instructions which trap to run-time system procedures.  These
run-time system procedures are written in Id.  The same heap manager
code runs on the various configurations of Monsoon.

 The Id run-time system places all aggregate object storage (such as
arrays and tuples) on the I-structure processors.  This storage is
interleaved so that adjacent logical addresses are actually on
different I-structure processors.  Interleaving is used to reduce the
contention on individual I-structure processors and hence the average
latency of access.  As pointed out in Section~\ref{sec:PE},
I-structures can also be allocated in a Monsoon processor's local
memory.  These local I-structures, however, are not interleaved.

 Each processor manages its own partition of I-structure storage in
order to reduce RTS contention and to improve throughput.  The current
heap allocator uses the quick-fit algorithm to manage each partition,
and keeps 15 quick-lists for object sizes of 2 through 16
words.  Larger objects are managed by the first-fit algorithm.
Detailed analyses of various heap allocation algorithms are presented
in Iyengar's thesis~\cite{Iyengar92a}.

 I-structure objects have presence-bits associated with each word.
These presence bits are initially {\em empty\/} on all words of an
object, and are set to {\em full\/} by I-Store operations.  In our
implementation, the presence-bits of a piece of storage are cleared
when that storage is first cut off of the {\em tail} (pool of unused
memory), and then cleared again whenever the storage is returned to
the heap manager for reuse.  The heap manager keeps around storage
that has been cut from the tail rather than returning it to the tail.
Presence bits are cleared upon deallocation in order to minimize the
latency of subsequent allocation requests.

Even though each processor has a heap manager, if too many requests
to allocate or release heap objects come bunched-up together in time,
the heap manager can stil become a temporary bottleneck. We will see
some evidence of this in the statistics presented later.

\subsubsection{Parallelism Control and Resource Management}
\label{sec:parallelism-control}

Our eventual goal is to have both parallelism and storage management
be implicit in Id.  Such an Id program will contain no user
annotations to direct where to exploit parallelism or how to manage
storage.  Unfortunately, our current system has not reached this goal
yet, and the Id compiler and RTS are not able to run a program
efficiently without some user help.  To deal with the current
situation, we have added two kinds of {\em annotations} to programs to
control the amount of parallelism and the amount of resources used by
them.  The first annotation, {\em loop bounds}, which were briefly
introduced in Section \ref{sec:execution-model}, controls how many
iterations of each loop are executed in parallel.  The second
annotation causes heap storage to be reclaimed when it is no longer
needed.  This storage annotation is not discussed in this paper;
the interested reader is referred to~\cite{hicks93a}.

%The use of these annotations are similar in sprit to array distribution directives, and parallel loop constructs in parallel extensions to Fortran.

Currently, the user must specify loops as either {\em sequential,
bounded, or unbounded}.  The compiler generates specific code for each
kind of loop.  A sequential loop executes one iteration at a time and
uses only one frame.  A bounded loop executes a specified number ($k$)
of iterations in parallel, and uses $k$ frames.  $k$ can be computed
at run time but must be greater than or equal to 2.  An unbounded loop
is compiled into a recursive call so all loop iterations can
potentially execute in parallel.  The sequential loop schema incurs
less overhead than the bounded loop, which has to allocate and
initialize more frames. However, it also exploits less parallelism
than a bounded loop. It is usually used for the inner-most loops where
it is more important to achieve smaller instruction counts than
parallelism.  Parallelism is, instead, provided by the outer loops.

 Each iteration of a loop that is executing in parallel consumes a frame
and, perhaps, some heap storage.  By controlling the number of iterations
executing in parallel, one can control how much storage is used.
Generally, the number of iterations executing in parallel must be
large enough to keep the machine busy but small enough not to exceed
the storage available on the machine.  Culler~\cite{culler89} presents
some heuristics for selecting loop bounds.

 Categorizing loops as sequential, bounded or unbounded and
determining how many bounded loop iterations to execute in parallel is
currently perhaps the only tedious part of achieving good performance
on Monsoon.  It is partly due to the relatively small size of
Monsoon's frame memory.  Some prior research has been done in this
area, notably by Culler~\cite{culler89}.  We had not automated this
process as we needed more experience to see what impacts such choices
have on an actual system (Culler's work was done on GITA, a simulator
for TTDA).  We plan to take the results of our studies and of
Culler~\cite{culler89}, and automate this process through a
combination of compiler analysis and run-time mechanisms.  We believe
that this should get us good performance in most cases without user
intervention.


%******************************************************************

\section{The Benchmarks}
\label{benchmark-section}
\label{sec:benchs}

We studied four benchmarks on Monsoon: Matrix-Multiply, Gamteb,
Simple, and Paraffins.  These benchmarks are described in this
section.  Members of the Computation Structures Group (CSG) and
collaborators of CSG have written other applications as well.  We will
not discuss the performance of those applications in this paper.
One of the
largest Id applications currently being developed is a version of the
Id compiler written in Id.  Another is the Monte Carlo Neutron Photon
(MCNP) application being written by our collaborators at Los Alamos
National Laboratory.

 All Id programs described in this document were written in Id90.1
with some annotations for storage deallocation~\cite{id90}.  These
programs are available from the authors upon request.  Our
Matrix-Multiply benchmark was written in Id, C, and Fortran by experts
in each of these languages.  Our two large benchmark programs, Simple
and Gamteb, were originally written in Fortran.  These programs were
ported to Id by programmers familiar with both Id and the
applications.  Paraffins was originally written in Id and was then
ported to C by an expert.

 The following sections describe our benchmarks in great detail.
Readers who are not interested in the details can skip to
Section~\ref{sec:monsoon-software}.

\subsection{Matrix-Multiply}
\label{sec:blocked-mm}

This benchmark creates two matrices of size $n\times n$, multiplies
them, and returns the sum of the elements of the product matrix as its
result.  The matrices contain double-precision floating point
numbers.  The Id version of Matrix-Multiply is written as a
straightforward triply-nested loop.  In early versions of this
benchmark, run before September 1991, the innermost loops of the
matrix creation, multiplication, and summation routines were all
unfolded ten times by the compiler to ameliorate the overhead of loop
iteration.  Compiler improvements since then have reduced the overhead
of loop iteration by a large amount.  We scaled unfolding down to four
times as further unfolding increases code and frame sizes without
providing much improvement in performance.

 The Matrix-Multiply program is invoked by supplying a matrix size $n$ and
several loop bounds.  Our Matrix-Multiply runs are of size 500 by 500.  The
loop bounds control how much parallelism is exposed in the outer loops of
the matrix creation, multiplication, and summation routines.

This benchmark has been coded in C to compare the performance of Id
with the performance of C.  The Id code implementing Matrix-Multiply
is about 130 lines long, including comments.  The corresponding C code
is 152 lines long.

 We also have a version of this benchmark written in both C and Id in
a $4\times4$ blocked style.  This blocked version simultaneously
computes the value of 16 elements that form a $4\times4$ block in the
final matrix.  The net effect is to reduce the number of fetches that
we perform on the two source matrices.  Thus, each time we execute the
innermost loop, we fetch 8 matrix elements, 4 from each source matrix,
and use them to update 16 elements of the product matrix.  The
unblocked version needs 32 fetches to support the same computation.
Blocking in this manner reduces the number of fetches by a factor of
four.  Although the numbers reported here for Id are obtained by
changes to the source code, work is underway to have the compiler
automatically perform this transformation as an optimization.


%%% \subsection{Wavefront}
%%%
%%%  Wavefront is a successive over-relaxation problem that defines a sequence
%%% of matrices $X^{k}$ such that for each iteration $k$, $X^{k+1}$ is defined
%%% in terms of a matrix $X^{k}$, where
%%% $$      X^{k+1}_{i,j} = \frac{X^{k+1}_{i-1,j} + X^{k+1}_{i,j-1} + 
%%%                            X^{k+1}_{i-1,j-1} + X^{k}_{i,j}}{5}
%%% $$
%%%  and $X^{0}$ is given as an initial parameter and $1 \le k < m$.  The $m$th
%%% matrix is returned as a result.
%%%
%%% Wavefront has the property that all of the elements along diagonals of a
%%% matrix may be computed in parallel, as soon as the preceding diagonal has
%%% been computed.  This parallelism is impossible to expose when written in
%%% standard Fortran.  Furthermore, successive relaxations may execute in
%%% parallel.
%%%

\subsection{Gamteb}

Gamteb~\cite{gamteb} statistically simulates the trajectory of particles
(photons) through a carbon rod that is partitioned into cells.  Each
particle is statistically {\em weighted} to emphasize particles that are in
the right-most cells.  Each particle can be simulated in parallel.  Gamteb
was written by researchers from Los Alamos National Laboratories as a
standard supercomputer benchmark derived from MCNP, a real application.

 We have two versions of Gamteb, corresponding to two different rod
geometries.  In the first version, gamteb-2c, which corresponds to the
Fortran benchmark code, the rod is divided into 2 cells with 4 surfaces.
In the second version, gamteb-9c, the rod is divided into 9 cells and 11
surfaces.  The second version is much more computationally intensive than
the first because each particle is split many more times.

  The simulation considers $n$ particles independently, where typical
problem sizes are forty thousand to several million particles.  Particles
enter the simulation through the front surface and may exit the simulation
in one of four ways: {\em escaping\/} through the cylindrical surface, {\em
backscattering\/} through the front surface, {\em transmitting\/} through
the back surface, or {\em dying\/} due to lack of statistical significance.
The result is three histograms of the energies of the particles that
exited, plus counts of particles that underwent various processes.

 This program is storage intensive.  It operates on particles and counts
functionally, so whenever a new particle or count of events is needed, a
new nine-tuple is allocated.  This code has been hand annotated with
storage reclamation pragmas which direct the compiler to insert heap
deallocation calls.

Our Gamteb runs are of forty thousand particles, which is a small but
standard benchmark size.  Real program runs would be in the millions
or tens of millions of particles.  The Id code implementing Gamteb is
about 750 lines long, including comments.  The Fortran code is 720
lines long.

\subsection{Simple}

 This application is a hydrodynamics and heat conduction simulation
program known as the Simple code~\cite{simple}.  The Simple document,
along with the associated Fortran program, was developed as a
benchmark to evaluate various high performance machines and compilers.
Although Simple is supposed to reflect some ``real applications,'' it
is contrived to reflect a more complex mix of numerical methods than
the usual problems in that class.

 Simple uses a Lagrangian formulation of equations to simulate the
behavior of a fluid in a sphere.  To simplify the problem, only a
semi-circular cross-sectional area is considered for simulation.  The
area is divided into parcels by neighboring radial and axial lines.
Each parcel is called a {\em zone}.  The intersection of radial and
axial lines are called {\em nodes}.  In the Lagrangian formulation,
the nodes are mapped onto a two-dimensional logical grid where grid
points have coordinates $(k,l)$ for $k_{min} \le k \le k_{max},
l_{min} \le l \le l_{max}$.  The product, $(k_{max} -
k_{min}+1)\times(l_{max} - l_{min}+1)$, is the {\em grid size} of the
problem.  A parameter of {\em ghost zones} is added around the
rectangular grid to incorporate the appropriate boundary conditions.
For each time step, the simulation computes the following nine
quantities based on the values of these quantities in the previous
time step: the velocity and position of each node; and the area,
volume, density, pressure, artificial viscosity, energy and
temperature of each zone.  Some additional calculations are performed
to compute the size of the time step to be taken and to check the
energy balance.

The simulation is performed a specified number of cycles.  Simple runs
reported here are of 100 cycles with a grid size of $100\times 100$.  The
Id and Fortran codes implementing Simple are about 1000 and 2400 lines
long, respectively.

\subsection{Paraffins}

 The Paraffins benchmark~\cite{paraffins} enumerates all of the
distinct isomers of each paraffin of size up to $n$.  Paraffins are
molecules with chemical formula $\mbox{C}_{n}\mbox{H}_{2n+2}$, where C
and H stand for carbon and hydrogen atoms, respectively, and $n > 0$.
A paraffin is essentially an unrooted 4-ary tree.  Thus the problem of
generating distinct paraffins is the same as the problem of detecting
isomorphism in labeled free trees.  The number of paraffins grows 
exponentially with $n$.

Paraffins is an example of a non-numeric program.  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.

Paraffins runs are of size 22, meaning paraffins up to and including
those of size 22 are generated.  This came up to a total of 3807508
paraffins.  The Id code implementing Paraffins is about 300 lines
long.  The C code is 370 lines long.


%***************************************************************


\section{Monsoon Software Improvements}
\label{sec:monsoon-software}

The software running on Monsoon has improved greatly over the lifetime of
the project, as shown in  Table~\ref{tab:1pe}. The improvement in the
benchmarks' run times is entirely due to improvements in the code generated
by the compiler, and  the implementation of the RTS
(although RTS improvements mostly affected multiprocessor times.)  The
numbers were produced on a single processor Monsoon system.

\begin{table}
\caption{Single Processor Monsoon Performance}\label{tab:1pe}
\begin{center}
\begin{tabular}{|l|r|r|r|r|}
\hline
Program         & Feb, '91 & Aug, '91 & Mar, '92 & Jun, '92\\
                & (hr:min:sec) & (hr:min:sec) & (hr:min:sec) & (hr:min:sec) \\\hline
\hline
Matrix-Multiply ($500\times 500$)       
                        & 4:04    & 3:58    & 3:55    & 2:57 \\\hline
$4 \times 4$ Blocked-MM ($500\times 500$)       
                        & --      & --      & --      & 1:46 \\\hline
Gamteb-9c (40,000 particles)      & 17:13   & 10:42   & 5:36    & --\\
 (1,000,000 particles)            & 7:13:20   & 4:17:14   & 2:36:00    & 2:22:00\\ \hline
Simple  ($100 \times 100$, 1 iteration)
                        & 0:19    & 0:15    & 0:10    & 0:06 \\
  ($100 \times 100$, 1000 iterations)
                        & 4:48:00 & --      & --      & 1:19:49 \\\hline
Paraffins (n=19)        & 0:50    & 0:31    & --      & 0:02.4\\\hline
Paraffins (n=22)        & --      & --      & --      & 0:32.2\\\hline
\end{tabular}
\end{center}
\end{table}

The following sections describe compiler and run-time system improvements.
The casual reader may skip to Section~\ref{sec:speedup} for the
speedup results.

\subsection{Compiler Improvements}
\label{compiler-improvements}

 Over the past year, we made a large effort to improve the Id compiler.  In
addition to general improvements to the quality of the back end, we worked
on a few key areas.

\paragraph{Reducing Heap Allocations:}

Tuples are often used in Id to package multiple values to return to
the calling procedure.  Such tuples are allocated on the heap, though
frequently, they are just initialized by the callee and immediately
read and then discarded by the calling procedure.  We can avoid
allocating heap objects in such cases by passing each of the component
values individually to the calling procedure.  In this way, relatively
expensive heap allocation and deallocation operations are avoided.
While it may seem that passing many values explicitly is expensive,
the original code which allocates and uses a new structure incurs even
more overhead.  This optimization, which is performed automatically,
provided a large part of the improvement in the performance of Simple
and Gamteb seen between the August, '91 and March, '92 columns of
Table~\ref{tab:1pe}.

\paragraph{Improving the Sequential Loop Schema:}
\label{sec:seq-loop-improve}

Sequential loop efficiency has a great impact on the overall
performance of a program because most inner loops are sequential.
Although the iterations of a sequential loop are serialized~--- each
iteration must terminate before the following one may begin~--- the
body of each iteration actually executes in parallel.  Therefore, we
must execute synchronization code at the boundary of each iteration to
guarantee that all the threads executing in each iteration have
terminated before any thread in the next iteration begins execution.
This synchronization code is quite tricky to write. It can also be
quite expensive in terms of execution time, if the compiler does not
perform crucial analysis and optimization.  Interested readers are
referred to~\cite{Ang93} for more details.

  We discovered in early 1991 that our implementation of sequential
loops had a relatively large overhead when the loop body was small and
there was a fair number of ``nextified'' variables.  Matrix-Multiply, for
example, had an innermost loop that took 34 cycles per iteration, more
than half of which were spent ensuring that the sequential loops
executed sequentially.  Out of the 34 cycles, 9 were bubbles, 5 were
fanouts, 5 were gates and joins, 2 were switches. There were only 2
Floating point operations and two fetches from the heap!  Our first
fix was to unroll the loop ten times which increases the useful work
done in each iteration of the unrolled loop while incurring the same
overhead as one iteration of the original loop.  The overhead is thus
amortized over ten iterations.  When unrolled this way,
Matrix-Multiply took an amortized 19 cycles per iteration. This
run-time statistic suggested that the original code incurred a 16
cycle overhead during each iteration.

Unrolling the loop reduced the overhead in terms of cycle counts, but
also increased the frame and code sizes of the loop.  We devised a
much more efficient implementation of sequential loops in August,
1991, which reduces the overhead itself without loop unrolling, and
hence without increasing the frame size.  This new loop schema reduced
the cycle counts for the generic Matrix-Multiply to 19 cycles per
iteration {\em without} any loop unrolling.  This one had only 3
bubbles, 2 fanouts, 1 join and 1 switch while the rest of the
instructions remained the same.  A modest loop unrolling of four times
further reduced this to 16 cycles per iteration.  The overhead of the
new loop schema is 4 cycles compared to the original overhead of 16
cycles.  The improved sequential loop implementation reduced the
running time of both Paraffins and Simple by \percent{6}.


The overhead of sequential loop execution is proportional to the
number of variables that are updated each loop iteration.  This
overhead is significant only when the loop body is small relative to
the number of nextified variables.  Thus, the new sequential loop
schema only shows appreciable improvement if there are small loops in
the code.  This however does not diminish the importance of having
efficient sequential loops as loops with small loop bodies often form
the innermost loops of programs.


%%% This improvement may not seem like much when compared to the 19
%%% cycles/iteration that loop unrolling alone produced.  Loop unrolling
%%% tends to increase not only code size, but also the activation frame size.
%%%  It is therefore desirable to keep the number of times a loop is unrolled
%%% within a small number.
%%%

\paragraph{Lifting Loop Initialization Code:}

 We improved the code generated for loops by adding a compiler
transformation module that lifts the initialization code of inner
loops in a loop nest as far as possible into the outer loops.  Loop
initialization code includes the allocation of frames and the storing
of loop-constants.  This transformation has the greatest impact when
there is a large number of loop-constants and, on each call of the
inner loop, the number of iterations executed is not large.

 Consider, for example, a triply-nested loop where the outer two loops
are executed a large number of times and the innermost loop is
executed only a few iterations each time it is called.  Overall, the
initialization of the inner loop becomes significant since it is
amortized over very few iterations but is executed many times.
Lifting the inner loop initialization out of the outer loops will
reduce run time, especially if there are many loop constants.  Simple
is a program that benefited from this optimization.  Lifting the
initialization as described above reduced Simple's run time by almost
\percent{10}.

\paragraph{Work in Progress:}

Currently, we are augmenting the compiler to automatically perform
{\em blocking}.  The compiler would detect cases where we can reduce
the number of fetches in the body of a loop through a combination of
loop unrolling and loop merging.  The interesting cases are those
involving a loop nest, where the fetches are in the innermost loop,
but the loops that are to be unfolded are the outer loops.  The
blocking transformation merges the inner loops after unfolding the
outer loops of the loop nest.  Matrix-Multiply and some relaxation
codes are examples of programs that take advantage of blocking.  Our
goal is to have the compiler automatically transform the generic
Matrix-Multiply code into the blocked version described in
Section~\ref{sec:blocked-mm}.  This work has not been completed as of
Mar 93.

We have also experimented with allocating I-structure objects with
deterministic lifetimes in frames.  Doing so requires that the heap
object being allocated is small and that the lifetime of the heap
object can be determined at compile time.  Certain versions of the
compiler already have this feature implemented.

%We have reported the generic and blocked
%Matrix-Multiply run time numbers in the first two rows of the ``June, '92''
%column in Table~\ref{tab:1pe}.

\subsection{Run-time System Improvements}
\label{sec:rts-improvements}

 Our early run-time systems processed memory requests with very low
throughput.  Since the frame manager is written in a threaded style, 
the low throughput was caused in part by the eight-way interleaving
of the pipeline.  As mentioned earlier, the interleaving
multiplies the execution time of critical sections by eight since only
one instruction in a particular thread is executed every eight cycles.
In addition, initial RTS implementations used a single free-list which
forced the sequentialization of critical sections.  Increasing throughput
requires either a reduction in the critical sections or an increase in
the number of resource sets or both.

\paragraph{Reducing Critical Section Size:}

An example of the problems encountered when critical sections were
long was discovered when writing this paper.  Matrix-Multiply had a
large percentage of idles. Most of them, but not all, were due to the
hardware hazard.  After some investigation, it was discovered that the
heap manager had unusually long critical sections making it a
bottleneck.  We found that it was locking the heap tail pointer,
allocating the heap object by incrementing the tail pointer, clearing
the presence bits of the newly allocated heap object, {\em then}
unlocking the heap tail pointer.  The heap tail pointer could have
been unlocked right after it was incremented.  After the heap manager
was changed to reduce the critical section, the number of idles
decreased significantly

Paraffins is another benchmark which revealed the weakness of a
low-throughput heap manager.  Paraffins was analyzed after the dismal
runs in February and August 1991.  We discovered that the processor
was 50\% idle, and spent 30\% of the time in heap management, 10\% in
frame management and only 10\% running Paraffins itself.  We further
discovered by looking at the C code that it hardly generated any
garbage, that is, all the allocated storage remained in use through
out. Since the heap manager was not running at the necessary
throughput, we wrote a faster heap manager that did not handle
deallocation of memory.  Furthermore we wrote it in assembly code. (We
used the assembly code heap manager for Matrix-Multiply as well.)

The assembly-coded heap manager starts with a large contiguous chunk
of memory, and cuts memory from one end to satisfy heap allocation
requests.  It takes only three instructions in its critical section.
These three instructions are guaranteed to execute one right after
another. In contrast, the critical section of the general heap manager
written in Id takes at least tens of instructions.  In the worst case,
when the general heap manager has to coalesce the free storage into
larger blocks, the critical section lasts thousands of instructions.
Thus, the throughput of the Id heap manager is often not sufficient
for codes that allocate many heap objects.

\paragraph{Splitting Resources among Managers:}

Splitting resources to create more resource sets can cause poor
utilization of available resources.  Thus, most of our effort has been
directed at reducing critical sections to increase throughput.
Nevertheless, some division of resources are made~--- for instance,
there are several free-lists in each set of resources, and each
processor has its own set of resources for both the frame and the heap
managers.  The frame and heap managers communicate with managers on
other processors, allowing them to share resources.

\input scalability.tex
\input baseline.tex
\input conclusion.tex

\paragraph{Credits:}

The Monsoon project is the result of a large team effort composed of
MIT and Motorola people.  Greg Papadopoulos designed Monsoon and
managed much of its implementation.  Chris Joerg and Andy Boughton
designed the network, while Ken Steele designed the I-structure board.
Motorola built the hardware.  Ken Traub wrote the TTDA Id compiler
while at MIT and then became the Monsoon software architect at
Motorola.  Jamey Hicks became the compiler guru after Ken Traub left
and lead the Monsoon software effort at MIT. Andy Shaw wrote the
original Monsoon back-end for the Id compiler.  Boon Ang improved the
performance of compiled code by hacking the middle and back ends of
the compiler.  Derek Chiou and Arun Iyengar designed and wrote the
frame and the heap managers, respectively.  Mike Beckerle wrote the
MINT simulator and defined the IO software system for Monsoon. R.~Paul
Johnson implemented the I/O substrate, while Christine Flood
implemented the I/O libraries. Christine also wrote the transcendental
libraries.  Peter DeWolf wrote most of the Id World interface and
execution manager.  Venkat Natarajan and Maria Carlon worked on
statistics and visualization.  Maria Carlon wrote the loader.  Gamteb
was written by Olaf Ludbeck of Los Alamos National Laboratory.

\paragraph{Acknowledgements:}

We would like to thank Christine Flood, Shail Aditya, Alejandro Caro,
Paul Barth, Arun Iyengar and Kyoo-Chan Cho for their invaluable
assistance in tuning various programs, in adding storage reclamation
annotations, for run-time system and compiler hacking, and for running
these programs on GITA and Monsoon.

%\bibliographystyle{abbrv}
%\bibliography{abbrevs,jamey}
\bibliographystyle{abbrv}
\bibliography{abbrevs,perf}

\pagebreak
\tableofcontents

\end{document}
