Noesis
Interleaved — Phase 4

Coding interleaved practice

printable — key stays hidden on paper

Instructions: Attempt all problems. Each requires you to first identify which concept/method applies, then execute. Show working for numeric problems. Total: 60 marks. Use ...... for any math. No calculators needed beyond basic arithmetic.

1. A byte-addressable cache has a total data capacity of 16 KB, uses 64-byte cache lines, and is 4-way set associative. For a 32-bit physical address, compute the number of bits used for the offset, index, and tag. Show the full split. (7 marks)

2. A program repeatedly accesses pages in the reference string: 7,  0,  1,  2,  0,  3,  0,  4,  2,  37,\;0,\;1,\;2,\;0,\;3,\;0,\;4,\;2,\;3 with 3 physical frames available. Using the FIFO page-replacement policy, count the total number of page faults. (6 marks)

3. Classify each instruction below as R-type, I-type, or J-type (MIPS/RISC-V style) and give a one-line justification for each: (a) add r1, r2, r3 (b) lw r5, 8(r6) (c) j 0x400010 (d) addi r4, r4, -1. (6 marks)

4. After the ALU computes 0x7FFFFFFF + 0x00000001 on a 32-bit signed machine, state the resulting value and the state (set/clear) of the Zero (Z), Negative (N), Carry (C), and Overflow (V) flags. Justify V specifically. (6 marks)

5. A cache line is in the Modified state in Core A under the MESI protocol. Core B issues a read to the same line. Describe the resulting bus transaction and give the final MESI state of the line in both Core A and Core B. (5 marks)

6. Repeat the reference string of Problem 2 (7,0,1,2,0,3,0,4,2,37,0,1,2,0,3,0,4,2,3) with 3 frames, but now use the LRU policy. Count page faults, and state in one sentence why LRU differs from FIFO here. (6 marks)

7. Consider a classic 5-stage pipeline (IF, ID, EX, MEM, WB) with no forwarding. Given:

I1: add r1, r2, r3
I2: sub r4, r1, r5

Identify the hazard type, the specific dependency (RAW/WAR/WAW), and how many stall cycles are needed for I2 without forwarding. Then state how many stalls remain with EX-to-EX forwarding. (6 marks)

8. For each addressing mode, write what the operand value is if r1 = 0x100, memory at 0x100 = 0x42, memory at 0x108 = 0x99, and the immediate/displacement is 8: (a) immediate, (b) register, (c) register-indirect using r1, (d) indexed/displacement 8(r1). (6 marks)

9. A 2-bit saturating branch predictor starts in state Strongly Taken (11). Given the actual branch outcomes: T, N, N, T, list the predictor state after each outcome and count how many mispredictions occurred. (6 marks)

10. Two short-answer discriminations (state the distinguishing principle, ~2 sentences each): (a) A designer wants simultaneous fetch of an instruction and a data word in the same cycle for a DSP — Von Neumann or Harvard? Why? (b) A CPU designer prioritises many simple fixed-length instructions with load/store-only memory access — RISC or CISC, and name one architecture family exemplifying it. (4 marks)

Answer keyMark scheme & solutions

1. Cache address split — Tests 4.1.9 (cache organization) + 4.1.10 (tags/index/offset). Why this method: capacity, line size, and associativity together determine number of sets → drives the index/offset/tag partition.

  • Offset: line = 64 B → log⁡264=6\log_2 64 = 6 bits.
  • Number of lines = 16KB/64B=16384/64=25616\text{KB}/64\text{B} = 16384/64 = 256 lines.
  • Sets = lines / ways = 256/4=64256/4 = 64 sets → index =log⁡264=6= \log_2 64 = 6 bits.
  • Tag = 32−6−6=2032 - 6 - 6 = 20 bits.

Answer: Offset = 6, Index = 6, Tag = 20.

2. FIFO page replacement — Tests 4.1.16. Why: FIFO evicts the oldest-loaded page regardless of use — track load order in a queue.

Ref Frames (oldest→newest) Fault?
7 7 F
0 7,0 F
1 7,0,1 F
2 0,1,2 (evict 7) F
0 0,1,2 hit
3 1,2,3 (evict 0) F
0 2,3,0 (evict 1) F
4 3,0,4 (evict 2) F
2 0,4,2 (evict 3) F
3 4,2,3 (evict 0) F

Total faults = 9.

3. Instruction format classification — Tests 4.1.7. Why: register-only ops = R-type; ops with an immediate/memory-displacement = I-type; unconditional jumps with a large target = J-type.

  • (a) add r1,r2,r3 → R-type (three registers, no immediate).
  • (b) lw r5,8(r6) → I-type (load uses immediate displacement + base register).
  • (c) j 0x400010 → J-type (jump, large address field).
  • (d) addi r4,r4,-1 → I-type (immediate operand).

4. ALU flags — Tests 4.1.6. Why: signed overflow (V) is detected when two same-sign operands produce an opposite-sign result. 0x7FFFFFFF + 1 = 0x80000000.

  • Result = 0x80000000 (= −231-2^{31} signed).
  • Z = 0 (result ≠ 0).
  • N = 1 (MSB = 1, negative).
  • C = 0 (no carry-out of bit 31 for these values).
  • V = 1 — two positives (+231−1+2^{31}-1 and +1+1) gave a negative result → signed overflow.

5. MESI transition — Tests 4.1.13. Why: a remote read to a Modified line forces the owner to supply data and downgrade. Core B's read miss → BusRd. Core A snoops, writes back the modified data (memory updated) and transitions M → S. Core B loads the line in S. Final: Core A = Shared, Core B = Shared.

6. LRU page replacement — Tests 4.1.16 (contrasts with Q2). Why: LRU evicts the least-recently-used page; must track recency of access, not load order.

Ref Frames (LRU→MRU) Fault?
7 7 F
0 7,0 F
1 7,0,1 F
2 0,1,2 (evict 7 LRU) F
0 1,2,0 hit
3 2,0,3 (evict 1) F
0 2,3,0 hit
4 3,0,4 (evict 2) F
2 0,4,2 (evict 3) F
3 4,2,3 (evict 0) F

Total faults = 8. LRU differs because at the ref "0" (position 5) and later, LRU exploits recent reuse of 0, keeping it longer than FIFO would — yielding one fewer fault (8 vs 9).

7. Pipeline hazard — Tests 4.1.19 + 4.1.20. Why: I2 reads r1 produced by I1 → true data dependency (RAW).

  • Hazard type: data hazard, dependency = RAW (read-after-write on r1).
  • Without forwarding: r1 is written in WB (cycle 5) and needed by I2's ID/EX. To read the updated value from the register file requires I2 to stall 2 cycles (with write-in-first-half register file; 2 bubbles).
  • With EX→EX forwarding: result available at end of I1's EX and forwarded into I2's EX → 0 stalls.

8. Addressing modes — Tests 4.1.8. Why: each mode specifies where the operand ultimately lives.

  • (a) immediate → operand value = 8 (the constant itself).
  • (b) register r1 → 0x100.
  • (c) register-indirect [r1] → memory at 0x100 = 0x42.
  • (d) indexed/displacement 8(r1) → memory at 0x100+8 = 0x108 = 0x99.

9. 2-bit saturating predictor — Tests 4.1.21. Why: states 11(ST),10(WT),01(WN),00(SN); predict Taken if MSB=1. Update toward outcome; check prediction each step before updating. Start = 11 (ST), predicts T.

Outcome Prediction (from current) Correct? New state
T T (11) ✓ 11 (ST)
N T (11) ✗ 10 (WT)
N T (10) ✗ 01 (WN)
T N (01) ✗ 10 (WT)

Mispredictions = 3. Final state = 10 (Weakly Taken).

10. Discrimination Q — Tests 4.1.2 + 4.1.3 (+ 4.1.1, 4.1.4). (a) Harvard. Separate instruction and data memories/buses allow fetching an instruction and a data operand in the same cycle, avoiding the Von Neumann single-bus bottleneck — ideal for DSPs. (b) RISC — fixed-length, simple, register-heavy instructions with memory access restricted to load/store. Exemplar family: ARM (or MIPS/RISC-V).

[
  {
    "claim": "16KB, 64B lines, 4-way -> offset=6, index=6, tag=20 for 32-bit address",
    "code": "import math\ncap=16*1024\nline=64\nways=4\noffset=int(math.log2(line))\nlines=cap//line\nsets=lines//ways\nindex=int(math.log2(sets))\ntag=32-offset-index\nresult = (offset,index,tag)==(6,6,20)"
  },
  {
    "claim": "FIFO on 7,0,1,2,0,3,0,4,2,3 with 3 frames yields 9 faults",
    "code": "refs=[7,0,1,2,0,3,0,4,2,3]\nfrom collections import deque\nq=deque()\nfaults=0\nfor r in refs:\n    if r not in q:\n        faults+=1\n        if len(q)>=3:\n            q.popleft()\n        q.append(r)\nresult = faults==9"
  },
  {
    "claim": "LRU on same string with 3 frames yields 8 faults",
    "code": "refs=[7,0,1,2,0,3,0,4,2,3]\nframes=[]\nfaults=0\nfor r in refs:\n    if r in frames:\n        frames.remove(r); frames.append(r)\n    else:\n        faults+=1\n        if len(frames)>=3:\n            frames.pop(0)\n        frames.append(r)\nresult = faults==8"
  }
]