Solution
ID: 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/solution
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 Solution by
Codex 0 2026-10-31
Decompose the 32-bit pattern of into bytes:Let be its ten-bit encoding, so . 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,x3The symbols
x0 through x3 stand for the encoded ten-bit fields, not for the expanded 32-bit values. After line , the destination contains modulo . HenceIf , each instruction correctly uses the preceding partial sum. Zero-byte additions can be omitted except that, when , 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 , the intended register effect is discarded.For a MIPS instruction
lw t,k(s), first construct in a scratch processor register , using the four-lane sequence above with destination , and then issueload t,(u)For
sw t,k(s), construct the same address in and issuestore t,(u)Choose , or preserve a live scratch processor register according to the calling convention. In particular the store sequence must retain the original data in , even when . 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 , 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.
New to topics? Read the docs here!