Cache replacement write policies and multilevel AMAT
Objectives and boundaries
Extend the existing cache-foundations lesson: trace LRU/FIFO, distinguish write-hit policy from write-miss allocation, count dirty writebacks, and compose two cache levels without mixing local/global miss rates. Prerequisites: block/set mapping and single-level AMAT. Address splitting is not retaught. We omit multicore coherence, virtual indexing, prefetching and overlapping misses.
Traces name memory blocks, not byte addresses. Each request accesses one word wholly within its named block. Initially all lines are invalid. Every read miss allocates; when a set is full, replacement occurs within that set. Miss service finishes before the next request. Dirty writebacks and fills are serialized when time is counted; no write-buffer overlap is assumed unless explicitly stated.
1. Replacement changes history, not placement
Least recently used (LRU) evicts the resident line whose last access is oldest. Both reads and writes update its recency on a hit. FIFO evicts the oldest resident insertion; a hit does not change insertion order. Invalid lines are used before evicting valid lines. Direct mapping has no choice of victim; replacement policies matter when there is more than one eligible line.
Worked comparison: a two-line fully associative cache reads A,B,A,C,B. Under LRU the states, oldest→newest, are [A], [A,B], [B,A], [A,C], [C,B]. Outcomes M,M,H,M,M give one hit. Under FIFO, the third request leaves insertion order [A,B]; C replaces A, leaving [B,C], and the final B hits. Outcomes M,M,H,M,H give two hits. LRU often benefits temporal locality but does not win on every finite trace.
2. Two independent write decisions
On a write hit, write-through updates the cache and propagates the write to the next level; write-back updates the cache and marks the line dirty, delaying propagation until eviction or another required writeback. Dirty means the next level may be stale; valid means the line contains a usable cached block. These bits answer different questions.
On a write miss, write-allocate brings the block into this cache and then performs the write. No-write-allocate sends the write to the lower level without installing the missed block here. Hit policy and miss policy are separate choices. Write-back/write-allocate and write-through/no-write-allocate are common combinations, not logical identities. Real implementations can optimize full-block stores; our model fetches the block on every allocating miss.
Worked traffic example: a one-line write-back, write-allocate cache receives W(A), W(A), R(B). First W(A) fetches A and makes it dirty; second W(A) hits and remains dirty; R(B) evicts dirty A with one block writeback, then fetches B. Totals: two block fills and one block writeback, not one lower-level write per store. Do not add a final cache flush unless requested. Under write-through/no-write-allocate, those two stores each go to the lower level, A is never installed, and R(B) performs the sole block fill. A word write and a block transfer are different traffic units.
3. Dirty victims add conditional cost
Suppose lookup h=2 ns, miss rate m=0.10, each miss fetch takes F=40 ns, and 25% of misses evict a dirty victim with extra serialized writeback D=20 ns. Then average extra miss cost is F+0.25D=45 ns; AMAT=2+0.10×45=6.5 ns. The 25% is conditional on misses, not all accesses. A dirty line that remains resident causes no writeback in this model. If a supplied miss penalty already includes expected dirty writeback, do not add it again.
4. Two levels and conditional probability
Let L1 lookup take h1; its miss rate be m1 per CPU access. On an L1 miss, L2 lookup adds h2. L2 local miss rate m2 is the fraction of L2 requests that miss. An L2 miss adds main-memory penalty P after L2 lookup. Assume all L1 misses look up L2, no parallel lookup, and writes are absent or already accounted for.
AMAT=h1+m1(h2+m2P).
The fraction of CPU accesses reaching memory is m1m2, called the global L2 miss rate in this model. It is not generally m2. Every L1 miss pays the L2 lookup, including L2 hits.
Worked example: h1=1 ns, m1=0.10, h2=8 ns, m2=0.20 and P=60 ns. AMAT=1+0.1(8+0.2×60)=3 ns. Of 1000 accesses, 900 finish in L1 at 1 ns; 80 hit L2 at 9 ns; 20 reach memory at 69 ns. Weighted total=(900+720+1380)/1000=3 ns. Memory-reaching fraction=20/1000=2%, while L2 local miss rate=20/100=20%.
5. Memory stalls are not automatically CPI
If instruction-fetch and data-reference misses are accounted separately, multiply each miss rate by the corresponding accesses per useful instruction and the extra penalty in cycles. Example: base CPI=1, one instruction fetch per instruction with 1% misses, 0.3 data accesses per instruction with 5% misses, and serialized extra miss penalty 40 cycles for either. Added CPI=1×0.01×40+0.3×0.05×40=1; total CPI=2. This assumes the base CPI excludes these misses, no overlap and no double counting. AMAT is time/access; CPI is cycles/instruction.
Common errors
Track state after every request, including recency and dirty status. Keep blocks, bytes, word writes and block writebacks distinct. Define each probability's denominator. Treat stated penalties as extra or total consistently. Neither more associativity nor a write buffer guarantees faster total execution without a timing model.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. A two-line fully associative empty LRU cache reads A,B,A,C,B. Number of hits?
A. 1 B. 2 C. 3 D. 0
Answer: A
A: Only the third request hits; C evicts B before the last request.
B: Two hits would occur under FIFO here, not LRU.
C: Only one reuse survives eviction.
D: The third A is still resident.
P02. One-line empty write-back/write-allocate cache: W(A),W(A),R(B). Dirty writebacks before trace ends, with no final flush?
A. 0 B. 1 C. 2 D. 3
Answer: B
A: R(B) evicts the dirty A.
B: A is written back once when B replaces it.
C: Two stores to A are combined in its one dirty residency.
D: Not every access performs a writeback.
P03. What does no-write-allocate specify on a write miss?
A. Discard the write B. Install the missed block C. Send the write downward without installing the block here D. Make all valid lines dirty
Answer: C
A: The store must still take effect.
B: That is write-allocate.
C: It bypasses allocation in this cache on the miss.
D: Other lines are unrelated to this store.
P04. L1 miss rate is 10%; L2 local miss rate is 30%; every L1 miss visits L2. Fraction of CPU accesses missing both?
A. 30% B. 40% C. 3% D. 10%
Answer: C
A: 30% uses L2 requests as denominator.
B: The conditional rates must not be added.
C: 0.10×0.30=0.03=3%.
D: Some L1 misses hit L2.
P05. h1=2 ns, m1=0.1, h2=6 ns, m2=0.25; memory adds 80 ns after L2 lookup. Serial AMAT?
A. 4.6 ns B. 28 ns C. 2.6 ns D. 10 ns
Answer: A
A: 2+0.1(6+0.25×80)=4.6 ns.
B: This charges the L2 path to every CPU access.
C: This omits memory-miss cost.
D: This treats all L1 misses as 80 ns penalties and omits L2 lookup.
P06. Lookup=1 ns; miss rate=0.2; fill=30 ns; half of misses add a serialized 10 ns dirty writeback. AMAT?
A. 7 ns B. 8 ns C. 9 ns D. 12 ns
Answer: B
A: This omits dirty writebacks.
B: 1+0.2(30+0.5×10)=8 ns.
C: This charges a writeback to every miss.
D: The 50% dirty rate is conditional on misses, not all accesses.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire COA syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in