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

In the pictured single-cycle MIPS architecture, RegDst selects the write address of the register file: zero selects instruction bits $20\dots 16$, the rt field used by a load; one selects bits $15\dots 11$, the rd field used by an MIPS R-type instruction. RegWrite enables the clocked write to the selected processor register.

ALUSrc selects the second ALU input: zero uses the second register file read output, while one uses the sign-extended 16-bit immediate field. The zero signal is produced by the ALU, rather than being an opcode-decoder output: it is one exactly when the ALU result is zero. During beq, the ALU subtracts its operands, so zero tests equality. The diagram combines it with Branch to select the branch target instead of $PC+4$.

Run the following two MIPS instruction tests separately from externally prepared states, and inspect the register file after the indicated instruction. External preparation is useful in a manufacturing test: code that initializes processor registers through the very control line being tested need not work. Assume the one potentially faulty line is RegDst; all other lines work normally.

For the first test, preset $t0=7, $t1=5, $t2=99, and executeThe encoded rt is $t1, while rd is $t2. A healthy line or a line stuck at one writes 12 into $t2. A line stuck at zero instead writes 12 into $t1, leaving $t2=99.

For the second test, preset $t3=4, $s0=L, and the aligned memory word at $L$ to 37, then executeThe zero immediate makes instruction bits $15\dots 11$ zero. A healthy line or a line stuck at zero writes 37 into $t3; a line stuck at one attempts to write the MIPS zero register, leaving $t3=4. The MIPS zero register ignores attempted writes. Thus, recording the first test's $t2 and the second test's $t3,

A writing MIPS instruction distinguishes a line stuck at zero. With $t0=7, $t1=5, $t2=99, executeA healthy line or a line stuck at one produces $t2=12; a line stuck at zero leaves $t2=99.

To distinguish normal operation from stuck at one, execute a normally nonwriting MIPS instruction. The following functional test uses the usual concrete controller choice MemToReg=0 during sw, selecting the ALU result on the write-data bus. Prepare $t0=37 and $s0=L-16384, for an aligned writable address $L\ne 37$, then executeThe ALU computes $L$. Here rt is register 8 ($t0), and immediate $16384=0x4000$ also puts 8 into bits $15\dots 11$. Thus either value of the otherwise irrelevant RegDst selects $t0. With a healthy RegWrite, $t0 remains 37. With RegWrite stuck at one and the specified write-data selection, the unwanted register file write changes $t0 to $L$. Combining the two independent observations gives

Controller qualification. The source diagram does not specify values of otherwise irrelevant control outputs during a store. MemToReg is a don't-care condition when RegWrite=0; its chosen implementation matters when that enable line is faulty. The functional test above explicitly fixes this convention instead of assuming that all implementations resolve it identically. A manufacturing fixture can also observe the register file write-enable directly while executing add followed by sw: the expected pairs are $(1,0)$ normally, $(0,0)$ stuck at zero, and $(1,1)$ stuck at one. This second observation does not depend on unused write-data controls or on whether an unwanted write happens to repeat an old value.

Again use independent externally initialized MIPS instruction tests. First preset $t0=7, $t1=5, and executeThe normal result, also obtained with ALUSrc stuck at zero, is 12. If the line is stuck at one, the second ALU operand is the sign-extended low 16 instruction bits. For this exact instruction they encode rd=10, shift amount zero and function $0x20$, giving $0x5020=20512$. The erroneous result is therefore $7+20512=20519$.

For the second test, preset $s0=L, $t3=4, memory at $L$ to 37 and memory at $L+4$ to 99, with both words valid and aligned. ExecuteNormally, and with ALUSrc stuck at one, the address is $L+0$ and the result is 37. With the line stuck at zero, the second ALU operand is the old $t3=4, so the load reads 99 from $L+4$. Thus

Execute this MIPS instruction fragment twice, once with equal operands and once with unequal operands, and observe whether its conditional branch is taken:Use $t0=7,$t1=7 for the first test and $t0=7,$t1=8 for the second. All padding instructions are explicit harmless MIPS instructions. In the pictured single-cycle model, the next program counter after beq is either hit or the sequential address. The branch target is deliberately different from the next sequential instruction. The extra padding also keeps a branch delay slot harmless if a test fixture uses an implementation with one, although the pictured model itself has none.

A healthy zero line reports the first subtraction as zero and the second as nonzero. A line stuck at zero prevents both branches, while a line stuck at one forces both branches. ThereforeObserve the branch decision or execution trace itself; an alleged unconditional beq used to skip result-recording code would also be affected by the fault.

The register file in this datapath supplies both read ports combinationally for whatever read addresses the instruction fields present. Reading a processor register is harmless, and a result that the current MIPS instruction does not need can simply be ignored. Only writes require an explicit enable because writes change architectural state. There is consequently no functional need for RegRead in this design.

The data-memory read interface has an explicit MemRead enable. Non-load MIPS instructions can present irrelevant or invalid addresses at the memory address input; an external memory transaction should not be initiated merely because those bits happen to be present. An explicit enable also permits interfaces with memory-mapped input-output, where a read can have a side effect. It can reduce unnecessary activity even for ordinary memory.This is a distinction in the supplied datapath, rather than a universal physical prohibition: other register files can have read enables, and an ideal side-effect-free memory can be modeled with continuous reads.