\documentclass[11pt]{article}

\def\choice#1{\left\{ \begin{array}{ll} #1 \end{array} \right.}
\def\AND{\mbox{ and }}
\def\OR{\mbox{ or }}
\def\IF{\mbox{\it if }}
\def\WHERE{\mbox{\it where }}



\title{6.823 Problem Set 3}
\author{Chris Laas}
\date{March 13, 2000}

\pagestyle{myheadings}
\markright{Chris Laas \hfil 6.823 \hfil 3/13/2000}

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

\begin{document}
\maketitle

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

\item%(a)

\begin{verbatim}
LW  R1, (R0)+28
ADD R2, (R0)+54, R1
ADD R3, (R0)+26, R2
\end{verbatim}


\item%(b)

There is a hazard if the Adder stage requires the result of an
immediately preceding memory read:
\begin{verbatim}
...
LW R1, (R2)+42
ADD R3, (R1)+69, R4
...
\end{verbatim}

There is a hazard if the Adder stage requires the result of an
ALU instruction within the two preceding instructions:
\begin{verbatim}
...
SUB R1, R2, R3
<zero or one instructions>
ADD R4, (R1)+42, R5
...
\end{verbatim}
In the above, the ADD instruction could instead be
\begin{verbatim}
LW R4, (R1)+42
\end{verbatim}
or
\begin{verbatim}
SW (R1)+42, R4
\end{verbatim}
These two latter forms of the hazard did not exist in the old architecture.

There is also a hazard if a Store in the the Memory stage requires the
result of an immediately preceding ALU operation:
\begin{verbatim}
...
SUB R1, R2, R3
SW (R4)+42, R1
...
\end{verbatim}
This hazard did not exist in the old architecture.

All other pipeline hazards can be dealt with by the bypassing.  These
must be stalled.


\item%(c)

A new signal must be created; I'll call it MA, for ``memory/adder''.
It is true for the new memory/ALU instructions and for LW and SW, and
false otherwise, and so it depends only on the opcode.  For
convenience, I will also define the signal ALU true if and only if
the instruction is an ALU instruction or an ALUi instruction.  I.e.:
$$\rm alu_X = ( opcode_X = ALU_X ) + ( opcode_X = ALUi_X )$$

The ``A'' underscore will stand for the Adder stage.

\begin{eqnarray*}
\rm stall
& = & \rm
( rf1_D = ws_A ) \cdot ( opcode_A = LW_A )
   \cdot (ws_A \neq R0) \cdot ma_D +           \\&&\rm
( rf1_D = ws_A ) \cdot alu_A
   \cdot (ws_A \neq R0) \cdot ma_D +           \\&&\rm
( rf1_D = ws_M ) \cdot alu_M
   \cdot (ws_M \neq R0) \cdot ma_D +           \\&&\rm
( rf2_D = ws_A ) \cdot alu_A
   \cdot (ws_A \neq R0) \cdot (opcode_D = SW_D)
\end{eqnarray*}


\item%(d)

Using the ALU to perform the comparison, four delay slots are required
to eliminate any stalls.

By moving the comparison logic backwards in the pipeline, the number
of delay slots can be reduced.

For three delay slots, the comparison must be performed in the Memory
stage.  It's fairly unlikely to change the clock period much, since
the comparison can be performed in parallel with the memory access,
but since it cannot share any hardware with the memory subsystem, it
will add a complete comparator to the circuitry required.

For two delay slots, the comparison must be performed in the Adder
stage.  This can be done with fairly minimal extra hardware:  one
input to the adder is made optionally invertable (to turn it into a
subtractor) and the output is straightforwardly tested to give the
comparison result.  It's OK to reuse the adder in this way, because it
will not be being used for memory calculations during BLAB
instructions.  Unless the adder propagation delay is at or very near
the clock period, adding this additional hardware is unlikely to add
enough delay to change the clock period.  (I.e. the adder is highly
unlikely to be the critical path.)

For one delay slot, the comparison must be performed in the Decode
stage.  This adds about as much hardware as in the three-delay-slot
case, since no hardware can be reused; and, since the comparison can't
be performed until after the registers are read, the time for this
stage will be increased by the propagation delay of the comparator.
It's very likely that this will increase the clock period (if it
wouldn't, then there would be no benefit to placing the Adder in a
separate pipeline stage).

There isn't any way to eliminate all delay slots without introducing
any new stall conditions or killing instructions in the pipeline.

In conclusion, I think the best place to put the comparator would be
into the Adder stage, resulting in two delay slots (or stalled/killed
instructions).  It would only require minimal additional hardware, and
would be very unlikely to change the clock period.  While another
delay slot could be pared off by placing the comparator in the Decode
stage, the clock period could as much as double (most likely it would
increase by a significant percentage), and so there would be a net
loss in performance.


\item%(e)

The first (LW followed by dependent memory-access) could not be
eliminated using extra hardware.

However, the second and third types of stalls could be eliminated by
converting the Adder into a full-fledged ALU.  Then, the results of
all ALU instructions would be available to the ``Adder'' stage and the
Memory stage, so the processor could run all code from the original
ISA as fast as the original datapath could.


\item%(f)

If only one instruction is fetched at a time, at most one (old-style)
instruction can be executed per clock cycle.  Since the point of the
dynamic translation mechanism would be to execute some sequences of
more than one old-style instruction using only one cycle, it would be
impossible to realize any performance gain without the
multiple-fetch-unit.

Given the special two-instruction-fetching multiple-fetch-unit, the
decode unit can convert two-instruction sequences of the form
\begin{verbatim}
LW R2, (R1)+42
ADD R4, R2, R3
\end{verbatim}
to the more efficient
\begin{verbatim}
ADD R4, (R1)+42, R3
\end{verbatim}

This translation would be performed by simply adding tests on the
opcodes and register source/destinations of the two fetched
instructions to recognize the translation pattern.  If it matches, the
translation result is fed to the rest of the pipeline, and the PC is
incremented twice; in the usual case that it doesn't match, the first
instruction is executed, and the PC is held to only one increment.

This would result in a maximum gain of 100\% speedup on certain
segments of code; however, it seems likely that pipeline interlocks
would nullify the speedup in certain matching code patterns, and
certainly not all code will follow that pattern anyway.

A problem with this translation mechanism is that the naive
translation fails to maintain all the semantics of the code: more
specifically, in the code example above, R2 is not updated with the
contents of the memory at address (R1)+42.  It is for this reason that
the second write port is added to the register file: the
two-instruction sequence is translated into a special form of the
memory/ALU instruction that causes the result of the memory lookup to
be written back to the register file during the write-back stage.
This requires adding a second write port to the register file, and
adding an additional data path from the memory stage output to this
second port in the write-back stage (bypassing the ALU).


\end{enumerate}
\newpage


\section*{Problem 3-2}

Logic needs to be added to stall {\em every} pipeline stage if the
memory request cannot be satisfied in one cycle.  (It might be
possible to create bypass paths to complete instructions that are
independent of the memory operation, but this would be an extremely
in-depth modification to the datapath, and undoubtedly outside the
scope of this problem.)

The implementation of this is trivially simple.  An enable is added to
every register in the machine (except those within the memory
subsystem, of course); for those which already have enables, the new
enable is ANDed with the old, so that the register will only change if
both enables are asserted.  Then the busy signal is tied to every one
of these new enables.  As a result, no operation is performed in the
machine until the busy signal is de-asserted.

Since the PC is frozen along with the rest of the machine,
control-transfer instructions don't need to be treated particularly
specially.  It is important to note that the write-back stage must be
frozen along with the rest of the machine, to prevent the register
file changes from being committed too early.  Since killing
instructions happens long before they reach the memory stage, having
memory instructions directly following a jump or branch is not a
hazard.  Likewise, so long as the bypasses are performed correctly,
register-indirect-jumps and conditional branches should perform as
before.

\newpage



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

\item%(a)

In Case 2, since the stride is less than the block size, every block
in the range will be accessed, in order.  And, since the range is
greater than the cache size, the first blocks accessed will be thrown
out of the cache before the access pattern wraps around; thus, the
cache will {\em never} be hit due to wraparound.  The only cache hits
will be due to sequential same-block accesses (due to the stride being
less than the block size), and thus the cache size is irrelevant (a
one-block cache would perform as well).  There will be $b/S$ accesses
per block, and all but one will be cache hits; thus, the total penalty
will be amortized over the number of accesses per block.  Thus:
$$T_{avg} = T_{base} + \frac{S}{b} D$$

In Case 3, since the stride is greater than or equal to the block
size, a given block will not be accessed again until the benchmark
wraps around.  Thus, the only cache hits will be the result of
wraparound; and there will be such cache hits if and only if the
number of accesses to a given ``set'' in the cache is less than the
number of things that can fit in that set (i.e. the associativity of
the cache).  To rephrase: the situation will be optimal if the number
of hits to a given cache set, per cycle of the benchmark, is less than
or equal to the associativity of the cache; if it is greater than the
associativity of the cache, then the situation will be pessimal.  The
separation between blocks which are mapped to the same cache set is
$(C/b)/a$ blocks (this is an identity due to the way the cache sets
are addressed); the number of blocks spanned by every stride is $S/b$.
Thus, the number of accesses between hits to a particular cache set
will be equal to the former divided by the latter, i.e.
$N_{\Delta set-hits} = \frac{(C/b)/a}{S/b} = \frac{C}{a S}$.  Also, it
is clear that the number of accesses between wrap-arounds is
$N_{\Delta address-hits} = \frac{R}{S}$.  Thus, in conclusion, the
number of hits to a given set in a cycle of the benchmark
(i.e. between wrap-arounds) is equal to
$$\frac{N_{\Delta address-hits}}{N_{\Delta set-hits}}
   = \frac{R/S}{C/(a S)} = \frac{a R}{C}$$
If this number is less than or equal to $a$, the situation is optimal
($T_{avg} \approx T_{base}$ for large $N$); if it is greater than $a$,
the situation is pessimal ($T_{avg} = T_{base} + D$).  Thus, the
access times are optimal if and only if $\frac{a R}{C} \leq a$,
i.e. iff $R \leq C$.  Since, by assumption, $R > C$, the situation is
pessimal.  Thus, in conclusion, $T_{avg} = T_{base} + D$.

In Case 4, since the stride is greater than $R/a$, the benchmark will
wrap around after at most $a$ accesses.  Thus, even if all of these
accesses fall within the same set of the cache, the cache is
associative enough to hold {\em all} of the values.  (Quoting from the
example) thus, after the round of initial cold-start misses, all of
the addresses touched by the benchmark will be loaded into the cache.
The benchmark never encounters any further misses.  Thus for large
$N$, $T_{avg} \approx T_{base}$.


\item%(b)

$D$ can easily be read off the graph:  since
$T_{base} \approx 150 \mbox{ ns}$
and $T_{base} + D \approx 810 \mbox{ ns}$, we have
$D \approx 660 \mbox{ ns}$.

$C$ can be determined by observing the difference between the flat
graphs (corresponding to Case 1 with $R \leq C$) and the non-flat ones
(corresponding to Cases 2, 3, and 4 with $R > C$).  Since the largest
$R$ with a flat curve is $R = 64K$, we can conclude that $C = 64K$.

The non-flat curves can now be used to determine $b$ and $a$.  $b$ is
found by noting the transition from Case 2 to Case 3:  since the
curves flatten out at $S = 128$, we have $b = 128$.  And, we find $a$
by noting the transition from Case 3 to Case 4:  since each curve
drops sharply at $S = R/2$, we can conclude that $a = 2$.

\end{enumerate}
\newpage


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

\item%(a)

The results we see are due to the sequential words from a block being
read by the sequential progress through the four vectors.  As the
block size increases (without increasing the miss penalty, rather
unrealistically), performace increases, since the remainder of the
reads from a given block are essentially free (cost only $T_{base}$)
after the block has been read into the cache.  However, once the
blocksize becomes large enough that there are less than four blocks in
the cache, the LRU policy and the round-robin access pattern of the
code with respect to accessing the four vectors causes a block to be
thrown out of the cache on every access; thus, when $b > C/4$, every
access is a cache miss.

The cache capacity $C$ is found by noting the point where the access
time drops sharply (and multiplying by four to take into account the
four vectors involved).  Thus, $C = 512$.

When $b \geq 256$, $T_{avg} = h + p$: every access is a miss, because
blocks from all four vectors cannot fit in the cache at the same time.

When $b \leq 128$, $T_{avg} = h + \frac{p}{b}$, since once a block is
cached (a miss occurs once every $b$ accesses) the remaining $b-1$
accesses are hits.

$p$ and $h$ are found by substituting measurements into the above
relations: $123 = h + p$, and $14.9 = h + p/128$.  Thus, the miss
penalty $p$ is 109 cycles, and the hit time $h$ is 14 cycles.


\item%(b)

If the cache were direct-mapped rather than fully associative, the
results would still be possible: it depends entirely of the layout of
the base addresses of the vectors.

Changing the replacement policy from LRU to FIFO could not change the
results at all; this is because, for this loop, the
least-recently-used block is always the one that was first-in.


\item%(c)

In this setup, we essentially are reading blocks of four words from
memory at a time; we basically need to be careful that we use every
word before throwing it away.  Thus, to maximize cache performance, we
want to unroll the loop four times and execute the four iterations in
parallel.

\begin{verbatim}
loop:
        ; check the number of iterations left to perform for 3, 2, 1
        SUB  R9, R5, 3
        BEQZ R9, loop3          ; three more iterations if n == 3
        SUB  R9, R5, 2
        BEQZ R9, loop2          ; two more iterations if n == 2
        SUB  R9, R5, 1
        BEQZ R9, loop1          ; one more iteration if n == 1

        ; perform four iterations in parallel
        LW   R10,  0(R1)        ; load X[i] (preps the cache)
        LW   R11,  4(R1)        ; load X[i+1]
        LW   R12,  8(R1)        ; load X[i+2]
        LW   R13, 12(R1)        ; load X[i+3]
        LW   R14,  0(R2)        ; load Y[i] (preps the cache)
        LW   R15,  4(R2)        ; load Y[i+1]
        LW   R16,  8(R2)        ; load Y[i+2]
        LW   R17, 12(R2)        ; load Y[i+3]
        LW   R18,  0(R3)        ; load Z[i] (preps the cache)
        LW   R19,  4(R3)        ; load Z[i+1]
        LW   R20,  8(R3)        ; load Z[i+2]
        LW   R21, 12(R3)        ; load Z[i+3]

        ADD  R9,  R10, R14      ; do the add for index i
        ADD  R9,  R9,  R18
        SW   R9,   0(R4)        ; store W[i]
        ADD  R9,  R11, R15      ; do the add for index i+1
        ADD  R9,  R9,  R19
        SW   R9,   4(R4)        ; store W[i+1]
        ADD  R9,  R12, R16      ; do the add for index i+2
        ADD  R9,  R9,  R20
        SW   R9,   8(R4)        ; store W[i+2]
        ADD  R9,  R13, R17      ; do the add for index i+3
        ADD  R9,  R9,  R21
        SW   R9,  12(R4)        ; store W[i+3]

        ADD  R1,  R1,  16       ; increment the vector indices
        ADD  R2,  R2,  16       ; 4 bytes per word * 4 words = 16 bytes
        ADD  R3,  R3,  16
        ADD  R4,  R4,  16
        SUB  R5,  R5,   4       ; decrement n by 4 iterations' worth
        BEQZ loop_end
        J loop


loop3:
        ; do 3 more iterations to finish
        LW   R10,  0(R1)        ; load X[i] (preps the cache)
        LW   R11,  4(R1)        ; load X[i+1]
        LW   R12,  8(R1)        ; load X[i+2]
        LW   R14,  0(R2)        ; load Y[i] (preps the cache)
        LW   R15,  4(R2)        ; load Y[i+1]
        LW   R16,  8(R2)        ; load Y[i+2]
        LW   R18,  0(R3)        ; load Z[i] (preps the cache)
        LW   R19,  4(R3)        ; load Z[i+1]
        LW   R20,  8(R3)        ; load Z[i+2]

        ADD  R9,  R10, R14      ; do the add for index i
        ADD  R9,  R9,  R18
        SW   R9,   0(R4)        ; store W[i]
        ADD  R9,  R11, R15      ; do the add for index i+1
        ADD  R9,  R9,  R19
        SW   R9,   4(R4)        ; store W[i+1]
        ADD  R9,  R12, R16      ; do the add for index i+2
        ADD  R9,  R9,  R20
        SW   R9,   8(R4)        ; store W[i+2]

        ADD  R1,  R1,  12       ; increment the vector indices
        ADD  R2,  R2,  12       ; 4 bytes per word * 3 words = 12 bytes
        ADD  R3,  R3,  12
        ADD  R4,  R4,  12
        SUB  R5,  R5,   3       ; decrement n by 3 iterations' worth
        J loop_end


loop2:
        ; do 2 more iterations to finish
        LW   R10,  0(R1)        ; load X[i] (preps the cache)
        LW   R11,  4(R1)        ; load X[i+1]
        LW   R14,  0(R2)        ; load Y[i] (preps the cache)
        LW   R15,  4(R2)        ; load Y[i+1]
        LW   R18,  0(R3)        ; load Z[i] (preps the cache)
        LW   R19,  4(R3)        ; load Z[i+1]

        ADD  R9,  R10, R14      ; do the add for index i
        ADD  R9,  R9,  R18
        SW   R9,   0(R4)        ; store W[i]
        ADD  R9,  R11, R15      ; do the add for index i+1
        ADD  R9,  R9,  R19
        SW   R9,   4(R4)        ; store W[i+1]

        ADD  R1,  R1,   8       ; increment the vector indices
        ADD  R2,  R2,   8       ; 4 bytes per word * 2 words = 8 bytes
        ADD  R3,  R3,   8
        ADD  R4,  R4,   8
        SUB  R5,  R5,   2       ; decrement n by 2 iterations' worth
        J loop_end


loop1:
        ; do 1 more iteration to finish
        LW   R10,  0(R1)        ; load X[i]
        LW   R14,  0(R2)        ; load Y[i]
        LW   R18,  0(R3)        ; load Z[i]

        ADD  R9,  R10, R14      ; do the add for index i
        ADD  R9,  R9,  R18
        SW   R9,   0(R4)        ; store W[i]

        ADD  R1,  R1,   4       ; increment the vector indices
        ADD  R2,  R2,   4       ; 4 bytes per word * 1 word = 4 bytes
        ADD  R3,  R3,   4
        ADD  R4,  R4,   4
        SUB  R5,  R5,   1       ; decrement n by 1 iteration's worth
        J loop_end


loop_end:
        ; end of function.  move along, nothing to see here.
\end{verbatim}



\end{enumerate}
\newpage



\end{document}
