 \documentstyle[11pt]{article}
\input setup
\input macros

%%% Illustrations --from ILLUSTRATIONS.TEX
\def\illustrationfileprefix{/bk/motomura/pics/}
\def\illfileprefix{/bk/motomura/pics/}

\input{psadobe}
\def\illustration#1{\begin{center}
{\psadobe{\illustrationfileprefix#1.ps}}
\end{center}}
\def\illustrationpercent#1#2{\begin{center}
{\psadobepercent{#2}{\illustrationfileprefix#1.ps}}
\end{center}}

\title{An Analysis of Memory Reference Behavior in A Tightly Coupled
        Multithreaded Architecture}

\author{Masato Motomura\thanks{On leave from System ULSI Research
        Laboratory, Microelectronics Research Laboratories, NEC
Corporation. Phone: 81-427-71-xxxx, Fax: 81-427-71-xxxx, Email:
motomura@mel.cl.nec.co.jp}\\Gregory M.Papadopoulos\thanks{Phone:
1-617-253-2623, Fax: 1-617-253-6652, email: greg@abp.lcs.mit.edu}
\\ \\Laboratory for Computer Science    \\Masachusetts Institute of
Technology\\Cambridge, MA 02139}

\def\illustrationpercentauto#1#2{
{\psadobepercent{#2}{\illustrationfileprefix#1.ps}}
}

\date {\today}

\begin{document}
\maketitle

\begin{abstract} 
Multithreaded(MT) architecture has been drawing attention because of
its capability of hiding long memory latency by switching among
threads. In a tightly coupled MT architecture, each thread comes from
one of code blocks in a single program. Tightly coupled MT is quite
attractive because it can fully utilize fine grained parallelism that
exists in a single program.  However, possible impact of this
architecture on programs' memory reference locality has not been
studied well.  In this paper, we present the results of trace
simulation study on the locality shown in a tightly coupled MT
architecture. Results shows LRU stack locality model found in single
thread arhitectures also holds for the architecure. We discuss the
relation between parallelism and locality based on this model. The
influence of thread scheduling is also discussed. Furthermore, we
build an analitical cache model based on the analysis of the locality
behavior. The model quantitatively predicts simulated cache miss ratio
quite well. We also propose as adequate cache organization and thread
scheduling strategy to obtain a better hit ratio in a tightly coupled
MT architecture.



\end{abstract}  

%\bibliographystyle{plain}
%\pagestyle{empty}
%\markright{DRAFT: \today}

\newpage
\pagestyle{plain}

%1
\section{Introduction}
\label{Introduction}

\subsection {Paper Overview}
In this paper, we will closely investigate this issue by utilizing
both trace driven simulation and analytical method. In section 2 we
present a tightly coupled MT architecture and its execution model
which lays a basis of our study.  Section 3 describes trace driven
simulation set up. Results of the simulation that shows relation
between parallelism and locality are presented in Section 4 with an in
depth analysis. Section 5 gives an analitical cache model in a tightly
coupled MT architecture along with simulated cache miss ratios. The
model predicts simulation results quantitatively very well. Section 6
gives a thought for an adequate cache organization and a thread
execution scheduling in a tightly coupled MT architecture.

%2
\section{Tightly coupled MT execution model}

%2.1    
\subsection{*T Execution Model}
\label{*T Execution Model}

\section{Trace Driven Simulation}
Previous simulation studies of MT architecture have been always using
traces obtained by artificially interleaving reference streams from
several contexts~\cite{Weber}\cite{Agarwal-2} simply because real trace
was not available . Though this kind of approach has its meaning for
loosely coupled MT architectures, it is impossible to capture memory
reference behavior of a titghtly coupled MT model in this way.  As
explained in Section~\ref{Introduction}, context switch in the
architecuture is deeply involved in its fine grained parallel
execution model: it does not make sense to treat number of contexts or
context switch intervals as ad hoc parameters. Thus it is really
important to get real multithreaded memory reference traces for the
study of tightly coupled MT architectures. Our study, as far as the
authors know, is the first try to explore general behavior of memory
references in this architecture by utilizing real traces.

High level *T simulator has been developed at Motorola Cambridge
Research Center~\cite{Andrea} for the purpose of verifing several
aspects of *T architecture in an early stage of its design. We used
this simulator for getting memory traces, and ran our own simulator on
them to collect statistics. We first explain the *T simulator briefly.
This simulator uses Id language and TAM compiler~\cite{Culler} as its
substrate.  A program written in Id is compiled by TAM compiler into a
threaded code. TL0, a high level machine language for TAM, is used for
the genterated code. The simulator simulates dynamic scheduling of
this code in multiprocessor environment by applying a *T execution model
explained in Section~\ref{*T Execution Model}. Memory reference traces
for each processor is obtained by substituting RISC type instruction
for each of scheduled TL0 instructions. This simulator is farely high
level and is not designed for predicting absolute *T performance. Since
the purpose of our study is to explore general features found in a
tightly coupled MT architecture, this has little impact for the
quality of results.

\subsection{Charactersitics of Traces}
We ran following two benchmark programs for our study.

\begin{description}
\item[Gamteb:] An Monte carlo simulation program of photons
traversing through a carbon rod. It has one outermost loop, and the
code inside consists of banch of code blocks, whose calling path
depends on a number randomly generated for each iteration of the loop.
\item[Matrix Multiply(MMP):] A triply nested loop program calculating
multiplication of two matrixes. No blocking is used in this program.
\end{description}
We ran above programs on various system configurations, data size, and
loop bounds. We report here simulation results on 8 node
configuration, 20,000 photons for Gamteb and 600 $\times$ 600 matrix
for MMP. Three kinds of loop bounds are experimented for each program:
50, 200 and 800 for Gamteb, and 25, 50 and 100 for MMP. Note that loop
bounds in MMP is applied for all of the three loops. Furthermore, to
see how scheduling infuluence a program's memory reference behavior,
we conducted experiments on thread scheduling policies: using two kind
of scheduling policies, LIFO and FIFO, for local continuations.  A
scheduling of global continuations is fixed to FIFO in order to
maintain FIFO ordering of a network. The two programs have opposite
characteristics in a sense that Gamteb has only one loop, and MMP is
heavily looped. It is quite interesting to see how they behave
differently in accordance with variations of a loop bound and/or a
local continuation scheduling policy. In total, the number of run we
report here is 12.


(NOTE: Decralaiton of doing simulation by changing loop bound and
scheduling policy in Introduction is assumed)

Table~\ref{static-tab} summarizes static information for these two
benchmark programs. MMP's program size is about 16KB, which is
apparently too small for the purpose of instruction cache simulation.
For data cache, however, this program is a good test of locality
behavior, because it is well studied that to get high data cache hit
ratio for the program is quite tricky~\cite{Monica}. In both programs,
the average length of syncronization threads, around 5 instructions,
are considerably shorter than those of Data threads, which are well
above 10 instructions. This is an expected result from a nature of
each type of threads. The average number of syncronization threads per
code block, however, is larger than one may imagine. A compiler could
be improved to decrease this number by compiling away unnecessary
syncronization event.

\begin{table}
\begin{center}
\begin{tabular}{||c|l|r|r||}
\hline \hline
\multicolumn{2}{||c|}{Benchmark Name}   &Gamteb   &MMP \\\hline
\hline
\multicolumn{2}{||c|}{Program size (Instruction)}     &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 (Instruction)  &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}
\caption{Static information of benchmark Programs. Program sizes and
thread lengths are measured in 4-Byte RISC type instruction count.}
\label{static-tab}
\end{table}

Table~\ref{trace-length-tab} shows trace length for two runs out of 12
runs that we explore in this paper.  Other runs for each benchmark has
essencialy the same size. The traces are not the ones for all nodes
from the begining of the execution to the end of execution, mainly
because the lack of time and disk space to accomodate full traces.
Instead, we recoreded memory reference trace for one of 8 nodes until
the statistics we report later has reached stable state and the traces
are long enough for simulations of caches smaller than 64KB. For the
purpose of justifing using traces for one node, we verified that
statistics variations between nodes are negligible. We will discuss
other aspects of possible drawbacks caused by this trace collection
method wherever necessary. About the length of traces, all refereces
except I\_structure references are long enough to simulate desired
size of caches. Since I\_structure references are not a primary
concern for our local cache study, though we will report cache miss
rate result later, this lack of sufficient trace lengh is not a
problem. I\_structure references experience long network latency,
which makes caching behavior less important.

\begin{table}
\begin{center}
\begin{tabular}{||c|c|c||c|c|c|c||}
\hline \hline
Benchmark &Scheduling &Loop  &Number of &Instruction &Frame &I\_structure \\
Name      &Policy     &Bound &Threads &References &References
&References \\ \hline \hline
Gamteb &LIFO &200 &0.69M &7.95M &3.66M &0.18M\\ \hline
MMP    &LIFO &50  &0.81M &9.40M &4.60M &0.34M\\ \hline
\hline
\end{tabular}
\end{center}
\caption{Trace lengh examples.}\label{trace-length-tab}
\end{table}

Figure~\ref{proc-util-fig} shows processor utilization of each run by
dividing processor time into Data thread execution time,
Syncronization thread execution time and Idle time. This graph takes
into account only network latency for calculating Idle time. The large
fraction of idle time in MMP can be basically explained by the fact
that only a small amout of calculation is done per one I-structure
reference in this program. There isn't significant difference in
processor utilization between LIFO and FIFO scheduling, though slight
improvement can be found for Gamteb. Caution should be used in
dictating Figure~\ref{proc-util-fig} not only because high level
nature of our simulation environment but also because we are not using
full traces. As is well studied, amount of parallelism in a program,
which strongly affects idle time thorough the latency torelance
mechanism, changes a lot along phases of program
execution~\cite{Arvind}. Thus Figure~\ref{proc-util-fig} should not be
thought as predicting performance of these programs.  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}
\illustrationpercent{proc-util-fig}{60}
\caption{Processor utilization for 12 runs. The processor time is
devided into Idle time, Syncronization thread execution time and Data
thread execution time. Note that y-axis minimum is not 0.}\label{proc-util-fig}
\end{figure}

\section{Local Memory Reference Behavior Analysis}
\label{Local Memory Reference Behavior Analysis}
Since we are seeing memory references no one has seen before, it is
quite important to closely investigate into them in order to
understand cache memory behavior. In this section, frame and
instruction memory references are analyzed separately. We will show
how notion of working sets, which is a key for understanding cache
behavior in our tightly coupled architecture, can be defined for each
of two references.

\subsection{Frame Memory Reference}
\label{Frame Memory Reference}
Before seeing actual statistics we have got from the trace simulation,
it may be beneficial to overview expected relation between frame
statistics and scheduling policy or loop bounds quickly. Generally
speaking, LIFO policy schedules an execution of threads by depth first
order in a frame activation tree explained in Section~\ref{*T
Execution Model}, whereas FIFO policy schedules it by width first
order. It means higher locality of frame references should be found in
LIFO scheduling than FIFO scheduling. Larger loop bounds increases
parallelism, thus may distract locality.

Table~\ref{frame-tab} shows frame statistics for each run. Frame size
is about 80 8-Byte words for Gamteb and 20 words for 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 life time, time from an allocation to a
deallocation of a frame measured as a total number of executed threads
in a processor, strongly depends on a scheduling policy and a loop
bound.  Since smaller life time means computation focuses on smaller
set of frames rather than keep allocating new frames, this correlation
is an expected result. There is a significant difference between
Gamteb and MMP in frame execution time to life time ratio. Here frame
execution time is a number of thread executed relative to that frame
during its life time. Comparatively, MMP is working on smaller size of
frame for much longer time than Gamteb, which implicates better frame
cache hit ratio for MMP. A number of extant frames, i.e., an average
number of allocated frames at a time, strongly depends on loop bounds
as frame life time does.  However, it does not show any significant
difference among two schedulings. The rightmost column shows context
switch interval according to a definition given in Section~\ref{*T
Execution Model}. Apparently LIFO scheduling gives longer interval,
which is again an expected result. One thing to note here is that the
fact context switch interval in Gamteb is longer than MMP. It is
surprising given that other statistics shows better locality for MMP.
This means simple view of treating context switch interval as a
measure of locality~\cite{Weber}\cite{Agarwal-2} does not work in our
MT model. We should find another metric of locality. 

\begin{table}
\begin{center}
\begin{tabular}{||c|c|r||r|r|r|r||r||}
\hline \hline
Benchmark &Scheduling &\multicolumn{1}{|c||}{Loop}  &\multicolumn{1}{|c|}{Frame}
&\multicolumn{1}{|c|}{Frame} &\multicolumn{1}{|c|}{Frame} 
&\multicolumn{1}{|c||}{Num. of} &\multicolumn{1}{|c||}{Context} \\
           &       &\multicolumn{1}{|c||}{  } &\multicolumn{1}{|c|}{  }
&\multicolumn{1}{|c|}{Life}   &\multicolumn{1}{|c|}{Exec.}
&\multicolumn{1}{|c||}{Extant} &\multicolumn{1}{|c||}{switch} \\
Name       &Policy &\multicolumn{1}{|c||}{Bound}
&\multicolumn{1}{|c|}{Size}
&\multicolumn{1}{|c|}{Time} &\multicolumn{1}{|c|}{Time} 
&\multicolumn{1}{|c||}{Frames} &\multicolumn{1}{|c||}{Interval} \\
\hline \hline
       &      &50  &80.25 &2975.81 &62.92  &63.38 &2.70\\ \cline{3-8}
       &LIFO  &200 &80.86 &5294.50 &62.94  &161.49 &2.86\\ \cline{3-8}
Gamteb &      &800 &81.61 &6559.92 &64.06  &372.96 &2.65\\ \cline{2-8} \cline{2-8}
       &      &50  &81.21 &1846.34 &63.91  &39.51  &1.86\\ \cline{3-8}
       &FIFO  &200 &79.06 &8044.61 &62.25  &169.95 &1.40\\ \cline{3-8}
       &      &800 &80.47 &15445.56 &62.27 &374.81 &1.41\\ \hline \hline
       &      &25  &17.45 &11306.96 &2671.69 &18.21 &2.24\\ \cline{3-8}
       &LIFO  &50  &19.14 &20018.77 &2469.50 &43.01 &2.00\\ \cline{3-8}
MMP    &      &100 &20.30 &32025.45 &2339.11 &92.25 &2.10\\ \cline{2-8} \cline{2-8}
       &      &25  &17.24 &12311.56 &2512.49 &21.86 &1.48\\ \cline{3-8}
       &FIFO  &50  &18.45 &22778.21 &2461.87 &43.12 &1.14\\ \cline{3-8}
       &      &100 &19.53 &46450.58 &2368.63 &89.93 &1.13\\ \hline
\hline
\end{tabular}
\end{center}
\caption{Frame Statistics. All numbers are average. Frame size is
measured in 8-Byte word. A number of executed threads is used as a
measure of time. A difference of length between data thread and
syncronization thread is ignored.}\label{frame-tab}
\end{table}

What kind of locality can we expect for frame references? This is the
fundamental question we want to answer here. As is well known, there
are two kinds of locality generally found in any memory references:
spatial locality and temporal locality. A frame can be seen as a
mechnism to maintain spatial locality of data references in parallel
executions of a program, since it is a small set of local storage that
is used during an invocation of a code block. It means both spatial
and temporal locality will be maintained well, if frame memory
references are focused around a few set of frames. In other words, the
queston posted above is reduced to a question about temporal locality
among frame pointers (FPs) in dynamically scheduled continuations.

One interesting way of investigating this temporal locality is to see
correlation between a frame being referenced and a frame referenced in
recent past. For this sake, we measured frame LRU stack jump
probabilities. Here, a frame LRU (Least Recently Used) stack is
defined as a stack which records fixed amount of FPs from most
recently used ones. The higher the jump probalilities for recently
used frames are, the more temporal locality a program will experience.
This way of investigating locality in frame references is analogas to
a tequeneque used for studying paging
behavior~\cite{Turner}\cite{Kobayashi}.  Figure~\ref{frame-lru-1-fig}
shows results of the measurement for the LRU stack of 50 deep. The
result for both programs are quite telling about nature of their
locality.  For Gamteb, especially in LIFO scheduling, power law
behavior between jump probability and stack depth is observed. The
power constant is about -2.1. Surprisingly, at least at a first
glance, this constatnt is almost indepentent on loop bounds. Too large
loop bound allocates frames more than necessary, as apparent from
Table~\ref{frame-tab}, however, a locality of frame reference itself
is not affected in this case. This can be understood as a consequence
of depth first execution of LIFO scheduling, though it is still a
little surprising that fixed FIFO scheduling for global continuation
seems to have a little impact on this characteristics.  For FIFO
scheduling, the power law applies less acurately and a behavior for
each loop bound shows difference as they deviate from the power law.
The loop bound dependency is quite natural. MMP shows more complicated
curves: simple structure of a program manifest itself in abnormalies
in the jump probabilities.  However, these curves are generally
characterized by initial rather constant probalities, a sharp drop
after that and a bump following them. The constant portion extends to
deeper region as a loop bound is increasedand scheduling is changed
from LIFO to FIFO.

\begin{figure}
\begin{tabular}{lr}
\illustrationpercentauto{fram-lru-gam-fig}{47} &
\illustrationpercentauto{fram-lru-mmp-fig}{47} \\
\end{tabular}
\caption{Frame LRU stack jump probability for (a) Gamteb and (b)
MMP. }
\label{frame-lru-1-fig}
\end{figure}
%splot >>>>>> -tx -0.7; -2x -3.8

Figure~\ref{frame-lru-2-fig} provides a more detailed view of a same
probability for one run from each program's runs. In this Figure, the
probability is devided into four categories by a combination of two
conditions: from which type of thread and to which type of thread. It
can be seen that Data thread shows better locality than syncronization
thread in both programs: jump probability to a data thread is higher
than that to a syncronization thread in recently used frames,
regardless of which type of thread is being executed. This reflects
stocastic nature of syncronization thread execution.  Syncronization
thread is executed mostly in response to a message arrived from
network.

\begin{figure}[t]
\begin{tabular}{lr}
\illustrationpercentauto{fram-sd-lru-gam-fig}{47} &
\illustrationpercentauto{fram-sd-lru-mmp-fig}{47} \\
\end{tabular}
\caption{Frame LRU stack jump probability for (a) Gamteb LIFO 200 and
(b) MMP LIFO 50. Jump probability is categorized into 4 curves,
depending on data thread or syncronization thread.}
\label{frame-lru-2-fig}
\end{figure}

Figure~\ref{frame-lru-1-fig} and \ref{frame-lru-2-fig} shows that an
execution of threads tends to have some set of frames on which threads
are intensively scheduled. This tells us a working set model, which is
well etsablished as a memory reference model for conventional
architectures~\cite{Denning}, holds also for frame memory reference
behavior in our parallel architecture. Here 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 Gamteb
shows again power law behavior, which does not depend on loop bounds
neither. MMP's frame working set function shows saturation after
initial rise whose slope is compatible with Gamteb. Intuitively, the
power law for Gamteb implicates that this program's working set has
``transient'' nature: some portion of a working set is continuously
changing along with an execution of a program, which results in a
continuously growing frame working set function.  On the otherhand,
saturation behavior for MMP means that this program's working set has
``recurrent'' nature: the working set is rather closed in a sense that
same fixed number of frames are used for some interval of time.

It is easy to find direct correlation between frame LRU stack jump
probabilities and frame working set functions. If you rotate a
Figure~\ref{frame-wind-fig} for 90 degrees, you will find similar
curves to Figure~\ref{frame-lru-1-fig} with smoother charactersitics.
For instance, saturation of MMP's working set size around 10 frames
can be understood as a direct consequence of the fact that jump
probabilities for this program drops around stack depth 10. Actually,
working set function can be derived from LRU stack jump
probabilities by simple calculations as shown in~\cite{Kobayashi}.
Let $J_{i}$ be a jump probability to depth $i$ of a frame LRU stack.
The required time for a working set to grow size of n, which
corresponds to an inverse function of a $W_{F}(t)$, is calculated as,
\[\sum_{j=1}^{n} \frac{1}{1-\sum_{i=1}^{j}J_{i}}.\]
Calculation of this equation fit measured curves farely well.

The range of power constant for Gamteb, from 0.42 to 0.55 overlaps the
values found in conventional architectures, which ranges from 0.484 to
0.544~\cite{Thiebaut}. This implicates locality level in frame memory
reference is about the same as memory references in conventional
architectures, though data points are not enough to judge. One thing
to note is that we are seeing only frame references which corresponds
to stack references in conventional architectures whereas above
numbers for conventional architectures incude all memory references.


\begin{figure}[t]
\begin{tabular}{lr}
\illustrationpercentauto{fram-wind-gam-fig}{47} &
\illustrationpercentauto{fram-wind-mmp-fig}{47} \\
\end{tabular}
\caption{Measured frame working set function $W_{F}(t)$ for (a) Gamteb and (b) 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. }
\label{frame-wind-fig}
\end{figure}

\subsection{Instruction Memory Reference}
\label{Instruction Memory Reference}
For instruction memory references, scheduling influence should have
diffent aspect from the infuluence for frame memory references.
Intuitively, there was no chance that FIFO policy works better for
frame reference because of its width first scheduling nature. However,
at least there seems to be a chance that FIFO works better for
maintaining locality for instruction references, because in our
parallel execution model, same code block might be invocated in
parallel, which might assist instruction reference locality in FIFO
scheduling.

What is a good way to see locality of reference for instructions?
Unfortunately, there is no single framework as a frame in a former
case. A code block gives us a good measure of spatical locality, but
not for temporal locality. The reason for this difference is quite
simple: threads that belong to a same code block and a same frame
never share a code itself though they share a frame as a common
resource. Thus in order to see locality behavior in instruction
references, we have to separately investigate how code block and
threads are scheduled. We will report measurement of two functions,
{\it code block working set function} $W_{C}(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.  Though we measured corresponding LRU stack jump
probabilities, we omit the results here because their direct
relationship with working set function has already been clarified.

Figure~\ref{cblk-wind-fig} shows measured $W_{C}(t)$. Since number of
code blocks is small and limited number, both of the curves show
saturation. Gamteb shows again power law behavior with lower power
constant ranges from 4.0? to 5.0?. In MMP, working set is limited to
almost 1 code block, which may be a code block inside of inner most
loop, for a long period. From this figure, it can be seen that FIFO
shows poor spatial locality in both cases. This can be understood in
following way. Threads which have same frame pointer are guarandeed to
belong same code block. So locality of frame reference is almost
directly dictated for locality in code block references, though as
explained above, this only gurantees a spatial locality. 

\begin{figure}[t]
\begin{tabular}{lr}
\illustrationpercentauto{cblk-wind-gam-fig}{47} &
\illustrationpercentauto{cblk-wind-mmp-fig}{47} \\
\end{tabular}
\caption{Measured code block working set function $W_{C}(t)$ for (a) Gamteb and (b) MMP. This
function shows how many new code blocks are scheduled for execution within
a given period of time window. }
\label{cblk-wind-fig}
\end{figure}

Figure~\ref{thrd-wind-fig} shows measured $W_{t}(t)$ which shows how
temporal locality in instruction references is exibited for each
program. It is easy to find out poor temporal locality for Gamteb. The
power constant here, 0.992, is almost 1.0, which means nearly zero
thread is re-executed during this period, regardless of scheduling and
loop bounds. This is a disappointing but still understandable result
because Gamteb has only one outermost loop and the execution pass
inside of the loop varies on each iteration. In MMP, though LIFO seems
to be working better for maintaining temporal locality in overall,
FIFO performs slightly better in small working set region before
reaching a knee around size of 5 threads. This could be attributed to
an argument in the begging of this section. Though it is invisible
from the figure, actually there is slight improvement in Gamteb too.

We will see how these two locality component affect instruction cache
miss ratio in Section~\ref{Instruction Cache}.


\begin{figure}[t]
\begin{tabular}{lr}
\illustrationpercentauto{thrd-wind-gam-fig}{47} &
\illustrationpercentauto{thrd-wind-mmp-fig}{47} \\
\end{tabular}
\caption{Measured thread working set function $W_{t}(t)$ for (a) Gamteb and (b) MMP. This
function shows how many new threads are scheduled for execution within
a given period of time window. }
\label{thrd-wind-fig}
\end{figure}

\section{Tightly coupled Multithread Cache Model}

In Section~\ref{Local Memory Reference Behavior Analysis}, we have
shown working set function can capture locality behavior of both frame
and instruction reference quite well. In this section, we will buid up
analytical cache model for a tightly coupled MT architecture. This
model explains measured cache miss ratio quite well, as we will see in
a next section. Though our cache model is geared toward explaining
cache behavior in a tightly coupled MT architecture, it incorporates
new and general idea for using working set function as a basis for
calculating cache miss ratio. This idea is readily applicable to any
cache modeling whereever working set model applies.

\subsection{Previous Work}

The most important and most extensive work in modeling cache behavior
was done by Agarwal, Hennesy and Horowitz~\cite{Agarwal-1}. This work
proposed full framework for understanding cache behavior for various
cache configurations including changing line size and associativity.
Though this work gives us good insight into cache behavior, we believe
several points are yet to be solved by this model. First of all, a
time granule, which they used for measuring a working set size, was
chosen in an ad hoc manner. Though they claimed the choice of time
granule does not affect model's predection much, we believe there
should be some systematic way of deciding this parameter. If a working
set is measured by some ambiguous parameter, the meaning of working
set itself is also ambiguous. Secondly, one parameter named collision
rate, which is measured from traces separately, plays a key roll in
their modeling. Since working set model is proven to work well for
tightly coupled multithreaded architecture as well as conventional
architectures, we want parameters to be derived directly from a
working set function.  Lastly, LRU algorithm, which has practical
importance for set associative cache is not modeled in their work.

Another important work was reported in \cite{Thiebaut}. This work
introduced notion of fractal random walk in the field of cache
modeling for the first time. Actually, the power law we observed in
LRU stack jump probabilities and in working set functions can be
explained by this concept. Our programs show behavior of fractal
random walk, just programs in conventional architectures do. The cache
model proposed in the paper is superior in a respect that it relates
cache miss ratio directly to working set funciton.  However, only a
model for fully associative cache was proposed in this paper.

In a context of multithreaded architecture, there has been only one
work of cache modeling \cite{Agarwal-2}. This work ins a direct
descendent of work described in \cite{Agarwal-1}. In this work,
multithreading is treated as an extreme case of multiprograming, where
context switch interval is not long enough to fully bring its working
set into cache. Number of context is treated as an artificiatlly
controlable parameter. We already stated that this treatement is not
applicable for our target architecture.

\subsection{Working Set for Cache Modeling}
\label{Working Set for Cache Modeling}
We start our cache modeling effort with an observation of a notion of
working set. This section serves for supplying general idea of our work
for readers. Accuracy of terms is sacrificed for this purpose, only in
this section.

As we saw in Section~\ref{Local Memory Reference Behavior Analysis},
and is well known~\cite{Denning}, working set function is a
continuously growing function of time. This is simply because a
program touches new memory localitions as its execution proceeds. This
means size of a working set for a program depends on how long it is
measured. In other words, in an intuitive notion of working set, i.e.,
where program is ``currently'' focusing its computation, a choice of
how ``currently'' changes working set size completely. This is a
fundamental difficulty in building perspective cache model based on a
notion of working set, which has not been tackled well in previous
works.

An important claim we make here is that a time interval for measuring
a working set size, $\tau$, should vary depending on cache size.  As
an intuitive example, suppose we have a memory reference stream which
referes, say, 4 consequtive memory locations cyclicaly, i.e, $00$,
$01$, $10$, $11$, $00$, $01$, $10$, $11$, $\cdot \cdot
\cdot \cdot$.  Let's assume we decide to measure working set at, say,
10-reference interval. Thus working set size of this reference stream
is 4, because there are only 4 distinct memory locations that are
referenced.  If our ``cache'' can memorize more than 4 locations, it
can succesfully accomodate this reference pattern. However, if our
``cache'' size is less than 4, this cache continuously misses. The
cyclic reference pattern does not help at all for the size of cache
less than the pattern cycle. It has no meaning whether working set
size defined through above ad hoc way is 4 or, say, 10.  Put it in
another way, different size of cache ``sees'' references with
different ``time resolution''. A smaller size of cache sees more
detailed, shorter period pattern of memory reference streams than a
larger size of cache.  Decision of $\tau$ should incorporate this
fundamental view in order to model various size of caches coherently.

We introduce {\it working set growth rate} $p$ as
\begin{equation}
\label{ref-prob-gen-eq}
p=\tau\frac{W'(\tau)}{W(\tau),}
\end{equation}
where $W({\tau})$ is a working set function at time ${\tau}$, which
gives a working set size by definition of $\tau$, $W'(\tau)$ is a time
$t$ derivative of $W(\tau)$.  $p$ gives a ratio of newly referenced
working set witin $W(\tau)$. That is, $(1-p)W(\tau)$ out of $W(\tau)$
is carried over from a working set in an adjacent $\tau$ period. If
$p$ is 0, for example, a working set function is not growing at all.
If $p$ is 1, there is no overlap in adjacent $\tau$ period, which
means working set is increasing linearly against time.  We can derive
a general equation which $W(\tau)$ should satisfy as follows:
\begin{equation}
\label{w-set-size-gen-eq}
W(\tau) ~\times ~(1-~Miss~Ratio) ~= r(p) ~\times ~Cache~Capacity,
\end{equation}
where $r(p)$ is an unknown function we are going to find below.  The
left hand side of Equation~(\ref{w-set-size-gen-eq}) gives size of
cache resident portion of a working set, because hit ratio means that
amont of portion out of a working set should be cache resident in
order to experience cache hit. Thus,
Equation~(\ref{w-set-size-gen-eq}) simply says a cache resident porion
of a current working set occupies $r(p)$ of cache capacity. $(1-r(p))$
fraction of a cache is left over from references which have drifted
out from the current working set. There are two conditions that $r(p)$
should satisify. $r(0)$ should be equal to 1 because working set size
is not increasing when $p=1$. On the other hand, $r(1)$ should be
equal to 0 because no memory location is being reused, i.e, left hand
side of the equation is 0. $r(p)$ can be chosen arbitrarily provided
that it satisfies these two boundaly conditions. Thus we can set
simply
\begin{equation}
r(p)=1-p.
\end{equation}

Since miss ratio of a cache is going to be calculated by using
$W(\tau)$, Equation~(\ref{w-set-size-gen-eq}) is actually a self
consistency equation that $W(\tau)$ and a miss ratio should satisfy.
This is why we could choose $r(p)$ freely under two boundaly
conditions. Mathematicaly, a miss ratio is obtained as a fixed point
of self consistent of equations, which we will derive following
sections.

This self consistency requirement has been a key to solve the {\it
chiken and egg} type problem of deciding working set size.  This
technieque is applicable to dicide any type of working set size
required in modeling a cache behavior.

Here we can preview why previous study that decides $\tau$ in an ad
hoc way~\cite{Agarwal-1} has made success. Suppose power law applies
to a working set function, i.e., $W(t)={\alpha}t^{\beta}$. Above
defined working set growth ratio is calculated as,
\begin{equation}
p=\tau\frac{\alpha\beta\tau^{\beta-1}}{\alpha\tau^{\beta}}=\beta.
\end{equation}
Thus this ratio does not depend on ${\tau}$. It means, as we will see,
a miss ratio does not depend on ${\tau}$ neither. This is one example
of a sefl-similar behaviors generally observed in fractal random
walks. However, a problem is that simple power law does not apply to
all cases. In many cases, there are often changes of power constant as
time window grows~\cite{Stone}. Moreover, working set function shows
saturation sooner or later. In order to obtain cache behavior when
working set function shows saturation for that size of cache, cache
size dependency of working set size must be introduced to predict
cache miss ratio correctly. Note that simulation results that were
compared with a model in ~\cite{Agarwal-1} did not cover this region
\cite{Stone}.

\subsection{Frame Cache}
\label{Frame Cache}
Now we apply above general idea for modeling frame cache behavior.
Several mean values that characterize frame reference behavior as well
as a measured frame working set function are used for the model. We
make several assumptions. First, we assume there is no
self-interference on a cache set among references that belong to a
same frame. This is a quite reasonable assumption for a direct map
cache, because it has enough number of sets in cache size ranges of
interest. This assumption is quite helpful for simplifying our frame
cache model. Secondly, we assume random mapping of FPs on cache lines,
and random memory references within a frame. We model only {\it warm
start miss ratio} here, because we are modeling a multithreaded
execution model in a single programming environment.

We calculate miss ratio of a frame cache by counting how many
references from a thread miss a cache on average. Let $T_{F}$ be an
average number of total frame references from a thread, and $M_{F}$ be
an average number of missed references in a thread. A {\it frame cache miss
ratio} $m_{F}$ is defined as
\begin{equation}
m_{F}(L, A, S)=\frac{M_{F}(L, A, S)}{T_{F}}.
\label{total-miss-ratio-1-eq}
\end{equation}
Here, we use $L$ for a line length measured in bytes, $A$ for
associativity in a set, and $S$ for number of sets, so that cache
capacity is expressed as $LAS$. In the following discussion, we omit
L, A, S dependency wherever approapriate in order to keep notational
simplicity.

$T_{F}$ can be divided into three components: $T_{Fc}$, average number
of first references to cache lines of a frame during that frame
allocation, $T_{Ft}$, average number of references to cache lines
which were referenced by other instructions in a same thread, and
$T_{Fi}$, average number of references to cache lines which were not
referensed in a same thread.

Generally, each of $T_{Fc}$ references directly gives a miss, which is
known as {\it compulsory miss}, because it is the first access to a
line any way. It doesn't hold for our case, however, because $T_{Fc}$
is a first request to frame locations within one allocation of a
frame, and a same FP might have been used before the current
allocation. This possible previous allocation might have left several
lines in a cache which reduce compulsory misses. Since a frame is a
local storage of a code block invocation, a compiler guarantees there
is no data consistency problem between different frame allocations.
Thus, we can define compulsory miss rate $m_{Fc}$, so that
$m_{Fc}T_{Fc}$ is a number of compulsory miss references.

$T_{Ft}$ is a measure of temporal and spatial locality within one
thread.  It is independent of dynamic execution of threads, because a
thread is guaranteed to execute until its completion. Each of $T_{Ft}$
references gives a hit.  To get $T_{Ft}$ from a compiled code is quite
straitforward.

$T_{Fi}$ is a most important source of misses, which are known as {\it
interference misses}.  We define $m_{Fi}$ as an {\it interference miss
ratio}, so that $m_{Fi}T_{Fi}$ gives a number of interference miss
references.  In totl, a frame cache miss ratio is given by
\begin{equation}
m_{F}=\frac{T_{Fc}}{T_{F}}m_{Fc}+\frac{T_{F}-T_{Fc}-T_{Ft}}{T_{F}}m_{Fi}.
\end{equation}


\subsubsection*{Direct Map Cache Case}
We first show the calculation of $m_{Fi}$ for a direct map cache. 
Let $F$ be an average frame size measured in bytes. The number of
cache lines required to hold a frame size of $F$ is calculated by
using {\it cover function} $C$~\cite{Agarwal-1} as
\begin{equation}
C(F)=1+\frac{F-1}{L}.
\label{cover-eq}
\end{equation}
Suppose $R_{F}$ lines of a frame within a working set are resident in
a cache on average. Based on an idea in Section~\ref{Working Set for
Cache Modeling}, working set size for frame references is defined as a
frame working set function measured at some time interval $\tau$,
$W_{F}(\tau)$. By definition of this function, working set size in
this case means a number of frames that constitute a working set.
Thus, Equation~(\ref{w-set-size-gen-eq}) is dictated into a following
equation:
\begin{equation}
\label{working-set-size-frame-eq}
W_{F}(\tau)R_{F}=(1-p_{F})S,
\end{equation}
because $W_{F}(\tau)R_{F}$ gives a number of cache resident lines of a
working set. Here, {\it frame working set growth ratio} $p_{F}$ is
given by
\begin{equation}
\label{frame-working-set-growth-ratio-eq}
p_{F}=\tau\frac{W'_{F}(\tau)}{W_{F}(\tau)}.
\end{equation}
Since average fraction of a frame that is not resident in a cache
gives an average ratio where references to that frame misses,
\begin{equation}
\label{frame-miss-resident-relation-eq}
m_{Fi}=1-\frac{R_{F}}{C(F)}
\end{equation}
holds. Thus Equation~(\ref{working-set-size-frame-eq}) gives a
frame working set size as a function of $m_{Fi}$.
\begin{equation}
\label{working-set-size-frame-2-eq}
W_{F}(\tau)=\frac{1-p_{F}}{1-m_{Fi}}\frac{S}{C(F)}.
\end{equation}
As explained in Section~\ref{Working Set for Cache Modeling},
Equation~(\ref{working-set-size-frame-2-eq}) is a self-consistency
equation that $m_{Fi}$ and $W_{F}(\tau)$ should satisfy. 

Now, we want to derive an equation which gives $R_{F}$. Look at one
thread and see which frame does this thread belong to. If it belongs
to a frame within a working set, $R_{F}$ will increase because of
addition of new lines. If not, $R_{F}$ will decrease because of
interference in a cache. By requiring these increment and decrement
for $R_{F}$ to be balance at a steady state, following equation is
obtained.
\begin{equation}
\label{steady-frame-direct-eq}
T_{Fi}(1-p_{F})\left(1-\frac{R_{F}}{C(F)}\right)=T_{Fi}p_{F}\frac{R_{F}}{S}.
\end{equation}
Here, $\left(1-\frac{R_{F}}{C(F)}\right)$ gives a cache non-resident
fraction of a frame in a working set. Since there are $T_{Fi}$
references from a thread, increment of $R_{F}$ in Poisson
approximation is given by the left hand side of the equation. Right
hand side gives a decrement of $R_{F}$, because $\frac{R_{F}}{S}$ gives a
probability that intereference occurs. Thus, 
\begin{equation}
\label{frame-residence-eq}
R_{F}=\frac{C(F)}{1+\frac{p_{F}}{1-p_{F}}\frac{C(F)}{S}}.
\end{equation}
is obtained. $m_{Fi}$ is easily derived from $R_{F}$ by using
Equation~(\ref{frame-miss-resident-relation-eq}) as 
\begin{equation}
\label{frame-intrinsic-miss-ratio-direct-eq}
m_{Fi}=\frac{1}{1+\frac{1-p_{F}}{p_{F}}\frac{S}{C(F)}}.
\end{equation}
It turns out that $p_{F}$ and $\frac{S}{C(F)}$ are two important
parameters that completely decides this miss ratio. If $p_{F}=1$,
$m_{Fi}=1$ as expected. Note, again, that $pF$ is calculated from
Equation~(\ref{frame-working-set-growth-ratio-eq}) and
Equation~(\ref{working-set-size-frame-2-eq}) through the self
consistency mechanism.

Calculation of compulsory miss ratio $m_{Fc}$ can be carried out in a
similar manner. Let $R_{c}$ be an average number of cache lines which
hold a frame when that frame is deallocated. Suppose the probability
of reuse of the deallocated frame is $p_{r}$. Steady state equation
for $R_{c}$ is given by
\begin{equation}
\label{steady-frame-compulsory-eq}
C(F)p_{r}\left(1-\frac{R_{c}}{C(F)}\right)=C(F)(1-p_{r})\frac{R_{c}}{S}
+C(F)(N_{c}-1)\frac{R_{c}}{S}.
\end{equation}
Left hand side and a first term of the right hand side can be
understood in a same fashion as corresponding terms in
Equation~(\ref{steady-frame-direct-eq}). These terms are multiplied by
$C(F)$ because $C(F)$ distinct lines are referenced within a frame
allocation. Second term of right hand side is turbulance from other
concurrently executing frames. Here, $N_{c}$ is the average number of
frames in a working set during frame life time interval $\tau_{L}$.
Thus,
\begin{equation}
N_{c}=\frac{1}{\tau_{L}}\sum_{t=1}^{\tau_{L}}W_{F}(t).
\end{equation}
From Equation~(\ref{steady-frame-compulsory-eq}),
\begin{equation}
R_{c}=\frac{C(F)}{1+\frac{N_{c}-p_{r}}{p_r}\frac{C(F)}{S}}
\end{equation}
is obtained. $m_{Fc}$ is given by $R_{c}$ as follows,
\begin{eqnarray}
m_{Fc}&=&p_{r}\left(1-\frac{R_{c}}{C(F)}\right)+(1-p_{r}) \nonumber \\
      &=&1-\frac{p_{r}}{1+\frac{N_{c}-p_{r}}{p_{r}}\frac{C(F)}{S}},
\end{eqnarray}
because all of $T_{Fc}$ references will miss a cache if a frame is
allocated for the first time.

In summary, we get a complete frame cache miss ratio for direct map
cache as follows:
\begin{equation}
\label{frame-direct-miss-ratio-eq}
m_{F}=\frac{T_{Fc}}{T_{F}}\left(1-\frac{p_{r}}{1+\frac{N_{c}-p_{r}}{p_{r}}\frac{C(F)}{S}}\right)
+\left(1-\frac{T_{Fc}}{T_{F}}-\frac{T_{Ft}}{T_{F}}\right)
\left(\frac{1}{1+\frac{1-p_{F}}{p_{F}}\frac{S}{C(F)}}\right).
\end{equation}
For this model, we need following average numbers and a function: a
number of frame memory references per thread $T_{F}$, number of
compulsory references $T_{Fc}$, number of frame references that are
covered within a thread $T_{Ft}$, size of a frame $F$, frame life time
$\tau_{L}$, and a frame working set function $W_{F}(t)$. Note that
these parameters and function does not depend on any cache parameter.
Though $T_{Ft}$ depends on line size, this dependency is calculated by
using a cover function $C$. $T_{F}$ and $T_{Ft}$ is obtained by static
analysis. Moreover, it is also possible to get a good estimate of
$T_{Fc}$ and $F$ staticaly.  Thus only $\tau_{L}$ and $W_{F}(t)$ are
the dynamic components of our modeling.

\subsubsection*{Set Associative Cache Case}
We model an LRU set associative cache again by neglecting
self-interference on a cache set. Though it was a farely good
assumption for direct map cache, this is not necessarily good for set
associative cache, because $S$ decreases as $A$ increases for a same
size of cache. We use this assumption, however, because it gives us a
good insight on cache behavior with a simple mathematical form.
Self-interference can be introduced into a model quite easily, but
gives more compicated form. Note this assumption gives optimistic miss
ratio when inappropriately applied.

First of all, a self consistency equation for frame working set in
this case is given as,
\begin{equation}
\label{working-set-size-frame-associative-eq}
W_{F}(\tau)=\frac{(1-p_{F})}{1-m_{Fi}}\frac{AS}{C(F)}.
\end{equation}
we divide $R_{F}$ into $R_{F}(1)$ to $R_{F}(A)$ depending on position
in an LRU stack of a corresponding line. Here, for example, $R_{F}(1)$
is a number of cache resident lines marked most reacently used. We
solve following steady state equations for each component of $R_{F}$.
\begin{eqnarray}
\label{steady-frame-set-1-eq}
T_{Fi}(1-p_{F})\left(1-\frac{R_{F}(1)}{C(F)}\right)&=&T_{Fi}p_{F}\frac{R_{F}(1)}{S},
\\
\label{steady-frame-set-2-eq}
T_{Fi}p_{F}\frac{R_{F}(i-1)}{S}&=&T_{Fi}p_{F}\frac{R_{F}(i)}{S}+T_{Fi}(1-p_{F})\frac{R_{F}(i)}{C(F)},
\end{eqnarray}
where $1~<~i~{\leq}~A$. Left hand sides give increment of $R_{F}$'s,
while right hand side gives decrement.
Equation~(\ref{steady-frame-set-1-eq}) is basicaly a same equation as
Equation~(\ref{steady-frame-direct-eq}). In
Equation~(\ref{steady-frame-set-2-eq}), increment is due to
probability of interference on a set in $R_{F}(i-1)$, which causes a
line to shift its position in an LRU stack from $i-1$ to $i$.
Decrement is due to same interference on $R_{F}(i)$, a first term, and
a reference to a line in $R_{F}(i)$ itself which makes that line be
brought into top of an LRU stack.
Equations~(\ref{steady-frame-set-1-eq}) and
~(\ref{steady-frame-set-2-eq}) are easily solved as,
\begin{eqnarray}
\label{frame-residence-set-1-eq}
R_{F}(1)&=&\frac{C(F)}{1+\frac{p_{F}}{1-p_{F}}\frac{C(F)}{S}},\\
\label{frame-residence-set-2-eq}
R_{F}(i)&=&\left(1-\frac{R_{F}(1)}{C(F)}\right)R_{F}(i-1).
\end{eqnarray}
Since $R_{F}$ is given by a sum of this series, $m_{Fi}$ is calculated
by using Equation~(\ref{frame-miss-resident-relation-eq}) as
\begin{equation}
\label{frame-intrinsic-miss-ration-set-eq}
m_{Fi}(L, A, S)=m_{Fi}^A(L, 1, \frac{S}{A}),
\end{equation} 
which means $m_{Fi}$ for a cache of set associativity $A$ is given by
a power $A$ of $m_{Fi}$ of a direct map cache which has $\frac{S}{A}$
lines. 

Compulsory miss ratio can be calculated in a similar manner.  The
result is
\begin{equation}
\label{frame-intrinsic-miss-ration-set-eq}
m_{Fc}(L, A, S)=m_{Fc}^A(L, 1, \frac{S}{A}).
\end{equation}
 
\subsection{Instruction Cache}
\label{Instruction Cache}

Instruction cache needs a little different modeling because of two
kinds of locality component that should be considered separetely (see
Section~\ref{Instruction Memory Reference}). In this section, we will
show how two kinds of working set function, code block and thread, are
incorporated into instruction cache modeling.

Let $T_{I}$ be an average number of instruction reference in a thread,
i.e., thread length. We will calculate {\it instruction cache miss
ratio} $m_{I}$ again by counting how many references miss a cache out
of $T_{I}$ references.  We neglect compulsory miss in order to
simplify the notation, because compulsory misses are a negligible
component in any practical program for an instruction cache. Since a
thread occupies consective $T_{I}$ locations in an instruction memory,
the number of cache lines which cover one thread is given by
$C(T_{I})$.  Thus, $m_{I}$ is calculated as,
\begin{equation}
\label{inst-miss-ratio-1-eq}
m_{I}=\frac{C(T_{I})}{T_{I}}m_{Ii},
\end{equation}
where $m_{Ii}$ is an interference miss ratio for an instruction cache. 

We need some preparation in order to calculate $m_{Ii}$. First
$C(T_{I})$ is devided into two components: one is an average number of
lines that are shared by two or more threads, $C_{B}(T_{I})$, and the
other is an average number of lines that belong only to one thread,
$C_{T}(T_{I})$. These are derived as follows.
\begin{eqnarray}
\label{thread-cover-t-eq}
C_{T}(T_{I})&=&\frac{1}{N_{T}}C(B),\\
\label{thread-cover-c-eq}
C_{B}(T_{I})&=&\frac{1}{N_{T}}\left\{N_{T}C(T_{I})-C(B)\right\},
\end{eqnarray}
where $N_{T}$ is an average number of threads in a code block, and B
is an average size of a code block. This division of $C(T_{I})$ is
quite important in order to model an instruction cache behavior
correctly. A cache line in $C_{T}(T_{I})$ is never brought into a
cache unless a thread which occupies that line is executed, whereas a
line in $C_{0}(T_{I})$ can be brought by several threads in a code
block.  In other words, locality that helps increasing cache residency
of $C_{T}(T_{I})$ is not of code blocks but of threads. On the other
hand, code block level locality plays an important role for
$C_{B}(T_{I})$.  Thus, $C_{B}(T_{I})$ and $C_{T}(T_{I})$ should be
treated in terms of how many distinct code blocks or threads have been
executed, respectively. This is why we need two kinds of working set
functions.

Now we define cache resident portion of $C_{B}(T_{I})$ and
$C_{T}(T_{I})$ as $R_{B}$ and $R_{T}$, respectivly.  Since
$C_{T}(T_{I})$ and $C_{B}(T_{I})$ does not overlap each other by their
definition, a self consistency equation to give working set size and
its measurement time $\tau$ in this case becomes as
\begin{equation}
\label{working-set-size-inst-eq}
\frac{W_{B}(\tau)N_{T}R_B}{1-p_{B}}
+\frac{W_{T}(\tau)R_T}{1-p_{T}}=S.
\end{equation}
Here, $p_{B}$ and $p_{T}$ are defined as
\begin{equation}
\label{working-set-growth-ratio-inst}
p_{B}=\tau\frac{W'_{B}(\tau)}{W_{B}(\tau)}, 
~~~~~p_{T}=\tau\frac{W'_{T}(\tau)}{W_{T}(\tau)}.
\end{equation}

As in frame cache modeling, we count increment and decrement for
$R_{B}$ and $R_{T}$ when a thread is executed. Steady state equations
for $R_{B}$ and $R_{T}$ are respectively given by
\begin{eqnarray}
\label{steady-state-inst-b-eq}
(1-p_{B})\frac{C_{B}(T_{I})}{C(B)}(C_{B}(T_{I})-R_{B})&=&p_{B}C(T_{I})\frac{R_B}{S},
\\
\label{steady-state-inst-t-eq}
(1-p_{T})(C_{T}(T_{I})-R_{T})&=&p_{B}C(T_{I})\frac{R_{T}}{S}.
\end{eqnarray}
In a left side of Equation~(\ref{steady-state-inst-b-eq}),
$\frac{C_{B}(T_{I})}{C(B)}$ gives a probability that a thread
references $C_{B}(T_{I})$ portion of a code block. If it does, cache
resident portion increases from $R_{B}$ to $C_{B}(T_{I})$ because of
consequtave nature of instruction references. Right hand side of the
same equation is multiplied by $C(T_{I})$ because any reference from a
thread which belongs to a code block outside of working set may cause
interference. In Equation~(\ref{steady-state-inst-t-eq}), right hand
side is multiplied by $p_{B}$ not $p_{T}$, because a thread which
belongs to a code block working set does not cause interference.
These equations give
\begin{eqnarray}
\label{cache-resident-inst-b-eq}
R_{B}&=&\frac{C_{B}(T_{I})}{1+\frac{1-p_{B}}{p_{B}}\frac{C(B)}{C_{B}(T_{I})}\frac{C(T_{I})}{S}},\\
\label{cache-resident-inst-t-eq}
R_{T}&=&\frac{C_{T}(T_{I})}{1+\frac{1-p_{B}}{p_{T}}\frac{C(T_{I})}{S}}.
\end{eqnarray}
Thus an instruction cache miss ratio $m_{I}$ is given as 
\begin{eqnarray}
\label{interference-miss-ratio-inst-eq}
m_{I}&=&\frac{C(T_{I})}{T_{I}}\left(1-\frac{R_{B}+R_{I}}{C(T_{I})}\right) \nonumber \\
      &=&\frac{C_{B}(T_{I})}{T_{I}}
        \frac{1}{1+\frac{p_{B}}{1-p_{B}}\frac{C_{B}(T_{I})}{C(B)}\frac{S}{C(T_{I})}}
        +\frac{C_{T}(T_{I})}{T_{I}}
        \frac{1}{1+\frac{p_{T}}{1-p_{B}}\frac{S}{C(T_{I})}}
\end{eqnarray}

Set associativity is modeled in a same manner as a frame cache. The
miss ratio is obtaind as follows.
\begin{equation}
\label{interference-miss-ratio-inst-set-eq}
m_{I}=\frac{C_{B}(T_{I})}{T_{I}}
        \left(\frac{1}{1+\frac{p_{B}}{1-p_{B}}\frac{C_{B}(T_{I})}{C(B)}\frac{S}{C(T_{I})}}\right)^A
        +\frac{C_{T}(T_{I})}{T_{I}}\left(
        \frac{1}{1+\frac{p_{T}}{1-p_{B}}\frac{S}{C(T_{I})}}\right)^A
\end{equation}

Informations required to model an instruction cache are, an average
thread length $T_{I}$, average code block size $B$, average number of
threads per code block $N_{T}$, a code block working set function
$W_{B}(t)$ and a thread working set function $W_{T}(t)$. Only dynamic
informations required are just these two woking set functions.

\section{Application of Cache Model}
We will show how our model reproduce simulatd cache miss ratio. Then
we simplify our model to predict range of cache miss ratio for a
tightly coupled MT architecture.


\subsection{Comparison with Simulated Results}

\subsection{Cache Performance Prediction}
Since we understand detailed cache behavior of multithreaded
architecture, we are free to reduce complexity of the model and see
what are the expected performances for caches in multithreaded
architecture, in general. Simplification of the model is as follows:
\begin{itemize}
\item Working set function obeys simple power low. We assume
\[W_{F}(t)=\alpha_{F}t^{\beta}_{F},\]
\[W_{B}(t)=\alpha_{B}t^{\beta}_{B},\]
\[W_{T}(t)=\alpha_{T}t^{\beta}_{T},\]
\item Compulsory misses for a frame cache is treated as a constant. 
\end{itemize}
As already explained in Section~\ref{Working Set for Cache Modeling},
miss ratio does not depend on $\tau$ and $W(\tau)$ when simple power
low applies. 

Figure~\ref{model-prediction-fig} shows predictions of a simplified
model for a variety of choices of parameters. 

What parameters affects cache hit ratio. scheduling, etc


\newpage
\begin{thebibliography}{99}

\bibitem {Weber} Wolf-Dietrich Weber and Anoop Gupta.  Exploaring the
Benefits of Multiple Hardware Contexts in a Multiprocessor
Architecture: Preliminary Results. In Proceedings of 16th Annual
International Symposium on Computer Architecture, IEEE, June 1989, pp.
273-280.

\bibitem {Agarwal-1} Anant Agarwal, Mark Horowitz and John Hennessy.
An Analytical Cache Model. ACM Transactions on Coumputer Systems, Vol.
7, No. 2, May 1989, Pages 184-215.

\bibitem {Agarwal-2} Anant Agarwal. Performance Tradeoffs in
Multithreaded Processors. IEEE Transactions on Parallel and
Distributed Systems, Vol. 3, No. 5, September 1992, Pages 525-539.

\bibitem {Monica} Monica S. Lam, Edward E. Rothberg and Michael E.
Wolf. The Cache Performance and Optimizations of Blocked Algorithms.
In Proceedings of 19th Annual International Symposium on Computer
Architecture, IEEE, June 1991, pp. 63-74.

\bibitem {Culler} David E. Culler, Anurag Sah, Klaus Erik Shauser,
Thorsten von Eicken and Jhen Wawrzynek. Fine-grain Parallelism with
Minimal Hardware Suppot: A Compiler-Controlled Threadsd Abstract
Machine. In Proceedings of 19th Annual International Symposium on
Computer Architecture, IEEE, June 1991, pp. 164-175.

\bibitem {Saavedra} Rafael H. Saavedra-Barrera, David E. Culler and
Thorstem von Eicken. Analysis of multithreaded architectures for
parallel computing. In proceeding of 2nd Annual ACM Symposium on
Parallel Algorithms and Architectures, IEEE, July, 1990, pp.169-177.

\bibitem {Turner} Rollins Turner and Bill Strecker. Use of the LRU
Stack Depth Distribution for Simulation of Paging Behavior.
Communications of the ACM, Vol. 20, No. 11, November 1977, Pages
795-798. 

\bibitem {Denning} Peter J. Denning. The Working Set Model for Program
Behavior. Communications of the ACM, Vol. 11, No. 5, November 1968,
Pages 323-333.

\bibitem {Kobayashi} Makoto Kobayashi and Myron H. MacDougall. The
Stack Grouth Function: Cache Line Reference Models. IEEE Transactions
on Computers, Vol. 38, No.6, June 1989, Pages 798-805.

\bibitem {Thiebaut} Dominique Thiebaut. On the Fractal Dimension of
Computer Programs and its Application to the Prediction of the Cache
Miss Ratio. IEEE Transactions on Computers, Vol. 38, No.7, July 1989,
Pages 1012-1026.

\bibitem{Stone} Harold S. Stone. High-Performance Computer
Architecture. 2nd-edition. Addison-Wesley, 1990, page 81.


\end{thebibliography}


\end{document}
