\section{Introduction}
\vspace {-1.0pc}

Multithreaded execution is often advocated as an effective latency-tolerance
technique for multiprocessors. The term ``multithreading'' loosely
applies to a fairly broad range of hardware mechanisms and compiling
disciplines which share the common property of multiplexing, in time,
several distinct computational contexts onto a single processor. The
latency tolerance property is a consequence of the situation where at
least one of the simultaneous contexts can make progress executing
while some or all of the others might be blocked due to a long latency
event, {\em e.g.,} a cache miss, explicit receive, or split-phase
transaction. 

Unfortunately, rapidly switching a processor among distinct contexts
will, in general, decrease the locality of the processor's
instruction, activation frame (stack frame), and heap reference
streams with a commensurate increase in cache miss
ratios~\cite{WeberGupta,Anant}.  This study is concerned with
quantifying, both analytically and experimentally, the effects on
instruction and activation frame cache performance of an aggressive
fine-grained multithreaded compiling model, the threaded abstract
machine (TAM) model developed by Culler~{\em et al}~\cite{Culler}.
The instruction and activation frame reference streams comprise the
{\em local\/} memory reference streams of TAM programs and typically
are cached by processors as private or read-only data.  Global
references are made through explicit split-phase transactions, which
can be thought of as a kind of binding prefetch into local memory (an
entry in an activation frame). Here, we focus upon the locality
properties of the local references.

In execution models like TAM, threads are short and non-blocking, and
the number of potentially executing threads are not bound to fixed
hardware resources such as the number of hardware contexts.  Indeed,
we make minimal assumptions about the underlying hardware, and in fact
assume that the storage for, and scheduling of, multiple contexts are
managed in software.\footnote{Practically speaking, however,
fine-grained multithreading will only make sense on processors that
support an efficient short message network interface. Otherwise
network overhead will dominate execution time. Fortunately, tightly
integrated network interfaces are appearing in a number of commercial
and research machines, {\em e.g.,} the CM-5~\cite{CM5}, NCUBE,
Tera~\cite{Tera}, iWARP, J-Machine~\cite{JMachine},
Alewife~\cite{Alewife} and *T~\cite{Start}.  Our results should give
insight to the local memory reference behavior of codes running any of
these machines which have been compiled for a TAM-like execution
model.}

We believe we have made three basic contributions to the understanding
of local reference streams under fine-grained multithreading in
the multiprocessor setting:
\begin{enumerate}

\vspace {-0.3pc}

\item{\bf Multiprocessor Execution Traces.} 
Using a multiprocessor instruction-level simulator, we have gathered
extensive execution traces for two classes of applications:
loop-parallel dense matrix arithmetic (matrix multiply -- {\tt MMP})
and procedure-parallel event simulations (Monte-Carlo neutral particle
transport -- {\tt GAMTEB}). Previous studies obtained traces by
artificially interleaving traces from several
contexts~\cite{WeberGupta,Anant}.

\vspace {-0.3pc}

\item{\bf Working Set Model.} Surprisingly, we have 
determined a working set model for local activation frame references that
closely matches uniprocessor working sets for stack and heap data. The
multithreaded working set is well-described by the power law function 
$W(t)={\alpha}t^{\beta}$ --- the size of the working set grows
according to some power of the length of time over which references
are considered. Similar to working sets reported for uniprocessors,
the $\beta$ for activation frame references is often around 0.5.

\vspace {-0.3pc}

\item{\bf Validated Analytic Cache Model.} Using the working set model
for activation frame and instruction references, we have derived a set
of useful formulae which predict cache performance under multithreaded
execution. We have validated this model through actually simulating
various cache configurations against the reference traces and have
found excellent agreement.
\end{enumerate}

\vspace {-0.3pc}

The structure of the paper follows the items above. After quickly
articulating the underlying multithreaded execution model, we
describe the two codes we studied and the simulation environment.
Careful study of the execution traces reveals the underlying power law
working set model, which we then use as the basis for an analytic
model of cache performance. Finally, we compare the model predictions
with simulated caches and suggest possible scheduling techniques for improving
miss ratios. 



