\section{Scalability and Implicit Parallelism Studies}
\label{sec:speedup}
\label{implicit-parallelism-section}

In this section we study the scalability of Id programs on Monsoon.  The
same object code is run on all machine configurations from one processor to
eight processors.  We also use the same run-time system for one processor
and multiple-processor systems, even though we could write a more efficient
RTS for specific use with single-processor configurations.  We estimate
that such an RTS would save up to \percent{50} of the frame and heap
management overhead compared to the multiprocessor RTS.  However, run-time
system overhead on Monsoon is usually less than \percent{30}, so total run
times would only be reduced by \percent{15}.  Since our goal was to write
an RTS that would run on any number of processors, we did not think the
effort required to write a specialized uniprocessor RTS was worthwhile.

 We saw in Section~\ref{sec:parallelism-control} that currently the
programmer must add loop bound annotations to control how much parallelism
is exploited in each loop.  Optimal performance is tied to the choice of
loops to execute in parallel and the loop bounds for those loops.  Since
our compiler and RTS do not automatically choose loop bounds yet, in order
to do this study, we tried a number of loop bounds and chose the ones that
performed the best.

 For our speedup studies, we ran the four benchmarks on 1, 2, 4, and 8
processor Monsoon configurations.  Our speedup results are shown in
Table~\ref{tab:speedup}, which contains the critical path for each program
on each configuration.  We define the critical path to be the total number
of cycles executed by the processor which starts and ends the execution of
the program.  All other processors will always execute fewer instructions,
because they must start after and end before the first processor.

%(These numbers were all generated using id-rts/040/rts14 except for
%Paraffins which used id-rts/045/rts99.)

% Gamteb: /home/prj/monsoon-study/performance/Gamteb-2c
%       Gamteb-2c-40000_1pe_045_16_8.5.1992
%       Gamteb-2c-40000_2pe_045_16_8.5.1992
%       Gamteb-2c-40000_4pe_045_16_8.5.1992
%       Gamteb-2c-40000_8pe_045_16_8.5.1992
%
% Paraffins: /home/prj/derek/monsoon/performance/
%       Paraffins_1pe_045_99_7.30.1992
%       Paraffins_2pe_045_99_7.30.1992
%       Paraffins_4pe_045_99_7.30.1992
%       Paraffins_8pe_045_99_7.30.1992
%
%(These were actually run with 040, but because of some naming
%problem, they are saved in 041 files.)
% Simple: /home/prj/derek/monsoon/performance/
%       Simple-100-100_1pe_041_14_6.6.1992
%       Simple-100-100_2pe_041_14_6.5.1992
%       Simple-100-100_4pe_041_14_6.5.1992
%       Simple-100-100_8pe_041_14_6.6.1992
%
% Matrix-Multiply: /home/prj/derek/monsoon/performance/
%       mmt44-500_1pe_044_99_7.27.1992
%       mmt44-500_2pe_044_99_7.28.1992
%       mmt44-500_4pe_044_99_7.27.1992
%b      mmt44-500_8pe_044_99_7.27.1992
        
\begin{table}
\caption{Speedup Results: Id on Monsoon}\label{tab:speedup}
\begin{center}
\begin{tabular}{|l||l|l||l|l||l|l||l|l|}
\hline
\hfill Configuration  & \multicolumn{2}{c||}{1 PE} & \multicolumn{2}{c||}{2 PE} & \multicolumn{2}{c||}{4 PE}  & \multicolumn{2}{c|}{8 PE} \\ \cline{2-9}
  &  & $\times10^6$ &  & $\times10^6$ &  & $\times10^6$ &  & $\times10^6$\\
Program  & $\frac{1 PE}{1 PE}$ & critical  & $\frac{1 PE}{2 PE}$ & critical &
$\frac{1 PE}{4 PE}$ & critical & $\frac{1 PE}{8 PE}$ & critical\\
  & & path  &  & path &  & path &  & path\\\hline
\hline
%Matrix-Multiply & 1   & 1057   & 1.99  & 531   & 3.90  & 271   & 7.62  &139 \\
%$500\times 500$         &     &         &       &        &       &        &       &\\\hline
$4 \times 4$ Blocked-MM      & 1   & 1057   & 1.99  & 531   & 3.90  & 271   & 7.74  &137 \\
$500\times 500$         &     &         &       &        &       &        &       &\\\hline
Gamteb-2c       & 1   & 590     & 1.95  & 303    & 3.81  & 155   & 7.35  &80.3 \\
40000 particles &     &         &       &        &       &        &       &\\\hline
%Simple          & 1   & 4994   & 1.87  & 2670  & 3.48  & 1435  & 6.21
%&804 \\
Simple          & 1   & 4681   & 1.86  & 2518  & 3.45  & 1355  & 6.27
& 747 \\
100 iters, $100 \times 100$&   &         &       &        &       &        &       &\\\hline
Paraffins       & 1   & 322    & 1.99  & 162   & 3.92  & 82.2  & 7.25  &44.4 \\
n = 22          &     &         &       &        &       &        &       &\\\hline
\end{tabular}
\end{center}
\end{table}


Tables~\ref{tab:mmt44-opmix} to~\ref{tab:paraffins-opmix} give the detailed
breakdown of the dynamic instruction counts for each of the four
benchmarks.  Each table shows the total dynamic opcode mix for a single
benchmark on all four machine configurations.  The column for each
configuration shows the sum of the statistics, including idles, from all of
the processors in the configuration.

\subsection{Why Linear Speedup was not Achieved}
%\subsection{Accounting for Differences in Total Cycle Counts}

Ideally, a program exhibiting perfect speedup would execute the same number
of total cycles (summed over all processors in the configuration)
regardless of the number of processors.  However, there is always some
overhead associated with exposing more parallelism, so the total number of
cycles executed always increases with the number of processors in the
configuration.  Most of the overhead on multiprocessor configurations of
Monsoon shows up as additional idle cycles executed, but some shows up
as additional instructions executed.  In this section we
discuss the causes of these overheads.

\subsubsection{Additional Instructions in the Multiprocessor Case}

\paragraph{Loop bounds:}

In order to keep more processors busy, a program needs to expose more
parallelism.  We increase the loop bounds in order to increase the
parallelism exploited by a program.  The overhead of a {\em $k$-bounded}
loop consists of allocating and initializing the iteration frames, and is
directly proportional to the loop bound $k$.  Thus, a program on a larger
machine configuration requires larger loop bounds and executes more
overhead instructions than on a single processor system.

\paragraph{Resource management:}

As mentioned before, each processor in the system has a set of frame and
heap resources and associated managers for these resources.  Due to
differences in scheduling and available resources, the resource managers on
two different machine configurations may process requests at different
rates.  Furthermore, increasing loop bounds causes more frame requests to
be made and so may increase contention for frame managers.  This increase
in frame manager contention shows up as the increase in the number of
tokens recirculated.  The number of tokens recirculated indicates the
cycles spent waiting for a frame manager lock.

\paragraph{Deferred reads:}

An I-structure fetch request may arrive at an I-structure element before
the corresponding I-structure store completes (see
Section~\ref{sec:deferred}).  In the case of an I-fetch before an I-store,
a small sequence of instructions are executed to enqueue the deferred
requests on a linked-list.  When the I-store finally occurs, a few more
instructions are executed respond to the deferrred reads by distributing
the written value.  Whether an I-fetch is deferred or not depends upon
scheduling, and hence on machine configuration.  We suspect that a
multiprocessor system will defer more reads than a single-processor system
executing the same program, because it will do more computation in
parallel.

\subsubsection{Causes of Idle Cycles}

Idles tend to be the largest contributor to increased total cycle counts on
Monsoon.  Idles on Monsoon are caused either by its hardware hazard, or by
a lack of work on one or more processors.  Multiprocessor Monsoon systems
are guaranteed to have more idles than single processor systems due to both
of these reasons.  Multiprocessor configurations require more network
tokens, increasing the number of idles due to Monsoon's hardware hazard.
Too little parallelism, which results in lack of work, is much more likely
on a multiprocessor since more parallelism is required to keep it busy.
Load imbalance, a problem only on multiprocessor configurations, causes
idles because some processors will not have enough work to do.  These
causes are explained in greater detail below.

\paragraph{Hardware Hazard:}

As explained in Section~\ref{sec:hazard}, Monsoon has a hardware hazard caused
by a shared bus between the token queues and the network interface.  This
hazard prevents any token from being enqueued or dequeued from the network
input or output queues while a token is  enqueued or dequeued from the
user or system token queue, and {\em vice versa\/}.  Any time there is
contention on this shared bus, an idle cycle occurs.

{\em Fetches} and {\em Tag} operations can excite the hardware hazard
in two ways.  If an instruction produces exactly one token that goes
to the network, an idle is forced because that token will be sent to
the network while the token fetch from the token queue is delayed one
cycle.  The fetches executed by the frame manager have local
destinations and, therefore, do not cause idles.  But the benchmarks
are all compiled and  our compiler, which produces dataflow-style code,
stops a thread after every split-phased instruction.  Hence, all compiled 
fetches and tag instructions excite this hazard.

Once a token arrives at its destination processor, the token may cause
an idle by interfering with an operation being performed on the token
queue of the destination processor.  The hardware implements a fair
policy between processor-pipeline and network tokens.  When a network
token arrives, it is placed in the network input queue.  If network
input queue contains tokens, and the processor pipeline is kept busy
by recirculating tokens, then every other cycle, a processor token is
enqueued in the user queue, and a network token is popped from the
network input queue.  This causes an idle cycle to be placed in the
processor pipeline.  If the processors are always busy, then the
fraction of network tokens that will cause an idle on the destination
processor is one half.  Thus, we estimate the number of idles due to
the hardware hazard to be roughly 1.5 times the sum of the number of
fetches and the number of remote send operations, in the worse case
(assuming that the processor is always busy.)  If the processor is
idle due to lack of work, then this ratio will be somewhere between
1.0 and 1.5.


\paragraph{Lack of Work:}

A processor also executes an idle cycle when its token queues
are empty due to lack of work.  A processor can have a lack of work
because of: (i) load imbalance, (ii) lack of parallelism due to RTS
sequentialization, (iii) lack of parallelism during startup and
termination of program, or (iv) lack of parallelism in the algorithm.

{\em Load imbalance} can cause a lack of work on one or more processors
even though there is enough work in the machine to keep all processors
busy.  The RTS cannot balance load perfectly, because it cannot know which
processors need work at a given moment, and which may need work in the
future.  However, by definition load imbalance cannot occur on single
processor configurations.

The run-time system can artificially reduce parallelism by
taking a long time to satisfy a frame or heap object request.  A
processor may need the frame or heap memory in order to continue
computation and thus may idle if that object is not returned by a
specific time.  To see how long a typical RTS request takes, we
describe the steps involved in allocating frame memory, giving an
instruction count for each step.

 Under the best scenario, allocating a frame requires executing 31 or
32 instructions sequentially.  It takes 16 instructions to read a
frame request, choose a processor, and forward a request to that
processor.  If a frame is available on that processor's free-lists, it
then takes 7 instructions to pop a frame, and another 8 or 9 more
instructions to form a context by combining the frame pointer,
instruction pointer and statistics color of the called code-block.  On
Monsoon, the actual latency will be eight times as long because of
processor pipeline interleaving.

 If no frames are on a free-list, the cost of allocation is much
higher, because the presence-bits of a new frame will have to be
cleared.  Allocating a new frame takes eight instructions plus about
$\frac{n}{16}$ instructions to clear out the presence bits of an $n$
word frame.  We clear frame presence-bits sixteen words at a time
using a block clear instruction.  We only clear the presence bits the
first time we allocate a frame because procedures automatically clean
their own frames before returning them.

 The execution of Id on Monsoon starts with the invocation of a top
level procedure on one processor which spreads work to other
processors.  The computation ends in a similar way, but in reverse
order.  Thus during the {\em startup and termination phases}, the
parallelism ramps up and then ramps down again and there is not enough
parallelism to keep all the processors busy.  The length of the
startup and termination phases are affected by the rate at which the
program exposes parallelism, the latency of RTS requests, the latency
of interprocessor communication, and the number of processors.  Notice
this cost is non zero even on a single processor due to the 8-way
interleaved pipeline. In our experiments, increasing the number of
processors linearly increases the length of the startup and
termination phases.

 Finally, a lack of parallelism may occur because the {\em algorithms}
used in a program are inherently serial in nature.  In these cases,
the program must be rewritten to use a more appropriate algorithm.
However, we think that all of our benchmarks had sufficient parallelism
for an eight processor Monsoon machine.

 On Monsoon, it is difficult to differentiate idles caused by a lack of
parallelism, load imbalance and the hardware hazard, because neither the
sizes of the token queues, nor the number of cycles when they are empty can
be measured while running a program.  If we had this information, we could
determine whether it was lack of work or the hardware hazard that was
causing the idles in our programs.  By periodically sampling this
information on each of the processors, we may be able to distinguish
between a temporary load imbalance and the lack of parallelism.  For these
statistic to make sense, we have the additional requirement that the
statistics be collected from all the processors at exactly the same time,
something that is impossible to do on Monsoon in particular, and difficult
on any (large) asynchronous system in general.

%*** Should comment on bandwidth limitations ***


In the following sections, we will try to explain the idle cycles for
each of the benchmark runs; the precision of our explanation is
limited by the ways in which we can gather statistics.

\subsection{Analysis of Benchmarks}

\subsubsection{Blocked-MM}

\begin{table}
\caption{Blocked-MM Opcode Mix}
\begin{center}
\begin{tabular}{|l|r|r||r|r||r|r||r|r|}
\hline
\hfill Configuration & \multicolumn{2}{c||}{1 PE} & \multicolumn{2}{c||}{2 PE}
& \multicolumn{2}{c||}{4 PE} & \multicolumn{2}{c|}{8 PE}\\ 
\cline {2-9}
Op category & cycles & fraction & cycles & fraction & cycles & fraction & cycles & fraction \\ 
& $\times10^6$ & \% & $\times10^6$ & \%  
& $\times10^6$ & \% & $\times10^6$ & \% \\ \hline
\hline
Intop & 77.0 & 7.28 & 77.0 & 7.25 & 77.1 & 7.11 & 77.2 & 7.06\\\hline
Floatop & 250.3 & 23.66 & 250.3 & 23.55 & 250.3 & 23.07 & 250.3 & 22.90\\\hline
Fetch & 62.8 & 5.93 & 62.8 & 5.91 & 62.8 & 5.79 & 62.9 & 5.76\\\hline
Store & 1.5 & .14 & 1.5 & .14 & 1.6 & .14 & 1.6 & .15\\\hline
Identity & 289.4 & 27.36 & 289.4 & 27.23 & 290.0 & 26.73 & 290.7 & 26.60\\\hline
Tag & 0.5 & .05 & 0.5 & .05 & 0.7 & .06 & 0.9 & .08\\\hline
Miscop & 7.5 & .71 & 7.5 & .71 & 7.7 & .71 & 7.9 & .72\\\hline
\hline
Bubble & 269.2 & 25.45 & 269.2 & 25.34 & 269.6 & 24.85 & 270.0 & 24.70\\\hline
Second Phase & 0.1 & .01 & 0.1 & .01 & 0.2 & .02 & 0.4 & .04\\\hline
Recircs & 0.0 & .00 & 0.0 & .00 & 0.0 & .00 & 0.0 & .00\\\hline
\hline
Idles & 99.5 & 9.41 & 104.2 & 9.81 & 125.1 & 11.53 & 131.1 & 12.00\\\hline
\hline
Total & 1057.7 & 100  & 1062.5 & 100  & 1084.9 & 100  & 1093.0 & 100 \\\hline
\hline
Speedup  
& \multicolumn{2}{c||}{1.00}
& \multicolumn{2}{c||}{1.99}
& \multicolumn{2}{c||}{3.90}
& \multicolumn{2}{c|}{7.74} \\ \hline
Efficiency
& \multicolumn{2}{c||}{100.0\%}
& \multicolumn{2}{c||}{99.5\%}
& \multicolumn{2}{c||}{97.5\%}
& \multicolumn{2}{c|}{96.8\%} \\ \hline
\end{tabular}
\end{center}
\label{tab:mmt44-opmix}
\end{table}

Our matrix multiplication benchmark running with a problem size of 500
by 500 achieves an excellent speedup of 7.74 on 8 processors.  It
achieves an {\em efficiency\/} of 97\%, where we define efficiency to
be the speedup divided by the number of processors.  The dynamic
opcode mix for Blocked-MM is given in Table~\ref{tab:mmt44-opmix},
which shows that the total cycle count increases very little from the
1 PE to 8 PE configuration.  The more interesting issue here is why
there are any idle cycles in the 1 PE case to start with.

On this configuration, about 6\% of the total cycles executed are
fetches and 9.4\% are idle cycles.  All of the fetches in the
Blocked-MM occur in compiled code, and thus, excite the hardware hazard.
We believe the additional 3.5\% idles are caused by startup and end
costs as well as incoming network tokens.  This probably contributes
to the slightly rising percentage of idles as we go from the 1PE to
the 8PE configuration.

\subsubsection{Gamteb}  

Gamteb is actually an ``embarrassingly parallel'' program, so we expected
it to show excellent speedups on Monsoon.  It does so, achieving a
92\% efficiency on 8 processors, with a speedup of 7.35.

 Gamteb actually executes fewer idle cycles than fetch instructions.  We
have determined, through code-block coloring, that about two thirds of the
fetches are performed by the frame manager and thus do not excite the
hardware hazard.  For a single processor, therefore, all idles are
accounted for.  The additional idles for multiprocessors come from the {\em
tag\/} operations, most of which are used to send arguments to other
procedures.  The number of procedure calls in Gamteb is proportional to the
total number of particles generated, and usually 6 to 7 times the number of
initial particles in our data set.  With runs that start with 40000
particles, the number of procedure calls, and consequently the number of
tag operations, can be very substantial.

When there is only one processor, all of the tag operations send their
arguments back to the same processor.  When the number of processors $p$
increases, however, the number of remote procedure calls go to
approximately $\frac {(p-1)}{p}$ (assuming perfect distribution).  Thus,
about $\frac {(p-1)}{p}$ of the {\em Send} operations (a subset of the tag
operations) send a token to the network but none back to the same
processor, causing a hardware hazard.  This explains most of the increase
in the number of idle cycles as we move to configurations with more
processors.

For eight processors, Gamteb's idles are a little higher (around 6.7
million cycles or about 10.6\%) than expected according to this formula.
This excess is probably due to the start up cost not being amortized when
the problem size is small.  This hypothesis is partially confirmed by the
fact that the fraction of idle cycles decreased dramatically when we
increased the problem size from 40000 particles to 1,000,000 particles.  On
smaller runs (8 PE Monsoon took only 8 seconds for 40,000 particles), there
is also a significant perturbation of the statistics by the skew in the
timing of when each processor is started and halted by the the front end
processors.  Because of this skew, some of the processors may be idling
while waiting for tokens from processors that are not yet running.

\begin{table}
\caption{Gamteb Opcode Mix}
\begin{center}
\begin{tabular}{|l|r|r||r|r||r|r||r|r|}
\hline
\hfill Configuration & \multicolumn{2}{c||}{1 PE} & \multicolumn{2}{c||}{2 PE}
& \multicolumn{2}{c||}{4 PE} & \multicolumn{2}{c|}{8 PE}\\ 
\cline {2-9}
Op category & cycles & fraction & cycles & fraction & cycles & fraction & cycles & fraction \\ 
& $\times10^6$ & \% & $\times10^6$ & \%  
& $\times10^6$ & \% & $\times10^6$ & \% \\ \hline
\hline
Intop & 47.5 & 8.05 & 47.5 & 7.85 & 47.5 & 7.68 & 47.6 & 7.40\\\hline
Floatop & 40.4 & 6.84 & 40.4 & 6.67 & 40.4 & 6.52 & 40.4 & 6.28\\\hline
Fetch & 27.6 & 4.69 & 27.6 & 4.57 & 27.6 & 4.46 & 27.6 & 4.30\\\hline
Store & 13.3 & 2.26 & 13.3 & 2.20 & 13.3 & 2.15 & 13.4 & 2.08\\\hline
Identity & 171.6 & 29.07 & 171.6 & 28.36 & 171.7 & 27.72 & 171.8 & 26.72\\\hline
Tag & 43.6 & 7.40 & 43.7 & 7.21 & 43.7 & 7.05 & 43.7 & 6.80\\\hline
Miscop & 83.6 & 14.17 & 83.7 & 13.82 & 83.7 & 13.51 & 83.7 & 13.02\\\hline
\hline
Bubble & 119.2 & 20.21 & 119.3 & 19.71 & 119.3 & 19.27 & 119.4 & 18.57\\\hline
Second Phase & 25.7 & 4.35 & 25.7 & 4.24 & 25.6 & 4.14 & 25.6 & 3.98\\\hline
Recircs & 2.3 & .39 & 1.8 & .29 & 1.9 & .30 & 1.9 & .30\\\hline
\hline
Idles & 15.2 & 2.57 & 30.7 & 5.07 & 44.5 & 7.19 & 67.9 & 10.56\\\hline
\hline
Total & 590.1 & 100  & 605.3 & 100  & 619.2 & 100  & 642.9 & 100 \\\hline
\hline
Speedup  
& \multicolumn{2}{c||}{1.00}
& \multicolumn{2}{c||}{1.95}
& \multicolumn{2}{c||}{3.81}
& \multicolumn{2}{c|}{7.34} \\ \hline
Efficiency
& \multicolumn{2}{c||}{100.0\%}
& \multicolumn{2}{c||}{97.5\%}
& \multicolumn{2}{c||}{95.3\%}
& \multicolumn{2}{c|}{91.8\%} \\ \hline
\end{tabular}
\end{center}
\label{tab:gamteb-opmix}
\end{table}

\subsubsection{Simple}

\begin{table}
\caption{Simple Opcode Mix}
\begin{center}
\begin{tabular}{|l|r|r||r|r||r|r||r|r|}
\hline
\hfill Configuration & \multicolumn{2}{c||}{1 PE} & \multicolumn{2}{c||}{2 PE}
& \multicolumn{2}{c||}{4 PE} & \multicolumn{2}{c|}{8 PE}\\ 
\cline {2-9}
Op category & cycles & fraction & cycles & fraction & cycles & fraction & cycles & fraction \\ 
& $\times10^6$ & \% & $\times10^6$ & \%  
& $\times10^6$ & \% & $\times10^6$ & \% \\ \hline
\hline
Intop & 591.2 & 12.63 & 593.0 & 11.77 & 593.2 & 10.94 & 600.4 & 10.05\\\hline
Floatop & 334.8 & 7.15 & 334.8 & 6.65 & 334.8 & 6.18 & 334.8 & 5.60\\\hline
Fetch & 399.6 & 8.54 & 400.0 & 7.94 & 399.8 & 7.38 & 403.6 & 6.75\\\hline
Store & 79.2 & 1.69 & 80.0 & 1.59 & 80.3 & 1.48 & 82.6 & 1.38\\\hline
Identity & 1194.3 & 25.51 & 1201.0 & 23.84 & 1199.9 & 22.13 & 1235.6 & 20.68\\\hline
Tag & 265.2 & 5.67 & 267.9 & 5.32 & 268.1 & 4.95 & 280.7 & 4.70\\\hline
Switch & 270.9 & 5.79 & 273.4 & 5.43 & 272.8 & 5.03 & 287.6 & 4.81\\\hline
\hline
Bubble & 937.1 & 20.02 & 942.2 & 18.71 & 941.3 & 17.36 & 967.8 & 16.20\\\hline
Second Phase & 146.2 & 3.12 & 143.3 & 2.84 & 142.7 & 2.63 & 149.3 & 2.50\\\hline
Recircs & 12.2 & .26 & 9.4 & .19 & 9.7 & .18 & 10.0 & .17\\\hline
\hline
Idles & 451.0 & 9.63 & 791.8 & 15.72 & 1178.4 & 21.74 & 1622.2 & 27.15\\\hline
\hline
Total & 4681.7 & 100  & 5036.8 & 100  & 5421.0 & 100  & 5974.6 & 100 \\\hline
\hline
Speedup  
& \multicolumn{2}{c||}{1.00}
& \multicolumn{2}{c||}{1.86}
& \multicolumn{2}{c||}{3.45}
& \multicolumn{2}{c|}{6.27} \\ \hline
Efficiency
& \multicolumn{2}{c||}{100.0\%}
& \multicolumn{2}{c||}{92.9\%}
& \multicolumn{2}{c||}{86.4\%}
& \multicolumn{2}{c|}{78.4\%} \\ \hline
\end{tabular}
\end{center}
\label{tab:simple-opmix}
\end{table}

We ran Simple for 100 iterations of 100 by 100 grid.  The best speedup we
have achieved for Simple is a factor of 6.2 on an 8 processor
configuration, giving an efficiency of 78\%.  We believe that this is
mainly because of a throughput problem in our current general heap manager.
It is also possible that data dependence in the user code (the time step
calculation between iterations) contributes to the sequentialization of
computation between iterations.  Together, they result in a lack of
parallelism which was observed by looking at the front-panel LEDs on
Monsoon which indicate computation and network activities.  They dim in a
periodic fashion, the same number of times as the number of iterations
executed.  Table~\ref{tab:simple-opmix} shows the dynamic operation mixes
for Simple running on the four Monsoon configurations.

%We believe we have not
%exposed enough parallelism to keep each processor busy~--- the loop
%bounds were chosen in an {\em ad hoc\/} fashion and some loop bounds
%were used in more than one loop.  Also, we seem to be having a

The total cycles that Simple executes increases with the number of
processors.  We believe that this is due to the rising number of frame
allocations performed on multiprocessor configurations.

\subsubsection{Paraffins}

\begin{table}
\caption{Paraffins Opcode Mix}
\begin{center}
\begin{tabular}{|l|r|r||r|r||r|r||r|r|}
\hline
\hfill Configuration & \multicolumn{2}{c||}{1 PE} & \multicolumn{2}{c||}{2 PE}
& \multicolumn{2}{c||}{4 PE} & \multicolumn{2}{c|}{8 PE}\\ 
\cline {2-9}
Op category & cycles & fraction & cycles & fraction & cycles & fraction & cycles & fraction \\ 
& $\times10^6$ & \% & $\times10^6$ & \%  
& $\times10^6$ & \% & $\times10^6$ & \% \\ \hline
\hline
Intop & 77.4 & 24.01 & 77.4 & 23.94 & 77.4 & 23.54 & 77.4 & 21.82\\\hline
Floatop & 0.0 & .00 & 0.0 & .00 & 0.0 & .00 & 0.0 & .00\\\hline
Fetch & 15.6 & 4.85 & 15.7 & 4.84 & 15.7 & 4.77 & 15.7 & 4.42\\\hline
Store & 49.8 & 15.46 & 49.8 & 15.41 & 49.8 & 15.16 & 49.8 & 14.05\\\hline
Identity & 73.6 & 22.85 & 73.7 & 22.80 & 73.7 & 22.43 & 73.8 & 20.79\\\hline
Switch & 42.0 & 13.05 & 42.1 & 13.02 & 42.1 & 12.81 & 42.1 & 11.88\\\hline
Tag & 16.0 & 4.97 & 16.1 & 4.97 & 16.1 & 4.90 & 16.1 & 4.55\\\hline
\hline
Bubble & 33.4 & 10.36 & 33.4 & 10.34 & 33.4 & 10.17 & 33.5 & 9.43\\\hline
Second Phase & 0.5 & .15 & 0.6 & .18 & 0.6 & .19 & 0.6 & .18\\\hline
Recircs & 4.4 & 1.37 & 4.5 & 1.39 & 4.6 & 1.40 & 4.9 & 1.37\\\hline
\hline
Idles & 9.5 & 2.94 & 10.0 & 3.10 & 15.2 & 4.62 & 40.9 & 11.52\\\hline
\hline
Total & 322.3 & 100  & 323.3 & 100  & 328.8 & 100  & 354.8 & 100 \\\hline
\hline
Speedup  
& \multicolumn{2}{c||}{1.00}
& \multicolumn{2}{c||}{1.99}
& \multicolumn{2}{c||}{3.92}
& \multicolumn{2}{c|}{7.27} \\ \hline
Efficiency
& \multicolumn{2}{c||}{100.0\%}
& \multicolumn{2}{c||}{99.7\%}
& \multicolumn{2}{c||}{98.0\%}
& \multicolumn{2}{c|}{90.8\%} \\ \hline
\end{tabular}
\end{center}
\label{tab:paraffins-opmix}
\end{table}

Our current Paraffins runs had speedups of 7.25 for eight processors,
giving an efficiency of 91\%.  One through four processor runs of Paraffins
actually execute fewer idles than fetches.  About half of the fetches were
due to critical instructions in the frame manager and half were due to
fetches in Paraffins itself, revealing that the idles were due to the
hardware hazard.

We believe a lack of parallelism in the tail of the computation reduces the
efficiency of each processor in the eight processor case.  This theory is
supported by manually observing the front-panel LEDs on the Monsoon
hardware that indicates processor and pipeline activities.  Towards the end
of the computation, the work lights on all processors get dimmer
simultaneously, indicating a lack of work.  A larger problem size will
probably amortize the tail and increase efficiency.  Another possibility
would be to change some of the sequential loops to bounded to expose more
parallelism.

%Our initial experiments with running Paraffins on multiprocessor
%Monsoon configurations, however, were very disappointing because we
%did not seem to get very good speedup.  We were only seeing about 5.5
%times speedup.  We found that this was because we were trying to
%measure intervals that were too short compared to the amount of time
%it takes to start and stop all processors.  The runs we were making
%were taking about .4 seconds on eight processors.  It was difficult to
%run larger problem sizes because we run out of I-Structure memory on
%the smaller configurations.  Now we use eight I-structure processors on
%all configurations, so that we can run a larger problem size.  On this
%problem size (22 carbons), we see a speedup of about 7.3 times on
%eight processors.
%


%%%
%%% end scalability
%%%
%%***************************************************************


