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 / e

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.