\documentclass[11pt, twoside]{article}
\usepackage{amsmath}
\usepackage{calc}
\usepackage{ifthen}
\input{homework}

\begin{document}

\solutions{4}

\begin{problems}
\bigskip

\problem{Branch Prediction}
\medskip

\begin{problemparts}
\problempart{Two-Level Adaptive Branch Prediction}

(two tablesd are attached, one demonstrating the computation with a
history bit as requested, and one demonstrating the computation
without it, which was used in the following answer.

We got 9 mispredictions (although 2 of those were initial
mispredictions that had to happen no matter what scheme was used,
since the BP bits were not initialized to anything useful).

Now, when comparing this scheme (with the history bit) to a scheme
that does not use a history bit, we can draw several conclusions.
First of all, it does not help at all for the exact situtation we had
on the problem set. That is, in both cases, we had nine
mispredictions, and in exactly the same place (see attached tables).
HOWEVER, that does not mean that in all cases the history bit and an
extra set of BP bits are useless. What it does mean is that the for
the particular algorithm AND the particular choice of strings, it was
not helpful.

For other situtations, the history bit is very useful (along with the
extra set of BP bits).  For example, a best-case situtation for the
hsitory bit involves branches that alternate, with the previous branch
dictating which is the next branch to take.  That is, say we have five
branches in a big loop, thus:

\begin{center}\begin{tabular}{l}
A \\
A1 \\
A2 \\
B \\
B1 \\ 
B2\\
C \\
C1 \\
C2 \\
(goto A) \\
\end{tabular}\end{center}

And the following rules:
\begin{enumerate}
\item If the branch is true, goto the 2 line, else continue onto the 1
line (that is, if A was true, it would jump to line A2).
\item If A is true, then the next call of B is usually false, and vice-versa.
\item if B is true, then the next call of C is usually false, and vice-versa.
\item if C is true, then the next call of A is usually false, and vice-versa.
\end{enumerate}

It is easy to see that a likely run of this algorithm has alternating
branching and non-branching, all dependent on whether we branched
before (i.e. the hsitory bit is an almost perfect predictor of whether
we branch or not).  After a few iterations, the BP bits will reflect
the following info:  if we branched on the previous branch, then do not branch now,
and if we didn't, then do branch.  If we did not have a history bit,
the single-set BP bits would be less useful (since at every branch, what
we did last time is EXACTLY NOT what we will do this time around), and
when using 2 bits, this means 50\% error, and if only using one bit,
it means 100\% error rate.

So, it all depends on the program being executed, and the type of data
the program receives. In the homework, the program had a relationship
from B1 to B2, but none from B2 to B1, and so the history bit was not
very useful. In the counterexample above, the history bit had a
profound effect on the prediction.  When designing the chip, it is
important to analyze the type of code which will be run upon it to
decide whether the extra processing and storage overheads are worth
the potential improvements in speed.
\end{problemparts}
%%%%%%%%%  Problem 2

\problem{Microbenchmark for Characterizing Caches}
\medskip

\begin{problemparts}
\problempart{Analysis of the Benchmark}

\begin{enumerate}
\item {\bf $R \leq C$} : Already solved in the problem set.
\[ T_{avg} \approx T_{base} \]

\item {\bf $R>C \text{ and } 1 \leq S < b$} : Since the stride size
is smaller than the size of a block, we know we each block we cache
will bring in more than one element we try to read. We know that
$b,S,R,C$ are all powers of two, so the stride will pick an equal
number of elements per block. There will be exactly $b/S$ addresses in
each block that interest us. When we try the $1^{st}$, we will have a
cache miss, and then for the rest ($b/S - 1$) we will have a
hit. Then, when we wrap around, the first cached block will have
already been removed since $C<R$. So, the formula we get is the
following:
\[ T_{avg} = \frac{( T_{base} + D) + (b/S - 1) T_{base}}{b/S} \]

\item {\bf $R>C \text{ and } b \leq S < R/a$} : The final formula for
this case is actually simple, but the way to compute it is rather
complex. First, we note that $b,S,R$ are all powers of 2, which means
that they divide each other perfectly.  We know we will, in total, try
and read from $R/S$ addresses. However, each sequential read will come
from a different block than the previous (or else case 2 applies). In
fact, since $S$ is a multiple of $b$ and a divisor of $R$, we know
only every $S/b$'th block will be entered into the cache (when we wrap
around, we will hit the same blocks again). There is room for exactly
$\frac{C}{ab}$ sets of blocks in the cache (assuming $a$-way set
associativity). However, we may not use all the sets in the cache. In
fact, if $S/b < C/(ab)$ then $\frac{C/(ab)}{S/b}$ of those sets are
used. Otherwise only 1 set is used (the 0'th set). We analyze the two
cases:
\begin{itemize}
\item $S \geq C/a$ : We know only 1 set is used, and we know that this
set can hold up to $a$ blocks.  We need to read $R/S$ different
addresses sequentially, and each of those addresses lie in a different
block. Therefore, we will try to fit in $R/S$ blocks in a space of $a$
blocks sequentially (and wrapping around). But we know from the
problem description that $S<R/a$ which means that $a <
R/S$. Therefore, we can't fit all the blocks, and so using LRU policy,
we will lose a block before we try to read it again. This means that
$T_{avg} = T_{base} + D$.

\item $S < C/a$ means that more than one of the sets in the cache will
be used. We still want to store $R/S$ different addresses, but this
time we will store them in $\frac{C/(ab)}{S/b} = C/Sa$ different
sets. Each of this set can hold up to $a$ blocks, so we can, in total,
hold $C/S$ different blocks.  Because of the nice divisibility of all
the variables, we know an equal number of blocks will be in every set,
and when we hit wraparound, we will be going with the same blocks
again, so we only analyze one run through $R$.  We need to store $R/S$
blocks in $C/S$ space. However, from the problem, we know that $R>C$,
which means that by the time we wrap around to get the same blocks
again, they have already been removed from the cache, so again,
$T_{avg} = T_{base} + D$.
\end{itemize}
This leaves us with the final result of
\[ T_{avg} = T_{base} + D \]

\item {\bf $R>C \text{ and } R/a \leq S \leq R/2$} : We have $R/S$
total different addresses to fit in the cache, and none of those share
the same block (since $S>b$).   We know that $R/a \leq S$ from the
description, and so $R/S \leq a$. This means that ALL the blocks will
fit into one of the sets (of size $a$ blocks) in the cache. So whether
they get distributed among the sets or if all the addresses go into
the same set in the cache, they will all fit before we wrap
around. When we wrap around, we will try to read from the same blocks,
which should still be in the cache. So, the first time we try to read,
we will have a cache miss. Then, for the rest of the benchmark, we
will have cache hits.
\[ T_{avg} = \frac{\bigl(\frac{R}{S}[T_{base} + D]\bigr) + \bigl(N -
\frac{R}{S}\bigr)T_{base}}{N}  \approx T_{base} \]
\end{enumerate}

\bigskip
\problempart{Applying the Benchmark}

From looking at the graph, this is what was learned (according to the
previous equations, and the assumption that all variables except $a$
were powers of $2$):

\begin{description}
\item[$T_{base} = 200 ns$] : This was easy to compute. When the stride
is huge (case 4) we should be at about $T_{base}$, and when the
address space is small (case 1) we should also be there. This places
it at $200 ns$.
\item[$D = 670 ns$] : This was computed since the top of the curve
(worst case) was when none of the cache hits occurred, which yields a
timing of $T_{base} + D$. From the chart, we get that to be about $870
ns$, and we can subtract the known value of $T_{base}$ from that to
get $670 ns$.
\item [$C = 64 K$] : We know that if $R \leq C$, then we will
constantly have $T_{avg} = T_{base}$. This happens for $R = 32K, 64K$,
but not for $R = 128K$, so $C = 64 K$.
\item [$a = 2$] : Case 3 and 4 tell us that we switch from the worst
case to the best case when $S$ grows to be larger than $R/a$. From
looking at the graph, when $R = 128K$, then the switchover happens at
approximately $S=64K$. This indicates that $a = 2$.  (similar things
happen for other values of $R$ as long as $R>C$).
\item [$b = 256K$] : $b$ is probably the hardest to pin down from this
graph if there is a lot of noise, since we need to calculate it from
case 2. From the formula, we know that when $b=S$, then we have just
arrived at the worst-case point. As S grows to reach this, we are
rising on the graph. Specifically, we know that when $b=2S$, then the
point on the graph is approximately at $T_{base} + 1/2 D$. The graph
has that approximate point at $128K$, and has $S = b$ at $256K$, so it
is fair to assume from the graph that $b = 256K$.
\end{description}

\end{problemparts}

\problem{TRS Description of a Pipelined AX}
\medskip

\begin{problemparts}
\problempart{Shortening the Pipeline}
Basically we combine the Execute and Memory phases.  The idea is that during
any operation where the ALU does real work (Jz and ALU Ops), the writeback is
done to a register, so memory doesn't get affected.  And, during any operation
where data memory is used (Load/Store) no address calculation is done --
therefore the ALU doesn't do any real work.  

We don't need to make any significant changes to the processor in order to
shorten the pipeline.  All we have to do is get rid of the buffer between
the execute and memory phases.  The multiplexor in the write back phase will
choose the appropriate data between ALU and Data-memory depending on the 
kind of operation that was done (let the ALU data pass through for AluOps
and Jumps and let the Memory data pass through for Load/Stores).

\problempart{More TRS's}
Here is a high level picture of our TRS modifications -- we give the 
new TRS description afterwards. 
We modify the TRS description of the processor as follows.  
\begin{enumerate}
\item We "combine" the buffers for the execute and memory phases.  In particular,
any occurence of "bsE, bsM" in the TRS description should be supplanted with
"bsEM"  (a single buffer!)

\item Anything that used to get enqueued onto the bsE now gets enqueued onto
bsEM.  Anything that gets dequeued from bsM now gets dequeued from bsEM (and
the next buffer after bsEM is bsW).

\item Remove all the "copy" rules.
\end{enumerate}
Here is the actual TRS:

\newlength{\Mylen}
\newcommand{\rulelabel}[1]{%
  \settowidth{\Mylen}{\textsf{#1:}}%
  \ifthenelse{\lengthtest{\Mylen > \labelwidth}}%
    {\parbox[b]{\labelwidth}%
       {\makebox[Opt][l]{\textsf{#1:}}\\}}%
    {\textsf{#1:}}%
  \hfil\relax}
\newenvironment{rules}
  {\begin{list}{}%
   {\renewcommand{\makelabel}{\rulelabel}%
    \setlength{\labelwidth}{90pt}%
    \setlength{\leftmargin}{40pt}%
   }%
  }%
  {\end{list}}

\begin{rules}
\item[Fetch State Rules]
Proc((ia, rf, bsD, bsEM, bsW), im, dm) 
$\rightarrow$ \\ Proc((ia+1, rf, bsD;IB(ia, inst), bsEM, bsW), im, dm) where inst=im[ia]
\item[Load Constant decode rule] 
Proc((ia, rf, IB(sia, r:=loadc(v);bsD, bsEM, bsw), im, dm) 
$\rightarrow$ \\ Proc((ia, rf, bsD, bsEM;ITB(sia, r:=v), bsW), im, dm) 
\item[Load Pc decode Rule]
Proc((ia, rf, IB(sia, r:=loadpc);bsD, bseM, bsW), im, dm) 
$\rightarrow$ \\ Proc((ia, rf, bsD, bsEM;ITB(sia, r:=sia), bsW), im, dm)
\item[Op decode rule]
Proc((ia, rf, IB(sia, r:=Op(r1, r2));bsD, bsEM, bsW), im, dm) 

if r1 $\notin$ Dest(bsEM) and r2 $\notin$ Dest(bsEM) and
r1 $\notin$ Dest(bsW) and r2 $\notin$ Dest(bsW) 
$\rightarrow$ \\ Proc((ia, rf, bsD, bsEM;ITB(sia, r:=Op(rf[r1], rf[r2]), bsW)), 
im, dm) 

\item[Jz decode rule]
Proc((ia, rf, IB(sia, r:=Jz(r1, r2));bsD, bsEM, bsW), im, dm)
if r1 $\notin$ Dest(bsEM) and r2 $\notin$ Dest(bsEM) and
r1 $\notin$ Dest(bsW) and r2 $\notin$ Dest(bsW) 
$\rightarrow$ \\ Proc((ia, rf, bsD, bsEM; ITB(sia, Jz(rf[r1], rf[r2]), bsW)), im,
dm)

\item[Load decode rule]
Proc((ia, rf, IB(sia, r:=Load(r1));bsD, bsEM, bsW), im, dm)
if r1 $\notin$ Dest(bsEM) and r1 $\notin$ Dest(bsW)
$\rightarrow$ \\ Proc((ia, rf, bsD, bsEM; ITB(sia, r:=Load(rf[r1])), bsW)), im,
dm)

\item[Store decode rule]
Proc((ia, rf, IB(sia, r:=Store(r1, r2));bsD, bsEM, bsW), im, dm)
if r1 $\notin$ Dest(bsEM) and r2 $\notin$ Dest(bsEM) and
r1 $\notin$ Dest(bsW) and r2 $\notin$ Dest(bsW) 
$\rightarrow$ \\ Proc((ia, rf, bsD, bsEM; ITB(sia, r:=Store(rf[r1], rf[r2])), bsW)), im, dm)

\item[Op execute/memory rule]
Proc((ia, rf, bsD, ITB(sia, r:=Op(v1, v2);bsEM, bsW)), im, dm)
$\rightarrow$ \\ Proc((ia, rf, bsD, bsW;ITB(sia, r:=v)), im, dm) where
v=Op(v1, v2)

\item[Jz execute/memory Rules]
Proc((ia, rf, bsD, IB(sia, r:=Jz(0, nia);bsEM, bsW)), im, dm)
$\rightarrow$ \\ Proc((ia, rf, $\epsilon$, bsEM, bsW), im, dm) \\
\\
Proc((ia, rf, bsD, IB(sia, r:=Jz(v,\_);bsEM, bsW)), im, dm) if v $\neq$ 0
$\rightarrow$ \\ Proc((ia, rf, bsD, bsEM, bsW), im, dm) 

\item[Load execute/memory Rule]
Proc((ia, rf, bsD, ITB(sia, r:= Load(a)); bsEM, bsW), im, dm) 
$\rightarrow$ \\
Proc((ia, rf, bsD, bsEM, bsW;ITB(sia, r:=v)), im, dm) where v=dm[a] 

\item[Store execute/memory Rule]
Proc((ia, rf, bsD, ITB(sia, r:= Store(a, v)); bsEM, bsW), im, dm) 
$\rightarrow$ \\
Proc((ia, rf, bsD, bsEM, bsW), im, dm[a := v]) 

\item[Writeback Rule]
Proc((ia, rf, bsD, bsEM, ITB(sia, r:=v));bsW, im, dm) 
$\rightarrow$ \\ Proc((ia, rf[r:=v], bsD, bsE, bsM, bsW), im, dm)

\end{rules}
\end{problemparts}
\end{problems}
\end{document}
