Level 5 — MasteryInstruction Set Architecture (ISA)

Instruction Set Architecture (ISA)

⏱ 90 minutes60 marksprintable — key stays hidden on paper

Level 5 — Mastery (cross-domain: math + hardware + coding) Time limit: 90 minutes Total marks: 60

Answer all three questions. Show reasoning, encodings in binary/hex, and justify every design claim. Assume little-endian, byte-addressable memory unless stated otherwise.

Question 1 — RISC-V encoding, addressing, and semantics (24 marks)

You are hand-assembling a fragment of an RV32I loop that sums an array. The symbolic assembly is:

        # a0 = base pointer p, a1 = n (count), a2 accumulates sum
        li      a2, 0            # (pseudo-instruction)
loop:   beq     a1, x0, done
        lw      t0, 0(a0)
        add     a2, a2, t0
        addi    a0, a0, 4
        addi    a1, a1, -1
        jal     x0, loop
done:   ...

(a) State the RV32I instruction format (R/I/S/B/U/J) used by each of these five real instructions: beq, lw, add, addi, jal. (5)

(b) Encode addi a0, a0, 4 fully into a 32-bit word (give the binary field-by-field, then the hex). Register numbers: a0 = x10, t0 = x5, a2 = x12. The I-type opcode is 0010011, funct3 for ADDI is 000. (6)

(c) The beq at address 0x0040 must branch to done at address 0x0060 when taken. Compute the B-type immediate value and show how its bits are scattered into the encoding fields imm[12|10:5] and imm[4:1|11]. Explain why the LSB (bit 0) of the branch offset is never stored. (6)

(d) The pseudo-instruction li a2, 0 expands to a single real instruction. Give one valid RV32I expansion and name its format. Then explain why loading an arbitrary 32-bit constant (e.g. li a2, 0xDEADBEEF) generally requires two instructions, referencing the immediate width limits of the ISA. (7)

Question 2 — Endianness, ABI, and a stack-frame proof (20 marks)

A function int f(int a, int b, int c) compiled for RV32I with the standard calling convention (integer args in a0–a7, return value in a0, sp is the stack pointer, and sp must stay 16-byte aligned at function boundaries).

(a) The 32-bit integer 0x12345678 is stored at memory address 0x1000. List the four bytes at addresses 0x1000–0x1003 under little-endian and under big-endian. Then explain why a network protocol ("network byte order") and a little-endian CPU can disagree, and what one instruction class fixes it. (6)

(b) f is a non-leaf function: it calls another function and uses saved registers s0, s1. It must preserve ra, s0, s1. Write the prologue and epilogue (sp adjustment + stores/loads), choosing a frame size that satisfies the 16-byte alignment rule while wasting the least space. Justify the chosen frame size arithmetically. (8)

(c) Prove that under this ABI, if a caller passes 9 integer arguments, at least one must be passed on the stack, and state exactly how many go in registers versus memory. Then state which side (caller or callee) is responsible for cleaning up stack-passed arguments in the standard RISC-V convention, contrasting it with the cdecl vs stdcall distinction on x86. (6)

Question 3 — CISC vs RISC design trade-off, quantified (16 marks)

Consider computing the same task on two machines using the classic performance equation:

$\text{CPU time} = IC \times CPI \times T_c$

where $IC$ = instruction count, $CPI$ = cycles per instruction, $T_c$ = clock period.

A CISC implementation executes the task in $IC_{C} = 8 \times 10^{6}$ instructions at $CPI_{C} = 6$ with a clock of $2.0\text{ GHz}$ . A RISC implementation of the same task uses $IC_{R} = 1.4 \times IC_{C}$ instructions at $CPI_{R} = 1.8$ with a clock of $2.5\text{ GHz}$ .

(a) Compute the CPU time for each machine and the speedup of RISC over CISC. Show the equation substitution. (8)

(b) A load/store architecture forbids memory operands in ALU instructions, which is one reason $IC_R > IC_C$ . Explain the architectural mechanism (register file + load/store model) that lets RISC still win despite executing more instructions, tying it to the CPI and $T_c$ figures above. (4)

(c) Suppose an M-extension gives RISC a single-cycle mul that removes $0.5\times10^6$ instructions (replacing multi-instruction sequences) but leaves overall CPI unchanged. Compute the new RISC instruction count and the new RISC CPU time, and state the revised speedup. (4)

Answer keyMark scheme & solutions

Question 1

(a) Formats (5, one each):

beq → B-type
lw → I-type (loads are I-type)
add → R-type
addi → I-type
jal → J-type

(b) Encode addi a0, a0, 4 = addi x10, x10, 4. (6)

I-type layout: imm[11:0] | rs1 | funct3 | rd | opcode.

imm = 4 → 000000000100 (12 bits)
rs1 = x10 → 01010
funct3 = 000
rd = x10 → 01010
opcode = 0010011

Binary (32 bits): 000000000100 01010 000 01010 0010011 Group into nibbles: 0000 0000 0100 0101 0000 0101 0001 0011 Hex: 0x00450513

Marks: imm field (1), rs1 (1), funct3 (1), rd (1), opcode (1), correct hex (1).

(c) Branch offset = target − PC = 0x0060 − 0x0040 = 0x20 = 32. (6)

Immediate value = +32 = binary 0000 0010 0000 in a 13-bit signed field imm[12:0] where bit 0 is always 0.

imm[12] = 0
imm[11] = 0
imm[10:5] = 000001 (bits 5..10 of 32: bit5=1)
- 32 = 0b100000, so bit5 = 1, bits 6–12 = 0
imm[4:1] = 0000

So scattered fields:

imm[12|10:5] = 0 000001 → the high field bits = 0000001
imm[4:1|11] = 0000 0

Why bit 0 is dropped: all RV32I instructions are aligned to 2-byte boundaries (with the C extension) / 4-byte otherwise, so branch targets are always even addresses; the offset's least-significant bit is guaranteed 0 and need not be stored. This effectively doubles the reachable range using the same number of encoded bits (±4 KiB).

Marks: offset = 32 (2), correct bit placement (2), justification of dropped LSB + range doubling (2).

(d) (7)

One valid expansion: addi a2, x0, 0 — I-type. (li a2,0 = addi x12, x0, 0 = mv-style with zero.) (format naming = I-type.)

Why arbitrary 32-bit constants need two instructions: the largest immediate an I-type instruction carries is a 12-bit sign-extended field (range −2048…+2047). A U-type (lui) carries a 20-bit immediate placed in bits [31:12]. Neither alone spans a full 32-bit value. The canonical sequence is:

lui  a2, %hi(0xDEADBEEF)   # loads upper 20 bits
addi a2, a2, %lo(0xDEADBEEF) # adds sign-extended lower 12 bits

Because addi's 12-bit immediate is sign-extended, the assembler adds 1 to the lui value when the low 12 bits have their top bit set, to compensate for the sign extension. Thus 20 + 12 bits = 32 bits requires two instructions.

Marks: correct single-instruction expansion + format (2), 12-bit imm limit stated (2), lui 20-bit + addi 12-bit split (2), sign-extension correction note (1).

Question 2

(a) (6)

0x12345678 at 0x1000:

addr	little-endian	big-endian
0x1000	0x78	0x12
0x1001	0x56	0x34
0x1002	0x34	0x56
0x1003	0x12	0x78

Little-endian stores the least-significant byte at the lowest address; big-endian stores the most-significant byte first. Network byte order is big-endian, so a little-endian CPU sees multi-byte fields byte-reversed. The fix is a byte-swap instruction (e.g. x86 BSWAP, ARM REV, or RISC-V rev8 from the Zbb bitmanip extension) or software htonl/ntohl.

Marks: LE column (2), BE column (2), byte-order mismatch + byte-swap instruction (2).

(b) (8)

Need to save ra, s0, s1 = 3 words = 12 bytes. Round frame up to a multiple of 16 → 16 bytes (least waste; 12 rounds to 16).

Prologue:

    addi sp, sp, -16
    sw   ra, 12(sp)
    sw   s0, 8(sp)
    sw   s1, 4(sp)

Epilogue:

    lw   ra, 12(sp)
    lw   s0, 8(sp)
    lw   s1, 4(sp)
    addi sp, sp, 16
    ret

Justification: three 4-byte saves need 12 bytes; ABI requires sp % 16 == 0, and $\lceil 12/16 \rceil \times 16 = 16$ . A 12-byte frame would break alignment; 16 is the smallest legal multiple, wasting only 4 bytes.

Marks: frame = 16 with arithmetic justification (2), prologue stores + sp decrement (3), epilogue loads + sp restore + ret (3).

(c) (6)

RISC-V provides 8 integer argument registers a0–a7. With 9 integer arguments, only 8 fit in registers; the 9th (and beyond) is passed on the stack. Therefore at least one must go to memory. Exactly 8 in registers, 1 on the stack.

Cleanup: in the standard RISC-V convention the caller cleans up stack-passed arguments (caller reserves and reclaims the outgoing-argument area). This matches x86 cdecl (caller cleans up), and contrasts with stdcall where the callee pops the arguments (via ret n).

Marks: 8 registers stated (2), pigeonhole "9 > 8 ⇒ ≥1 on stack" (2), caller-cleanup + cdecl/stdcall contrast (2).

Question 3

(a) (8)

CISC: $T_c = 1/2.0\text{GHz} = 0.5\text{ ns}$ . $t_C = 8\times10^6 \times 6 \times 0.5\text{ns} = 48\times10^6\text{ns} = 24\text{ ms}$

RISC: $IC_R = 1.4 \times 8\times10^6 = 11.2\times10^6$ ; $T_c = 1/2.5\text{GHz} = 0.4\text{ ns}$ . $t_R = 11.2\times10^6 \times 1.8 \times 0.4\text{ns} = 8.064\times10^6\text{ns} = 8.064\text{ ms}$

Speedup $= t_C/t_R = 24/8.064 = \mathbf{2.976}$ (≈2.98×).

Marks: CISC time (3), RISC time (3), speedup (2).

(b) (4) A load/store model keeps a large general-purpose register file; operands for ALU ops must already be in registers, so most instructions are simple, fixed-length, single-purpose. This uniformity (i) enables a low, near-uniform CPI (1.8 vs 6) because there are no microcoded multi-cycle memory-ALU instructions, and (ii) shortens the critical path so the clock period $T_c$ can be smaller (0.4 ns vs 0.5 ns). The product $CPI\times T_c$ falls enough to overcome the 1.4× instruction-count penalty. (2 for register/load-store mechanism, 2 for tying to CPI + Tc.)

(c) (4) New $IC_R = 11.2\times10^6 - 0.5\times10^6 = 10.7\times10^6$ . $t_R' = 10.7\times10^6 \times 1.8 \times 0.4\text{ns} = 7.704\times10^6\text{ns} = 7.704\text{ ms}$ Revised speedup $= 24/7.704 = \mathbf{3.115}$ (≈3.11×).

Marks: new IC (1), new time (2), revised speedup (1).

[
  {"claim":"addi x10,x10,4 encodes to 0x00450513","code":"imm=0b000000000100; rs1=0b01010; f3=0b000; rd=0b01010; op=0b0010011; word=(imm<<20)|(rs1<<15)|(f3<<12)|(rd<<7)|op; result = (word==0x00450513)"},
  {"claim":"branch offset 0x60-0x40 equals 32","code":"result = (0x60-0x40)==32"},
  {"claim":"3 saved words need a 16-byte aligned frame of 16 bytes","code":"import math; need=12; frame=math.ceil(need/16)*16; result = frame==16"},
  {"claim":"CISC=24ms, RISC=8.064ms, speedup approx 2.976","code":"tc=8e6*6*0.5; tr=11.2e6*1.8*0.4; result = (abs(tc-48e6)<1 and abs(tr-8.064e6)<1 and abs(tc/tr-2.976)<0.01)"},
  {"claim":"M-ext RISC time=7.704ms, speedup approx 3.115","code":"tc=8e6*6*0.5; trp=10.7e6*1.8*0.4; result = (abs(trp-7.704e6)<1 and abs(tc/trp-3.1153)<0.01)"}
]