\section{Validation of the Cache Model}
\vspace {-1.0pc}

\begin{twocolumnfig}{fram-cache-1-fig}{Frame cache miss ratio for
(a) {\tt GAMTEB} and (b) {\tt MMP}.  ~Cache configuration: 32B/Line,
Direct Map. Dashed curves are model predictions.}
\centering
\vspace {-2.0pc}
\begin{tabular}{cc}
\illustrationsize{fram-cache-gam-1-fig}{3.5in} &
\illustrationsize{fram-cache-mmp-1-fig}{3.5in} \\
\end{tabular}
\end{twocolumnfig}

We verify the analytic model by comparing it to cache miss ratios
produced by simulation. Initialization misses are omitted from the
simulation results so that warm start miss ratio can be compared with
the model. Figure~\ref{fram-cache-1-fig} to
Figure~\ref{fram-cache-mmp-2-fig} show the results of a frame cache
simulation along with our model prediction.
Figure~\ref{fram-cache-1-fig} shows the miss ratios of 32-byte line,
direct map caches of various size for all of twelve runs.  The solid
and dashed curves show simulated data and predictions using the
analytic model, respectively. The model tracks simulated results quite
well.  For {\tt GAMTEB}, the model deviates from the simulated data in
two cases: FIFO 200 and FIFO 800.  It successfully predicts, however,
the behavior that miss ratios for these two cases start diverging
around 1KB.  The reason for this separation can be found in
Figure~\ref{frame-wind-fig}, where frame working set functions show
separation around 100-thread window.  Observe that it was impossible
to model this behavior without introducing a working set size's
dependency on a cache size. For {\tt MMP}, our model shows excellent
matches, which is surprising, given that modeling rapid changes in
miss ratios is generally quite difficult. The reason for this success
is that our model correctly captures saturation behavior of a working
set size of this program.

Results for set associative frame caches are shown in
Figure~\ref{fram-cache-gam-2-fig} and
Figure~\ref{fram-cache-mmp-2-fig}. Here, two runs for each program are
chosen. As explained in Section~\ref{Frame Cache}, our model gives
optimistic prediction for set associative caches. It can be easily
seen, however, our model captures many detailed features of almost all
curves surprisingly well.

In a frame cache, as the model correctly predicts, FIFO scheduling
increases frame cache misses. This behavior is due to poorer
working set property of FIFO scheduling. 

\begin{twocolumnfig}{fram-cache-gam-2-fig}{Associativity dependency of a
frame cache miss ratio for two runs of {\tt GAMTEB}.  (a) LIFO 200,
and (b) FIFO 200. Cache configuration: 32B/Line.}
\centering
\vspace {-2.0pc}
\begin{tabular}{cc}
\illustrationsize{fram-cache-gam-2-1-fig}{3.5in} &
\illustrationsize{fram-cache-gam-2-2-fig}{3.5in} \\
\end{tabular}
\end{twocolumnfig}

\begin{twocolumnfig}{fram-cache-mmp-2-fig}{Associativity dependency of
a frame cache miss ratio for two runs of {\tt MMP}.  (a) LIFO 50, and
(b) FIFO 50. Cache configuration: 32B/Line.}
\centering
\vspace {-2.0pc}
\begin{tabular}{cc}
\illustrationsize{fram-cache-mmp-2-1-fig}{3.5in} &
\illustrationsize{fram-cache-mmp-2-2-fig}{3.5in} \\
\end{tabular}
\end{twocolumnfig}

\begin{twocolumnfigtwo}{inst-cache-1-fig}{(a) Instruction cache miss
ratio for {\tt GAMTEB} runs.  Cache configuration: 32B/Line, Direct
Map.  (b) Associativity dependency of instruction cache miss ratio for
{\tt GAMTEB}, LIFO 200.  Cache configuration: 32B/Line.}
\centering
\vspace {-2.0pc}
\begin{tabular}{cc}
\illustrationsize{inst-cache-gam-1-1-fig}{3.5in} &
\illustrationsize{inst-cache-gam-1-2-fig}{3.5in} \\
\vspace {-0.8pc}
\end{tabular}
\end{twocolumnfigtwo}

\begin{twocolumnfigtwo}{cache-line-size-fig}{Block size dependency of
direct map cache miss ratio for {\tt GAMTEB}, LIFO 200. (a) Frame
cache, and (b) Instruction cache.}
\centering
\vspace {-1.5pc}
\begin{tabular}{cc}
\illustrationsize{fram-cache-gam-3-fig}{3.5in} &
\illustrationsize{inst-cache-gam-3-fig}{3.5in} \\
\end{tabular}
\end{twocolumnfigtwo}
\vspace {-0.3pc}

Figure~\ref{inst-cache-1-fig} shows instruction cache miss ratios.
Data for {\tt GAMTEB} runs are shown in (a), and the effect of set
associativity is shown for one of runs in (b). {\tt MMP} is not shown
here because program size is too small. The model predictions, shown
as dashed lines, match the simulation results very well.  The dotted
curves shown in Figure~\ref{inst-cache-1-fig}~(b) are the miss ratio
components corresponding to second term in
Equation~(\ref{instruction-miss-ratio-eq}), which is a miss ratio due
to lack of temporal locality in thread executions. It can be seen that
most cache misses are due to this component for mooderately sized
caches.  Note that the model successfully explains the subtle
difference in miss ratios between LIFO and FIFO scheduling in
Figure~\ref{inst-cache-1-fig}~(a).  This difference arises from the
difference in the code block working set behavior. It is impossible to
predict this instruction cache behavior using a model based on thread
properties alone or only code block properties.

Line size dependency is summarized in Figure~\ref{cache-line-size-fig}
for one run for both frame and instruction caches. The model's
prediction is again quite successful. 

All the parameters used in model calculations are given in
Section~\ref{Local Memory Reference Behavior Analysis} except
$\frac{T_{Fc}}{T_F}$ and $\frac{T_{Fi}}{T_{F}}$. These numbers for {\tt
GAMTEB} LIFO 200, for example, are 0.150 and 0.312 in 8-byte line case,
respectively. Numbers for other line sizes are calculated from these.

Aside from comparison between the simulation and the analytic model,
we must evaluate the miss ratio values themselves. It is difficult to
say whether the cache miss ratios are satisfactory or not compared to
caches in conventional execution model. We apparently need to explore
much more trace data.  There is some evidence, however, that our frame
cache may be working at least at a competitive level to caches in
conventional architectures.  That is, for {\tt MMP}, our miss ratios
are much smaller than those reported in~\cite{Monica}.  Since global
data references are one order of magnitude fewer than frame
references, our overall miss ratio for data references is quite good.
This supports the view that explicitly managing local memory, {\em
i.e.}, frames, is beneficial not only for latency tolerance, but also
for maintaining locality. For instruction caches, the stochastic
nature of thread scheduling in our execution model seems to have
substantial effect for poor miss ratio.



