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

Use the MIPS zero register as a write-suppression destination: encode $r_d=0$. There are only 31 stored processor registers, and address zero denotes the constant-zero source rather than a writable storage cell. Its writes are discarded, soThis permits a store to write memory while its unavoidable register file write has no effect. It also implements a no-operation by selecting no memory write and destination zero. The statement that reads of register zero return zero is realized consistently by this standard constant-zero, discard-writes implementation.

The opcode occupies bits $31:26$, the arithmetic logic unit operation is wired directly to $15:10$, and an immediate operand uses all of $9:0$. A three-register instruction needs fifteen register-selection bits, whereas an immediate instruction must retain independent source and destination selectors outside $9:0$.

Thus put $r_s$ and $r_d$ in the ten bits $25:16$, and place $r_t$ in five of $9:0$, where it can overlap the unused immediate operand of a register instruction. One valid instruction encoding isBits $4:0$ are unused for a three-register instruction. In an immediate instruction, $r_t$ has no effect because its read value is deselected by the ToAlu multiplexer. In a store, $r_s$ selects the address and $r_t$ selects the data; $r_d$ must be zero to suppress the incidental register write. These observations follow the original datapath, particularly its direct $va{l}_s$ memory-address connection and the connection from the ToAlu output to memory write data.^[ref]

Choose ToAlu=0 for the $va{l}_t$ input and ToAlu=1 for the expanded immediate operand. Choose ToReg=0 for the arithmetic logic unit result and ToReg=1 for memory read data. The diagram does not label the multiplexer polarities, so these are explicit conventions.

Let $F_{+}$ and $F_{\vee }$ denote the six-bit arithmetic logic unit operation codes for addition and bitwise OR. Their numerical codes are not specified by the paper. The opcode needs to distinguish register, immediate, load and store modes; add and or can share register mode, and addi and ori can share immediate mode, since $15:10$ selects the operation directly. For example, choose $o_R=000000$, $o_I=000001$, $o_L=000010$ and $o_S=000011$. With $X$ denoting a field whose bits do not matter, the formats are:

The required opcode control table is:

Here MemRd is irrelevant whenever read data is unused, under the ordinary side-effect-free memory interpretation of the diagram. It is sensible to choose zero for those $X$ entries to save activity; memory-mapped devices with read side effects would require that choice. For store, ToReg is irrelevant because $r_d=0$; ToAlu is essential because its output supplies both the second arithmetic logic unit operand and memory write data. For load, the memory address is $va{l}_s$ independently of ToAlu and of $15:10$.

The resulting effects, with 32-bit addition, arewhere $E(x)=(x\mathrm{mod}256)2^{8\lfloor x/256\rfloor }$ for the ten-bit field $x$.

The addi immediate operand is a byte-lane immediate: an unsigned eight-bit quantity shifted by $0,8,16$ or $24$ positions. ThusIt is not the sign extension of a 16-bit constant used by the MIPS instruction addi. For example, this design can add $0x12000000$ directly, but cannot add $0x00000123$ in a single immediate instruction. A field containing byte $\mathtt{FF}$ in the low lane adds 255, not $-1$.

The load and store memory address is exactly the content of $r_s$. The arithmetic logic unit result is not connected to the memory-address input. ThereforeThere is no native base-plus-offset calculation during either memory instruction. The paper does not specify exception behavior for signed overflow, so the representable constants and address calculation are the justified differences; the datapath alone cannot establish MIPS-compatible overflow traps.

Decompose the 32-bit pattern of $n$ into bytes:Let $x_j=256j+b_j$ be its ten-bit encoding, so $E(x_j)=b_j{2}^{8j}$. The following custom-ISA assembly language sequence implements the requested sum:

addi t,s,x0
addi t,t,x1
addi t,t,x2
addi t,t,x3

The symbols x0 through x3 stand for the encoded ten-bit fields, not for the expanded 32-bit values. After line $j+1$, the destination contains $R_s+{\sum }_{i=0}^j{b}_i{2}^{8i}$ modulo $2^{32}$. HenceIf $t=s$, each instruction correctly uses the preceding partial sum. Zero-byte additions can be omitted except that, when $t\ne s$, an initial instruction must still copy the original source if all earlier omitted bytes are zero. An assembler can initialize t with add t,s,0 instead and then emit only nonzero lanes. If $t=0$, the intended register effect is discarded.

For a MIPS instruction lw t,k(s), first construct $R_u=R_s+{\mathrm{signextend}}_{16}(k)$ in a scratch processor register $u$, using the four-lane sequence above with destination $u$, and then issue

load t,(u)

For sw t,k(s), construct the same address in $u$ and issue

store t,(u)

Choose $u\ne 0,s,t$, or preserve a live scratch processor register according to the calling convention. In particular the store sequence must retain the original data in $t$, even when $s=t$. Both expansions need at most five custom instructions and have the same address and memory-word effects as the corresponding MIPS instructions, assuming aligned valid memory and 32-bit modular address arithmetic. When $k=0$, the memory instruction alone suffices. These are listings for the examination's custom instruction set architecture, not native MIPS encodings; exact exception and pipeline behavior is outside the specified datapath.