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

\begin{document}

\solutions{2}

\begin{problems}
\bigskip

\problem{What is a Delayed Branch?}
\medskip

\begin{problemparts}
\problempart{What happens when you delay a branch?}

For this problem, we assume r0 is a source of '0' bits, which suggests
that all the BEQZ instructions are functionally non-conditional
indirect branches. What basically happens here is that the next value
for the PC is delayed by one instruction, so that when a branch
happens, the next instruction gets executed anyway (potentially
allowing a new future value for the PC). Tracing the execution of the
program out, we get the following sequence of instructions:

i0, i1, i2, i4, i5, i3, i4, i3, i3, i3, i3, i3, i3, i3, i3, i3, i3 ...

\problempart{What does it really mean to delay a branch?}
TRS can be used to demonstrate what happens in delayed-branch DLX. We
create a new TRS description for AX/D. Most importantly, we need to
keep track of the next value for the PC, which allows us to execute an
instruction following a branch and then branch. (There were several
ways to define this system, we picked to encode this state as part of
the process state, since it seemed most correct).
\begin{eqnarray*}
\text{SYS} & \equiv & \text{Sys(MEM, PROC)} \\
\text{MEM} & \equiv & \epsilon \| \text{ Cell(a,v) } | \text{ MEM} \\
\text{PROC} & \equiv & \text{Proc(PC, NEXT\_PC, RF, PROG)} \\
\text{PC} & \equiv & \text{ ia } \\
\text{NEXT\_PC} & \equiv & \text{PC} \\
\text{RF} & \equiv & \epsilon \| \text{ Reg(r,v) } | \text{ RF } \\
\text{PROG} & \equiv & \epsilon \| \text{ Inst(ia, INST) } | \text{ PROG}
\end{eqnarray*}
There were no changes required to the actual instruction set, and this
is how the instructions were redone:

\begin{trs-rules}

\item [Loadc Rule] \mbox{} \\
Proc(ia, next\_ia, rf, prog) {\it if} prog[ia] = r := Loadc[v] \\
$\longrightarrow$ Proc(next\_ia, next\_ia+1, rf[r:=v], prog)

\item [Loadpc Rule] \mbox{} \\
Proc(ia, next\_ia, rf, prog) {\it if} prog[ia] = r := Loadpc \\
$\longrightarrow$ Proc(next\_ia, next\_ia+1, rf[r:=ia], prog)

\item [Op Rule] \mbox{} \\
Proc(ia, next\_ia, rf, prog) {\it if} prog[ia] = r := Op($r_1$, $r_2$) \\
$\longrightarrow$ Proc(next\_ia, next\_ia+1, rf[r:=v], prog)
\hfill where v = Op(rf[$r_1$], rf[$r_2$])

\item [JzJump Rule] \mbox{} \\
Proc(ia, next\_ia, rf, prog) {\it if} prog[ia] = Jz($r_1$, $r_2$) {\it
and} rf[$r_1$] = 0\\
$\longrightarrow$ Proc(next\_ia, next\_ia:=rf[$r_2$], rf, prog)

\item [Jz-NoJump Rule] \mbox{} \\
Proc(ia, next\_ia, rf, prog) {\it if} prog[ia] = Jz($r_1$, $r_2$) {\it
and} rf[$r_1$] $\neq$ 0\\
$\longrightarrow$ Proc(next\_ia, next\_ia+1, rf, prog)

\item [Load Rule] \mbox{} \\
Sys(m, Proc(ia, next\_ia, rf, prog)) {\it if} prog[ia] = r := Load($r_1$) \\
$\longrightarrow$ Sys(m, Proc(next\_ia, next\_ia+1, rf[r:=m[a]],
prog)) \hfill where a=rf[$r_1$]

\item [Store Rule] \mbox{} \\
Sys(m, Proc(ia, next\_ia, rf, prog)) {\it if} prog[ia] = r :=
Store($r_1$, $r_2$) \\
$\longrightarrow$ Sys(m[a:=rf[$r_2$]], Proc(next\_ia, next\_ia+1, rf,
prog)) \hfill where a=rf[$r_1$]
\end{trs-rules}

The above set specifies the rules for the system. The Next\_PC allows
a delay before processing the jump instructions, although can cause
inconsistencies if there are multiple jump instructions in a
sequence. There are also extensions that can be done should a stack be
supported, but the changes are similar to those in problem set 1, so
were not covered here.

\end{problemparts}

\end{problems}
\end{document}
