Computer Architecture (Deep)

Question 1 (12)

(a) Line = 64 B ⇒ offset = $\log_2 64 = 6$ bits. Cache = 32 KiB = 32768 B. Number of lines = $32768/64 = 512$. 4-way ⇒ sets = $512/4 = 128$ ⇒ index = $\log_2 128 = 7$ bits. Tag = $32 - 7 - 6 = 19$ bits. Offset 6, Index 7, Tag 19. (1 each for offset, index, tag; 1 for method) (4)

(b) Overhead per line = tag(19) + valid(1) + dirty(1) = 21 bits. Total lines = 512. Total overhead = $512 \times 21 = 10752$ bits. (4) (2 for per-line overhead, 2 for total.)

(c) Working set = 128 KiB / 64 B = 2048 distinct lines accessed per iteration. Cache holds only 512 lines. Since $2048 > 512$, every line is evicted before reuse in the next iteration ⇒ 0% reuse hit rate; this is capacity-miss thrashing (working set exceeds cache capacity). (4) (2 for the numeric comparison, 2 for naming capacity thrashing.)

Question 2 (12)

(a) 4 KiB page ⇒ offset = $\log_2 4096 = 12$ bits. VPN = $48 - 12 = 36$ bits. PPN = $40 - 12 = 28$ bits. (3) (1 each)

(b) Address 0x00007FFCA3B1. Offset = low 12 bits. 0x...A3B1 low 12 bits = 0xB1 & bits: binary of A3B1 = 1010 0011 1011 0001; low 12 = 011110110001? Let's compute properly. $0x7FFCA3B1$ = 0111 1111 1111 1100 1010 0011 1011 0001. Low 12 bits = 0011 1011 0001 = 0x3B1. Remaining = value shifted right 12: $0x7FFCA3B1 \gg 12 = 0x7FFCA$. VPN = 0x7FFCA, offset = 0x3B1. (4) (2 offset, 2 VPN.)

(c) Physical addr = (PPN << 12) | offset = $0x2F00A \times 0x1000 + 0x3B1$ = 0x2F00A3B1. Physical address = 0x2F00A3B1. (3)

(d) Avg = hit_cost + miss_rate × walk = $1 + 0.02 \times 90 = 1 + 1.8 = 2.8$ ns. (2)

Question 3 (14)

(a) RAW dependencies: (4)

• I1 → I2 on x2 (load produces x2, add uses it)
• I2 → I3 on x3
• I1 → I3 on x2
• I3 → I4 on x5 (1 each.)

(b) The only stall is the load-use hazard: I2 needs x2, but a load's data is ready only after MEM, so it cannot be forwarded to I2's EX in time. 1 bubble is required between I1 and I2. All other dependencies (I2→I3 on x3, I3→I4 on x5) are satisfied by EX/MEM → EX forwarding with no stall. (5) (2 identify load-use, 1 count = 1 bubble, 2 justification.)

(c) Timing (F=IF, D=ID, X=EX, M=MEM, W=WB, -=stall): (5)

Cycle:   1  2  3  4  5  6  7  8
I1 lw:   F  D  X  M  W
I2 add:     F  D  -  X  M  W
I3 sub:        F  -  D  X  M  W
I4 sw:              F  D  X  M  W

I2's ID stalls one cycle (bubble). Last instruction I4 completes WB in cycle 9? Re-align: I4 IF in cycle 6, ID 7, EX 8, MEM 9? Let me recount from diagram: I4 IF=6,D=7,X=8,M=9,W=10.

Corrected diagram:

Cycle:   1  2  3  4  5  6  7  8  9  10
I1 lw:   F  D  X  M  W
I2 add:     F  D  -  X  M  W
I3 sub:        F  -  D  X  M  W
I4 sw:              F  D  X  M  W

Total cycles = 10. (Baseline without stall would be 4 + 4 = 8 cycles; one bubble adds 1 → 9. Note diagram shows I4 finishing cycle 10 because IF of I3 also stalls one cycle propagating the bubble; total = 9 cycles is acceptable if the bubble is counted once. Accept 9 as the number of cycles to complete = last WB.) Accept 9 cycles (5 base + 4 instr − overlap + 1 bubble = 8 + 1 = 9). Award full marks for correct diagram + one bubble + stated total of 9. (3 diagram, 2 total cycles = 9.)

Question 4 (12)

(a) 2-bit counter, start 00 (SNT). (7)

Mispredictions = 4. (1 per row correctness, 1 for count.)

(b) MESI trace: (5)

(1 per step + 1 for naming invalidate/writeback correctly.)

Question 5 (10)

(a) Harvard preferred. Separate instruction and data memories/buses allow simultaneous instruction fetch and data access in the same cycle, eliminating the Von Neumann bottleneck (single shared bus forcing fetch and data to contend serially). This gives single-cycle fetch during data access and more predictable timing — ideal for real-time control. (4)

(b) A set-associative cache with LRU makes access latency data-dependent (hit vs miss varies), so WCET analysis must assume worst-case misses everywhere, and LRU state depends on execution history → non-deterministic timing. Alternative: tightly-coupled memory (TCM) / scratchpad with fixed single-cycle latency (or a locked/way-partitioned cache) giving bounded, analyzable access time. (3)

(c) Any two: (3)

• Fixed 32-bit encoding lets IF fetch exactly one instruction per cycle with predictable instruction boundaries (no need to decode length first) → simpler pipelined fetch.
• Simpler, faster decode (regular field positions) → shorter ID stage / higher clock.
• Easier alignment / branch-target computation and simpler superscalar dispatch. (1.5 each.)

[
  {"claim":"Q1a tag bits = 19 for 32-bit addr, 6 offset, 7 index","code":"offset=6; index=7; tag=32-offset-index; result = (tag==19)"},
  {"claim":"Q1b total overhead bits = 10752","code":"lines=32768//64; per=19+1+1; result = (lines*per==10752)"},
  {"claim":"Q1c working-set lines 2048 exceeds 512 capacity","code":"ws=(128*1024)//64; cap=(32*1024)//64; result = (ws==2048 and cap==512 and ws>cap)"},
  {"claim":"Q2c physical address = 0x2F00A3B1","code":"pa=(0x2F00A<<12)|0x3B1; result = (pa==0x2F00A3B1)"},
  {"claim":"Q2d average translation time = 2.8 ns","code":"result = (1 + Rational(2,100)*90 == Rational(28,10))"},
  {"claim":"Q2b VPN=0x7FFCA offset=0x3B1","code":"a=0x7FFCA3B1; result = ((a>>12)==0x7FFCA and (a & 0xFFF)==0x3B1)"}
]