Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Digital systems, linear algebra, introduction to formal proof / 3

Fetch the MIPS instruction at the program counter, and compute $pc+4$. The opcode selects an MIPS R-type instruction; register-file read addresses $rs$ and $rt$ select the two operands. The function field selects ALU addition. The result returns through write-back multiplexer input zero to destination $rd$, and the next program counter is $pc+4$.

Using the diagram's actual selector encodings, the control signals areHere $\mathrm{ALUOp}=10$ means decode the function field; $00$ means add and $01$ means subtract. The source's $\mathrm{Branch}=(B{r}_1,B{r}_0)$ is a two-bit control: the branch-taken output is $B{r}_1\wedge (B{r}_0\oplus \mathrm{Zero})$. With $B{r}_1=0$, $B{r}_0$ is immaterial; zero is a convenient concrete setting. No data-memory access occurs.

Fetch and decode the MIPS I-type instruction, read $rs$ and $rt$, and subtract their values in the arithmetic logic unit. The zero flag is one exactly when they are equal. The branch target isThe branch selector chooses that target when $B{r}_1=1$ and $B{r}_0=0$ make the diagram's condition equal to $\mathrm{Zero}$. Otherwise it chooses $pc+4$. Neither registers nor data memory are written. The control signals areDashes are don't-care conditions because register write enable is zero. The immediate goes to the branch-target adder, while the main ALU's second input remains the value in $rt$.

For the semantics stipulated by the question, write $pc+4$ to register 31 and load the next $pc$ from register $rs$. Read $rs$ through register-file output $r{d}_0$. Select input two of the next-PC multiplexer, which is already wired from $r{d}_0$. Select destination input two, already the constant register number 31, and write-back input two, already $pc+4$.

Thus the printed diagram already contains the necessary three-way multiplexers and wires. Extend the controller's opcode/function decoding to generateThe displayed $\mathrm{ALUOp}$ and $\mathrm{ALUSrc}$ settings are arbitrary safe choices for an unused result. No additional datapath hardware or control field is required beyond decoding this instruction into the existing values. This uses the question's explicitly specified $pc+4$ link convention.

Use the stipulated MIPS I-type instruction encoding, whose unused $rt$ field is zero, so register-file output $r{d}_1$ supplies the hardwired zero register. With $\mathrm{ALUSrc}=0$ and subtraction selected, the arithmetic logic unit computes $R[rs]-0$. Its zero flag detects $R[rs]=0$, while bit 31 of $r{d}_0$ is the sign in two's complement. Therefore the required signed test isIntroduce one new control bit $GT$, and replace the zero-flag input to the existing branch XOR byThis needs an AND gate, an OR gate and a tap of the sign bit. With $GT=0$, existing branch behavior is unchanged. With $GT=1$ and $\mathrm{Branch}=11$, the existing branch-taken circuit gives $\neg Z^{\ast }$, exactly the positive test. Its output still selects between $pc+4$ and the usual sign-extended branch target. The complete control row isSet $GT=0$ for each instruction in parts (a)–(c). Registers and data memory remain unchanged. The available signed slt operation could support a different design; the sign-and-zero design above avoids adding an ALU-input swap and explicitly distinguishes zero from positive values.