\documentclass[11pt]{article}

\usepackage{simplemargins}
\setleftmargin{1in}
\setrightmargin{1in}
\settopmargin{2in}
\setbottommargin{1in}

\def\choice#1{\left\{ \begin{array}{ll} #1 \end{array} \right.}
\def\AND{\mbox{ and }}
\def\OR{\mbox{ or }}
\def\NOT{\mbox{ not }}
\def\RULE#1#2#3{{\bf #1} \\
                \begin{tabular}{ll}
                        & $\mathrm{#2}$ \\
                  $\to$ & $\mathrm{#3}$ \\
                \end{tabular}}
\def\BIGRULE#1#2#3#4#5{
                     {\bf #1} \\
                     \begin{tabular}{ll}
                              & $\mathrm{#2}$ \\
                              & $\mathrm{#3}$ \\
                        $\to$ & $\mathrm{#4}$ \\
                              & $\mathrm{#5}$ \\
                     \end{tabular}}
%\def\RULE#1#2#3{
%  \noindent\bf #1 \\
%  \phantom{$\to$} \em $\mathrm{#2}$ \\
%           $\to$  \em $\mathrm{#3}$ \\ \relax
%}
\def\IF{\mbox{\quad \it\ if\ }}
\def\WHERE{\mbox{\quad \it where }}





\title{6.823 Problem Set 5}
\author{Chris Laas}
\date{April 24, 2000}

\pagestyle{myheadings}
\markright{Chris Laas \hfil 6.823 \hfil 4/24/2000}

\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{\arabic{enumii}}

\begin{document}
\maketitle




\section*{Problem 5-1}
\begin{enumerate}

\item%(a)

\RULE{Jz-Jump Rule}{
  Proc(nextPc, pc, rf, im) \IF im[pc] = Jz(r_c, r_a) \AND rf[r_c] = 0
}{
  Proc(rf[r_a], nextPc, rf, im)
}

\RULE{Op Rule}{
  Proc(nextPc, pc, rf, im) \IF im[pc] = r:= Op(r_1, r_2)
}{
  Proc(nextPc+1, nextPc, rf[r:=v, im])
    \WHERE v = \underline{Op}(rf[r_1], rf[r_2])
}


\item%(b)

\RULE{Jz-Jump Rule, non-empty bsE}{
  Proc(pc, rf, bsD, Itb(ia_J, r:=Jz(0,npc)); Itb(ia_E,insn_E); bsE, bsM, bsW, im)
}{
  Proc(npc, rf, \varepsilon, Itb(ia_E,insn_E), bsM, bsW, im)
}

\RULE{Jz-Jump Rule, empty bsE}{
  Proc(pc, rf, Itb(ia_D,insn_D); bsD, Itb(ia_J, r:=Jz(0,npc)), bsM, bsW, im)
}{
  Proc(npc, rf, Itb(ia_D,insn_D), \varepsilon, bsM, bsW, im)
}


\item%(c)

If both bsD and bsE are empty, i.e. the pipeline behind the Jz is
empty, then the processor still won't stall, because the fetch rule
will fetch an instruction, causing bsD to become non-empty, causing
the second of the above rules to fire.


\item%(d)

The state given doesn't give us a reasonable way to signify the
validity of jumpPc:  instructions need some way of telling whether
they should jump to jumpPc.  Here, I simply use the symbol
$\varepsilon$ to signify ``no jump''; it would be more explicit to use
a separate jumpPc-valid-bit, which is equivalent.

\RULE{Jz-Jump Rule}{
  Proc(pc, rf, bsD, Itb(ia_J, r:=Jz(0,npc)); bsE, jumpPc, bsM, bsW, im)
}{
  Proc(pc, rf, bsD, bsE, npc, bsM, bsW, im)
}

\RULE{Op-Execute Rule, with Jump}{
  Proc(pc, rf, bsD, Itb(ia, r:=Op(v_1,v_2)); bsE, jumpPc, bsM, bsW, im)
}{
  Proc(jumpPc, rf, bsD, bsE, \varepsilon, bsM;Itb(ia, r:=v), bsW, im) \WHERE v=Op(v_1,v_2)
}

\RULE{Op-Execute Rule, no Jump}{
  Proc(pc, rf, bsD, Itb(ia, r:=Op(v_1,v_2)); bsE, \varepsilon, bsM, bsW, im)
}{
  Proc(pc, rf, bsD, bsE, \varepsilon, bsM;Itb(ia, r:=v), bsW, im) \WHERE v=Op(v_1,v_2)
}


\end{enumerate}
\newpage




\section*{Problem 5-2}
\begin{enumerate}

\item%(a)

In general, the BTB performs a very simple prediction heuristic; then,
when the BHT is used to refine the prediction by looking at the branch
history, the BTB's prediction might be overruled.  Then, finally, the
execute stage either confirms the branch prediction or nullifies it,
killing everything in the prediction pipeline as well.

UpdateBTB and UpdateBHT are only used in the execute stage.
UpdateBTB(btb, pc, ppc, Taken/NotTaken) updates the BTB by putting the
entry $\mathrm{< pc, ppc, Valid >}$ in slot pc[r-1:0] if Taken, or by
putting the entry $\mathrm{< pc, -, NotValid >}$ in slot pc[r-1:0] if
NotTaken and the slot currently has pc as its tag.  UpdateBHT(bht, pc,
p, Taken/NotTaken) updates entry pc[s-1:0] in the usual way, based on
the old value p and the jump result Taken/NotTaken.


If the BTB is hit, then the predicted next PC goes into PC and into bsPC.

\BIGRULE{BTB Hit Rule}{
  Proc(pc, btb, bsPC, imem, bht, bsI, rf)
}{
  \begin{array}{l}
   \mathrm{\IF v = Valid \AND pc = entryPC } \\
   \mathrm{\quad \WHERE \langle entryPC, targetPC, v \rangle = btb[pc[r-1:0]] }
  \end{array}
}{
  Proc(targetPC, btb, enq(\langle pc, targetPC \rangle, bsPC), imem, bht, bsI, rf)
}{
}

If, upon fetch, the BHT agrees with the BTB that the branch will be
Taken or NotTaken, then the pipeline is undisturbed.

\BIGRULE{Fetch Rule for BZ, BHT Agrees with BTB on Taken}{
  Proc(pc, btb, bsPC, imem, bht, bsI, rf)
}{
  \begin{array}{l}
   \mathrm{\IF imem[ipc] = BZ(r_c, offset) \AND (p = WT \OR p = ST) \AND ipc + offset = ippc } \\
   \mathrm{\quad \WHERE \langle ipc, ippc \rangle = first(bsPC) \AND p = bht[ipc[s-1:0]] } \\
  \end{array}
}{
  Proc(pc, btb, deq(bsPC), imem, bht, enq(\langle ipc, ippc, p, BZ(r_c, offset) \rangle, bsI), rf)
}{
}

\BIGRULE{Fetch Rule for BZ, BHT Agrees with BTB on NotTaken}{
  Proc(pc, btb, bsPC, imem, bht, bsI, rf)
}{
  \begin{array}{l}
   \mathrm{\IF imem[ipc] = BZ(r_c, offset) \AND (p = WNT \OR p = SNT) \AND ipc + 1 = ippc } \\
   \mathrm{\quad \WHERE \langle ipc, ippc \rangle = first(bsPC) \AND p = bht[ipc[s-1:0]] } \\
  \end{array}
}{
  Proc(pc, btb, deq(bsPC), imem, bht, enq(\langle ipc, ippc, p, BZ(r_c, offset) \rangle, bsI), rf)
}{
}

If, on the other hand, the BHT disagrees with the BTB's prediction (or
if, for some unusual reason, the BTB predicts neither ipc+1 nor
ipc+offset), the PC pipeline before the BTB is flushed (killing one
potential instruction), the PC is reset to what the BHT thinks it
should be, and the branch is passed on to the execute unit.

\BIGRULE{Fetch Rule for BZ, BHT says Taken but BTB doesn't}{
  Proc(pc, btb, bsPC, imem, bht, bsI, rf)
}{
  \begin{array}{l}
   \mathrm{\IF imem[ipc] = BZ(r_c, offset) \AND (p = WT \OR p = ST) \AND ipc + offset \neq ippc } \\
   \mathrm{\quad \WHERE \langle ipc, ippc \rangle = first(bsPC) \AND p = bht[ipc[s-1:0]] } \\
  \end{array}
}{
  Proc(ipc+offset, btb, clear(bsPC), imem, bht, enq(\langle ipc, ippc, p, BZ(r_c, offset) \rangle, bsI), rf)
}{
}

\BIGRULE{Fetch Rule for BZ, BHT says NotTaken but BTB says Taken}{
  Proc(pc, btb, bsPC, imem, bht, bsI, rf)
}{
  \begin{array}{l}
   \mathrm{\IF imem[ipc] = BZ(r_c, offset) \AND (p = WNT \OR p = SNT) \AND ipc + 1 \neq ippc } \\
   \mathrm{\quad \WHERE \langle ipc, ippc \rangle = first(bsPC) \AND p = bht[ipc[s-1:0]] } \\
  \end{array}
}{
  Proc(ipc+1, btb, clear(bsPC), imem, bht, enq(\langle ipc, ippc, p, BZ(r_c, offset) \rangle, bsI), rf)
}{
}

There needs also be a fetch rule for Ops.

\BIGRULE{Fetch Rule for Op}{
  Proc(pc, btb, bsPC, imem, bht, bsI, rf)
}{
  \begin{array}{l}
   \mathrm{\IF imem[ipc] = Op(r_d, r_1, r_2) } \\
   \mathrm{\quad \WHERE \langle ipc, ippc \rangle = first(bsPC) } \\
  \end{array}
}{
  Proc(pc, btb, deq(bsPC), imem, bht, enq(\langle ipc, ippc, SNT, Op(r_d, r_1, r_2) \rangle, bsI), rf)
}{
}

In case we do jump and the prediction was good, we merely update the
prediction tables to reflect that.

\BIGRULE{BZ-Jump Execute Rule, Good Predict}{
  Proc(pc, btb, bsPC, imem, bht, bsI, rf)
}{
  \begin{array}{l}
   \mathrm{\IF inst = BZ(r_c, offset) \AND rf[r_c] = 0 \AND ipc + offset = ippc } \\
   \mathrm{\quad \WHERE \langle ipc, ippc, ip, inst \rangle = first(bsI) } \\
  \end{array}
}{
  Proc(pc, UpdateBTB(btb, ipc, ippc, Taken), bsPC, imem,
}{
  \quad UpdateBHT(bht, ipc, ip, Taken), deq(bsI), rf)
}

If we jump but that wasn't predicted correctly, kill the queued
instructions and PCs, jump, and update the tables.

\BIGRULE{BZ-Jump Execute Rule, Mispredict}{
  Proc(pc, btb, bsPC, imem, bht, bsI, rf)
}{
  \begin{array}{l}
   \mathrm{\IF inst = BZ(r_c, offset) \AND rf[r_c] = 0 \AND ipc + offset \neq ippc } \\
   \mathrm{\quad \WHERE \langle ipc, ippc, ip, inst \rangle = first(bsI) } \\
  \end{array}
}{
  Proc(ipc + offset, UpdateBTB(btb, ipc, ippc, Taken), clear(bsPC), imem,
}{
  \quad UpdateBHT(bht, ipc, ip, Taken), clear(bsI), rf)
}

If we don't jump and the prediction was good, we merely update the
prediction tables to reflect that.

\BIGRULE{BZ-No-Jump Execute Rule, Good Predict}{
  Proc(pc, btb, bsPC, imem, bht, bsI, rf)
}{
  \begin{array}{l}
   \mathrm{\IF inst = BZ(r_c, offset) \AND rf[r_c] \neq 0 \AND ipc + 1 = ippc } \\
   \mathrm{\quad \WHERE \langle ipc, ippc, ip, inst \rangle = first(bsI) } \\
  \end{array}
}{
  Proc(pc, UpdateBTB(btb, ipc, ippc, NotTaken), bsPC, imem,
}{
  \quad UpdateBHT(bht, ipc, ip, NotTaken), deq(bsI), rf)
}

If we don't jump but that wasn't predicted correctly, kill the queued
instructions and PCs, change the PC to undo the jump, and update the
tables.

\BIGRULE{BZ-No-Jump Execute Rule, Mispredict}{
  Proc(pc, btb, bsPC, imem, bht, bsI, rf)
}{
  \begin{array}{l}
   \mathrm{\IF inst = BZ(r_c, offset) \AND rf[r_c] \neq 0 \AND ipc + 1 \neq ippc } \\
   \mathrm{\quad \WHERE \langle ipc, ippc, ip, inst \rangle = first(bsI) } \\
  \end{array}
}{
  Proc(ipc + 1, UpdateBTB(btb, ipc, ippc, NotTaken), clear(bsPC), imem,
}{
  \quad UpdateBHT(bht, ipc, ip, NotTaken), clear(bsI), rf)
}



\item%(b)

This is an improvement over a BTB alone, because the BHT stage (which
comes pretty much for free, since it's in parallel with the IMEM
lookup) can prevent certain (previously) pessimal branching patterns
from hosing the branch prediction.

On the other hand, it is also an improvement over a BHT alone, because
if there were no BTB, the branch predictor would have to wait on the
IMEM lookup to determine the branch target to feed to the PC when the
BHT speculates Taken.


\item%(c)

We could easily move the BHT into the earlier stage, as the only input
to the BHT is the PC.  This might actually improve performance, as one
PC wouldn't need to be killed when a BTB Taken prediction is overruled
by a BHT NotTaken prediction.


\item%(d)

Moving the BTB to the later stage (containing the IMEM) would
completely defeat its purpose, which is to provide the branch target
before it is available from the IMEM.


\item%(e)

We don't know for certain whether the branch is taken until the
Execute stage, which is the last stage in this pipeline.


\end{enumerate}
\newpage







\section*{Problem 5-3}
\begin{enumerate}

\item%(a)

The problem here is that, when the memory returns its data response
$<t,v>$, the dispatched Load that initiated the query will no longer
exist if the ROB has been rolled back, and thus the Load-Retire rule
will not be able to fire, and thus the MPB buffer will not be able to
advance, leading to deadlock.  Possibly even worse, there might be a
{\em different} Load instruction using the tag $t$ in the ROB by then,
and it would incorrectly be given the value $v$ returned by the memory
in response to the speculative query.  This second possibility would
lead to corruption.

A simple solution would be to, before rolling back the ROB, first wait
for the memory to finish responding to all dispatched speculative
loads.

A more complicated solution would be to attempt to pluck out the
speculative queries from the PMB.  A much more complicated solution
would be to try to keep track of the tags associated with outstanding
speculative queries (so as not to reuse them in the ROB and to be able
to accept responses from the MPB).  These solutions would require much
more complicated circuitry and TRS's, and are probably not worth the
effort.


\item%(b)

Assume the Load-Dispatch rule has been changed by substituting ``$U
\notin rob_1$'' for ``$U, Jz \notin rob_1$''.  The rules for
completion of incorrectly-speculated branches must be modified to
allow for the simple solution I describe above, by not firing until
there are no dispatched speculative loads left in the ROB.  In the
following rules,
$$\mathrm{btb' = updateBTB(btb, ia, npc, taken/not taken)}$$

\BIGRULE{Ps-Jz-Jump-WrongSpec Rule}{
  Proc(pc, rf, rob_1;Itb(ia, Jz(0,npc), Sp(ppc));rob_2, btb, im)
}{
     \IF ppc \neq npc \AND D \notin rob_2
}{
  Proc(pc, rf, rob_1, btb', im)
}{
}

\BIGRULE{Ps-Jz-NoJump-WrongSpec Rule}{
  Proc(pc, rf, rob_1;Itb(ia, Jz(v,-), Sp(ppc));rob_2, btb, im)
}{
     \IF v \neq 0 \AND ppc \neq ia + 1 \AND D \notin rob_2
}{
  Proc(pc, rf, rob_1, btb', im)
}{
}

{\bf Additionally,} if one assumes that the memory subsystem processes
the PMB and the MPB atomically, and that any given memory request is
either in the PMB or the MPB at any point (i.e the memory system does
not keep requests hidden inside itself ever), then we can pluck the
speculative loads out of the PMB.  This allows us to remove the
corresponding loads from the ROB, allowing the above branch completion
rules to fire sooner.  In terms of real circuitry, this might make the
implementation of PMB much more complicated, and might not be playing
fair with the memory subsystem (which might expect the PMB and MPB to
be FIFO queues which the processor can't touch); nevertheless, the TRS
rules to do this follow.  (These new rules are in addition to the two
modified rules above.)

\BIGRULE{Ps-Jz-Jump-WrongSpec-PluckPMB Rule}{
   Sys(Proc(pc, rf, rob_1;itb_J;rob_2;itb_L;rob_3, btb, im), pmb_1;\langle{}t,Load(a)\rangle;pmb_2, mpb)
}{
     \IF itb_J = Itb(ia,Jz(0,npc),Sp(ppc)) \AND ppc \neq npc \AND itb_L = Itb(ia,t:=Load(a,D),Wr(r))
}{
  Sys(Proc(pc, rf, rob_1;itb_J;rob_2;rob_3, btb, im), pmb_1;pmb_2, mpb)
}{
}

\BIGRULE{Ps-Jz-NoJump-WrongSpec-PluckPMB Rule}{
   Sys(Proc(pc, rf, rob_1;itb_J;rob_2;itb_L;rob_3, btb, im), pmb_1;\langle{}t,Load(a)\rangle;pmb_2, mpb)
}{
   \begin{array}{l}
   \mathrm{ \IF itb_J = Itb(ia,Jz(v,-),Sp(ppc)) \AND v \neq 0 \AND ppc \neq ia+1 } \\
   \mathrm{ \quad\quad \AND itb_L = Itb(ia,t:=Load(a,D),Wr(r)) } \\
   \end{array}
}{
  Sys(Proc(pc, rf, rob_1;itb_J;rob_2;rob_3, btb, im), pmb_1;pmb_2, mpb)
}{
}


\end{enumerate}
\newpage







\section*{Problem 5-4}
\begin{enumerate}

\item%(a)

A Fence instruction can be fetched just like any normal instruction;
it is its mere presence in the ROB that affects the memory dispatch
order.  The template for a Fence instruction is Itb(pc, Fence, -).

\RULE{Ps-Fence-Fetch Rule}{
  Proc(pc, rf, rob, btb, im) \IF im[pc] = Fence
}{
  Proc(pc+1, rf, rob;Itb(pc, Fence, -), btb, im)
}


\item%(b)

In these memory access rules, the current state is
$\mathrm{ Sys(Proc(ia, rf, rob_1;irb;rob_2, btb, im), pmb, mpb) }$.
The only change from the standard version is the replacement of
``Fence,Jz $\notin rob_1$'' for ``U,Jz $\notin rob_1$'' in the
predicates for dispatching.

{\small
\begin{tabular}{|l|l|l||l|l|} \hline
\bf Rule Name   & \bf itb & \bf pmb & \bf Next itb & \bf Next pmb \\
\hline
Load-Dispatch   & Itb(ia$_1$, t:=Load(a,U),Wr(r))
  & pmb & Itb(ia$_1$, t:=Load(a,D),Wr(r)) & pmb;$\langle$t,Load(a)$\rangle$ \\
                & Fence,Jz $\notin rob_1$ &&&         \\
\hline
Store-Dispatch  & Itb(ia$_1$, t:=Store(a,v,U))
  & pmb & Itb(ia$_1$, t:=Store(a,v,D)) & pmb;$\langle$t,Store(a,v)$\rangle$ \\
                & Fence,Jz $\notin rob_1$ &&&         \\
\hline
\end{tabular}
}


\item%(c)

A Fence instruction can be retired only after all loads and stores
coming before it in program order have been retired.

\RULE{Ps-Fence-Retire Rule}{
  Proc(pc, rf, rob_1;Itb(ia, Fence, -);rob_2, btb, im)
    \IF Load,Store \notin rob_1
}{
  Proc(pc, rf, rob_1;rob_2, btb, im)
}


\end{enumerate}
\newpage





\end{document}
