Memory Hierarchy & Caches

Question 1

(a) L1 = 32 KiB = $2^{15}$ B. Line = 64 B $\Rightarrow$ offset $= \log_2 64 = 6$ bits. (1) Number of lines $= 2^{15}/2^6 = 512$. Ways = 8 $\Rightarrow$ sets $= 512/8 = 64 = 2^6$, index $= 6$ bits. (2) Tag $= 32 - 6 - 6 = 20$ bits. (1)

(b) L2 = 512 KiB = $2^{19}$ B. offset $=6$. Lines $=2^{19}/2^6=8192$. Ways=16 $\Rightarrow$ sets $=8192/16=512=2^9$, index $=9$. Tag $=32-6-9=17$ bits. (2) L1 tag storage: 512 lines $\times(20\text{ tag}+1\text{ valid}+1\text{ dirty})=512\times22=11264$ bits. (2)

(c) Working set $=4096\times8=32768$ B $=32$ KiB $=$ exactly L1 capacity. Because A is contiguous and fully-associative-enough here (8-way, 64 sets, and 32 KiB fills all lines evenly with a linear stride), the whole array just fits. Lines spanned $=32768/64=512$ lines = exactly all 512 L1 lines. (2)

• Compulsory: first pass ($r=0$) touches each of the 512 distinct lines once for the first time $\Rightarrow$ 512 compulsory misses. (2)
• Capacity/Conflict: working set (32 KiB) $\le$ capacity (32 KiB), and a linear scan maps the 512 lines onto 64 sets, 8 per set, exactly filling each set with no set over-subscribed under LRU. Hence on reuse passes $r=1..9$ the whole array is still resident $\Rightarrow$ 0 capacity, 0 conflict misses. Total misses $=512$. (2) (Note the array exactly equals capacity; had N been slightly larger, passes would thrash → capacity misses.)

(d) $\text{AMAT}=t_{L1}+m_{L1}\big(t_{L2}+m_{L2}\cdot t_{DRAM}\big)$. (1) $=1+0.04(12+0.25\times200)=1+0.04(12+50)=1+0.04\times62=1+2.48=3.48$ cycles. (2)

• Halve L1 miss to 2%: $1+0.02\times62=1+1.24=2.24$ → improvement $1.24$ cycles.
• Halve L2 local miss to 12.5%: $1+0.04(12+0.125\times200)=1+0.04(12+25)=1+0.04\times37=1+1.48=2.48$ → improvement $1.00$ cycle. L1 halving ($-1.24$) beats L2 halving ($-1.00$). (2) General condition: L1-rate halving improvement $=\tfrac{1}{2}m_{L1}(t_{L2}+m_{L2}t_{DRAM})$; L2-rate halving improvement $=\tfrac12 m_{L1}m_{L2}t_{DRAM}$. L1 dominates iff $t_{L2}+m_{L2}t_{DRAM} > m_{L2}t_{DRAM}$, i.e. iff $t_{L2}>0$ — always true here (the L1-miss penalty includes the full L2 access chain, so reducing L1 misses removes the L2 hit cost too). (1)

(e) Better: streaming/write-once workloads writing data never re-read soon (e.g. memset of large buffer): no-write-allocate avoids polluting L1 by fetching a line to be fully overwritten; write-through with a write buffer hides latency. (2) Worse: workloads with high write locality / read-after-write reuse (e.g. accumulating into a hot variable in a tight loop): write-through generates a bus/L2 write on every store (bandwidth blowup) and no-allocate keeps the line out of L1, causing repeated misses. (2)

Question 2

(a) 4 KiB page $\Rightarrow$ offset $=\log_2 4096=12$ bits. Index bits $=48-12=36=4\times9$. ✓ Consistent. (1) Entries per PT page $=2^9=512$; each PTE $=8$ B $\Rightarrow 512\times8=4096$ B $=$ one frame. ✓ (2)

(b) 2 GiB $=2^{31}$ B. Pages $=2^{31}/2^{12}=2^{19}=524288$ leaf pages (data). (1)

• L4 (PTE/leaf tables): each maps 512 pages $\Rightarrow 2^{19}/2^9=2^{10}=1024$ tables. (1)
• L3: each maps 512 L4 tables $\Rightarrow 1024/512=2$ tables. (1)
• L2: maps 2 L3 tables $\Rightarrow 1$ table. (1)
• L1 (root): $1$ table. (1) Total tables $=1024+2+1+1=1028$; each $=4$ KiB $\Rightarrow 1028\times4096=4{,}210{,}688$ B $\approx 4.02$ MiB. (1)

(c) TLB reach = amount of memory mappable by the TLB's entries simultaneously $=$ (entries)$\times$(page size). (1) 4 KiB pages: $512\times4\text{ KiB}=2048\text{ KiB}=2$ MiB. (2) 2 MiB huge pages: $512\times2\text{ MiB}=1024$ MiB $=1$ GiB. (1) An 800 MiB working set exceeds 2 MiB (base pages) → heavy TLB capacity misses; but $800<1024$ MiB fits in huge-page reach → TLB misses become rare (compulsory only). (1)

(d) $T_{eff}=h(t+m)+(1-h)(t+W+m)=t+m+(1-h)W$. (2) $=1+100+0.02\times100=101+2=103$ cycles. (2)

Question 3

(a) (8 marks; ~1.5 per correct row incl. bus txn)

(b) After a lone read that misses with no other cache holding the block, state E means the line is clean and privately owned. If the same core then writes it, it can silently transition $E\to M$ with no bus transaction (no other copy to invalidate). A protocol with only M/S/I would have loaded it as S, forcing a BusUpgr/BusRdX on the write to invalidate phantom sharers. So E saves one bus transaction on the read-then-write sequence. (4)

(c) Under SC, all four ops (2 stores, 2 loads) appear in one total order consistent with each core's program order: $x{=}1$ before $r0{=}y$, and $y{=}1$ before $r1{=}x$. (2) Suppose $r0=r1=0$. $r0=0$ means $r0{=}y$ read before $y{=}1$ in the global order. $r1=0$ means $r1{=}x$ read before $x{=}1$. Program order: $x{=}1 \prec r0{=}y \prec y{=}1$ (last from $r0$ reading old y) and $y{=}1 \prec r1{=}x \prec x{=}1$. Chaining: $x{=}1 \prec \dots \prec y{=}1 \prec \dots \prec x{=}1$ — a cycle, contradicting a total order. Hence $r0=r1=0$ impossible. (2) Under TSO/store-buffer: each store sits in the core's local store buffer; the load $r0{=}y$ and $r1{=}x$ execute (bypass buffer / read memory) before the buffered stores drain to memory. Both loads see the old value 0. Store→load reordering is allowed (a load may complete before an earlier store in program order becomes globally visible), so $r0=r1=0$ is permitted. (2)

[
{"claim":"L1 tag=20 bits, sets=64, offset=6","code":"offset=log(64,2); sets=(2**15//2**6)//8; idx=log(sets,2); tag=32-offset-idx; result=(offset==6 and sets==64 and idx==6 and tag==20)"},
{"claim":"L1 tag storage = 11264 bits","code":"result=(512*(20+1+1)==11264)"},
{"claim":"AMAT baseline = 3.48 cycles","code":"amat=1+Rational(4,100)*(12+Rational(25,100)*200); result=(amat==Rational(348,100))"},
{"claim":"Halving L1 improves 1.24, halving L2 improves 1.00","code":"base=1+Rational(4,100)*62; a=1+Rational(2,100)*62; b=1+Rational(4,100)*(12+Rational(125,1000)*200); result=(base-a==Rational(124,100) and base-b==1 and (base-a)>(base-b))"},
{"claim":"Page table total = 1028 tables","code":"leaf=2**19//2**9; l3=leaf//512; l2=1; l1=1; result=(leaf==1024 and leaf+l3+l2+l1==1028)"},
{"claim":"TLB reach 2MiB (4K) and 1GiB (2M huge)","code":"r4=512*4096; rh=512*2*1024*1024; result=(r4==2*1024*1024 and rh==1024*1024*1024)"},
{"claim":"Effective time with TLB = 103 cycles","code":"result=(1+100+(1-Rational(98,100))*100==103)"}
]