\section{Discussion and Conclusions}
\label{sec:conclusion}

%This paper described performance studies performed on the Monsoon
%system running Id code.  We started with a description of Monsoon and
%Id and discussed software improvements over time.  We then discussed
%our speedup numbers, where speedup was defined as the ratio of the
%critical path of a multiprocessor system to the critical path of a
%single processor system.  We ran with the same object code and
%run-time system for all machine configurations.  We then compared
%Monsoon running Id to a DECStation 5000 running a MIPS R3000 processor
%and optimized C/Fortran code.
%
%We divide this conclusions section into 2 parts: Monsoon performance
%and our future directions.
%

\subsection{Monsoon performance}

Monsoon has proven itself to be an effective parallel architecture,
achieving close to perfect speedups on the applications we ran.  Even
though the largest Monsoon configuration consists of 8 processors,
this configuration actually executes 64 threads in parallel because of
the eight-way pipeline interleaving on each PE.  Few other machines
have had this kind of success in exploiting 64-fold parallelism.

%% improvement of hand-coding: paraffins: 40%
%% improvement of hand-coding: mmt44: 20%

Id also proved to be effective at exposing parallelism inherent in the
ordinary algorithms we used.  The dataflow style code our compiler
generated is pretty efficient, even when compared to MIPS compilers.
Generating better code for Monsoon would require generating threaded
code which would give us at most 15\% to 20\% improvements in speed.
Since the effort to add threading to our compiler would be substantial
and the benefits small, we decided to wait until our next machine to
implement threading.  When we do generate threaded code, we must
consider the impact of long sequential threads on the parallelism
available in a program~--- the scheduling of these long threads, for
example, may have adverse effects on the ease of performing load
balancing.

Monsoon gave us our first real chance to explore run-time systems.  We
found that naive frame management and work distribution strategies
that our RTS uses to be adequate to achieve seven-fold speedups on
eight processors.  We also found that oblivious work distribution
schemes balanced the load well.  Although work distribution is, in
general, a difficult issue, a round-robin scheme works well for us
because work distribution is done at a very fine granularity,
resulting in many distribution decisions.

On the other hand, Monsoon's default instruction set is not geared
towards a threaded style of execution, making the writing of the
run-time system difficult.  Run-time systems have critical sections
that are most efficiently written in threaded code.  Though there are
enough threaded instructions in Monsoon to write a run-time system, a
more suitable instruction set would make the system coding much
easier.  Monsoon also suffers from rather weak addressability.
Three-address instructions will greatly improve code efficiency,
particularly when executing threaded code.  Finally, eight way
interleaving of the pipeline has the disadvantage of making critical
paths and critical sections longer than they need to be.

Our experiments have led us to the conclusion that instruction level
parallelism achieved by explicit fanout and joining is expensive, and
would be better exploited by hardware mechanisms.  We want to
emphasis, however, that superscalar architecture alone will not expose
enough parallelism.  Monica Lam's work~\cite{Lam&Wilson92} shows this
to be the case for a large number of benchmark programs.

On the positive side, our experiments with Monsoon have shown that
fine-grained parallelism, split-phased memory accesses, and fast
context switching can hide memory latency and synchronization waits
when there is sufficient parallelism.  The experiments also verify
that there is sufficient parallelism in most programs.  We reach this
conclusion from the fact that all of the benchmarks ran with very few
idle cycles aside from {\em idles} caused by hardware hazards.

The adoption of split-phased operations for global memory access
allows computation to overlap memory access latency.  This technique,
which has been used in Id implementations for many years, achieves the
memory-latency toleration goal confirmed to be important by
researchers at Stanford~\cite{gharachorloo92}.  The same paper
expressed doubt that hardware techniques for hiding memory-latency are
practical because these techniques dynamically reorder instructions
within a large instruction window.  The use of split-phased
transactions, implemented by a combination of software and hardware,
shows that memory-latency toleration is achievable without a large
investment in hardware.

High network bandwidth and low network latency are crucial to fine
grain parallel execution and must be supported by hardware.
Overlapping computation with communication and synchronization would
be impossible if the processor/network interface was not tightly
integrated.  Monsoon's tight processor-network integration allows
programs to perform frequent communications with very low overhead.
Furthermore, Monsoon's pipeline has a stage for formatting messages
(tokens), so even at the instruction set level Monsoon overlaps
communication and computation.

A single processor Monsoon running Id is still not competitive with a
single RISC processor running C or Fortran code.  Once we move to
multiprocessor systems, however, the overhead we see on a single
processor is spread out over many processors.  Also, more conventional
parallel processors will see much of the overhead that we see since
there is always overhead in generating parallelism and sychronizing
that parallelism.  Monsoon should be very competitive with other
parallel systems in terms of performance and ease of use.

\subsection{Future Work}

One can look at future work in two lights: what we would do if there
were no commercial processor market and what we would do since there is
a commercial market.  The reason for splitting in this fashion is
simple.  Though we have ideas about what should be done to execute our
paradigm efficiently, there is great momentum pushing conventional
processor design forward.  The amount of resources at our disposal is
a very small fraction of what the industry is using to develop their
systems.  Thus, though we are capable of designing systems from
scratch, we would be further ahead in terms of performance and price
if we modified conventional architectures. 

We will first discuss some possibilities for a machine unconstrained
by the forces of the commercial world.  We then focus our attention on
a more feasible system that leverages conventional hardware by adding
novel modifications to a commercial processor.

\subsubsection{No commercial market: Dream machines}

Our experience with Monsoon showed us that fast sychronization and a
fast network are extremely useful to our execution paradigm.
Monsoon's interleaving allowed us to exploit parallelism found in
single procedures and to tolerate branch latencies --- we do not need
delay slots after branches.  Monsoon's multithreading together with
dataflow's ability to expose parallelism allowed us to tolerate
latencies incurred when accessing data through the network.

Monsoon's poor single threaded performance, however, hampered us
greatly when executing code with critical sections (mostly in the
run-time system).  The techniques for combining the benefits of
multi-threading without sacrificing good single thread performance are
already emerging.  Two architectures that further advance dataflow
processsor design are a dynamically interleaved pipeline\cite{koike90}
or two or more pipelines fused together\cite{nishida92}.

Thus, if there were no commercial market, or if we were able to muster
as much resources as a commercial project, we would have gone on to
build a successor to Monsoon that is faster and larger, and which
retains Monsoon's positive features of fast access to the network,
while incorporating both multithreading and good single thread
performance.

%The research aspects of such an endeavor will include the design of
%the memory system, and the 
%
%Building a larger system that allows us to explore higher level of
%parallelism
%


%
%fast sychronization, 
% an ability to interleave and  performance would give us a processor that
%would eliminate many of the problems Monsoon faced.
%

%Dynamically interleaved pipelines allow interleaving to a certain
%point when there are extra threads to be executed.  If there are fewer
%threads than the number of interleaves, the processor will interleave
%only the available threads.  If there is only one thread, the
%processor will execute like a normal RISC pipeline with standard
%hazard detection.  One can imagine a system that will allow a thread
%to specify that it be run in single thread mode to reduce its latency
%and thus its critical section.
%
%Fusing two pipelines and dedicating one pipeline to high priority
%single threaded code is another option.  The high priority pipeline
%always executes the highest priorty code as quickly as possible while
%the second pipeline works away at the problem itself.  This solution
%avoids problems which may arise where some important thread gets stuck
%behind less important ones.  Of course, deciding which threads are
%more important can be difficult.
%
%Either of these solutions will give us the single threaded performance
%that Monsoon lacks and can be built with the advantages of Monsoon.
%Clearly, there are many other possibilites.

\subsubsection{Living in a real world}

Modifying an existing high-speed processor to support another paradigm
is a way to use existing technology to further our own research.  Our
next project does just that.  Our next machine, called *T~\cite{start}
(pronounced ``Start'') and being built in collaboration with Motorola,
will use 88110 processing nodes that have a fast network interface
incorporated as a functional unit on the chip.  While this is not
optimal, it is still very fast.  *T will also have hardware support
for handling continuations.  These are similar to token queues on
Monsoon but are an improvement in that it allows a certain degree of
software control over scheduling.

The architecture of *T was driven in part by observations of
Monsoon's architectural drawbacks.  *T will have good single thread
performance because threads are not interleaved in the processor
pipeline.  This will, among other things, cut down RTS latencies and
RTS critical section bottlenecks.  Furthermore, the *T processor will
be based on a RISC core so threads will be able to make better use of
registers than they could on Monsoon. Plans have been made for a 512
processor *T machine to be build by the end of 1994.

The research potential for *T is enormous.  The available of a large
machine coupled with the fact that software has control over
scheduling allows us to explore scheduling at a level which we have
not been able to before.  *T will have virtual memory and caches,
allowing us to experiment with sophisticated memory systems for parallel
processing.  With a large system, we will be able to develop and run
large real-world applications.




\subsubsection{A Challenge:}

Although the statistics we have gathered only cover a small number of
benchmarks, we believe that the results are extremely promising.  We
have seen good speedups for most of our programs, and have shown that
the amount of overhead to run Id on Monsoon is reasonable.  We have
also demonstrated that the execution times, measured in cycles, of Id
programs are within a small constant factor of those of corresponding
C or Fortran programs.  Finally, our experiments have shown that a
tightly coupled processor and network can support very fine-grained
parallelism and hide communication and synchronization latency.  We
would like to see similar analyses of these applications running on
other parallel machines, so that we can compare different approaches
to achieving parallelism.

We are continuing our work on both the compiler and the run-time
system.  More applications, including several SPEC benchmarks
have been written and are currently being debugged.  We hope to have
more performance numbers in the near future for these programs.
