\section{An Analytic Cache Model}
\vspace {-1.0pc}

In the previous section, we have shown how a working set function can
capture the locality behavior of both frame and instruction references
quite well. In this section, we will build an analytic cache model for
a fine-grain multithreaded execution. The model predicts measured
cache miss ratio quite well, as we will see in a next section.  Though
our cache model is geared toward explaining cache behavior for
multithreading, it incorporates what we believe to be a new and
general idea for using working set function as a basis for calculating
cache miss ratios. This idea is readily applicable to any cache
modeling wherever an underlying working set model applies.
\vspace {-0.4pc}

\subsection{Previous Work in Analytic Cache Modeling}
\vspace {-1.0pc}

The most important and most extensive work in modeling cache behavior
was done by Agarwal, Hennesy and Horowitz~\cite{Agarwal}. This work
proposed a full framework for understanding cache behavior for various
cache configurations including differing line sizes 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 a somewhat ad hoc manner. Although it is argued
that the choice of time granule does not have a significant effect on
the model's prediction accuracy, we believe there should be some
systematic way of deciding this parameter.  Secondly, a parameter
called the collision rate, which is measured from traces separately,
plays a key roll in their modeling. Since a working set model seems to
work as well for fine-grain multithreaded execution as it does for
sequential execution, we would like parameters to be derived directly
from a working set function.  Lastly, an LRU replacement strategy,
which has practical importance for set associative cache is not
modeled in their work.

Thiebaut has also conducted important work in this
area~\cite{Thiebaut} centered around the notion of fractal random
walks.  In fact, the power law observed in the working set functions
can be explained in terms of the self-similarity of fractal random
walks.  Unfortunately, Thiebaut limits his analytic model to fully
associative caches.

In a context of multithreaded architecture, we are aware of only the
work of Agarwal~\cite{Anant}, which is a direct descendent of work
described in \cite{Agarwal}. Agarwal treats multithreading as an
extreme case of multiprogramming, where context switch interval is not
long enough to fully bring its working set into cache. The number of
contexts is treated as an artificially controllable parameter. As we
have stated, this treatment seems to be insufficient for fine-grain
multithreading wherein data dependencies amongst threads have a first
order effect upon scheduling and thus cache behavior.
\vspace {-0.4pc}

\subsection{Working Sets for Cache Modeling}
\label{Working Set for Cache Modeling}
\vspace {-1.0pc}

A working set is a monotonically increasing function of time. Thus,
the size of a working set for a program depends on the size of the
time window, $\tau$, selected for that working set. In other words, in
an intuitive notion of working set, {\em i.e.,} where a program is
``currently'' focusing its computation, a choice of the window size
implied by ``currently'' changes the working set size completely. This
is a fundamental difficulty of modeling cache behavior based on a
notion of working sets.

We claim that ${\tau}$ should depend on cache size. Caches of
different size ``see'' memory reference streams with different ``time
resolution''. We must account for the different time resolution in
order to coherently model different sized caches.

We introduce {\it working set growth ratio} $p$ as,
\vspace {-0.4pc}
\begin{equation}
\label{ref-prob-gen-eq}
p=\tau\frac{W'(\tau)}{W(\tau),}
\vspace {-0.4pc}
\end{equation}
where $W({\tau})$ is the working set function at time ${\tau}$, a
working set size, and $W'(\tau)$ is a time $t$ derivative of
$W(\tau)$.  $p$ is the ratio of the newly referenced working set within
$W(\tau)$. That is, $(1-p)W(\tau)$ is carried over from a working set
in an adjacent $\tau$ period. For example, if $p$ is 0, the working
set function is not growing at all.  If $p$ is 1, there is no overlap
in adjacent $\tau$ period, which means the working set is increasing
linearly against time.  We can derive a general equation which
$W(\tau)$ should satisfy.
\vspace {-0.4pc}
\begin{equation}
\label{w-set-size-gen-eq}
W(\tau) ~\times ~Hit~Ratio ~= r(p) ~\times ~Cache~Capacity,
\vspace {-0.4pc}
\end{equation}
where $r(p)$ is an yet unknown function which will be defined below.
The left hand side of Equation~(\ref{w-set-size-gen-eq}) gives the
size of the cache resident portion of a working set, since the hit
ratio indicates the percent of a working set that should be cache
resident in order to insure a cache hit. Thus,
Equation~(\ref{w-set-size-gen-eq}) simply says the cache resident
portion of a current working set occupies $r(p)$ of the cache
capacity.  $(1-r(p))$ of a cache is left over from references which
have drifted out of the current working set. There are two conditions
that $r(p)$ should satisfy. $r(0)$ should be equal to 1 because the
working set size is not increasing when $p=1$. $r(1)$ should be equal
to 0 because no memory location is being reused, the left hand side
of the equation is 0. $r(p)$ can be chosen arbitrarily provided that
it satisfies these two boundary conditions. Thus we can simply set
\vspace {-0.4pc}
\begin{equation}
r(p)=1-p.
\vspace {-0.4pc}
\end{equation}

Since the miss ratio of a cache is calculated 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 boundary conditions.
Mathematically, a miss ratio is obtained as a fixed point of
self-consistent equations, which we will derive following sections.
This self-consistency requirement is the key to solve the {\em chicken
and egg} problem of determining the working set size. This technique
is applicable to choosing the working set size required to model any
cache.

We can now see why the previous study that chose $\tau$
arbitrarily~\cite{Agarwal} was successful. Suppose power law applies
to a working set function, {\em i.e.}, $W(t)={\alpha}t^{\beta}$.  The
working set growth ratio is calculated as,
\vspace {-0.4pc}
\begin{equation}
p=\tau\frac{\alpha\beta\tau^{\beta-1}}{\alpha\tau^{\beta}}=\beta.
\vspace {-0.4pc}
\end{equation}
This ratio does not depend on ${\tau}$. It means, as we will see, that
miss ratios do not depend on ${\tau}$ either. This is one example of
the self-similar behaviors generally observed in fractal random walks.
The simple power law does not apply to all cases, however.  In many cases,
there are often changes to the power constant as the time window
grows~\cite{Stone}.  Moreover, the working set function eventually shows
saturation. The working set size's dependency on the cache size must be
introduced to predict cache miss ratio for these cases correctly.
\vspace {-0.4pc}

\subsection{Frame Cache}
\label{Frame Cache}
\vspace {-1.0pc}

Now we apply the general idea from the previous section to model an
activation 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. Secondly, we assume
random mapping of {\tt FPs} on cache lines, and random memory references
within a frame. We model only the {\em warm start miss ratio}, because
we are modeling a multithreaded execution model in a single
programming environment.

We calculate the miss ratio of a frame cache by counting how many
references from a thread miss 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
\vspace {-0.4pc}
\begin{equation}
m_{F}(L, A, S)=\frac{M_{F}(L, A, S)}{T_{F}}.
\label{total-miss-ratio-1-eq}
\vspace {-0.4pc}
\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 dependencies wherever appropriate.

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

Generally, each of the $T_{Fc}$ references produces a miss, which is
known as a {\em compulsory miss}, because it is the first access to a
line in 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 {\tt 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 that
there is no data consistency problem between different frame
allocations.  Thus, we can define compulsory miss ratio $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
straightforward.

$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 total, a frame cache miss ratio is given by
\vspace {-0.4pc}
\begin{equation}
m_{F}=\frac{T_{Fc}}{T_{F}}m_{Fc}+\frac{T_{F}-T_{Fc}-T_{Ft}}{T_{F}}m_{Fi}.
\vspace {-0.4pc}
\end{equation}
\vspace {-1.2pc}

\subsubsection*{Direct Map Cache Case}
\vspace {-0.6pc}

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 the {\em cover function} $C$~\cite{Agarwal} as
\vspace {-0.4pc}
\begin{equation}
C(F)=1+\frac{F-1}{L}.
\label{cover-eq}
\vspace {-0.4pc}
\end{equation}
Suppose, on average, $R_{F}$ lines of a frame which is contained in a
working set are resident in a cache. Based on an idea in
Section~\ref{Working Set for Cache Modeling}, the 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, the working set size means the number of frames that
constitute a working set.  Thus, Equation~(\ref{w-set-size-gen-eq}) is
dictated into a following equation:
\vspace {-0.3pc}
\begin{equation}
\label{working-set-size-frame-eq}
W_{F}(\tau)R_{F}=(1-p_{F})S,
\vspace {-0.3pc}
\end{equation}
because $W_{F}(\tau)R_{F}$ gives the number of cache resident lines of
the working set. Here, the {\em frame working set growth ratio}
$p_{F}$ is given by
\vspace {-0.6pc}
\begin{equation}
\label{frame-working-set-growth-ratio-eq}
p_{F}=\tau\frac{W'_{F}(\tau)}{W_{F}(\tau)}.
\vspace {-0.4pc}
\end{equation}
Since the average fraction of a frame that is not resident in a cache
should give an average miss ratio,
\vspace {-0.4pc}
\begin{equation}
\label{frame-miss-resident-relation-eq}
m_{Fi}=1-\frac{R_{F}}{C(F).}
\vspace {-0.4pc}
\end{equation}
Thus Equation~(\ref{working-set-size-frame-eq}) gives a frame working
set size as a function of $m_{Fi}$.
\vspace {-0.5pc}
\begin{equation}
\label{working-set-size-frame-2-eq}
W_{F}(\tau)=\frac{1-p_{F}}{1-m_{Fi}}\frac{S}{C(F)}.
\vspace {-0.4pc}
\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 to see which frame it belongs 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.
\vspace {-0.4pc}
\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}.
\vspace {-0.6pc}
\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, the increment of $R_{F}$ in Poisson
approximation is given by the left hand side of the equation. The
right hand side gives a decrement of $R_{F}$, because
$\frac{R_{F}}{S}$ gives a probability that interference occurs. Thus,
\vspace {-0.4pc}
\begin{equation}
\label{frame-residence-eq}
R_{F}=\frac{C(F)}{1+\frac{p_{F}}{1-p_{F}}\frac{C(F)}{S}}.
\vspace {-0.4pc}
\end{equation}
is obtained. $m_{Fi}$ is easily derived from $R_{F}$ by using
Equation~(\ref{frame-miss-resident-relation-eq}) as 
\vspace {-0.5pc}
\begin{equation}
\label{frame-intrinsic-miss-ratio-direct-eq}
m_{Fi}=\frac{1}{1+\frac{1-p_{F}}{p_{F}}\frac{S}{C(F)}}.
\vspace {-0.4pc}
\end{equation}
It turns out that $p_{F}$ and $\frac{S}{C(F)}$ are two important
parameters that completely decide this miss ratio. If $p_{F}=1$,
$m_{Fi}=1$ as expected.

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}$. The steady state
equation for $R_{c}$ is given by
\vspace {-0.4pc}
\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}
The left hand side and the 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. The second term of right hand side is turbulence 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,
\vspace {-0.4pc}
\begin{equation}
N_{c}=\frac{1}{\tau_{L}}\sum_{t=1}^{\tau_{L}}W_{F}(t).
\vspace {-0.4pc}
\end{equation}
From Equation~(\ref{steady-frame-compulsory-eq}),
\vspace {-0.6pc}
\begin{equation}
R_{c}=\frac{C(F)}{1+\frac{N_{c}-p_{r}}{p_r}\frac{C(F)}{S}}
\vspace {-0.4pc}
\end{equation}
is obtained. $m_{Fc}$ is given by $R_{c}$ as follows,
\vspace {-0.4pc}
\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}},
\vspace {-0.6pc}
\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:
\vspace {-0.4pc}
\begin{eqnarray}
\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)
 \nonumber \\
     & &+\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).~~~
\vspace {-0.9pc}
\end{eqnarray}
For this model, we need the following average numbers and a function:
the number of frame memory references per thread $T_{F}$, the number
of compulsory references $T_{Fc}$, number of frame references that are
covered within a thread $T_{Ft}$, the size of a frame $F$, the 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$ statically.  Thus only $\tau_{L}$
and $W_{F}(t)$ are the dynamic components of our modeling.
\vspace {-1.2pc}

\subsubsection*{Set Associative Cache Case}
\vspace {-0.6pc}

We model an LRU set associative cache by again neglecting
self-interference on a cache set. Though it was a fairly good
assumption for direct map caches, it is not necessarily a good
assumption for set associative caches, because $S$ decreases as $A$
increases for a same size of cache. We use this assumption, however,
because it gives us good insight into the cache behavior simply.
Self-interference can be introduced into a model quite easily, but is
more complex. Note this assumption gives an optimistic miss ratio when
inappropriately applied.

First of all, a self-consistency equation for the frame working set in
this case is given as,
\vspace {-0.4pc}
\begin{equation}
\label{working-set-size-frame-associative-eq}
W_{F}(\tau)=\frac{(1-p_{F})}{1-m_{Fi}}\frac{AS}{C(F)}.
\vspace {-0.4pc}
\end{equation}
we divide $R_{F}$ into $R_{F}(1)$ to $R_{F}(A)$, depending on the
position in an LRU stack of a corresponding line. For example,
$R_{F}(1)$ is a number of cache resident lines marked most recently
used. We solve following steady state equations for each component of
$R_{F}$.
\vspace {-0.4pc}
\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)},
\vspace {-0.9pc}
\end{eqnarray}
where $1~<~i~{\leq}~A$. The left hand sides give increments of
$R_{F}$'s, while the right hand sides give decrements.
Equation~(\ref{steady-frame-set-1-eq}) is basically the 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,
\vspace {-0.4pc}
\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).
\vspace {-0.6pc}
\end{eqnarray}
Since $R_{F}$ is given by a sum of this series, $m_{Fi}$ is obtained
by using Equation~(\ref{frame-miss-resident-relation-eq}) as, simply,
\vspace {-0.3pc}
\begin{equation}
\label{frame-intrinsic-miss-ration-set-eq}
m_{Fi}(L, A, S)=m_{Fi}^A(L, 1, S),
\vspace {-0.3pc}
\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 $S$ lines.

The compulsory miss ratio can be calculated in a similar manner.  The
result is
\vspace {-0.3pc}
\begin{equation}
\label{frame-compulsory-miss-ration-set-eq}
m_{Fc}(L, A, S)=m_{Fc}^A(L, 1, S).
\vspace {-0.4pc}
\end{equation}
\vspace {-0.8pc}
 
\subsection{Instruction Cache}
\label{Instruction Cache}
\vspace {-1.0pc}

An instruction cache needs small changes in modeling because of two
kinds of locality components that should be considered separately (see
Section~\ref{Instruction Memory Reference}). We will show how two
kinds of working set functions, 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 {\em instruction cache miss
ratio} $m_{I}$ again by counting how many references miss a cache out
of $T_{I}$ references.  We neglect compulsory misses in an instruction
cache in order to simplify the notation, since compulsory misses are a
negligible component in any practical program. Since a thread occupies
consecutive $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,
\vspace {-0.4pc}
\begin{equation}
\label{inst-miss-ratio-1-eq}
m_{I}=\frac{C(T_{I})}{T_{I}}m_{Ii},
\vspace {-0.4pc}
\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 divided 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.
\vspace {-0.4pc}
\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\},
\vspace {-1.2pc}
\end{eqnarray}
where $N_{T}$ is the average number of threads in a code blocks, and B
is the 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, the 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}$, respectively.  Since
$C_{T}(T_{I})$ and $C_{B}(T_{I})$ does not overlap each other, a self-
consistency equation to give working set size and its measurement time
$\tau$ is
\vspace {-0.2pc}
\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, each of {\em working set growth ratios} $p_{B}$ and $p_{T}$ is
defined as
\vspace {-0.4pc}
\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)}.
\vspace {-0.3pc}
\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
\vspace {-0.4pc}
\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}.~~~
\vspace {-0.4pc}
\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 the $C_{B}(T_{I})$ portion of a code block. If it does,
cache resident portion increases from $R_{B}$ to $C_{B}(T_{I})$. The
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 the working set may cause interference. In
Equation~(\ref{steady-state-inst-t-eq}), the 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
\vspace {-0.4pc}
\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}}.
\vspace {-0.4pc}
\end{eqnarray}
Thus an instruction cache miss ratio $m_{I}$ is given as 
\vspace {-0.1pc}
\begin{eqnarray}
\label{instruction-miss-ratio-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})}} \nonumber \\
      & &+\frac{C_{T}(T_{I})}{T_{I}}
        \frac{1}{1+\frac{p_{T}}{1-p_{B}}\frac{S}{C(T_{I})}}
\vspace {-0.6pc}
\end{eqnarray}

Set associativity is modeled in a same manner as a frame cache. The
miss ratio is obtained as follows.
\vspace {-0.1pc}
\begin{eqnarray}
\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
\nonumber \\ 
+\frac{C_{T}(T_{I})}{T_{I}}\left(
\frac{1}{1+\frac{p_{T}}{1-p_{B}}\frac{S}{C(T_{I})}}\right)^A
\vspace {-0.6pc}
\end{eqnarray}

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

