
%%***************************************************************
%%%
%%% Begin 1pe-comparison.tex
%%%

\section{Establishing the Baseline Performance}
\label{sec:single-processor-section}

In this section, we present and discuss experiments comparing the
execution efficiency of Id on Monsoon with that of Fortran and C on a
MIPS R3000.  Each Fortran program was compiled with the DEC Fortran
({\tt f77}) compiler with full optimization ({\tt -O4}), while the C
programs were compiled using the stock MIPS {\tt cc} compiler with
full optimization ({\tt -O3}).

Since commercial processors do not have hardware support to count the
number of instructions a program executes, we used the {\em pixie\/} tool
for gathering this information on the MIPS R3000 processor.  The R3000
executables were preprocessed by the {\em pixie} program provided by MIPS.
The programs were then run on a DEC Station 5000 which contains an R3000
processor, and the resulting data was processed by the program {\em
pixstats}, which is also provided by MIPS.

 Table~\ref{tab:mips} include both cycle counts and run times for MIPS and
Monsoon runs of each program.  On the MIPS processor, cycle counts are
produced by pixstats, and run times are the sum of user and system times as
measured by the Unix {\em time\/} command.  When using Unix time, the
original binary is run, not the pixie-processed one.  On Monsoon, the total
cycle count is measured by Monsoon's hardware statistics counters, and run
times are calculated by dividing the total cycle count by $10^{7}$, because
Monsoon issues instructions at 10 MHz.  Both sets of cycle counts are in
millions of cycles, while the run times are in seconds.

\begin{table}
\caption{MIPS R3000/Monsoon critical path comparison}\label{tab:mips}
\begin{center}
\begin{tabular}{|l|c|c||c|c|}
\hline
Program         & \multicolumn{2}{c||}{MIPS R3000}          
                & \multicolumn{2}{c|}{1PE Monsoon} \\
\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}
\end{table}

 Our comparison is complicated by the fact that we are comparing two
different systems that include different source languages, compilers,
RTS's and hardware.  Aside from the algorithms, which stay the same,
all the other system components are changed at the same time.  The
rationale of making this study despite the difficulties has been
discussed in Section~\ref{sec:intro}.  In the next section, we will
describe the architectural differences between Monsoon and the MIPS
R3000 and motivate the use of cycle counts as the basis for
comparison.  Section~\ref{sec:rts-diff} describes the differences in
run-time system overheads between Id and C/Fortran.  In
Section~\ref{sec:overhead-contributors}, the remaining overhead is
examined and is shown to come mostly from asynchronous fine grain
parallel execution.

\subsection{Dynamic Cycle Counts as the Basis of Comparison}
%{Monsoon vs MIPS R3000 Architecture}
% We want to use cycle counts for comparison
% why does it make sense if one has clock of 10MHz and other has 25 30
% MHz.
% WE COULD BUILD FASTER MONSOON
% Memory systems only reason not able to push clock.
% cannot in front of I-structure, frame memory (though may )
% split-phase is to tolerate long latency ops.
% word size difference can be accounted for.

% Of course difference in ISA
% frame ops as opposed to registers
% Monsoon not so good for threading, but good for synchronization.
% we will discuss these points later.


\label{sec:pipeline-comparison}

We want to compare architectures, not implementations.  Consequently, we
need to factor out the differences in performance that are artifacts of the
implementations.  The biggest difference between the implementations is the
clock speed.  Monsoon, as mentioned before, runs at 10MHz, while the MIPS
R3000 that we used runs at 25MHz. The two machines have different cycle
times because they are implemented using different technologies~--- Monsoon
is a board-level design and the MIPS R3000 is a VLSI chip set.  We believe,
however, that we could build a Monsoon with clock speeds comparable to the
MIPS processor given the design and manufacturing resources used to build
the MIPS processor.  We account for the different cycle times by collecting
statistics in terms of number of cycles executed in addition to absolute
execution times.

Of course there are obvious and unadjustable differences between the
respective instruction set architectures (ISA).  Monsoon's ISA is good
at synchronization but poor at threaded performance, while the MIPS's
ISA is good at threaded performance but poor at synchronization.  The
MIPS, in executing imperative languages, uses long threads and almost
never synchronizes. Monsoon, on the other hand, runs mostly short
threads and synchronizes frequently in executing compiled Id code. 
Thus, the ISA of two processors is optimized for different purposes. 
We will discuss these differences in greater depth in later sections.

The next few paragraphs explain the architectural differences.  We
compare the pipeline stages of Monsoon and MIPS and suggest ways to
implement the Monsoon processor pipeline stages so that each stage is
no more complex than a MIPS pipeline stage.  We also discuss memory
system differences and word size differences.

\paragraph{Making a Monsoon with a fast clock:}

Comparing cycle counts is fair only if the complexity of a stage of
the Monsoon pipeline is similar to that of a stage of the MIPS R3000's
pipeline.  Looking at Monsoon's pipeline, every stage save the
presence bit stage is similar to a MIPS R3000 pipeline stage.  By
changing the presence bit stage into two stages, we can reduce its
complexity to that of a normal RISC pipeline stage.  Splitting the
presence bit stage into two stages can be done using a dual-ported
cache memory for the presence bits, one read port and one write port.
The first stage of the split stage will read the presence bits while
the second stage of the split stage will write back modified presence
bits. 

This two-ported cache memory is not that complex --- the size of the memory
will increase by no more than 4 times (2 times for the row lines, 2 times
for the column lines) and should run at the same speed, especially if we
take advantage of the fact that we are always writing to the location we
read the cycle before.  Also, since presence bits require only 3 bits per
word, less than 100 kilobytes of this memory is necessary.  It is important
to remember that ``unfamiliar'' does not necessarily mean ``more complex''.
Thus, our processor's pipeline stages are of reasonable complexity compared
to the MIPS R3000.  If compared to modern superscalar pipelines with
extensive hazard detection, our processor is considerably simpler.

\paragraph{Memory System Differences:}

The memory systems on the two machines are very different --- Monsoon has
no virtual memory and uses static RAM for local memory.  It, therefore, has
an advantage in that it does not incur cache miss or page fault overheads.
Monsoon's memory, however, is very small (2 megabytes) which is smaller
than the first-level caches in some modern RISC processors.  Thus,
Monsoon's lack of a cache does not make it an unrealistic machine --- in
reality, Monsoon can be thought of as having a compiler-managed cache, the
frame store, in which compiled code explicitly reads and writes its long
latency main memory, the I-store.  In fact, our fetches from I-structure
memory take approximately 26 cycles in the best case, making fetches to
main memory {\em worse} than most conventional RISC machines.  This method
of split-phase transactions and using parallelism to hide memory latency is
actually extremely effective.  For example, even though the cycle count of
Matrix Multiply on the R3000 is less than the cycle count on Monsoon and
the MIPS clock is 2.5 times faster, the MIPS run time is actually longer
than the Monsoon run time.

Fortunately, pixie-generated statistics do not include cache miss or
page fault overheads, allowing us to completely sidestep this issue.
Memory system support for parallel processing is a very important
issue but is not the subject of this comparison study.  Adding caches
to Monsoon, however, is straightforward since our frames are totally
local and our heap objects are write-once.

\paragraph{Word Size Differences:}

The final architectural difference is that Monsoon is a 64-bit
architecture and the MIPS R3000 is a 32-bit architecture.    This
difference shows up most clearly as the difference between the
execution times for 32-bit and 64-bit floating point arithmetic.  The
MIPS R3000 floating point processor performs 64-bit arithmetic at
almost the same speed as 32-bit arithmetic, but it requires twice as
many cycles to load 64-bit floating point values.  To quantify the
effect of this architectural difference, we ran Matrix-Multiply,
Blocked-MM and Simple on the MIPS R3000 with 32-bit floating point. We
were unable to run Gamteb with 32-bit floating point numbers.  The
resulting execution times are reported in Table~\ref{tab:mips}.
Paraffins does not use floating-point values and is, therefore
unaffected by this difference.


%%% Instead, we extrapolated the effect.  The difference between 32-bit
%%% and 64-bit runs in the case of Matrix-Multiply is due only to the
%%% number of cycles spent doing loads and stores.  It takes twice as many
%%% cycles to perform 64-bit loads and stores as 32-bit ones.  MIPS' FPU
%%% is such that the number of floating point registers available does not
%%% change whether they are used for 32-bit or 64-bit computation.
%%% Sixty-four bit floating point arithmetic takes almost the same number
%%% of cycles as thirty-two bit floating point on the MIPS FPU.  Thus, by
%%% noting the number of word loads and stores in the pixstats output for
%%% Gamteb, we can put a lower-bound on the time it will take Gamteb to
%%% run with single precision.  Based on this, Gamteb on MIPS would have
%%% been at most 20\% faster.
%%%
 
\bigskip

 Having accounted for the discrepancies due to implementation differences,
we can now start the more interesting part of the comparison.  Overall,
Table~\ref{tab:mips} shows that Id programs on Monsoon take about three
times as many cycles to execute as corresponding C or Fortran code on the
MIPS R3000.  While three times as long may seem very large, the same code
supports parallel execution on multiple processors with almost perfect
speedup, as reported in Section~\ref{implicit-parallelism-section}.
Nevertheless, it is important that we understand the source of this
overhead and identify means of improvement.

%%%  There are two ways to compare the Monsoon and RISC processors.  First,
%%% Section~\ref{sec:opmix-compare} compares the dynamic distribution of
%%% instruction opcodes.  While this comparison points out the overheads due to
%%% the instruction set architecture, it does not yield a very good indication
%%% of where we can further improve performance.  Therefore, in
%%% Section~\ref{sec:overhead-contributors} we identify the contributors to
%%% instruction set overhead.
%%%

One immediately apparent source of overhead is the Id run-time system.
Run-time systems supporting parallel computation are by necessity more
complicated and more expensive to run than those supporting sequential
computation.  This overhead is quantified and compared in the next section.
The remaining overhead comes from the style of parallel execution adopted
in Monsoon.  This is examined in Section~\ref{sec:overhead-contributors}.

%In the next two sections, we identify contributors to the overhead of
%execution on Monsoon.  In Section~\ref{sec:opmix-compare}, we compare
%the dynamic distribution of instruction opcodes on the two
%architectures to provide a different perspective of the overhead,
%namely from an instruction set architecture point of view.

\subsection{Accounting for the Differences due to the Id/Fortran-C
Runtime Systems}
% Look at Gamteb.  Normalize for number of particles.  Account for
% Gamteb Fortran heap manager

\label{sec:rts-diff}

The fine grain parallel execution of Id programs demands a more
sophisticated RTS than is found in the implementations of sequential
languages such as C or Fortran running on uniprocessors.  The RTS
overheads incurred by Id on Monsoon will probably be incurred in
other general purpose parallel processing systems as well.

Id activation frames cannot be stack-allocated because more than one child
of a given procedure may be executing at once, and these children may
terminate in an order unrelated to the order in which they were invoked.
The storage management problem for activation frames of arbitrary size that
may be allocated and deallocated in arbitrary order is essentially the same
as the heap management problem and is much more expensive than the stack
allocation of activation frames used for sequential languages.

 Another difference between the Id and Fortran run-time systems is that Id
programs dynamically allocate memory from the heap, while Fortran programs
use statically allocated storage.  The Fortran version of Gamteb explicitly
stack-manages a large block of statically allocated storage.  Part of the
dynamic heap allocation and deallocation overhead incurred by Id programs
is in clearing the presence-bits associated with each word of the storage.
This cost is proportional to the size of the object.

%\begin{table}
%\caption{Frame and heap management overheads on 1 PE Monsoon.}
%\begin{center}
%\begin{tabular}{|l|r|c||r|c||r|c|}
%\hline
%       & \multicolumn{2}{c||}{Frame Management}   
%       & \multicolumn{2}{c||}{Heap Management} 
%       & \multicolumn{2}{c|}{Total RTS} \\
%\cline {2-7}
%          &$\times 10^6$ & \% of total & $\times 10^6$ 
%          & \% of total & $\times 10^6$ & \% of total   \\
%Program   &   cycles    &  cycles  &    cycles   &  cycles &  cycles
%& cycles\\ 
%\hline 
%\hline
%$4 \times 4$ Blocked-MM & -- & -- & -- & --  & 1.03 & 0.10\% \\
%\hline
%Gamteb-2c        & 104.1 & 17.61\% & 78.0 & 13.20\% & 182.1 & 30.85\% \\
%\hline
%%Simple          & 628.7 & 12.59\% & 186.1 & 3.73\% & 814.8 & 16.32\% 
%%\\
%Simple           & 557.1 & 11.90\% & 198.4 & 4.23\% & 755.5 & 16.32\% \\
%\hline
%Paraffins        &   --  &  --  &  --  & --  & 165.8 & 51.45\%   \\
%\hline
%\end{tabular}
%\end{center}
%\label{tab:manager-overhead}
%\end{table}

\begin{table}
\caption{Frame and heap management overheads on 1 PE Monsoon and cost
of similar operations on the R3000.}
\begin{center}
\begin{tabular}{|l|l|r|r||r|r||r|r|}
\hline
\multicolumn{2}{|c|}{} & \multicolumn{2}{c||}{Frame Management}   
                     & \multicolumn{2}{c||}{Heap Management} 
                     & \multicolumn{2}{c|}{Total RTS} \\
\cline {3-8}
\multicolumn{2}{|c|}{Program} 
                     &$\times 10^6$ & \% of total & $\times 10^6$ 
                     & \% of total & $\times 10^6$ & \% of total   \\
\multicolumn{2}{|c|}{}  &   cycles    &  cycles  &    cycles   &
        cycles &  cycles & cycles\\
\hline 
\hline
$4 \times 4$ Blocked-MM & Id & -- & -- & -- & --  & 1.03 & 0.10\% \\
                         & C & .006 & 0.00\% & 0.13 & 0.02\% & 0.136 & 0.02\% \\
% C mmt-44 made 3062 calls.  1504 calls to Malloc, taking .133 million
% instructions. < .1 %
\hline
Gamteb-2c  & Id  & 104.1 & 17.61\% & 78.0 & 13.20\% & 182.1 & 30.85\% \\
           & F77 & 1.63 & 0.62\%   & 0.71 & 0.26\%  & 2.34  & 0.88\% \\
% F Gamteb made .81577 Million calls.  Split 17681 times.
\hline
Simple     & Id  & 557.1 & 11.90\% & 198.4 & 4.23\% & 755.5 & 16.32\% \\
           & F77 & 9.45  & 0.54\%    &  0   &  0\%  &  9.45 &  0.54\% \\
% F Simple made 4.727 Million calls.
\hline
Paraffins  & Id  &   --  &  --      &  --  & --     & 165.8 & 51.45\%   \\
           & C   & 7.62  &  7.47\%  & 49.5 & 48.5\% &  57.12 & 56.0\%    \\
% C Paraffins made 3.81 Million calls.
\hline
\end{tabular}
\end{center}
\label{tab:manager-overhead}
\end{table}

 Table~\ref{tab:manager-overhead} shows the percentage of run time
spent on frame and heap management for each of the benchmarks.  For
Paraffins and Blocked-MM, the frame and heap management overheads are
combined because we used a heap manager coded in Monsoon assembly
code, which prevented us from gathering these statistics separately.
Precise determination of the cost of frame management for C and
Fortran is difficult because these are tightly integrated into user's
code.  We estimate this by noting the number of procedure calls, and
assume that frame management for each call costs two cycles. (One to
increment the stack pointer at the beginning of the call, and another
to decrement it at the end of the call.  We assume that stack overflow
is taken care of by the underlying virtual memory system.)  Heap
management is virtually non existent in the Fortran version of Simple
as heap objects are allocated on the stack.  ``Heap'' space needs to
be allocated for the particles in Gamteb.  We estimate the heap
management overhead for the Fortran Gamteb by multiplying the total
number of particles generated by 4 (load pointer, increment pointer,
test pointer for overflow, store back new pointer.)

 The figures in Table~\ref{tab:manager-overhead} show that RTS
overhead is insignificant for Blocked-MM for both the Id and C code.
This is to be expected as the program allocates only three matrices,
and makes a small number of procedure calls.  The RTS overhead for
Gamteb-2c and Simple are however significant for the Id code, but
negligible for the Fortran code.  In particular, the Id version of
Gamteb-2c spends about 31\% of its cycles in the RTS.

 Paraffins, on the other hand, is intensive in its usage of heap
memory.  This is reflected in the statistics.  The C code performs
heap storage management by calling an optimized routine written by the
programmer.  Both the Id and C allocators use the same heap management
algorithm: start with a large chunk of memory and allocate storage by
incrementing a pointer indicating start of the free region.  The only
difference is that the Id allocator must clear the presence-bits on
the allocated storage, at a cost proportional to the amount of storage
allocated, in addition to performing standard heap management tasks.
Because of this and Monsoon's accumulator style instruction set, the
Id code ends up executing about 3 times as many cycles as the C code
to perform all RTS functions.

 While RTS differences can be significant at times, they do not account
for all of the cycle differences.  To continue our investigation, we
factor out the RTS cost from the run time statistics.  The result is
shown in Table~\ref{tab:no-rts}.  It shows that even if we discount
the frame and heap management overheads, Id code running on Monsoon
still executes more cycles than C or Fortran code on the MIPS system.
In the next section, we explain where the remaining overhead is coming
from.

\begin{table}
\caption{Dynamic Cycle Counts Excluding RTS code.}
\begin{center}
\begin{tabular}{|l|r|r|}
\hline
Program & Monsoon & MIPS R3000 \\ \cline{2-3}
& $\times 10^6$ cycles & $\times 10^6$ cycles \\
\hline \hline
Blocked-MM $500\times500$    & 1057 &  741 \\ \hline
Gamteb-2c (40,000)           &  408 &  263 \\ \hline
Simple ($100\times100$, 100) & 3926 & 1735 \\ \hline
Paraffins (n = 22)           &  156 &   45 \\ \hline
\end{tabular}
\end{center}
\label{tab:no-rts}
\end{table}


\subsection{The Cost of Asynchronous Parallel Execution}
%{Other Factors Contributing to Overhead}
\label{sec:overhead-contributors}
\label{sec:costasynch}

% reorganize to the end.
% bigger intro. explain what kind of instruction overhead is there
% because of parallel compilation.
% may be possible to make a single thread, but you may want to keep it
% as two threads, whenever join bubbles.
% switches, change tag instructions, asynchronous protocols loops,
% producer consumer, i-structures.
% all have overhead, we always incur it during compilation.
% support with numbers.

Asynchronous parallel execution is generally less efficient than
sequential execution in terms of the total amount of work that has to
be done.  There is a considerable amount of overhead involved with
running in an asynchronous fashion on a synchronous machine.  It is
important, however, to understand the overhead of our execution model,
what overhead is avoidable and what is not.  If the overhead is a
small constant and if we can get good speedups from the programs we
write, executing asynchronously would be worth it.

We examine the specific costs caused by asynchronous parallel
execution\cite{CSGmemo278}.  These overheads are incurred by forks and
joins used to spawn and synchronize tasks, tags used to send arguments
to threads, bubbles which are a synchronization cost, running loops in
parallel, termination detection, conditionals, and structure handling.
These overheads, though reducible, are not completely removable
without change to the execution style.  We have not worked to reduce
these overheads because of manpower reasons. In the following we
describe some of these costs.

\paragraph{Forks and Joins:} These instructions explicitly split and
combine computation and are the overhead of spawning tasks and rejoining
tasks. {\em Fork\/} instructions spawn new threads within the same frame
and consequently, on the same processor, while {\em join\/} instructions
can join data arriving from any processor.  When code executes in parallel
towards a common goal, work must be spawned to keep processors busy and
results must be joined to share the computation\footnote{Though SIMD or
data parallel machines do not do ``spawn'' tasks they must perform barrier
synchronizations which are also expensive.}.  Spawning and joining threads
is necessary to run a program in parallel but completely unnecessary to run
one sequentially since there is only one thread for the whole computation
and operations produce results in the order in which they are specified in
the instruction stream\footnote{Modern RISC processors can produce results
out of order, but use complicated hardware mechanisms to insure that it
{\em seems} like everything is executing in order.}.

%Even when we are just spawning another thread on the
%local processor, the ``pure'' dataflow style of execution requires
%fork/fanout instructions to supply data to the new thread. 

\paragraph{Tag:} 
The cost of spawning threads depends upon whether we are spawning to
another processor or to the local processor.  In the former case, send
instructions are needed for sending arguments and results between the
cooperating processors and are not required in conventional sequential
execution.  Though one may argue that sequential procedure calling
conventions may require some data movement akin to tag operations, tag
operations involve movement of data across the network and are thus
more expensive.

\paragraph{Bubbles:}  These represent the cost of synchronization
in collecting arguments to start a thread. Our compiler performs most
dyadic operations in a ``dataflow'' style which produce a bubble for
each useful operation.  Dyadic instructions are heavily used
throughout our compiled code and include arithmetic instructions,
switches to control dataflow through a conditional, loop protocols,
and producer/consumer parallelism using I-structures and deferred
reads.  The code our compiler generates allows computation to progress
as much as possible given the available data, but requires very
frequent synchronization, incurring bubbles in the process.  Using
threaded code will reduce the number of bubbles, but not eliminate
them since there will still be synchronization when entering a thread.

\paragraph{Parallel loops:} Such loops can execute each iteration of 
the loop on a potentially different processor.  This requires sending
data from one iteration of the loop to the next over the network.
Like sending arguments to a thread spawned on another processor, this
is expensive not only in terms of having to send the arguments and
results, but also in synchronizing the data.  We also use sequential
loops in our programs, particularly in the innermost loops.  As
mentioned in Section~\ref{sec:seq-loop-improve}, asynchronous
execution within each loop iteration incurs the overhead of
synchronization at the end of each iteration.

\paragraph{Termination signals:} Termination signals are needed in an Id
implementation to indicate that all side-effecting operations in a basic
block have completed, so that  frame or heap objects may be
reclaimed.    Termination detection for $n$ threads is achieved through
an $n$ way join, at a cost proportional to $n$.
Termination detection costs are not incurred in normal
sequential languages because we know that a side-effect is completed by the
execution of the instruction sequence.  Termination signals are different
from joins in that only the presence of the tokens are used, not the values
carried by the tokens.


%%% *** Shouldn't termination signal be included in Joins? ***

\paragraph{Conditionals:} Conditionals in data-driven execution must 
direct data to the code of the correct arm of the conditional, and
require a {\em switch} instruction for every free variable that is
needed in the conditional.  A {\em switch} instruction takes two
inputs, the value to be switched and a predicate, and has two possible
output destinations corresponding to the ``then'' and ``else'' parts
of the conditional.  The number of switch instructions in a
conditional is equal to the number of free values used in the
conditional.  A conventional implementation of a conditional, on the
other hand, executes a single branch instruction regardless of the
number of free variables in the conditional.  All the free variables
are carried either on the stack or in registers.  The overhead of
using {\em switch} instructions is significant in the heap manager
written in Id.  In addition, part of the overhead of loops in Id on
Monsoon is the {\em switch} instructions used to circulate values from
one iteration to the next.

\paragraph{Split-phase heap requests:} These also cost more than
normal memory reads.  At least two instructions are executed to make a
I-structure request --- one instruction to make the request and
another to actually do the read/write.  Even more instructions are
executed if the read is deferred. 

\paragraph{Fine Grain Synchronization with Presence bits:}
While the use of presence bits help fine grain synchronization,
particularly between producer and consumer, it incurs the cost of
clearing the presence bits before a heap object is allocated.  This
cost can be significant as it is proportional to the size of the
object. 

Our compiler produces code to expose maximum parallelism.  It would be more
efficient to expand the parallelism just enough so that the cost of
exploiting the exposed parallelism is no more than the gain obtainable from
running in parallel --- however, achieving this precise balance is very
difficult.  We only allow dynamic control over parallelism via loop bounds,
and but otherwise pay the parallelism overhead throughout the compiled
code.

By paying the price of asynchronous parallel execution, however, we
are able to obtain parallelism from a wide range of programs,
particularly programs with complicated control structures.  In
addition, we can fairly easily simulate code written in a synchronous
style with good efficiency\cite{Shaw93}.  Due to the overheads
involved with general asynchronous code, however, we expect Id code,
even without RTS cycles, to require more run time than C/Fortran code
running the same program.  This fact is obvious from
Table~\ref{tab:no-rts} which gives execution cycle times with the RTS
cycles removed. Our higher run times are caused by the non-strictness
of Id, the parallel code our compiler generates as well as
architectural constraints that make certain operations harder to
perform on Monsoon.


%%**********Radical reorganization after this point **************


Next we attempt to quantitatively estimate the cost of parallel
execution.  We do so by examining the dynamic opcode mixes and
analyzing some samples of compiled codes. Though such analyses can be
carried out for each benchmark with some degree of accuracy, it is
difficult to generalize across benchmarks.

\subsubsection{Dynamic Opcode-Distributions}
\label{sec:opmix-compare}

\begin{table}
\caption{Dynamic Opmix of Execution on Monsoon}
\begin{center}
\begin{tabular}{|l|r|r||r|r||r|r||r|r|}
\hline
%\hfill Program & \multicolumn{2}{c||}{$4 \times 4$ Blocked}
% & \multicolumn{2}{c||}{} & \multicolumn{2}{c||}{} & \multicolumn{2}{c|}{} \\
\hfill Program & \multicolumn{2}{c||}{$4 \times 4$ Blocked-MM} &
\multicolumn{2}{c||}{Gamteb-2c}
& \multicolumn{2}{c||}{Simple}
& \multicolumn{2}{c|}{Paraffins}\\ \cline {2-9}
& $\times10^6$ & \% of  & $\times10^6$ & \% of  
& $\times10^6$ & \% of  & $\times10^6$ & \% of  \\ 
Op category & cycles & total & cycles & total & cycles & total & cycles & total \\ \hline
\hline
Intop & 77 & 7.28\% & 48 & 8.05\%     & 591 & 12.63\% & 77 & 24.01\% \\ \hline 
Floatop & 250 & 23.66\% & 40 & 6.84\% & 335 & 7.15\% & 0 & 0.00\% \\ \hline 
Fetch & 63 & 5.93\% & 28 & 4.68\%     & 400 & 8.54\% & 16 & 4.85\% \\ \hline 
Store & 2 & 0.14\% & 13 & 2.26\%      & 79 & 1.69\% & 50 & 15.46\% \\ \hline 
Identity & 289 & 27.36\% & 172 & 29.06\%   & 1194 & 25.51\% & 74 & 22.85\% \\ \hline 
Tag & 1 & 0.05\% & 44 & 7.39\%        & 265 & 5.67\% & 16 & 4.97\% \\ \hline 
Others & 8 & 0.72\% & 112 & 18.91\%   & 429 & 9.17\% & 47 & 14.56\% \\ \hline 
\hline
Bubble & 269 & 25.45\% & 119 & 20.19\%   & 937 & 20.02\% & 33 & 10.36\% \\ \hline 
\hline
Idles & 100 & 9.41\% & 15 & 2.62\%    & 451 & 9.63\% & 9 & 2.94\% \\\hline 
\hline
Total & 1058 & 100\% & 590 & 100\% & 4682 & 100\% & 322 & 100\% \\
\hline 
\end{tabular}
\end{center}
\label{tab:monsoon-1pe-opmix}


\caption{Dynamic Opmix of Execution on MIPS R3000}
\begin{center}
\begin{tabular}{|l|r|r||r|r||r|r||r|r|}
\hline
%\hfill Program & \multicolumn{2}{c||}{$4 \times 4$ Blocked}
% & \multicolumn{2}{c||}{} & \multicolumn{2}{c||}{} & \multicolumn{2}{c|}{} \\
\hfill Program & \multicolumn{2}{c||}{$4 \times 4$ Blocked-MM} &
\multicolumn{2}{c||}{Gamteb-2c}
& \multicolumn{2}{c||}{Simple}
& \multicolumn{2}{c|}{Paraffins}\\ \cline {2-9}
& $\times10^6$ & \% of  & $\times10^6$ & \% of  
& $\times10^6$ & \% of  & $\times10^6$ & \% of  \\ 
Op category & cycles & total & cycles & total & cycles & total & cycles & total \\ \hline
\hline
Intop & 57 & 7.65\% & 25 & 9.51\% & 316 & 18.09\% & 37 & 36.33\% \\ \hline 
Floatop & 250 & 33.77\% & 60 & 22.74\% & 426 & 24.43\% & 0 & 0.00\% \\ \hline 
Load & 150 & 20.19\% & 65 & 24.39\% & 291 & 16.70\% & 21 & 20.58\% \\ \hline 
Store & 79 & 10.66\% & 35 & 13.21\% & 131 & 7.52\% & 29 & 27.97\% \\ \hline 
Branch & 9 & 1.21\% & 15 & 5.54\% & 73 & 4.16\% & 8 & 7.54\% \\ \hline 
Jump & 0 & 0.00\% & 0 & 0.06\% & 10 & 0.55\% & 8 & 7.44\% \\ \hline 
\hline
Nop & 1 & 0.15\% & 17 & 6.59\% & 118 & 6.75\% & 0 & 0.14\% \\ \hline 
Interlock & 195 & 26.36\% & 47 & 17.95\% & 381 & 21.80\% & 0 & 0.00\% \\ \hline 
\hline
Total & 741 & 100\% & 265 & 100\% & 1745 & 100\% & 102 & 100\% \\ \hline 
\end{tabular}
\end{center}
\label{tab:mips-opmix}
\end{table}

Tables~\ref{tab:monsoon-1pe-opmix} and \ref{tab:mips-opmix} show the
dynamic distribution of instructions on a 1-PE Monsoon and the MIPS
{R3000} respectively.  We show statistics from single-precision runs
for the MIPS {R3000} where possible.  These opcode categories were chosen 
for a reason but in retrospect, we wish we had categorized the operations
differently.

{\em Intop} and {\em Floatop} are the same on both machines.  {\em Fetch}
and {\em Store} instructions on Monsoon are only used for accesses to
I-structures, while on the MIPS architecture {\em Load} and {\em Store}
instructions are used to access both the frame and the heap stores. The
instructions to move data in and out of frame memory on Monsoon are
included in the {\em Identity} instructions.  {\em Identity} instructions
on Monsoon are however used in other ways too: as {\em forks} and {\em
joins}, and {\em jumps} instructions.  The {\em Others} category contains
{\em switches}, data conversion and the SVC instructions used to invoke the
RTS.  Finally, there are instructions which are ``penalties'' when we are
not able to exploit as much parallelism as the hardware is meant to handle.
{\em Idle} cycles on Monsoon correspond roughly to {\em Nop} and {\em
Interlock} cycles on the {R3000}.  Interestingly, the {R3000} incurs a
substantial number of {\em Nop} and {\em Interlock} cycles when floating
point operations are involved.  In 3 out of 4 of our benchmarks 25\% of
cycles on {R3000} are used up in these penalties.  We will use the {R3000}
numbers after subtracting {\em Nop}s and interlocks as an estimate of base
line work on a sequential machine.

{\em Bubbles}, {\em Tag}, {\em Others} are all operations that are
identified as the overheads of asynchronous execution in the previous
section.  In addition, all of the {\em identity} instructions except those
used as conventional {\em move} instructions are additional costs of
asynchronous execution.  The total number of cycles spent in these
categories gives us a quantitative indication of the cost of asynchronous
execution.  Unfortunately, the Monsoon instruction set normally collects
the number of all types of {\em Identity\/} instructions, including {\em
moves\/}, in a single statistics category.  Also, as can be seen in
Table~\ref{tab:monsoon-1pe-opmix}, {\em Identity} instructions account for
the largest numbers of cycles executed in almost every program.  Thus, in
order to accurately measure the costs of asynchronous execution, we must be
able to measure the {\em moves\/} separately from the other {\em
identities\/}.

So far, we have done that only for Gamteb-2c.  The initial analysis shows
that the 29\% of total processor cycles spent executing {\em identities} is
subdivided into: (i) 5\% dataflow synchronization ({\em Joins}) overhead;
(ii) 15\% dataflow-style {\em Fanouts}, (iii) 3\% architecturally-imposed
{\em Jump} instructions, and (iv) 11\% conventional {\em Move}
instructions.  If we assume that this subdivision of the {\em identity}
cycles in Gamteb-2c is representative, {\em i.e.\/}, that approximately 1/3
of all identities are conventional {\em moves} as opposed to asynchronous
execution overhead, the cost of asynchronous execution works out to be
44\% for Blocked-MM, 66\% for Gamteb-2c, 52\% for Simple and 45\% for
Paraffins.  Overall, it looks like about 1/2 of the cycles executed on
Monsoon are overheads of asynchronous execution.

%%%% calculations
%% 25.45 + .72 + .05 + 2/3* 27.36 for B-MM = 44.46
%% 20.19 + 18.91 + 7.39 + 2/3*29.06 for Gamteb = 65.86
%% 20.02 + 9.17 + 5.67 + 2/3*25.51 for Simple = 51.87
%% 10.36 + 14.56 + 4.97 + 2/3* 22.85 for Paraffins = 45.12

The overhead incurred by parallel execution is reasonably high, increasing
total run time by up to a factor of 2.  The speedups seen, however, seem to
indicate that we can about eight times faster for many programs.  Thus, the
overhead cost is dwarfed by the observed and potential speedups and makes
viable the asynchronous parallel execution model which we call dataflow.

One last question that we studied is whether there are ways of
lowering the overhead of asynchronous parallel execution while
preserving most of its benefits.  In particular, we studied the
effects of threading on Paraffins and Blocked-MM.  Each of these
benchmarks has an inner loop which dominates the run time.  Our study
involves hand-coding the inner loop in a threaded style.  

In the case of Paraffins, the compiled Id code for the inner loop took 35
cycles per iteration to execute on Monsoon.  The corresponding loop from
the C program executed in 14 cycles per iteration on the MIPS processor.
The hand-coded Monsoon version, written in threaded style, took 21 cycles
per iteration.  A threading Id compiler should be able to produce the same
code for the inner loop.  Comparison of this hand-coded inner loop with our
current compiled code shows that the 14 cycles overhead in the compiled
code comes from: fanout and join instructions, and sequential loop
overhead, all of which are the costs of highly asynchronous execution.

Blocked-MM with hand-coded inner loop ran about 20\% faster faster
than the compiled version, executing in 814 million cycles.  This
execution time compares very favorably to that of the C code executing
on MIPS listed in Table~\ref{tab:mips}, which is 954 million cycles.
Again, we see that threading can decrease the overhead of asynchronous
parallel execution.  However, the effect of threading on parallelism
has not been fully explored.  We will be exploring this issue in the
future. 

%%
%%This demonstrates not only that threading can decrease the overhead of
%%asynchronous parallel execution, but if done correctly, it can
%%preserve much of the parallelism as well.  
%%
%%
%%********
%%
%%Most of this explanation should not be here. It should be briefly mentioned 
%%in section 2 if it is already not there.
%%
%%both the bubble cycle and the cycle producing a token.  The Join category
%%also includes 8-way Join instructions that take 8 input tokens and produce
%%one output token.  Fanout (or Fork) instructions take one input token and
%%copy its value onto two output tokens.  Join and Fanout instructions are
%%overhead due to our dataflow compilation strategy.  If the Id compiler
%%generated threaded code, the number of Joins and Fanouts would be
%%reduced.
%%
%% Jump instructions are only used on Monsoon when an
%%instruction can send a token only to an the successive instruction in
%%instruction memory due to instruction encoding constraints, but
%%needs to send a token to another instruction.  A Jump instruction will
%%be placed after the constrained source instruction to reroute the
%%token to the desired destination.  Long-Jump instructions allow a
%%token to be sent to a destination that is more than 512 locations away
%%from the source instruction.  Both Jump and Long-Jump instructions are
%%overhead due to constraints imposed by Monsoon's implementation.
%%
%%End of deletions.
%%
%%**********
%%
%%--------------------------
%%
%%I am neutral about including table giving identities. It won't add much
%%over this info.
%%
%%-------------------------
%%
%%******* Guys,  now pull out as much as you can from the dynamic opcode mix
%%about the parallel execution overhead and support it further by 
%%analysis of the compiled code.
%%
%%---------------------------
%
%To help us gain a better understanding
%about the overhead, we examined the object code of Paraffins and
%Blocked-MM.  We chose these two pieces of code partly because they
%were easy to analyze, but more importantly because they represent the
%extremes of the efficiency of Id code compared to C code.  We will try
%to differentiate the cycles that pay for the inherent costs of running
%in parallel from the code that actually performs the desired
%computation.
%
%%\subsubsection{Detailed Analysis of Gamteb}
%%
%%[gamteb-2c splits 17681 times on MIPS, but only 13355 times on Monsoon]
%%
%%[SQRT implemented as instruction on Monsoon, but as procedure on
%%MIPS]
%
%\subsubsection{Case Study 1: Paraffins}
%
%In Paraffins, two procedures account for almost all the cycles
%executed in Paraffins.  These procedures are the heap allocation
%routine and {\tt CCP\_generator}, which generates all of the
%carbon-centered paraffins.  The heap manager was discussed in the
%previous section.  We will examine examine {\tt CCP\_generator} which
%consists of a nest of loops seven levels deep.  Most of the time is
%spent in the innermost loop, where two heap objects are allocated and
%initialized each iteration.  The compiled Id code for this loop takes
%35 cycles per iteration to execute on Monsoon.  The corresponding loop
%from the C program executes in 14 cycles per iteration on the MIPS
%processor.  These cycle counts exclude the cost of heap allocation.
%
%To study the overhead imposed by the pure dataflow style of
%compilation/execution, we hand-coded the innermost loop in {\sc
%Monasm}.  This hand-coded version, written in threaded style, takes 21
%cycles per iteration.  A threading Id compiler should be able to
%produce the same code for the inner loop.  Comparison of this
%hand-coded inner loop with our current compiled code shows that the 14
%cycles overhead in the compiled code comes from the following sources:
%\begin{itemize}
%\item{}
%  fanout instructions, which distribute values and trigger other operations
%\item{}
%  join instructions, which detect completion of other operations
%\item{}
%  sequential loop overhead
%\end{itemize}
%Adopting a threading style of compilation would reduce the above
%overhead.  In threaded code, values are written to frame slots and
%fanouts are replaced by references to these frame slots.  Join
%instructions are not required within a thread because synchronization
%within a thread is implicit in the scheduling of instructions within a
%thread.  (They are however still needed between threads.)  Finally,
%sequential loop overhead is reduced in the threaded implementation
%because only one control thread iterates, so only one branch
%instruction is needed.
%
%% By paying this overhead, the currently code has more parallelism in
%%each iteration of the inner loop and the critical path is much
%%shorter.  What we see here is that spawning off parallel thread and
%%then joining them again cost us overhead cycles.  A good compilation
%%strategy is somewhere between the two extremes, with overhead paid
%%only in cases where the parallelism gain is worthwhile.
%%%Section~\ref{?} talks more about the possibility of exploiting fine
%%%grain parallelism without paying overhead.
%%
%% The remaining difference of five cycles between the hand-coded {\sc
%%Monasm} version of the inner loop and the C inner loop is due to
%%Monsoon's accumulator style instruction set, which makes it necessary
%%to perform explicit store and load instructions to spill the
%%accumulator value.  Monsoon's temporary registers do not help in this
%%case because the thread is divided by a split-phased transaction~---
%%if the temporary registers were used, they would have to be saved and
%%restored explicitly.  The cost of spilling and restoring the
%%accumulator on Monsoon is an architectural overhead.  However, similar
%%overhead will exist in any general register architecture that executes
%%threaded code with short threads.
%%
%\subsubsection{Case Study 2: Blocked-MM} 
%
%Blocked-MM spends nearly all of its execution time in the inner loop
%which computes the inner-product of a row and column.  To determine
%the overhead of our compilation strategy, we hand-coded the inner loop
%in {\sc Monasm} to produce threaded code.  Using the hand-coded inner
%loop, Blocked-MM runs about 20\% faster, executing in 814 million
%cycles.  This execution time compares very favorably to that of the C
%code executing on MIPS listed in Table~\ref{tab:mips}, which is 954
%million cycles.
%
% The hand-compiled Id code on Monsoon is about as efficient as
%compiled C code on MIPS.  Given the performance of the other Id
%benchmarks relative to the corresponding C programs, this result is
%somewhat surprising.  When we examine the MIPS object code, we find
%that the $4 \times 4$ Blocked-MM requires more floating point
%registers than are available on the R3000.  Only six of the 16
%floating point values being accumulated in the inner loop can be kept
%in registers, so the other ten must be loaded and stored each
%iteration.  This code resembles the Monsoon object code for the same
%loop, which also loads and stores these values each iteration.  The
%RISC processor has lost some of its advantage because the state
%required by the inner loop does not fit in registers.  We also tried
%unblocked, $2 \times 2$ Blocked-MM, and $3 \times 3$ Blocked-MM on the
%MIPS processor, and found that the $3 \times 3$ Blocked-MM performed
%best, because it achieved the best balance between
%reducing the number of loads and reducing register spillage.  The $3
%\times 3$ Blocked-MM written in C executed 620 million cycles for
%single-precision arithmetic and 803 million cycles for
%double-precision arithmetic on the MIPS R3000.  The $3 \times 3$
%blocked-MM written in Id ran in 1099 million cycles on Monsoon.
%
% The difference between the cycle counts of the double and single precision
%versions of Blocked-MM in C is due only to the difference in the size of
%data that has to be loaded and stored.  The double-precision version
%executes more load and store instructions than the single-precision version
%because it must move twice as much data.  Performing double-precision
%arithmetic takes almost the same amount of time on the MIPS~R3000 as
%performing single-precision arithmetic.  Furthermore, the same number of
%floating point registers are available, regardless of whether they are used
%for single or double precision arithmetic, so register spillage is not
%decreased by operating on single-precision values.
%
%\subsubsection{Quantifying the Overheads by Opcode Category}
%
%%\begin{table}
%%\begin{center}
%%\caption{Quantification of Overheads on Monsoon, in Millions of
%%cycles.  The ``total'' for both Monsoon and R3000 exclude RTS cycles.}
%%\label{tab:overhead-quantification}
%%\begin{tabular}{|l||r|r|r|r|r||r|} \hline
%%Program     & Monsoon      & Bubbles & 2nd   & Idles & Remainder & R3000 \\
%%            & ``Total''    &         & Phase &       &           & ``Total'' \\ \hline
%%Blocked-MM $500\times 500$    & 1057 & 269 &   0 &  99 &  689 &  741 \\ \hline
%%Gamteb-2c (40,000)            &  408 & 119 &  26 &  15 &  248 &  263 \\ \hline
%%Simple ($100\times 100$, 100) & 3926 & 937 & 146 & 451 & 2392 & 1735 \\ \hline
%%Paraffins (n=22)              &  156 &  33 &   1 &  10 &  112 &   45 \\ \hline
%%\end{tabular}
%%\end{center}
%%\end{table}
%
%
%\begin{table}
%\begin{center}
%\caption{Quantification of Overheads on Monsoon, in Millions of
%cycles.  The ``total'' for both Monsoon and R3000 exclude RTS cycles.}
%\label{tab:overhead-quantification}
%\begin{tabular}{|l||r|r|r|r|r||r|r|r|r|} \hline
%        & \multicolumn{5}{|c||}{Monsoon} & \multicolumn{4}{c|}{R3000} \\ \cline{2-10}
%Program & Total* & Bub   & 2nd   & Idles & Rest & Total* &
%Nop & inter & Rest \\
%    &           & -bles & Phase &       &      &           &  
%    & -lock &    \\ \hline
%Blocked-MM $500\times 500$    & 1057 & 269 &   0 &  99 &  689 &  741 &
%1 & 195 & 545 \\ \hline
%Gamteb-2c (40,000)            &  408 & 103 &  26 &  15 &  264 &  263 &
%17 & 47 & 199 \\ \hline
%Simple ($100\times 100$, 100) & 3926 & 916 & 146 & 451 & 2413 & 1735 &
%118 & 381 & 1236 \\ \hline
%Paraffins (n=22)              &  156 &  33 &   1 &  10 &  112 &   45 &
%0 & 0 & 45 \\ \hline
%\end{tabular}
%\end{center}
%* Excludes RTS cycles.
%\end{table}
%%% NB:  we have taken out the bubbles that occur in the RTS.  These are:
%%%   mm: 0
%%%   gamteb: 15.716
%%%   simple: 21.36
%%%   paraffins: 0
%
%Table~\ref{tab:overhead-quantification} quantifies the overheads of
%fine grain, asynchronous parallel execution on Monsoon for the four
%benchmarks we have studied.  For each benchmark, we give the total
%number of cycles, in millions, that were executed excluding those due
%to RTS under the ``Total'' column.  For the Monsoon numbers, the
%cycles that were {\em bubbles}, {\em second-phase} instructions, and
%{\em idle} cycles are also listed.  These numbers represent a large
%part of the costs of asynchronous execution.  The ``Rest'' column
%contains the number of cycles that did ``useful'' work, obtained by
%deducting the overheads of parallel execution from the ``total''.  For
%the R3000, we listed ``Nop'' and ``Interlock'' as the costs of
%parallel execution and deducted these from the ``Total'' to obtain
%``Rest''.
%
%%The last column shows the total cycles executed by the same program on
%%the MIPS R3000, again excluding the estimated RTS costs.  For most of
%%these benchmarks the number of cycles spent doing useful computation
%%on Monsoon is roughly the same as that on the MIPS R3000 as to be
%%expected if both compiler perform similar levels of optimization.  The
%%only exception is Paraffins.  *** WHY? ****
%
%Comparing the ``Rest'' column for the two machines,( **** someone
%please help me out here.  What is really interesting about comparing
%these numbers?  It is not clear to me that these numbers are very
%meaningful anymore. The more interesting numbers are actually in the
%overheads.  Comparing the rest is only a sanity check at best.  - Boon
%****) we see that Monsoon is still executing more cycles.  There are
%two possible explanations for this.  One is that we simply have not
%done as good a job at optimizing our code.  For example, if we have
%not done as well at common subexpression elimination, or lifting
%invariant computation out of loops, we can end up executing more
%cycles.  However, another reason is that we still have not taken into
%account another source of asynchronous execution overhead, namely
%those in {\em identity} instructions.  Unfortunately, because of
%the many roles that identity instructions play (see
%Section~\ref{sec:opmix-compare}), it is difficult to differentiate the
%different roles identities play.  We had modified the compiler to
%split up identities, but that compiler does not produce the most
%efficient code and we were only able to make a Gamteb run with code
%generated by that compiler.
