Computer Architecture (Deep)

Q1 (12)

(a) Bit fields (6)

• Offset: line size $= 64 = 2^6$ B ⇒ 6 offset bits. (2)
• Number of sets: total size / (assoc × line) $= 16384 / (4 \times 64) = 16384/256 = 64$ sets $=2^6$ ⇒ 6 index bits. (2)
• Tag: $32 - 6 - 6 = 20$ ⇒ 20 tag bits. (2)

Why: offset selects a byte in a line; index selects a set; the remainder identifies the block within a set.

(b) 0xDEADBEEF (4) Binary breakdown: address = 1101 1110 1010 1101 1011 1110 1110 1111.

• Offset = low 6 bits = 101111 = 0x2F (=47).
• Index = next 6 bits. Low 12 bits = 1110 1110 1111; drop offset(6) → next 6 = 111011 = 0x3B (=59).
• Tag = top 20 bits = address >> 12 = 0xDEADB = 0xDEADB. (2 for tag, 1 each for index/offset)

Check: $0xDEADBEEF = (0xDEADB \times 4096) + (0x3B\times 64) + 0x2F$.

(c) Tag storage (2) Lines total = 64 sets × 4 ways = 256 lines. Tag bits = 256 × 20 = 5120 bits (= 640 B).

Q2 (10)

(a) (3) Page = 4 KB = $2^{12}$ ⇒ offset = 12 bits. VPN = $48-12 =$ 36 bits.

(b) (3) Entries = $2^{36}$ ≈ 68.7 billion. (1) Impractical: a flat table of $2^{36}$ entries (× several bytes each) is hundreds of GB per process — unfeasible; hence multi-level / inverted / hashed page tables. (2)

(c) (4) Physical address = PFN ∥ offset.

• PFN = 0xABCDE, offset = 0x678.
• Shift PFN left by 12 bits: 0xABCDE000, then OR offset: 0xABCDE000 | 0x678 = 0xABCDE678. (2 for method, 2 for result) Physical address = 0xABCDE678.

Q3 (12)

(a) RAW hazards (4) (1 each)

• I1→I2 on r1 (add writes r1, sub reads r1).
• I2→I3 on r4 (sub writes r4, lw uses r4 as base).
• I3→I4 on r6 (lw loads r6, and reads r6).
• I1→I4 on r1 (and reads r1) — resolved by natural distance, but note it.

(b) No forwarding (4) Write-in-first-half/read-in-second-half means a dependent instr must have its ID in the same cycle the producer does WB. Producer WB is in cycle (issue+4). Consumer ID must be ≥ that cycle.

I2 needs r1 (I1 WB in c5) → ID in c5 (2 stalls). I3 needs r4 (I2 WB in c8) → ID in c8. I4 needs r6 (I3 WB in c11) → ID in c11, EX 12, MEM 13, WB 14. Total ≈ 14 cycles (accept 13–14 depending on IF-stall accounting; consistent chain of 2 stalls each dependent pair).

(c) Full forwarding (4) With forwarding, ALU→ALU results bypass, removing add/sub stalls. But I3 (lw) → I4 (and) is a load-use hazard: lw's data is only available after MEM, one stage too late for I4's EX, so forwarding needs 1 stall. No-stall base = 5 + (4−1) = 8 cycles; +1 load-use stall = 9 cycles. Why unavoidable: the loaded value doesn't exist until end of MEM (cycle after EX), so it cannot be forwarded backward in time to the immediately following EX — exactly one bubble is mandatory.

Q4 (10)

(a) Trace (7) — states: 00=SN,01=WN,10=WT,11=ST. Predict T iff MSB=1. On Taken increment (saturate 11), on Not-taken decrement (saturate 00).

(1 mark per correct row = 5, +2 for correct transition logic)

(b) (3) Mispredictions = 4 (only branch 5 correct). (1) A 2-bit predictor tolerates a single anomaly without flipping its prediction: on a loop that is taken many times then falls through once, the counter stays in a "taken" region and mispredicts only the exit, whereas a 1-bit predictor mispredicts twice per loop pass (the exit and the first iteration of the next entry). (2)

Q5 (8) — MESI trace

(2 marks per step: state pair + action)

1. C0 reads B: BusRd, no other copy → C0=E, C1=I. (Exclusive: clean, sole owner.)
2. C1 reads B: BusRd; C0 snoops, downgrades E→S, supplies/shares → C0=S, C1=S.
3. C0 writes B: issues BusRdX/Upgrade (invalidate); C1 sees it, C1 S→I → C0=M, C1=I. (Modified: dirty, exclusive.)
4. C1 reads B: BusRd; C0 in M snoops → writes back / supplies data, M→S → C0=S, C1=S.

Final: (C0=S, C1=S). Key ideas: E allows silent upgrade to M; M requires write-back on external read.

Q6 (8)

(a) (4) $\text{CPU time}=IC\times CPI\times T_c$.

• RISC: minimises CPI (near 1, pipeline-friendly, fixed-length simple instrs) and lowers $T_c$, trading off higher IC (more instructions per task). (2)
• CISC: minimises IC (rich, complex multi-step instructions do more per instruction), trading off higher CPI (multi-cycle/microcoded instructions). (2)

(b) (4) Von Neumann bottleneck: instructions and data share one memory and one bus, so the CPU cannot fetch an instruction and a data operand simultaneously — bus throughput caps performance. (2) Harvard: provides separate instruction and data memories/buses, so an instruction fetch and a data access proceed in parallel each cycle, doubling effective memory bandwidth and removing that contention. (2)

[
  {"claim":"16KB 4-way 64B cache: 6 offset, 6 index, 20 tag bits","code":"total=16*1024; line=64; assoc=4; offset=6; sets=total//(assoc*line); import math; index=int(math.log2(sets)); tag=32-offset-index; result=(offset==6 and index==6 and tag==20)"},
  {"claim":"0xDEADBEEF decomposes to tag 0xDEADB, index 0x3B, offset 0x2F","code":"a=0xDEADBEEF; offset=a & 0x3F; index=(a>>6)&0x3F; tag=a>>12; result=(tag==0xDEADB and index==0x3B and offset==0x2F)"},
  {"claim":"Total tag storage = 5120 bits","code":"sets=64; ways=4; tagbits=20; result=(sets*ways*tagbits==5120)"},
  {"claim":"PFN 0xABCDE with offset 0x678 gives physical 0xABCDE678","code":"pfn=0xABCDE; off=0x678; pa=(pfn<<12)|off; result=(pa==0xABCDE678)"},
  {"claim":"2-bit predictor on T,T,N,T,T from state 00 yields 4 mispredictions","code":"state=0; seq=[1,1,0,1,1]; mis=0\nfor a in seq:\n    pred=1 if state>=2 else 0\n    if pred!=a: mis+=1\n    state=min(3,state+1) if a else max(0,state-1)\nresult=(mis==4)"}
]