\section{Trace Driven Simulation}
\vspace {-1.0pc}

Previous simulation studies on the cache implications of multithreaded
execution have used traces obtained by artificially interleaving
reference streams from several contexts~\cite{WeberGupta,Anant}
simply because real traces were not available.\footnote{Note that
others have performed realistic simulation of multithreaded codes,
however these do not seem to account for local cache behavior. For
examples, see~\cite{Boothe92} and~\cite{Keckler92}.} Though this kind
of approach has its meaning for the kind of context switching studied
--- essentially switching amongst a few (say, two or four) hardware
contexts in order to mask cache misses --- it is problematic for
fine-grain multithreaded execution where strong data dependencies
amongst threads have a first order effect upon scheduling and
therefore working set behavior.
\vspace {-0.4pc}

\subsection{Benchmark Programs}
\vspace {-1.0pc}

For this study, we extensively explored the behavior of two distinctly
different parallel programs: {\tt GAMTEB}, a Monte~Carlo neutral
particle transport simulation of photons traversing through a carbon
rod and {\tt MMP}, an unblocked matrix multiply. The parallelism in
{\tt MMP} is obvious, while {\tt GAMTEB} has one outermost loop
comprising a set of recursive code blocks whose calling path depends
on a number randomly generated for each iteration of the loop. Both
programs were written in Id and compiled to TL0 code using the
Berkeley backend~\cite{Culler}. While we certainly would desire to
study more programs, we felt that these were largely representative of
fairly broad classes of applications and preferred to apply our
resources to study their behavior in a great deal of depth.  Here is a
brief description of the codes:

We ran the programs on various system configurations, input data
sizes, and loop bounds. We report here simulation results on an eight
processor configuration with 20,000 photons for {\tt GAMTEB} and a
600~$\times$~600 matrix for {\tt MMP}. Three different loop bounds are
experimented for each program: 50, 200 and 800 for {\tt GAMTEB}, and
25, 50 and 100 for {\tt MMP}. Note that loop bound in {\tt MMP} is
applied to all of the three loops, whereas the loop bound for {\tt
GAMTEB} is applied to the outer loop only.  Furthermore, to see how
scheduling influences memory reference behavior, we conducted
experiments on thread scheduling policies: LIFO versus FIFO queues for
enabled data threads.
\vspace {-0.5pc}

\subsection{Statistical Summary}
\vspace {-1.0pc}

Table~\ref{static-tab} summarizes static information for these two
benchmark programs. {\tt MMP's} program size is about 16KB, which is
apparently too small for the purpose of instruction cache simulation.
For the frame cache, however, this program is a good test
of locality behavior, especially considering that controlling the
cache behavior of the matrices themselves can be quite
tricky~\cite{Monica}. This is reflected in the frame references
because the frames essentially hold pieces of the matrices
which have been explicitly prefetched.  In both programs, the average
length of synchronization threads (called inlets in the TAM model),
around five instructions, are considerably shorter than those of data
threads, which are well above ten instructions.

\begin{table}
\begin{center}
\begin{tabular}{||c|l|r|r||}
\hline \hline
\multicolumn{2}{||c|}{Benchmark}  &  {\tt GAMTEB} &  {\tt MMP} \\\hline
\hline
\multicolumn{2}{||c|}{Program size (Inst.)}     &24,921   &4,238 \\ \hline
\multicolumn{2}{||c|}{Number of Code Blocks} &51   &13 \\ \hline \hline
Data    &Avg. Number~(/CB)   &16.76  &14.69 \\ \cline{2-4}
Threads &Avg. Length~(Inst.)  &21.03  &14.63 \\ \hline
Sync.   &Avg. Number    &28.31  &19.69 \\ \cline{2-4}
Threads &Avg. Length  &4.81   &5.64 \\ \hline \hline
\multicolumn{2}{||c|}{Average Thread Length}  &10.84   &9.48 \\ 
\hline \hline
\end{tabular}
\end{center}
\vspace {-1.0pc}
\caption{Static information of benchmark Programs. Program sizes and
thread lengths are measured in 4-byte RISC-type instruction counts.}
\vspace {-0.5pc}
\label{static-tab}
\end{table}

Table~\ref{trace-length-example-tab} shows trace length for two runs out of
the twelve runs that we examine in this paper.  Other runs for each benchmark have
essentially the same characteristics. 
Rather than record the execution traces from all eight processors, we 
instead recorded references from only one of the processors until
the statistics we report later reached a stable state and the traces
are long enough for simulations of caches smaller than 64KB. For the
purpose of justifying using traces for one node, we verified that
statistics variations between nodes were negligible.

\begin{table}
\begin{center}
\begin{tabular}{||c|c|c||c|c|c||}
\hline \hline
Bench- &Sched. &Loop  &Num. of &Inst. &Frame \\
mark  &Policy &Bnd   &Threads &Refs.  &Refs. \\ \hline \hline
{\tt GAMTEB} &LIFO &200 &0.69M &7.95M &3.66M \\ \hline
{\tt MMP}    &LIFO &50  &0.81M &9.40M &4.60M \\ \hline
\hline
\end{tabular}
\end{center}
\vspace {-1.0pc}
\caption{Trace length examples.}
\vspace {-0.4pc}
\label{trace-length-example-tab}
\end{table}

Figure~\ref{proc-util-fig} shows processor utilization of each run by
dividing processor time into data thread execution time,
synchronization thread execution time and idle time. The numbers
$50,200,800$ and $25,50,800$ refer to the loop bounds used in {\tt
GAMTEB} and {\tt MMP}, respectively.  {\tt GAMTEB} achieves near
perfect utilization with loop bounds of 200 and greater. {\tt MMP}
only achieves a maximum of 85\% utilization, which we attribute to the
fact that the unblocked algorithm exhausts the interprocessor
communications bandwidth. Observe that there isn't significant
difference in processor utilization between LIFO and FIFO scheduling,
though slight improvement can be found for {\tt GAMTEB}.  We caution
that Figure~\ref{proc-util-fig} should not be thought as predicting
performance of these programs; this is not our objective.  Rather, the
important consequence of this figure is that choice of our loop bounds
are just around a saturation point of processor utilization for the
duration of program execution we study.  The saturation point is a
point where processor resource usage is optimized~\cite{Saavedra}.

\begin{figure}
\illustrationsize{proc-util-fig}{2.80in}
\vspace {-1.0pc}
\caption{Processor utilization for 12 runs. The processor time is
divided into Idle time, Synchronization thread execution time and Data
thread execution time. Note that the y-axis minimum is not zero.}
\vspace {-0.5pc}
\label{proc-util-fig}
\end{figure}

  