\section{Working Set Behavior}
\label{Local Memory Reference Behavior Analysis}
\vspace {-1.0pc}

Central to the prediction of cache behavior is the characterization of
temporal correlations in reference streams. A {\em working set
\/}$W(t)$~\cite{Denning} is a function of a  time window $t$ which 
describes the number of unique references that occur in the window. If
$W(t)$ grows slowly with $t$ then the reference stream has good
locality.  Often times, working sets will tend to follow a power law,
\vspace {-0.3pc}
\begin{equation}
\label{ref-wset-eq}
W(t) = \alpha t^{\beta}.
\vspace {-0.3pc}
\end{equation}
Typically, values for $\beta$ around 0.5 are encountered in
conventional architectures~\cite{Thiebaut}. That is, the working set
grows like the square root of the time window size considered.
Observe, if $\beta\approx 1$ then the reference stream is devoid of
locality. We have found that, for frame references in {\tt GAMTEB},
$\beta$ ranges from 0.45 to 0.71, and thus exhibit fair amount of
locality.  Unfortunately (and surprisingly), instruction references in
{\tt GAMTEB} experience very poor working set behavior ($\beta =
0.99$) until the window grows large enough to encompass all of the
code blocks included in the main outer loop. {\tt MMP} generally
experiences the same frame reference locality before its working set
function shows saturation, but has excellent instruction locality due
to its small inner loop.  In this section we detail our technique for
identifying the working set behavior for frame and for instruction
references.
\vspace {-0.4pc}

\begin{twocolumntable}{frame-tab}{Frame Statistics. All numbers are average. Frame size is
measured in 8-Byte words. A number of executed threads is used as a
measure of time. A difference of length between data thread and
synchronization thread is ignored.}
\begin{center}
\begin{tabular}{||c|c|r||r|r|r|r||r||}
\hline \hline
           &           &\multicolumn{1}{|c||}{ } 
&\multicolumn{1}{|c|}{ } &\multicolumn{1}{|c|}{Frame} &\multicolumn{1}{|c|}{~Frame~} 
&\multicolumn{1}{|c||}{Number of} &\multicolumn{1}{|c||}{Context} \\
Benchmark  &Scheduling &\multicolumn{1}{|c||}{Loop Bnd}
&\multicolumn{1}{|c|}{Frame Size} &\multicolumn{1}{|c|}{~Lifetime~}   &\multicolumn{1}{|c|}{Execution}
&\multicolumn{1}{|c||}{Extant} &\multicolumn{1}{|c||}{Switch} \\
           &       &\multicolumn{1}{|c||}{ }
&\multicolumn{1}{|c|}{ }
&\multicolumn{1}{|c|}{(1000's)} &\multicolumn{1}{|c|}{Time} 
&\multicolumn{1}{|c||}{Frames} &\multicolumn{1}{|c||}{~Interval~} \\
\hline \hline
       &      &50  &80.25 &2.98 &62.92  &63.38 &2.70\\ \cline{3-8}
       &LIFO  &200 &80.86 &5.29 &62.94  &161.49 &2.86\\ \cline{3-8}
{\tt GAMTEB} &      &800  &81.61 &6.56	&64.06  &372.96 &2.65\\ \cline{2-8} \cline{2-8}
       &      &50  &81.21 &1.85 &63.91  &39.51  &1.86\\ \cline{3-8}
       &FIFO  &200 &79.06 &8.04 &62.25  &169.95 &1.40\\ \cline{3-8}
       &      &800 &80.47 &15.45 &62.27 &374.81 &1.41\\ \hline \hline
       &      &25  &17.45 &11.31 &2671.69 &18.21 &2.24\\ \cline{3-8}
       &LIFO  &50  &19.14 &20.02 &2469.50 &43.01 &2.00\\ \cline{3-8}
{\tt MMP}    &      &100 &20.30 &32.03 &2339.11 &92.25 &2.10\\ \cline{2-8} \cline{2-8}
       &      &25  &17.24 &12.31 &2512.49 &21.86 &1.48\\ \cline{3-8}
       &FIFO  &50  &18.45 &22.78 &2461.87 &43.12 &1.14\\ \cline{3-8}
       &      &100 &19.53 &46.45 &2368.63 &89.93 &1.13\\ \hline
\hline
\end{tabular}
\end{center}
\end{twocolumntable}

\subsection{Frame Reference Patterns}
\label{Frame Memory Reference}
\vspace {-1.0pc}

Table~\ref{frame-tab} shows frame reference statistics for each run.
The dynamic average frame size is reported in double words (eight
bytes), and is about 80 double words for {\tt GAMTEB} and 20 double
words for {\tt MMP}. The small variation of frame sizes among runs for
each program reflects the different path each run takes depending on a
loop bound and a scheduling policy. Frame lifetime, which is the time
from an allocation to a deallocation of a frame, is measured as a
total number of executed threads in a processor. As expected, frame
lifetime strongly depends on both scheduling policy and loop bounds.
Frame execution time is measured in threads and denotes the average
number of threads executed in a given frame during its lifetime. The
number of extant frames describes the average number of frames which
exist at any given moment in time. Note how this value is directly
proportional to the loop bound, but is relatively independent of
scheduling policy.  Context switch interval, again measured in
threads, describes the average number of threads executed in a given
frame before executing a thread for another frame. Here, a LIFO
scheduling apparently yields somewhat longer context switch intervals.

There is a significant difference between {\tt GAMTEB} and {\tt MMP}
in frame execution time to lifetime ratio.  Comparatively, {\tt MMP}
is working on smaller frames for much longer time than {\tt GAMTEB},
which implies better frame cache hit ratio for {\tt MMP}.
Paradoxically, the context switch interval is {\em longer\/} in {\tt
GAMTEB} --- surprisingly so, given that other statistics shows better
locality for {\tt MMP}.  This means simple view of treating context
switch interval as a measure of locality~\cite{WeberGupta,Anant} is
not a good predictor for fine-grain multithreading.  We need to find a
more reliable metric.
\vspace {-0.4pc}

\subsection{The Frame Working Set Function}
\vspace {-1.0pc}

We define a {\it frame working set function}, $W_{F}(t)$, as a number
of distinctive frames on which threads are executed during time window
$t$, where $t$ is measured by a dynamic count of threads.

Figure~\ref{frame-wind-fig} shows measured $W_{F}(t)$ for all of runs.
LIFO scheduling for {\tt GAMTEB} shows power law behavior, which is
independent of loop bounds. {\tt MMP's} frame working set function
shows saturation after initial rise whose slope is compatible with
{\tt GAMTEB}. Intuitively, the power law for {\tt GAMTEB} implies that
this program's working set has a ``transient'' nature: some portion of
a working set is continuously changing along with the execution of a
program, which results in a continuously growing frame working set
function.  In contrast, the saturation behavior for {\tt MMP} means
that this program's working set has a ``recurrent'' nature: the
working set is closed in the sense that same fixed number of frames
are used over a long interval of time.

The range of power constants for {\tt GAMTEB}, from 0.45 to 0.71,
overlap the values found in conventional architectures, which range
from 0.484 to 0.544~\cite{Thiebaut}, and from 0.43 to
0.75~\cite{Kobayashi}. This suggests that the amount of locality in
frame memory references may be similar to memory references in
conventional architectures at least for LIFO scheduling. This is a
nice result if holds true for most multithreaded applications because
it suggests that the local memory systems designed for cacheing stack
and heap references on sequential processors could support the demands
of frame cacheing.
\vspace {-0.4pc}

\begin{twocolumnfig}{frame-wind-fig}{Measured frame working set function $W_{F}(t)$ for (a) {\tt
GAMTEB} and (b) {\tt MMP}. This
function shows how many new frames are scheduled for execution within
a given period of time window. Time $t$ is measured by dynamically
executed number of threads. }
\centering
\begin{tabular}{cc}
\illustrationsize{fram-wind-gam-fig}{3.5in} &
\illustrationsize{fram-wind-mmp-fig}{3.5in} \\
\end{tabular}
\end{twocolumnfig}

\begin{twocolumnfig}{cblk-wind-fig}{Measured code block working set function $W_{B}(t)$ for (a)
{\tt GAMTEB} and (b) {\tt MMP}. This function shows how many new code
blocks are scheduled for execution within a given period of time
window. }
\centering
\vspace {-1.7pc}
\begin{tabular}{cc}
\illustrationsize{cblk-wind-gam-fig}{3.5in} &
\illustrationsize{cblk-wind-mmp-fig}{3.5in} \\
\end{tabular}
\end{twocolumnfig}

\nopagebreak

\begin{twocolumnfig}{thrd-wind-fig}{Measured thread working set function
$W_{T}(t)$ for (a) {\tt GAMTEB} and (b) {\tt MMP}. This function shows
how many new threads are scheduled for execution within a given time
window. }
\centering
\vspace {-1.7pc}
\begin{tabular}{cc}
\illustrationsize{thrd-wind-gam-fig}{3.5in} &
\illustrationsize{thrd-wind-mmp-fig}{3.5in} \\
\end{tabular}
\end{twocolumnfig}

\subsection{The Instruction Working Set Function}
\label{Instruction Memory Reference}
\vspace {-1.0pc}

Unfortunately, a general framework for instruction reference locality
is more complicated than for frames.  Because threads from different
frames may point to the same code, but threads from the same frame
cannot (lest they not be unique), we have to separately investigate
how code blocks and threads are scheduled. As such, we report
measurements of two functions, {\it code block working set function}
$W_{B}(t)$ and {\it thread working set function}, $W_{T}(t)$. Those
are defined as distinct numbers of code blocks or threads referenced
during a given period of time $t$, respectively.

Figure~\ref{cblk-wind-fig} shows measured $W_{B}(t)$. Since the number of
code blocks is limited, both of the curves show
saturation. {\tt GAMTEB} shows again power law behavior with $\beta$
ranging from 0.42 to 0.56. In {\tt MMP}, the working set is limited almost to
a single code block, which is the code block of the inner-most
loop.

Figure~\ref{thrd-wind-fig} shows measured $W_{T}(t)$ which shows how
temporal locality in instruction references is exhibited for each
program. Here, {\tt GAMTEB} has very poor temporal locality; $\beta$
is 0.99, which means hardly any thread is re-executed during this
period, regardless of scheduling and loop bounds. This is a
disappointing but still an understandable result because {\tt GAMTEB}
has only one outermost loop and the execution pass inside of the loop
varies on each iteration. In {\tt MMP}, though LIFO seems to maintain better
overall temporal locality, FIFO performs slightly better in small
working set region before reaching a knee around size of 5 threads.
