Cache performance

ACompressed recap

🧾

Writes: write-through (memory every write) vs write-back (dirty bit, block written at eviction); write-allocate vs no-write-allocate; write-back T = t_c + (1−h)(1+d)t_block; write-through (writes take t_m) T = f_r[t_c + (1−h)t_m] + f_w t_m. Miss penalty = latency + (B/bus width) × transfer time; stall cycles = accesses × miss rate × penalty; CPI = base + m_I P + f_mem m_D P. Two levels: local vs global miss rate; AMAT = t₁ + m₁(t₂ + m₂ t_mem). Arrays: row-major addresses; row-wise misses = bytes/B; column-wise reuse needs all rows' blocks to survive.

BMerged rule card

4.3.1 Write policies: write-through vs write-back, dirty bit, write-allocate

• Write hit: write-through (cache + memory) vs write-back (cache only, dirty bit, write block on eviction).
• Write miss: write-allocate vs no-write-allocate. Pairs: WB + WA; WT + NWA.
• Write-back: T = t_c + (1−h)(1 + d)·t_block.
• Write-through (writes take t_m): T = f_r[t_c + (1−h)t_m] + f_w·t_m.

4.3.2 Miss penalty and block transfer; memory-stall cycles; CPI with cache misses

• Miss penalty = latency + (B / bus width) × transfer time (or interleaving formulas).
• Stall cycles = accesses × miss rate × penalty.
• CPI = CPI_base + m_I·P + f_mem·m_D·P.
• Perfect-cache speedup = CPI_eff / CPI_base.

4.3.3 Multilevel caches: L1 and L2, local vs global miss rate, inclusion

• Local miss rate = misses ÷ accesses reaching that level; global = misses ÷ all references = m₁·m₂.
• AMAT = t₁ + m₁(t₂ + m₂·t_mem) (m₂ local).
• Stalls/instr = accesses/instr × m₁ × (t₂ + m₂·t_mem).
• Inclusive vs exclusive.

4.3.4 Programs and caches: array layout, loop order, counting misses

• Row-major: addr = base + (i·M + j)·s. Column-major: base + (j·N + i)·s.
• Row-wise misses = bytes ÷ B; miss ratio = s ÷ B.
• Column-wise: stride M·s; reuse needs all N blocks to survive (size and mapping).
• Fix: loop interchange; blocking (tiling).

CInterleaved GATE-style questions

Q1NAT2 marksWrite-back

Write-back: t_c = 2 ns, block 60 ns, h = 0.9, 25% of victims dirty. AMAT (ns)?

Numerical answer: ________

Q2NAT2 marksWrite-through

Write-through, writes take 30 ns; reads hierarchical with t_c = 3 ns, t_m = 30 ns, read hit ratio 0.9; 80% reads. AMAT (ns)?

Numerical answer: ________

Q3NAT1 markPenalty

A 64-byte block over a 4-byte bus, 2 ns per transfer, 24 ns latency. Penalty (ns)?

Numerical answer: ________

Q4NAT2 marksCPI

Base CPI 1.5; I-miss 2%; D-miss 6%; 25% loads/stores; penalty 50 cycles. Effective CPI?

Numerical answer: ________

Q5NAT2 marksTwo levels

t₁ = 1, m₁ = 10%; t₂ = 8, local m₂ = 50%; memory 100. AMAT (cycles)?

Numerical answer: ________

Q6NAT1 markGlobal

10,000 references; 800 L1 misses; 200 L2 misses. Global L2 miss rate (percent)?

Numerical answer: ________

Q7NAT2 marksArrays

double A[32][32] (8 bytes) at address 0; 2 KB direct-mapped cache with 64-byte blocks; column-wise traversal. Misses?

Numerical answer: ________

Q8MCQ1 markInterchange

Loop interchange improves cache behaviour by:

• (A) making the inner loop walk consecutive addresses
• (B) changing the replacement policy
• (C) reducing the number of instructions
• (D) increasing the block size

DAnswer Vault