The idea: a write has to reach memory some time
A read only copies data up into the cache. A write changes the data, so the cache and the level below now disagree. A cache must answer two questions. When does the new value go down: at once (write-through) or only when the line leaves (write-back)? And on a write miss, is the block brought in first (write-allocate) or is the word just sent down (no-write-allocate)? The answers change the traffic to L2, the stalls, and even which later reads miss.
The canvas has one direct-mapped L1 of 4 lines × 16 B, a 2-entry write buffer, an L2 and memory, and a cycle clock t. An L1 access costs 1 cycle; a block from L2 costs 10 more; a block from memory costs 100 more again. Each access becomes a row in the table, and the counters panel adds up the misses, the bytes sent to L2, the stall cycles and the AMAT. How a CPU Cache Finds, Misses and Replaces covers associativity and LRU; this page keeps one simple cache and looks at what writes cost.
Write-through needs a write buffer
With write-through, every store also goes down to L2. Waiting 10 cycles for L2 on every store would be slow, so the store goes into a small write buffer and the CPU moves on after 1 cycle. The buffer drains into L2 in the background, one entry every 10 cycles here. This works as long as stores come slower than the buffer drains. When stores come in a burst, the buffer fills, and the next store must stall until an entry is free.
Demo 1 reads x at 0x100 (111 cycles: L2 and memory miss), then stores to x 5 times in a row. The first two stores fit in the buffer. The third waits 8 cycles, the fourth and fifth 9 cycles each: 26 stall cycles. 5 × 4 B = 20 B go to L2. Then R 0x140 maps to the same set, and the old block is clean, so it is simply dropped. The last R 0x100 misses again (a conflict miss) but L2 still has it: 11 cycles. The whole run is 264 cycles for 8 accesses.
Write-back keeps a dirty bit
With write-back, a store changes only the L1 line and sets its dirty bit D. L2 now holds an old copy, and the L1 line is the only correct one. When a dirty line is thrown out, the whole block is written back: 16 B, even if only one word changed. A clean line is just dropped.
Demo 2 runs the same 8 accesses. The 5 stores hit and set D = 1; the last 4 of them cost no traffic at all. R 0x140 evicts the dirty line, and one 16 B block goes into the write buffer, so the fetch of 0x140 need not wait for it. Result: 16 B to L2 instead of 20 B, 0 stall cycles instead of 26, 238 cycles instead of 264, and AMAT 29.75 instead of 33.00. Write-back wins when a block is written many times while it stays in the cache; with one store per block, write-through would send only 4 B where write-back sends 16 B.
| Same 8 accesses | Write-through (Demo 1) | Write-back (Demo 2) |
|---|---|---|
| misses | 3 (2 cold, 1 conflict) | 3 (2 cold, 1 conflict) |
| bytes written to L2 | 20 B (5 words) | 16 B (1 dirty block) |
| write-buffer stalls | 26 cycles | 0 cycles |
| total time, AMAT | 264 cycles, 33.00 | 238 cycles, 29.75 |
Write-allocate or not
On a write miss, write-allocate fetches the block first, like a read miss, and then writes into it. It bets that the program will soon use the rest of the block. No-write-allocate sends the word down and leaves L1 alone. Write-back caches almost always allocate (the point is to collect writes in the line); write-through caches often do not.
Demo 3 (write-through, no-write-allocate) writes 0x200 and 0x204, then reads them. Both writes miss but cost only 1 cycle each. Then R 0x200 misses too. Worse, the buffer still holds the writes to that block, so the read must wait 18 cycles for them to drain before it fetches the block from memory: 129 cycles for one read. Total 132 cycles, AMAT 33.00. Demo 4 is the same with write-allocate: the first write fetches the block (111 cycles), and the other three accesses hit. Total 114 cycles, AMAT 28.50. Both send the same 8 B to L2.
Demos 5 and 6 show the other side. The program reads two hot blocks (0x100, 0x110), writes one word into each of two output blocks (0x200, 0x210) that it never reads, and reads the hot blocks again. The output blocks map to the same sets as the hot ones. Without allocation (Demo 5) the hot blocks stay: 2 hits at the end, 8 B to L2, 226 cycles, AMAT 37.67. With allocation (Demo 6) each output write fetches its block from memory and throws a hot block out; the hot blocks then miss again (2 conflict misses), and each brings a 16 B write-back of a dirty output block: 6 misses, 32 B, 466 cycles, AMAT 77.67.
| Demo | Policy | Misses | To L2 | Stalls | Cycles | AMAT |
|---|---|---|---|---|---|---|
| 3. write then read | WT, no allocate | 3 cold | 8 B | 18 | 132 | 33.00 |
| 4. write then read | WT, allocate | 1 cold | 8 B | 0 | 114 | 28.50 |
| 5. output stores | WB, no allocate | 4 cold | 8 B | 0 | 226 | 37.67 |
| 6. output stores | WB, allocate | 4 cold + 2 conflict | 32 B | 0 | 466 | 77.67 |
The three C's, decided by two shadow caches
Every miss has a cause. The standard way to find it (Mark Hill's) is to run the same accesses through two imaginary caches next to the real one, shown in the referee panel:
- Compulsory (cold): an infinite cache would miss too, because the block was never loaded before. Only bigger blocks or prefetching help.
- Capacity: the infinite cache would hit, but a fully associative LRU cache of the same size (4 lines) would miss. The program uses more blocks than fit; only a bigger cache helps.
- Conflict: the fully associative cache would hit. The block was thrown out only because it had to share a set. More ways or a different data layout help.
Demo 7 reads 0x100, 0x110, 0x120, 0x130, 0x140, then 0x100, 0x140, 0x120. The first five are cold misses; 0x140 lands in set 0 and throws 0x100 out. Then R 0x100 misses: the 4-line fully associative cache has also lost it (it holds 0x110–0x140), so it is a capacity miss. R 0x140 misses in set 0, but the fully associative cache still holds it: a conflict miss. R 0x120 hits. 5 cold + 1 capacity + 1 conflict, 1 hit.
The rule for which cache "would have" the block follows the same allocate policy. With no-write-allocate, a write miss does not put the block in the infinite cache either, so in Demo 3 the read of 0x200 after two writes to it is still a cold miss.
AMAT with two levels and a write buffer
The average memory access time adds what each level costs, weighted by how often it is needed:
AMAT = L1 time + L1 miss rate × (L2 time + L2 local miss rate × memory time)
+ stall cycles per access
Here the L1 miss rate counts only the misses that fetch a block (a no-allocate write miss does not), and the local L2 miss rate is L2 misses divided by the fetches that reach L2. In Demo 7: 7 of 8 accesses fetch, and 5 of those 7 miss in L2. AMAT = 1 + 7/8 × (10 + 5/7 × 100) = 1 + 0.875 × 81.43 = 72.25 cycles, which is exactly 578 cycles / 8. In Demo 1 the stall term matters: AMAT = 1 + 3/8 × (10 + 2/3 × 100) + 26/8 = 1 + 28.75 + 3.25 = 33.00. The counters panel prints the formula with the numbers of the current run. The global L2 miss rate, L2 misses over all accesses, is the product of the two rates: 7/8 × 5/7 = 5/8.
What real caches choose
- L1 data caches of current x86 and ARM cores are write-back with write-allocate, and so are L2 and L3. Stores first go into a store buffer in the core, so a store rarely stalls.
- Write-through L1s appear where keeping L2 always up to date is worth the traffic, for example to make error recovery or coherence simpler. They come with a write buffer that merges stores to the same block (write combining).
- Programs that write big outputs they will not read soon can use non-temporal stores (for example x86
MOVNTDQ), which skip allocation: the behaviour of Demo 5 on a write-back cache.
See also One Load Through the Memory Hierarchy for a single load through the TLB, the caches and DRAM, and Cache Address Breakdown for how the tag, index and offset are cut from an address.
See also MESI Cache Coherence and False Sharing: with several cores, a dirty line is the Modified state, and another core's write must first invalidate it.
See also Cache Strategies for the same write-through and write-behind choice one level up, with Redis in front of a database, and Direct Memory Access for what a dirty line means when a device reads memory.
See also Cache-Friendly Loops, where the order of a loop and tiling decide how many reads miss in a small LRU cache.
What the page leaves out
- One tiny direct-mapped L1 (4 lines × 16 B) and 12-bit addresses; real L1s have 64 B lines, 8 to 12 ways and about 500 times the size.
- Word stores only, and no data values. A real write buffer also merges stores to the same block, and a load can take its value straight from the buffer (store-to-load forwarding) instead of waiting.
- L2 is big enough for every block here, has one write port that never blocks a fetch, and does not allocate on writes: a write to a block L2 lacks goes on to memory without delay.
- Blocking accesses one at a time: no out-of-order core, no store buffer in the core, no prefetcher, no overlapping misses.
- No coherence between cores, no inclusive or exclusive L2, and no write-back of dirty lines at a flush or context switch.
On the mind map
References
Patterson and Hennessy, Computer Organization and Design, Chapter 5: Large and Fast: Exploiting Memory Hierarchy (handling writes, the three C's, multilevel caches)
Hennessy and Patterson, Computer Architecture: A Quantitative Approach, Appendix B: Review of Memory Hierarchy (write strategy, write buffers, AMAT)
Cache writing policies (Wikipedia)
Mark D. Hill and Alan Jay Smith, Evaluating Associativity in CPU Caches, IEEE Transactions on Computers 38(12), 1989 (the three C's)