\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 2}
\author{Chris Laas}
\date{March 1, 2000}

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

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

\begin{document}
\maketitle

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

\item%(a)

See attached page for control signals.

\begin{verbatim}
ADDM0:  A  <- (Rb)
        B  <- Imm
        MA <- A + B
        A  <- Mem
        B  <- (Rd)
        Rd <- A + B ; microbranch to FETCH0
\end{verbatim}

\item%(b)

\begin{verbatim}
NUMCPY0:
        MA  <- (Rs)  ; A <- (Rs)
        B   <- Mem
        Rs  <- A + 4
        MA  <- (Rd)  ; A <- (Rd)
        Mem <- B
        Rd  <- A + 4
        A   <- (Rc)
        Rc  <- A - 1 ; microbranch to NUMCPY0 if not zero
        microbranch to FETCH0
\end{verbatim}

Note that the microinstruction
\begin{verbatim}
        MA <- (Rs) ; A <- (Rs)
\end{verbatim}
is one microinstruction, which places the value of the register Rs on
the bus and writes it to MA and A.

This microcode takes $8N+4$ cycles total to execute.

\item%(c)

The problem is that this 32-bit architecture does not support 8-bit
byte transfers, neither on the bus nor to or from memory.  Adding a
byte-transfer capability to the memory module would allow it to be
implemented; adding bitwise operations to the ALU might allow it to be
faked (by reading in memory a word at a time and patching together the
bytes manually).

\item%(d)

$$
\mu{}PCSrc = \choice{
\mu{}PCSrc + 1 & \mbox{ iff ``next'' or (``spin'' and \~{}busy) } \\
               & \mbox{ or (``beqz'' and \~{}zero) or (``bnez'' and zero) } \\
\mu{}PCSrc     & \mbox{ iff ``spin'' and busy } \\
absolute       & \mbox{ iff ``fetch'' or (``beqz'' and zero) or (``bnez'' and \~{}zero) } \\
op-group       & \mbox{ iff ``dispatch'' } \\
}
$$

\begin{eqnarray*}
\mu{}PCSrc_0 & = & \mbox{ ``$\mu{}$PCSrc'' or ``op-group'' } \\
             & = & \mbox{ (``spin'' and busy) or ``dispatch'' } \\
\mu{}PCSrc_1 & = & \mbox{ ``absolute'' or ``op-group'' } \\
             & = & \mbox{ ``fetch'' or (``beqz'' and zero) or (``bnez'' and \~{}zero) or ``dispatch'' }
\end{eqnarray*}

Expanding to full verbosity:

\begin{eqnarray*}
\mu{}PCSrc_0 & = & \mbox{ ($\mu$JumpType = ``001'' and busy) or ($\mu$JumpType = ``100'') } \\
\mu{}PCSrc_1 & = & \mbox{ ($\mu$JumpType = ``010'') or ($\mu$JumpType = ``110'' and zero)} \\
             &   & \mbox{ or ($\mu$JumpType = ``111'' and \~{}zero) or ($\mu$JumpType = ``100'') }
\end{eqnarray*}

(See pretty picture, attached.)


\item%(e)

\begin{verbatim}
MOV32:  A  <- (Rs)
        Rd <- A     ; microbranch to FETCH0

MOV16:  A  <- (Rs)
        Rd <- A
        A  <- PC
        A  <- A - 1
        PC <- A - 1 ; microbranch to FETCH0
\end{verbatim}

In a little-endian format, the instruction is at the wrong end of the
IR, so it can't be microcoded with this hardware; however, it could be
done with hardware modifications (for example, a change in the 32-bit
instruction format).

Well, one microcode cycle could be saved by introducing an $A - 2$ ALU
operation.  We could also shave off cycles by having each instruction
increment PC by the appropriate amount, instead of that being done in
FETCH0.  This would shave off all the extra cycles from the MOV16,
assuming that an $A+2$ ALU operation was available; on the downside,
the microcode would be increased by roughly 1 microinstruction per
macroinstruction.

An additional partial instruction register could be used to eliminate
some redundant memory accesses; however, the microcode to utilize it
would be rather complex, and the benefit would be small unless (a) the
number of 16-bit instructions in straight-line segments of code was
large, and (b) the memory access time was very slow compared to
microcode cycle time.

\end{enumerate}
\newpage



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

\item%(a)

{\bf Loadc Rule:} \\
Sys(Proc(ia, ir, rf), dm) \mbox{\it if } ir = r := Loadc(v) \\
$\to$ Sys(Proc(ia+1, dm[ia], rf[r:=v]), dm)

{\bf Loadpc Rule:} \\
Sys(Proc(ia, ir, rf), dm) \mbox{\it if } ir = r := Loadpc \\
$\to$ Sys(Proc(ia+1, dm[ia], rf[r:=ia]), dm)

(Note: the rule for loadpc cannot preserve the semantics of the $P_B$
model of AX; in particular, because of the jump delay slot.  This
cannot be fixed without adding additional state.  However, this form
of loadpc remains true to the intent, i.e. to load the PC.)

{\bf Op Rule:} \\
Sys(Proc(ia, ir, rf), dm) \mbox{\it if } ir = r:= Op(r$_1$, r$_2$) \\
$\to$ Sys(Proc(ia+1, dm[ia], rf[r:=v]), dm)
  \mbox{\it where } v := \underbar{Op}(rf[r$_1$], rf[r$_2$])

{\bf JzJump Rule:} \\
Sys(Proc(ia, ir, rf), dm)
   \mbox{\it if } ir = Jz(r$_1$, r$_2$) \mbox{ and } rf[r$_1$] = 0 \\
$\to$ Sys(Proc(rf[r$_2$], dm[ia], rf), dm)

{\bf JzNoJump Rule:} \\
Sys(Proc(ia, ir, rf), dm)
   \mbox{\it if } ir = Jz(r$_1$, r$_2$) \mbox{ and } rf[r$_1$] $\neq$ 0 \\
$\to$ Sys(Proc(ia+1, dm[ia], rf), dm)

{\bf Load Rule:} \\
Sys(Proc(ia, ir, rf), dm) \mbox{\it if } ir = r := Load(r$_1$) \\
$\to$ Sys(Proc(ia, Nop, rf[r:=dm[a]]), dm)
   \mbox{\it where } a = rf[r$_1$]

{\bf Store Rule:} \\
Sys(Proc(ia, ir, rf), dm) \mbox{\it if } ir = Store(r$_1$, r$_2$) \\
$\to$ Sys(Proc(ia, Nop, rf), dm[a:=rf[r$_2$]])
   \mbox{\it where } a = rf[r$_1$]

For the two-phase DLX implementation, the delay slot registers are
unnecessary because the IR takes care of the one-cycle jump delay of
the DLX architecture.

The mux before the IR will be needed to implement the load and store
instructions, which require injecting a Nop into the instruction
stream instead of fetching from memory as usual.

A DLX instruction that acts as a Nop could be
\begin{verbatim}
        R0 <- (R0) + (R0)
\end{verbatim}
since the value of R0 is always zero and anything assigned to it is
thrown away.


\item%(b)

Most of the equations are unchanged; I will refrain showing them
here.  The changes from the equations in the lectures notes are:

\begin{verbatim}
PCen = case opcode
  LW,SW => off
  else  => on

AddrSrc = case opcode
  LW,SW => ALU
  else  => PC

IRSrc = case opcode
  LW,SW => Nop
  else  => Mem
\end{verbatim}

See attached control table.


\item%(c)

The correct relation is AddrSrc = \~{}IRSrc = \~{}PCen; this is
because all of them are tied to the memory accesses of the processor.
If the processor is executing LW or SW, then AddrSrc = ALU; and it is
also going to stall, so IRSrc = Nop and PCen = off.


\item%(d)

I've transformed all of the control equations into NAND-style
equations; I'm omitting the NAND diagrams because they'd be huge and
useless.

\begin{eqnarray*}
ExtSel (unsigned/signed) & = & \neg(opcode = ALUui) \\
          & = & \neg(op_0 = 1 \AND op_3 = 1 \AND op_5 = 0) \\
\\
ExtSel(\mbox{16 or 26 bits}) & = & \neg(opcode = J \OR opcode = JAL \\
        & & \OR opcode = JR \OR opcode = JALR) \\
        & = & \neg(op_0 = 1 \AND op_2 = 0 \AND op_3 = 0) \\
\\
BSrc & = & \neg(opcode = ALU) \\
     & = & \neg(op_3 = 0 \AND op_5 = 0) \\
\\
OpSel_0 & = & (OpSel = Op) \OR (OpSel = 0?) \\
        & = & \neg((op_5 = 1) \OR (op_2 = 0 \AND op_3 = 0)) \\
        & = & (op_5 = 0) \AND \neg(op_2 = 0 \AND op_3 = 0) \\
        & = & \neg\neg((op_5 = 0) \AND \neg(op_2 = 0 \AND op_3 = 0)) \\
\\
OpSel_1 & = & (OpSel = +) \OR (OpSel = 0?) \\
        & = & \neg((op_5 = 0) \AND (op_2 = 0 \OR op_3 = 1)) \\
        & = & \neg((op_5 = 0) \AND \neg(op_2 = 1 \AND op_3 = 0)) \\
\\
MemWrite & = & (opcode = SW) \\
         & = & \neg\neg(op_3 = 1 \AND op_4 = 0 \AND op_5 = 1) \\
\\
RegWrite & = & \neg(opcode = SW \OR opcode = BEQZ \\
           & & \OR opcode = J \OR opcode = JR) \\
         & = & (op_0 = 1 \AND \neg(op_3 = 1 \AND op_5 = 1)) \\
           & & \OR (op_1 = 0 \AND op_2 = 0 \AND op_3 = 0) \\
           & & \OR (op_3 = 0 \AND op_5 = 1) \OR (op_3 = 1 \AND op_5 = 0) \\
         & = & \neg( \neg(op_0 = 1 \AND \neg(op_3 = 1 \AND op_5 = 1)) \\
           & &       \AND \neg(op_1 = 0 \AND op_2 = 0 \AND op_3 = 0) \\
           & &       \AND \neg(op_3 = 1 \AND op_5 = 1) \AND \neg(op_3 = 0 \AND op_5 = 0) ) \\
\\
PCSrc1 & = & (opcode = J \OR opcode = JAL \\
         & & \OR opcode = JR \OR opcode = JALR \\
         & & \OR (opcode = BEQZ \AND zero? = 1)) \\
       & = & (op_1 = 1 \AND op_3 = 0 \AND op_5 = 0) \\
         & & \OR (op_2 = 1 \AND op_3 = 0 \AND op_5 = 0 \AND zero? = 1) \\
       & = & (op_3 = 0 \AND op_5 = 0) \\
         & & \AND (op_1 = 1 \OR (op_2 = 1 \AND zero? = 1)) \\
       & = & \neg\neg(op_3 = 0 \AND op_5 = 0 \\
         & &       \AND \neg(op_1 = 0 \AND \neg(op_2 = 1 \AND zero? = 1))) \\
\\
PCSrc2 & = & \neg(opcode = JR \OR opcode = JALR) \\
       & = & (op_4 = 0) \\
       & = & \neg op_4 \\
\\
AddrSrc & = & op_5 \\
IRSrc   & = & \neg op_5 \\
PCen    & = & \neg op_5 \\
\end{eqnarray*}


\item%(e)

The microprogrammed implementation is somewhat more intuitive; one
doesn't have to worry about hazards so much.  However, the biggest
pain in implementing the pipelined controller was converting the
hardwired control logic into gates, and this is a task which is easily
automatable, so honestly I don't think the pipelined controller is
very difficult.

\end{enumerate}
\newpage



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

\item%(a)

The only needed change to the datapath is to add a multiplexor onto
the output of IMEM to shift up the instruction word by 16 bits, if
necessary.  The controller must become (at least) a two-state FSM,
with one state for normal operation and one for executing the
instruction in the low half of the word, by pulling the LowInsn flag
high.  Short instructions in the top half of the word are executed by
the normal datapath, i.e. with LowInsn off.

(The LowInsn flag may be thought of as bit 1 of PC, though we must
still provide aligned addresses to memory by forcing the bottom two
bits low.)


\item%(b)

Since we must read to the end of an instruction to get the whole
thing, we have
$$ IMA = PC + \choice{0 & \neg MI \\ 2 & MI} = PC + 2MI $$

And, in fact, the MI is redundant, because it is only true when PC is
a multiple of 2 but not a multiple of 4; hence, MI = PC[1].  (Thus
$IMA = 4 \left\lceil\frac{PC}{4}\right\rceil$.)


\item%(c)

The front end of the datapath now looks like this.  (See attached
diagram.)

The modifications to the front end are as follows:  The address
presented to the IMEM (i.e. the IMA) is
$$PC + \choice{0 & \neg MI \\ 2 & MI}$$
(MI is another name for PC[1].)
PC can be incremented by either 2 or 4, under control by the control
unit.  The IRR is fed from the low 16 bits out of the IMEM.  The
instruction fed to the decoding stage is
$$\choice{ MemWord & \neg MI \\ \{IRR, MemWord[31:16]\} & MI }$$


\newpage
\item%(d)

{\bf Aligned Add32 rule:} \\
Proc(pc, irr, mi, rf, imem, dmem) \\
      \IF mi = 0 \AND imem[pc] = r:=Add(r$_1$, r$_2$) \\
$\to$ Proc(pc+4, imem[pc][15:0], 0, rf[r:=v], imem, dmem) \\
      \WHERE v = rf[r$_1$] + rf[r$_2$]

{\bf Misaligned Add32 rule:} \\
Proc(pc, irr, mi, rf, imem, dmem) \\
   \IF mi = 1 \AND \{irr, imem[pc+2][31:16]\} = r:=Add(r$_1$, r$_2$) \\
$\to$ Proc(pc+4, imem[pc+2][15:0], 0, rf[r:=v], imem, dmem) \\
   \WHERE v = rf[r$_1$] + rf[r$_2$]

{\bf Aligned Add16 rule:} \\
Proc(pc, irr, mi, rf, imem, dmem) \\
   \IF mi = 0 \AND imem[pc][31:16] = r$_d$:=Add2(r$_d$, r$_s$) \\
$\to$ Proc(pc+2, imem[pc][15:0], 1, rf[r$_d$:=v], imem, dmem) \\
   \WHERE v = rf[r$_d$] + rf[r$_s$]

{\bf Misaligned Add16 rule:} \\
Proc(pc, irr, mi, rf, imem, dmem) \\
   \IF mi = 1 \AND irr = r$_d$:=Add2(r$_d$, r$_s$) \\
$\to$ Proc(pc+2, imem[pc+1][15:0], 0, rf[r$_d$:=v], imem, dmem) \\
   \WHERE v = rf[r$_d$] + rf[r$_s$]


\item%(e)

When a control instruction jumps to an unaligned PC, the IRR is not
initialized to the correct instruction fragment; it instead holds a
chunk of the jump instruction or the instruction after it (depending
on whether the jump instruction was aligned).  This problem is solved
by stalling for one cycle to read in the correct IRR; in order to do
so, a single bit of state, and ``unaligned jump'' (UJ) flag, is
introduced.  Most instructions behave identically to before when
UJ = 0; UJ remains 0 in these rules.  The new rules for the JR
instruction are:

{\bf Aligned JR rule:} \\
Proc(pc, irr, mi, uj, rf, imem, dmem) \\
      \IF uj = 0 \AND mi = 0 \AND imem[pc] = JR(r) \\
$\to$ Proc(a, imem[pc][15:0], a[1], a[1], rf, imem, dmem) \\
      \WHERE a = rf[r]

{\bf Misaligned JR rule:} \\
Proc(pc, irr, mi, uj, rf, imem, dmem) \\
      \IF uj = 0 \AND mi = 1 \AND \{irr, imem[pc+2][31:16] = JR(r) \\
$\to$ Proc(a, imem[pc+2][15:0], a[1], a[1], rf, imem, dmem) \\
      \WHERE a = rf[r]

The result of UJ going high is a stall cycle.  The rule is:

{\bf UJ stall rule:} \\
Proc(pc, irr, mi, uj, rf, imem, dmem) \IF uj = 1 \\
$\to$ Proc(a, imem[pc-2][15:0], 1, 0, rf, imem, dmem)

This loads the IRR properly and resets the MI and UJ flags appropriately.



\end{enumerate}
\newpage



\end{document}
