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

\begin{document}

\solutions{3}

\begin{problems}
\bigskip

\problem{Programmed Pipelines}
\medskip

\begin{problemparts}
\problempart{Product of Sums}
Since the code is fairly long and possibly non-obvious, I will first
attempt to explain what is actually going on in the mess, and then
with comments attempt to make the code clear.

First of all, we were asked to make this code as speedwise-efficient
as possible. One thing to note about this system is that it is best to
have floating values on the bus which are constantly fed around than
to put them into registers.  Since multiplying takes three cycles, and
adding two, BUT also since everything is fully pipelined, it is best
to view the problem in a way more easily computed by the system. We
are being asked to compute
\[ (A[0] + B[0]) * (A[1] + B[1]) * (A[2] + B[2]) * ... * (A[n] + B[n])
\]

We can let $C[j] = (A[j] + B[j])$. We never store $C[j]$ anywhere, but
let it float on the bus and feed it into the multiplier. It is useful
to note that each $C[j]$ is completely independent of the others, and
so we can just have two counters that count up along the arrays, and
spew the arrays $A,B$ into the adders, thereby giving us a $C[j]$ ever
cycle. 

We can view this formula as computing 
\[ C[0] * C[1] * C[2] * ... * C[n] \]
However, computing this sequence of multiplications on the multiplier
will take three cycles per multiplication. Instead we use the
commutativity property of multiplication, and compute:
\[ (C[0] * C[3] * C[6] ...) * (C[1] * C[4] * C[7] ...) * (C[2] * C[5]
* C[8] ...)) \]
Which allows us to make a useful multiplication every cycle, except
for in the end, where some minor cleanup has to be performed to get
the result.

Also, since we're working with both the memory and the auxiliary
memory, we need to start reading from normal memory first, and offset
the reading from auxiliary by two.

Finally, We have to wait two cycles before we even start multiplying
anything useful, because the adder will take that long to yield us our
first sum. We use this extra time to initialize the multiplier's chain
with ones.

{\bf optimizations}: We also added one optimization. We first check
whether the length of the vector is 2. If it is, we perform a somewhat
faster computation, since we do not need this long chain. This
optimization does make the code longer, but yield faster performance
for short vectors.

Another optimization that would normally be possible is the following
short-circuit: If any of the sums were zero, quit computing and jump
to the end and output 0.  Unfortunately, the command set doesn't
actually let us TEST any value apart from the $R_x$ registers, and
those do not allow us to load any value from the bus. So this idea,
while efficient and normally a good one, is moot.


\bigskip

{\it Comments}: The following is a description (line by line) of what is going
in the code in the table.
\begin{description}
\item [lines 1,2]  Start loading the Main memory in advance. In line 1, if we notice
we only have two elements in the vectors, we short-circuit to get a faster computation.
\item [lines 3,4]  Initiated loading from the Auxiliary memory. This starts two
 phases after Main memory since it's two clock cycles faster and we want the
 outputs to coincide. We will keep reading from Main and Auxiliary memory
 until we're completely done (in fact, we will read beyond the length
 of the array, though we will not use those values -- same assumption that
 this is okay as was done in the example code). Also, we read the value '1'
prewritten into $X_1$ to initialize the multiplier.
\item [line 5]  Do the last initializing of the multiplier. Also, we finally have $A[0]$
from main memory and $B[0]$ from auxiliary, so throw them in the adder.
\item [line 6] We're just about ready to start looping. Multiplier is filled with 1's, adder is
being filled with sums of respective elements of the vector. We know we have at least three elements
to work with (we already left if not in line 1) so we enter the loop.
\item [line 7] This is the main body, where we perform everything. At this point, everything
is gliding along, new values being thrust into the adder, and the adder's output is
immediately fed into the chain of multiplications. We finally break out of this loop when we
have exhausted our data, and start performing cleanup.
\item [lines 8, 9] We start grouping our data out. There are still two value in the adder's
pipeline we need to get into the multiplication's chain, which we do here.
\item [line 10] Now we have the first of the three groups of multiplication chains
output from the multiplier. We send it into the adder to use a temporary register (we
add the output of the multiplier to $R_0$ whose value we know to be 0).
\item [line 11] The second value in the chain is thrown into a scratch register ($Y_0$).
\item [line 12] The last value in the chain is not multiplied by the first value which
is being spewed by the Adder. We only need to multiply this by the second value to get
the final output.
\item [lines 13, 14, 15] We're waiting for the output of the multiplication in line 12. When
we finally get it (line 15) we multiply it by the second group (which we stored in
scratch register $Y_0$). Then we goto 'done' where we wait for the final result and
write it out (see lines 24-26).
\item [lines 16, 17, 18] We load up the values of the two element array, but set it up so
that we get a pair, nothing, and then the second pair (this is useful for timing purposes, since
we need those two pairs output together into the multiplier).
\item [lines 19, 20, 21] We run the pairs each through the adder when they show up. The output
of the first pair is sent into a scratch register to wait for the output of the second.
\item [lines 22, 23] We ready the scratch data to coincide with the second pair's output, and
when they both show up, we send them into the multiplier. We then continue into 'done'
where the output of the multiplier is waited upon and then written out.
\item [lines 24, 25, 26] This is common to the fast and regular paths. We wait for the
output they put into the multiplier, and when we have it, we write it out into $X_0$
as per spec.
\end{description}

\fontsize{8}{10}\selectfont
\begin{tabular}{||l|c|c|c|c|c|c|c|c|c||}\hline\hline
LABEL   & MAIN & AUX  & XR & YR & XW  & YW  & ADD   & MUL   & Counters + Control \\ \hline \hline
1 init  & LDR1 & NOP  & DC & DC & NOP & NOP & DC    & DC    & $R_1$++; if $R0=2$ goto speed \\ \hline
2       & LDR1 & NOP  & DC & DC & NOP & NOP & DC    & DC    & $R_1$++ \\ \hline
3       & LDR1 & LDR2 & 1  & DC & NOP & NOP & DC    & DC    & $R_1$++, $R_2$++ \\ \hline
4       & LDR1 & LDR2 & 1  & DC & NOP & NOP & DC    & X,X   & $R_1$++, $R_2$++ \\ \hline
5       & LDR1 & LDR2 & 1  & DC & NOP & NOP & Me,Au & X,X   & $R_1$++, $R_2$++, $R_0$--- \\ \hline
6       & LDR1 & LDR2 & DC & DC & NOP & NOP & Me,Au & X,X   & $R_1$++, $R_2$++, $R_0$--- \\ \hline
7 loop  & LDR1 & LDR2 & DC & DC & NOP & NOP & Me,Au & Mu,Ad & $R_1$++, $R_2$++, $R_0$---; if $R0>0$ goto loop \\ \hline
8 end   & NOP  & NOP  & DC & DC & NOP & NOP & DC    & Mu,Ad & \\ \hline
9       & NOP  & NOP  & DC & DC & NOP & NOP & DC    & Mu,Ad & \\ \hline
10      & NOP  & NOP  & DC & DC & NOP & NOP & Mu,R0 & DC    & \\ \hline
11      & NOP  & NOP  & DC & DC & NOP & 0:= Mu & DC & DC    & \\ \hline
12      & NOP  & NOP  & DC & DC & NOP & NOP & DC    & Mu,Ad & \\ \hline
13      & NOP  & NOP  & DC & DC & NOP & NOP & DC    & DC    & \\ \hline
14      & NOP  & NOP  & DC & 0  & NOP & NOP & DC    & DC    & \\ \hline
15      & NOP  & NOP  & DC & DC & NOP & NOP & DC    & Mu,Y  & goto done \\ \hline
16 speed& NOP  & NOP  & DC & DC & NOP & NOP & DC    & DC    & \\ \hline
17      & LDR1 & LDR2 & DC & DC & NOP & NOP & DC    & DC    & $R_2$++ \\ \hline
18      & NOP  & NOP  & DC & DC & NOP & NOP & DC    & DC    & \\ \hline
19      & NOP  & LDR2 & DC & DC & NOP & NOP & Me,Au & DC    & \\ \hline
20      & NOP  & NOP  & DC & DC & NOP & NOP & DC    & DC    & \\ \hline
21      & NOP  & NOP  & DC & DC & NOP & 0:=Ad & Me,Au & DC    & \\ \hline
22      & NOP  & NOP  & DC & 0  & NOP & NOP & DC    & DC    & \\ \hline
23      & NOP  & NOP  & DC & DC & NOP & NOP & DC    & Y,Ad  & \\ \hline
24 done & NOP  & NOP  & DC & DC & NOP & NOP & DC    & DC    & \\ \hline
25      & NOP  & NOP  & DC & DC & NOP & NOP & DC    & DC    & \\ \hline
26      & NOP  & NOP  & DC & DC & 0:=Mu & NOP & DC  & DC    & \\ \hline \hline
\end{tabular}
\end{problemparts}

%%%%%%%%%  Problem 2

\problem{Scoreboarding to resolve Data Dependency}
\medskip

\begin{problemparts}
\problempart{In-Order Issue}\begin{enumerate}
\item It is not possible to have a WAW hazzard if the Stall signal is set in the
manner implied by the problem set.  If, however, the Stall signal is *not* set 
correctly the following code segment could cause problems:

\begin{alltt}
        I1: MULTF F1 F2 F3
        I2: MULTF F2 F1 F5
        I3: ADDF  F1 F4 F5
\end{alltt}

There is an output dependency between I1 and I3 -- so if all three instructions
I1, I2, and I3 are issued and in floating point units concurrently -- and if
I3 finishes execution before I1 (which is likely since I3 is an ADDF whereas
I1 is a MULTF) then floating point register F1 will have a corrupted value
in it.

If you set the stall signal appropriately by checking whether WP[Destination
Register]=1 before issuing, then you can avoid WAW hazzards.

\item  A WAR cannot happen in this FP Datapath.  This is primarily because we are 
dealing with In Order Issue of instructions.  Suppose we had instructions
$I_i$ and $I_j$ (with $j > i$) where:

$I_i$ reads register Rs \\
$\quad \vdots$ \\
$I_j$ writes to register Rs

Then, for a WAR hazzard to happen, $I_j$ must complete its execution even before
$I_i$ is *issued.*  However, this cannot happen since we assume In-order-Issue.
Thus $I_i$ will always be issued before $I_j$.  

\item Here is the stall signal:

STALL = (BUSY[FMUL1] $\wedge$ BUSY[FMUL2]) $\vee$ WP[Rd] $\vee$ WP[Rs1] $\vee$ WP[Rs2]

Intuitively, this says that the stall signal will be set if either both the
Floating Point Multiplication units are busy, or if there is a write pending
on either the source or destination floating point registers in the 
instruction.   (i.e.  there is a data dependency or output dependency to
worry about)
\end{enumerate}

\bigskip
\problempart{Out-of-Order Issue}\begin{enumerate}
\item With out of order issue, you have to worry about WAR hazzards (in addition 
to the standard RAW and WAW hazzards that you have to worry about with 
In-Order-Issue)  Recall that with In-Order-Issue, the WAR hazzard wasn't 
something we needed to worry about.

Consider the following piece of sample code:

\begin{alltt}
I1: MULTF F0, F2, F4
I2: MULTF F9, F0, F8
I3: ADDF  F8, F8, F7
\end{alltt}

There is an *anti-dependence* between instructions I2 and I3.  Thus if I3 
is issued, executed, and completed before I2 is even issued, then the value
in Floating Point Register F8 will be corrupted -- hence the anti-dependence
will be violated.  


\item The new stall signal is:

STALL = (BUSY[FMUL1] $\wedge$ BUSY[FMUL2]) $\vee$ WP[Rd] $\vee$ WP[Rs1] $\vee$ WP[Rs2] $\vee$ RP[Rd]

Intuitively this says to stall if either both the Floating point multiplcation
units are busy, or if there is a write pending on either the source or 
destination registers in the instruction (i.e. there are data/ouptut 
dependencies to worry about) or if there is a read pending in a destination 
register (i.e. there is a data anti-dependency to worry about.)
\end{enumerate}

\bigskip

\problempart{The Magic Bookkeeper}

The scoreboard table (the dynamics table which is useful for
understanding what is actually going on) now needs to handle new
data. The existence of stalled instructions and the fact that each
stalled instruction may modify the RP set means that there are now two
tables. The first table is the one that we're used to from the
in-order execution, and the second table contains the list of pending
instructions (in the order they are pending), and the current set of
RP registers they affect. Note that for each instruction thrown into
the buffer, the RP set grows, and when the instruction is removed, the
RPset {\bf MAY} diminish. It is important to keep more than a bit of
storage per register here, since multiple stalled instructions may be
waiting to read a register. Alternatively, if this requires too much
space, it is possible to not allow instructions into the buffer until
the RP set they affect is back at zero (so this causes a full stall
should two consecutive instructions need to read the same register).
For the answer, I will assume that there will be only one bit for each
register in the vector (making RP 32 bits). It would, however, be
better if it were two bits per, allowing up to three instructions
all pending on one read to be in the buffer at any time.

\begin{enumerate}
\item When an instruction is issued, if it was in the instruction buffer
    (window) then the effect of that instruction on the RP vector is
    undone (destination registers set to zero in RP). The instruction
    gets dispatched, which means an effect on the Busy vector and on
    the WP vector occurs as it does in the lecture.  If an instruction
    gets stalled, it modifies the RP vectore by OR'ing the current RP
    with a string set to '1' in the position of where the register
    is. Once an instruction is executed and committed, the Busy vector
    is undone, and the WP set changes are undone. AGAIN, note that WP
    can only have one unit attempt to set it (no WAW) because of the
    out-of-order rules.

\item At each cycle, the Issue box gets an instruction from ID (assuming
it is not pushing back and asking for no more instructions that
cycle). First thing that is done is to check if the buffer is
(full-1). If it is, hold back on the ID. Now, check the buffer for the
first instruction that may be issued. This is NOT a simple process,
and I will describe two ways of approaching it later. If none of the
instructions in the window apply, then check if it's legal to issue
the one just received (using the {\bf out-of-order} execution
rule). If that is also impossible, just wait a cycle and repeat the
check (at some point, all the FPUs will be empty, and the first
instruction in the window WILL be legal). Once this is done, either an
entry in the table is cleared, or the most recently fetched
instruction was executed. If an entry in the table was executed, move
all the entries after it down one to fill in the gap, and put the most
recently fetched instruction at the end. Finally, undo the hold on the
ID if it was done.

Now, the way to figure out if an instruction in the window is valid
for execution is by having ANOTHER vector RP2, which has one bit
per-register. When the magic bookkeeper is trying to figure out which
instruction to reschedule, it starts off with an empty RP2. It tries
the first instruction in the window (using the {\bf in-order} rule. If
the first instruction in the window fails, then the bookkeeper sets
RP2 as would be appropriate for the instruction (same effect as on
RP). It then systematically tries all the other instructions, in order
(oldest fetched to newest) using the {\bf out-of-order} rules, using
RP2 instead of RP, and modifying RP2 with each instruction attempted
and failed. If an instruction passes the rules, then Issue it, and
deal as was explained in 2.C.1.
\end{enumerate}

\end{problemparts}


\end{problems}
\end{document}
