2.4 Cache Write Policies, Replacement Algorithms & Multi-Level AMAT

Back to DBMS Notes

📚02Topic 2.4⏱️24 min

🎯High-Yield For:Crucial for cache coherence protocols, kernel dirty page flushing, memory subsystem optimization, and reducing AMAT in high-performance processors.

💡 Core Intuition: The Draft vs Live Document

In previous lessons, we mastered how the CPU reads data from cache lines using Direct, Fully Associative, and Set-Associative mapping. However, memory operations are fundamentally bidirectional. Programs perform stores just as frequently as loads:

$\text{Memory Traffic Split} \approx 70\% \text{ to } 80\% \text{ Reads}, \quad 20\% \text{ to } 30\% \text{ Writes}$

Handling write operations introduces a severe architectural dilemma: whenever the CPU modifies a byte inside the ultrafast $L_1$ cache, the corresponding copy residing in Main Memory (DRAM) instantly becomes stale and obsolete. If an I/O device or another processor core reads that DRAM location, it reads corrupted, outdated data.

🍳 The Everyday Analogy: The Collaborative Google Doc vs Local Notepad Draft

Imagine you are authoring a mission-critical financial report with multiple department stakeholders:

1. The Write-Through Strategy (Live Collaborative Google Doc):
   Every single character you type on your keyboard is instantaneously transmitted across the network to the central cloud database.

   • The Benefit: 100% consistency. Anyone looking at the central cloud document sees your exact edits in real time.
   • The Penalty: Typing speed is completely handcuffed to network latency. If your network requires $50\text{ ms}$ round-trip, every keystroke stutters and stalls. To prevent your fingers from freezing, you place a small Write Buffer (an asynchronous local queue) to catch keystrokes while the network slowly flushes them.

2. The Write-Back Strategy (Local Notepad Draft with Auto-Save on Exit):
   You draft the entire document locally on your blazing-fast SSD text editor. You edit, re-type, and overwrite paragraphs millions of times without transmitting a single byte over the network.

   • The Benefit: Maximum speed with virtually zero network traffic.
   • The Penalty: The cloud database is out of sync until you hit "Save & Close". When your local workspace is full and you must close this document to open another, you inspect a single sticky note: the Dirty Bit (Modified Bit). If the document was modified ($\text{Dirty} = 1$), you write it back to the cloud before discarding. If you merely read it without typing ($\text{Dirty} = 0$), you discard it instantly with zero network cost!

Dimension	Write-Through Strategy	Write-Back (Copy-Back) Strategy
Update Scope	Simultaneous update to both Cache & Main Memory	Update cache line only; Main Memory updated on eviction
DRAM Consistency	Always 100% consistent with cache	Main Memory remains stale while cache line is dirty
Bus Traffic	High: Every write instruction consumes memory bus	Low: Multiple writes to same block incur zero bus traffic
Hardware Overhead	Requires FIFO Write Buffer to prevent CPU stalls	Requires Dirty Bit per line + Write-Back buffer
Eviction Cost	Zero cycles (victim discarded cleanly)	Variable: Clean line costs 0; Dirty line requires write-back

💻 Bridging to Computer Science

When a write operation occurs, two independent hardware decisions must be made:

1. What happens on a Write Hit?
   • Write-Through: Update both the cache line and Main Memory simultaneously.
   • Write-Back (Copy-Back): Update only the cache line and set the line's Dirty Bit ($\text{Modified Bit} = 1$). Main Memory is updated only when the block is eventually evicted.
2. What happens on a Write Miss?
   • Write-Allocate (Fetch-on-Write): Fetch the missing block from Main Memory into the cache, allocate a line, and perform the write into the cache. (Almost universally paired with Write-Back).
   • No-Write-Allocate (Write-Around): Bypass the cache entirely and write directly to Main Memory without loading the block into cache. (Almost universally paired with Write-Through).

Furthermore, because cache capacity is rigidly bounded, bringing any new block into a saturated set requires a Replacement Algorithm (FIFO, LRU, MRU, or OPT) to select a victim block. Finally, how do system architects evaluate the aggregate performance of these design decisions? By computing the Average Memory Access Time (AMAT) across serial and parallel multi-level hierarchies.

---

📑Table of Contents

• ⚙️ Cache Write Policies: Through vs Back & Allocation
  • Write-Through with Write Buffer Mechanics
  • Write-Back Mechanics & Tag Directory Sizing
  • Write Miss Policies: Write-Allocate vs No-Write-Allocate
• 🔄 Cache Replacement Algorithms (FIFO, LRU, MRU, OPT)
  • 1. First-In, First-Out (FIFO)
  • 2. Least Recently Used (LRU)
  • 3. Most Recently Used (MRU)
  • 4. Optimal Replacement Policy (OPT / Belady's MIN)
• 📈 Stack Algorithms & Belady's Anomaly Demystified
  • Concrete Proof of Belady's Anomaly under FIFO
  • Why LRU and OPT are Immune: The Inclusion Property of Stack Algorithms
  • 🎮 Interactive Belady's Anomaly & Replacement Simulator
• 🎯 The 3Cs of Cache Misses & Block Size Trade-Offs
  • The Fourth 'C': Coherence Misses
  • Block Size Trade-Offs
• 🧮 Multi-Level AMAT: Hierarchical vs Simultaneous
  • 1. Hierarchical (Serial / Sequential) Access Organization
  • 2. Simultaneous (Parallel) Access Organization
  • Average Cost per Byte Across Hierarchy
• 🏭 Real-World Production Context: Kernel Dirty Page Tuning & Hardware Coherence
  • 1. Linux Page Cache Dirty Ratio Tuning
  • 2. Multi-Core Cache Coherence: The MESI Protocol
• 📐 Numerical Applications & Worked Examples
  • Example 1: Multi-Level Cache AMAT with Mixed Read/Write Traffic
  • Example 2: 2-Way Set-Associative Cache Miss Trace & 3Cs Classification
  • Example 3: Multi-Level Cache Hierarchy with L1, L2, and Miss Penalty
• 🎯 Exam & Interview Pitfall Check

---

⚙️ Cache Write Policies: Through vs Back & Allocation

A processor datapath must cleanly handle both write hits and write misses without introducing race conditions or unrecoverable bus saturation.

Write-Through with Write Buffer Mechanics

In a naive Write-Through implementation, every CPU store instruction stalls execution until DRAM acknowledges the write (typically $50\text{ to }100\text{ ns}$, or $150\text{ to }300\text{ CPU cycles}$). This destroys CPU performance.

To overcome this bottleneck, computer engineers insert a hardware Write Buffer between the cache and Main Memory:

Architecture Flow

Write-Through Datapath with FIFO Write Buffer

💡 Hover or click any card for deep-dive operational details

CPU Store

Executes 32/64-bit store instruction at cycle t0

→

L1 Cache Update

Line updated in SRAM (1 cycle latency)

→

Write Buffer Enqueue

FIFO queue stores [Address, Data] without CPU stall

→

DRAM Controller

Drains buffer entries to DRAM in background

→

Buffer Saturation

CPU stalls only if FIFO buffer becomes completely full

Write Buffer Stall Condition: If the CPU issues a continuous burst of write instructions faster than the DRAM controller can drain them, the write buffer saturates. Once full, the CPU is forced to stall until an entry drains to memory.

Write-Back Mechanics & Tag Directory Sizing

In a Write-Back cache, a block is written directly to SRAM at full core clock speed. The memory bus remains completely idle. To track whether a line has been altered:

1. Tag Directory Augmentation: Each tag directory entry requires an extra status bit: $\text{Status Bits per Line} = \text{Valid Bit } (1\text{ bit}) + \text{Dirty Bit } (1\text{ bit})$
2. Read Hit: Dirty bit remains unchanged.
3. Write Hit: Data is written to the cache data array, and the hardware sets $\text{Dirty Bit} \leftarrow 1$.
4. Eviction on Replacement:
   • If $\text{Dirty Bit} == 0$ (Clean Block): The existing block is safely overwritten by the newly requested block. Latency penalty $= 0\text{ extra writes}$.
   • If $\text{Dirty Bit} == 1$ (Dirty Block): The controller must first write the entire modified block back to Main Memory before (or concurrently with) filling the line with the new block.

$\text{Tag Directory Size (Write-Back)} = N \times (t + 1_{\text{valid}} + 1_{\text{dirty}} + r_{\text{replacement}}) \text{ bits}$

Write Miss Policies: Write-Allocate vs No-Write-Allocate

When the CPU issues a store to a memory address that is not present in the cache (a write miss), how should the controller respond?

Write Miss Policy	Action on Miss	Bus Traffic Impact	Standard Pairing
Write-Allocate (Fetch on Write)	Fetch missing block from DRAM into Cache Line, then complete store into cache	Higher initial fill latency, but absorbs future repeated writes locally	Universally paired with Write-Back caches
No-Write-Allocate (Write-Around)	Bypass cache entirely; write data directly to DRAM over system bus	Low cache disruption; avoids polluting cache lines with one-off writes	Universally paired with Write-Through caches

• Write-Allocate (Fetch on Write):
  The missing block is fetched from Main Memory into the cache, exactly like a read miss. Once the block is seated in the cache line, the CPU completes the write into the cache. This policy leverages temporal locality under the assumption that a recently written address will likely be read or written again shortly.
• No-Write-Allocate (Write-Around):
  The block is not loaded into the cache. The CPU writes the data directly to Main Memory over the bus. The cache contents remain untouched.

---

🔄 Cache Replacement Algorithms (FIFO, LRU, MRU, OPT)

In a Direct-Mapped Cache, each memory block maps to exactly one predetermined line ($c = b \pmod N$). Therefore, no replacement algorithm is needed or possible—the incoming block deterministically kicks out whatever currently occupies that line.

In Set-Associative ($K$-Way) and Fully Associative caches, a block may reside in any of $K$ lines within a set (or any line in the cache). When a set becomes full and a miss occurs, the cache controller must execute a hardware replacement policy to select the victim block.

Policy	Full Name	Eviction Decision Rule	Hardware Complexity
FIFO	First-In, First-Out	Evicts the block that arrived earliest in chronological time, regardless of access count	Low ($\lceil \log_2 K \rceil$ counter per set)
LRU	Least Recently Used	Evicts the block unreferenced for the longest elapsed past duration	Medium (Tree-PLRU or age matrix)
MRU	Most Recently Used	Evicts the block accessed most recently (optimal for cyclic scans of size $K+1$)	Low (Single pointer / bit)
OPT (MIN)	Optimal Replacement	Evicts the block whose next reference is farthest in future (theoretical oracle)	Unrealizable in physical hardware

1. First-In, First-Out (FIFO)

FIFO replaces the block that has resided in the cache set for the longest continuous chronological duration. It treats each set as a circular queue.

• Hardware Implementation: A small counter of $\lceil \log_2 K \rceil$ bits per set that points to the next victim line on each allocation.
• Flaw: FIFO is completely blind to frequency and recency. A foundational variable or loop counter loaded at program startup will be evicted simply because it is old, even if it is accessed on every single clock cycle.

🎮 Interactive FIFO Replacement Trace Simulator

Step through the standard $20$-reference workload across $4$ cache lines under FIFO below. Observe how the oldest resident block is evicted in strict circular order across each clock cycle:

Presets:

Cycle:0 / 20

Click any cycle column to inspect cache state

Hit (H) Miss (M) Current (t0)

Cycle	t1	t2	t3	t4	t5	t6	t7	t8	t9	t10	t11	t12	t13	t14	t15	t16	t17	t18	t19	t20
Block	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
Line 0	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·
Line 1	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·
Line 2	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·
Line 3	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·
Result	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·

💡 Architectural Step Reasoning

Initial state: Cache is completely empty. Valid bits are 0. Click 'Step Next' to begin.

0

Hits

0

Misses

0%

Hit Ratio

0

Compulsory

0

Conflict

0

Capacity

2. Least Recently Used (LRU)

LRU evicts the block that has not been accessed for the longest period of time. It directly optimizes for the principle of temporal locality: if a block has not been touched in a long time, it is unlikely to be needed in the near future.

• Hardware Implementation (for $K = 2$): A single bit per set, toggled to point to the other line whenever one line is accessed.
• Hardware Implementation (for $K = 4$ or $8$): Pseudo-LRU (tree-based bit flipping) or age matrix registers. True LRU for high associativity incurs quadratic hardware complexity ($\frac{K(K-1)}{2}$ bits per set).

🎮 Interactive LRU Replacement Simulator & Recency Promotion

Watch temporal locality in action below. Notice how repeated hits on recently accessed blocks refresh their recency timestamps, protecting frequently used lines from eviction and boosting the hit rate to $60\%$:

Presets:

Cycle:0 / 20

Click any cycle column to inspect cache state

Hit (H) Miss (M) Current (t0)

Cycle	t1	t2	t3	t4	t5	t6	t7	t8	t9	t10	t11	t12	t13	t14	t15	t16	t17	t18	t19	t20
Block	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
Line 0	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·
Line 1	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·
Line 2	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·
Line 3	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·
Result	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·

💡 Architectural Step Reasoning

Initial state: Cache is completely empty. Valid bits are 0. Click 'Step Next' to begin.

0

Hits

0

Misses

0%

Hit Ratio

0

Compulsory

0

Conflict

0

Capacity

3. Most Recently Used (MRU)

MRU evicts the block that was accessed most recently. While counter-intuitive for general software, MRU is optimal for access patterns that loop repeatedly over an array of size $M$ that is strictly larger than cache capacity $C$ ($M = C + 1$). Under LRU, every single access in cyclic scans results in a miss ($0\%$ hit rate), whereas MRU preserves $C - 1$ hits per iteration!

4. Optimal Replacement Policy (OPT / Belady's MIN)

Formulated by Laszlo Belady in 1966, OPT replaces the block that will not be referenced for the longest period of time in the future.

• The Oracle Paradox: OPT requires clairvoyant, omniscient knowledge of future memory requests. Because real-time hardware cannot predict the future, OPT cannot be implemented in commercial hardware.
• Utility: OPT serves as the theoretical gold standard benchmark against which all practical algorithms (LRU, FIFO, Random) are compared.

🎮 Interactive Optimal (OPT / MIN Oracle) Simulator

Experience the clairvoyant MIN algorithm below. Notice how the controller scans future references to evict the block that will remain unused for the longest upcoming duration, achieving the theoretical upper-bound hit rate:

Presets:

Cycle:0 / 20

Click any cycle column to inspect cache state

Hit (H) Miss (M) Current (t0)

Cycle	t1	t2	t3	t4	t5	t6	t7	t8	t9	t10	t11	t12	t13	t14	t15	t16	t17	t18	t19	t20
Block	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
Line 0	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·
Line 1	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·
Line 2	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·
Line 3	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·
Result	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·	·

💡 Architectural Step Reasoning

Initial state: Cache is completely empty. Valid bits are 0. Click 'Step Next' to begin.

0

Hits

0

Misses

0%

Hit Ratio

0

Compulsory

0

Conflict

0

Capacity

---

📈 Stack Algorithms & Belady's Anomaly Demystified

Common intuition suggests that adding more memory or increasing the number of cache lines should always decrease (or at least keep constant) the total number of cache misses. However, under certain replacement policies, this intuition catastrophically fails.

Definition (Belady's Anomaly): The phenomenon where increasing the capacity (number of lines/frames) of a cache or memory system results in an increase in the total number of misses/faults for a fixed reference string.

Concrete Proof of Belady's Anomaly under FIFO

Consider a cache memory operating with the following reference sequence of memory block requests:

$\text{Reference String} = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]$

Trace 1: FIFO with 3 Cache Lines ($N = 3$)

Let us trace the cache state cycle-by-cycle across the 12 memory accesses:

Access	Request	Line 0	Line 1	Line 2	Result	Status / Victim
1	1	[1]	-	-	MISS	Compulsory (Placed in Line 0)
2	2	[1]	[2]	-	MISS	Compulsory (Placed in Line 1)
3	3	[1]	[2]	[3]	MISS	Compulsory (Placed in Line 2)
4	4	[4]	[2]	[3]	MISS	Evict 1 (Oldest)
5	1	[4]	[1]	[3]	MISS	Evict 2 (Oldest)
6	2	[4]	[1]	[2]	MISS	Evict 3 (Oldest)
7	5	[5]	[1]	[2]	MISS	Evict 4 (Oldest)
8	1	[5]	[1]	[2]	HIT	Block 1 present in Line 1
9	2	[5]	[1]	[2]	HIT	Block 2 present in Line 2
10	3	[5]	[3]	[2]	MISS	Evict 1 (Oldest)
11	4	[5]	[3]	[4]	MISS	Evict 2 (Oldest)
12	5	[5]	[3]	[4]	HIT	Block 5 present in Line 0

$\text{Total Misses with 3 Lines} = 9 \text{ Misses} \quad (\text{Hits} = 3)$

Trace 2: FIFO with 4 Cache Lines ($N = 4$)

Now let us increase the cache size by $33\%$ to 4 lines:

Access	Request	Line 0	Line 1	Line 2	Line 3	Result	Status / Victim
1	1	[1]	-	-	-	MISS	Compulsory
2	2	[1]	[2]	-	-	MISS	Compulsory
3	3	[1]	[2]	[3]	-	MISS	Compulsory
4	4	[1]	[2]	[3]	[4]	MISS	Compulsory
5	1	[1]	[2]	[3]	[4]	HIT	Block 1 present
6	2	[1]	[2]	[3]	[4]	HIT	Block 2 present
7	5	[5]	[2]	[3]	[4]	MISS	Evict 1 (Oldest)
8	1	[5]	[1]	[3]	[4]	MISS	Evict 2 (Oldest)
9	2	[5]	[1]	[2]	[4]	MISS	Evict 3 (Oldest)
10	3	[5]	[1]	[2]	[3]	MISS	Evict 4 (Oldest)
11	4	[4]	[1]	[2]	[3]	MISS	Evict 5 (Oldest)
12	5	[4]	[5]	[2]	[3]	MISS	Evict 1 (Oldest)

$\text{Total Misses with 4 Lines} = 10 \text{ Misses} \quad (\text{Hits} = 2)$

$\text{Notice the Anomaly: Increasing lines from } 3 \to 4 \text{ caused misses to INCREASE from } 9 \to 10!$

Why LRU and OPT are Immune: The Inclusion Property of Stack Algorithms

A replacement algorithm is classified as a Stack Algorithm if the set of memory blocks present in an $m$-frame cache at any cycle $t$ is strictly a subset of the blocks that would be present in an $(m+1)$-frame cache at the same cycle:

$B(m, t) \subseteq B(m + 1, t) \quad \forall t$

• Mathematical Consequence: For any stack algorithm, every cache hit that occurs with $m$ lines is guaranteed to also be a hit with $m + 1$ lines! Therefore, the miss rate can never increase when cache size grows.
• Stack Algorithms: LRU, OPT (MIN), and LFU. They are provably immune to Belady's Anomaly.
• Non-Stack Algorithms: FIFO, Random, and Clock (First-chance FIFO). They violate the subset inclusion property and can exhibit Belady's Anomaly.

🎮 Interactive Belady's Anomaly & Replacement Simulator

Test Belady's Anomaly in real time below. Select the preset Belady's Anomaly (3 Lines FIFO) to observe $9$ misses, then toggle Total Lines from $3 \to 4$ to watch misses jump to $10$! Then switch to LRU or OPT to observe how stack algorithms remain strictly monotonic:

Presets:

Cycle:0 / 12

Click any cycle column to inspect cache state

Hit (H) Miss (M) Current (t0)

Cycle	t1	t2	t3	t4	t5	t6	t7	t8	t9	t10	t11	t12
Block	1	2	3	4	1	2	5	1	2	3	4	5
Line 0	·	·	·	·	·	·	·	·	·	·	·	·
Line 1	·	·	·	·	·	·	·	·	·	·	·	·
Line 2	·	·	·	·	·	·	·	·	·	·	·	·
Result	·	·	·	·	·	·	·	·	·	·	·	·

💡 Architectural Step Reasoning

Initial state: Cache is completely empty. Valid bits are 0. Click 'Step Next' to begin.

0

Hits

0

Misses

0%

Hit Ratio

0

Compulsory

0

Conflict

0

Capacity

---

🎯 The 3Cs of Cache Misses & Block Size Trade-Offs

To diagnose and optimize memory bottlenecks, Mark Hill and Norman Jouppi classified all hardware cache misses into the 3Cs Model (extended to 4Cs in symmetric multi-core systems):

Miss Category	Architectural Root Cause	Hardware Mitigation Strategy
Compulsory (Cold Miss)	First-time reference to a memory block; cache is cold	Increase cache block size (spatial prefetch) or hardware prefetchers
Capacity Miss	Program working set exceeds total cache storage capacity	Increase total cache capacity ($C = N \times B$)
Conflict (Collision Miss)	Multiple active memory blocks map to the exact same set index	Increase set associativity ($K \to 2K \to \dots \to N$)

The Fourth 'C': Coherence Misses

In multi-processor and multi-core systems, a fourth category exists: Coherence Misses. When Core 0 writes to an address residing in Core 1's cache, Core 0 sends a bus invalidation signal. Core 1's cache line is forcibly invalidated. When Core 1 reads that address again, a cache miss occurs, known as an invalidation or coherence miss.

Block Size Trade-Offs

In designing a cache architecture, the block size (cache line size) is one of the most critical hardware tuning parameters:

Block Size Region	Spatial Locality Effect	Conflict & Penalty Effect	Net Miss Rate Behavior
Small Blocks ($16 - 32\text{ B}$)	Low spatial exploitation; misses on adjacent words	High total number of cache lines; low conflict	Decreases rapidly as block size grows
Optimal Window ($64\text{ B}$)	Captures typical loop bodies and struct fields	Balanced line count and bus bandwidth utilization	Global Minimum Miss Rate
Excessive Blocks ($128 - 512\text{ B}$)	Brings unused words; pollutes cache capacity	Drastically fewer lines; massive miss penalty ($T_{\text{miss}}$)	Miss rate and transfer penalty explode

1. Phase 1: Increasing Block Size Reduces Misses (Left of Minimum):
   • By fetching larger blocks ($16 \to 32 \to 64\text{ Bytes}$), the cache brings neighboring instructions and array elements into SRAM before they are requested.
   • This heavily exploits spatial locality and dramatically drops compulsory miss rates.
2. Phase 2: Excessive Block Size Increases Misses (Right of Minimum):
   • For a fixed total cache capacity $C$, larger block sizes mean fewer total cache lines ($N = C / B$).
   • With fewer lines, competing blocks from different parts of the program overwrite each other more rapidly, causing conflict misses and capacity misses to skyrocket.
   • Furthermore, fetching a massive block over the memory bus dramatically increases the Miss Penalty ($T_{\text{miss}}$), stalling the CPU for hundreds of cycles to load bytes that may never be executed.

---

🧮 Multi-Level AMAT: Hierarchical vs Simultaneous

The ultimate metric of memory system quality is Average Memory Access Time (AMAT) (also known as Effective Memory Access Time, EMAT). Caches are organized in multi-level hierarchies:

Modern 3-Level Cache Hierarchy Latency & Sizing

CPU Registers

↓

L1 Cache (Split I-Cache & D-Cache)

↓

L2 Cache (Unified)

↓

L3 Cache (Shared LLC)

↓

Main Memory (DDR5 DRAM)

Depending on how the hardware bus interconnect is wired, memory levels can be queried in two distinct topologies: Hierarchical (Serial) or Simultaneous (Parallel).

1. Hierarchical (Serial / Sequential) Access Organization

In a hierarchical organization, the CPU accesses level $L_1$ first. Only if $L_1$ reports a miss does the memory controller propagate the request to level $L_2$. If $L_2$ misses, the request propagates to Main Memory ($M$).

$\text{Hit Ratios: } H_1, H_2 \qquad \text{Access Times: } T_1, T_2, T_m$

Let us derive AMAT step-by-step from probability tree branches:

1. Hit in $L_1$: Occurs with probability $H_1$. Time required $= T_1$.
2. Miss in $L_1$, Hit in $L_2$: Occurs with probability $(1 - H_1) \times H_2$. Because $L_1$ was searched first and failed before $L_2$ was searched, total elapsed time $= T_1 + T_2$.
3. Miss in $L_1$, Miss in $L_2$, Hit in Main Memory: Occurs with probability $(1 - H_1) \times (1 - H_2)$. Total elapsed time $= T_1 + T_2 + T_m$.

Summing the weighted probabilities:

$\text{AMAT}_{\text{hierarchical}} = H_1 T_1 + (1 - H_1)H_2 (T_1 + T_2) + (1 - H_1)(1 - H_2)(T_1 + T_2 + T_m)$

Algebraically factoring out common terms:

$\text{AMAT}_{\text{hierarchical}} = T_1 + (1 - H_1) \Big[ T_2 + (1 - H_2) T_m \Big]$

📐The General Hierarchical AMAT Lawtheorem

2. Simultaneous (Parallel) Access Organization

In simultaneous access, all levels of the memory hierarchy are connected to the CPU bus. When a memory access is issued, the CPU probes $L_1$, $L_2$, and Main Memory simultaneously in parallel.

• If the block resides in $L_1$, it returns in $T_1$, and the slower background lookups in $L_2$ and DRAM are aborted.
• If $L_1$ misses but $L_2$ hits, the data is available at time $T_2$ (not $T_1 + T_2$, because $L_2$ was already searching concurrently from cycle 0).
• If both miss, data is returned from Main Memory at time $T_m$.

$\text{AMAT}_{\text{simultaneous}} = H_1 T_1 + (1 - H_1) H_2 T_2 + (1 - H_1)(1 - H_2) T_m$

📐The Simultaneous AMAT Lawtheorem

Average Cost per Byte Across Hierarchy

If level $i$ has capacity $S_i$ and manufacturing cost per byte $C_i$, the system-wide weighted average cost per byte is:

$\bar{C} = \frac{C_1 S_1 + C_2 S_2 + C_3 S_3 + \dots + C_n S_n}{S_1 + S_2 + S_3 + \dots + S_n}$

Because capacity is dominated by the lowest tier ($S_{\text{DRAM}} \gg S_{\text{Cache}}$), the system achieves the average cost per byte of cheap DRAM while delivering the effective access speed of expensive SRAM!

---

🏭 Real-World Production Context: Kernel Dirty Page Tuning & Hardware Coherence

The trade-offs between Write-Through, Write-Back, and replacement policies are not merely silicon abstractions; they govern modern operating systems and database storage engines.

Hardware Cache Architecture	Operating System / Database Architecture Equivalent
Write-Back + Dirty Bit	Linux Page Cache dirty pages (pdflush / kworker flush)
Write-Through + Write Buffer	Database WAL (Write-Ahead Log) sync with append buffer
LRU Cache Replacement	Two-Queue (2Q) / Adaptive Replacement Cache (ARC) page reclaim
Coherence Bus Invalidation	Distributed database invalidation message / cache bus snooping

1. Linux Page Cache Dirty Ratio Tuning

In modern Linux operating systems, the kernel operates its Virtual Memory page cache as a massive Write-Back cache over secondary storage (NVMe/SATA SSDs). When applications perform write system calls (write()), data is modified in RAM and marked with a dirty flag.

System administrators tune this behavior via two sysctl parameters:

• vm.dirty_background_ratio (default $\approx 10\%$): When dirty memory reaches this percentage of total system RAM, the kernel's background flusher threads (kworker/flush) start asynchronously writing dirty pages back to disk without blocking user threads.
• vm.dirty_ratio (default $\approx 20\%$): If an application issues disk writes so aggressively that dirty pages exceed this threshold, the kernel halts all incoming user writes, forcing the application to stall until dirty pages are flushed. This prevents memory exhaustion—the exact software equivalent of a hardware write buffer saturation stall!

2. Multi-Core Cache Coherence: The MESI Protocol

In multi-core server processors (e.g., AMD EPYC, Intel Xeon), every core possesses a private Write-Back $L_1$ and $L_2$ cache. If Core 0 writes to address $X$, Core 1's copy of $X$ becomes stale.

To maintain system correctness without reverting to slow Write-Through policies, modern silicon implements the MESI (Illinois) Protocol, appending two state bits to every cache line:

1. M (Modified): The block is present only in this cache and is dirty (different from Main Memory).
2. E (Exclusive): The block is present only in this cache and is clean (matches Main Memory).
3. S (Shared): The block may be present in multiple core caches and is clean.
4. I (Invalid): The block does not contain valid data (equivalent to $\text{Valid Bit} = 0$).

When Core 0 writes to a block in state S, it broadcasts an Invalidate bus transaction. All other cores change their state from S to I, granting Core 0 exclusive dirty ownership (M) without stalling on DRAM!

---

📐 Numerical Applications & Worked Examples

Example 1: Multi-Level Cache AMAT with Mixed Read/Write Traffic

Problem Statement:
A hierarchical memory system contains a processor with an $L_1$ cache and Main Memory with the following specifications:

• Cache access time ($T_c$) = $50\text{ ns}$
• Main memory access time ($T_m$) = $300\text{ ns}$
• Memory traffic consists of $75\%$ Read requests and $25\%$ Write requests.
• For Read requests, the cache hit ratio is $H_{\text{read}} = 0.80$.
• The cache uses a Write-Through policy. On every write request, Main Memory must be updated simultaneously. Assume writing to the cache and writing to Main Memory takes $300\text{ ns}$ (bound by main memory write speed).
• On a read miss, the block is fetched from main memory into the cache before being read (hierarchical access: $T_c + T_m$).

Calculate the overall Average Memory Access Time (AMAT) of the system.

Step-by-Step Solution:

1. Calculate Average Access Time for Read Requests ($T_{\text{read}}$):
   For read accesses, the cache behaves hierarchically:

   • Read Hit ($80\%$ probability): Access time $= T_c = 50\text{ ns}$.
   • Read Miss ($20\%$ probability): Access time $= T_c + T_m = 50\text{ ns} + 300\text{ ns} = 350\text{ ns}$.

   $T_{\text{read}} = H_{\text{read}} \times T_c + (1 - H_{\text{read}}) \times (T_c + T_m)$ $T_{\text{read}} = 0.80 \times 50\text{ ns} + 0.20 \times 350\text{ ns} = 40\text{ ns} + 70\text{ ns} = 110\text{ ns}$

2. Calculate Average Access Time for Write Requests ($T_{\text{write}}$):
   Under Write-Through without a decoupled write buffer, every write must update Main Memory: $T_{\text{write}} = 300\text{ ns}$

3. Compute the Total Weighted AMAT:
   Weight the read and write components by their traffic distribution ($75\%$ read, $25\%$ write): $\text{AMAT} = 0.75 \times T_{\text{read}} + 0.25 \times T_{\text{write}}$ $\text{AMAT} = 0.75 \times (110\text{ ns}) + 0.25 \times (300\text{ ns})$ $\text{AMAT} = 82.5\text{ ns} + 75\text{ ns} = 157.5\text{ ns}$

---

Example 2: 2-Way Set-Associative Cache Miss Trace & 3Cs Classification

Problem Statement:
Consider a small 2-Way Set-Associative cache consisting of a total of $4\text{ lines}$ (meaning $2\text{ sets}$: Set 0 and Set 1). The cache uses the LRU (Least Recently Used) replacement policy and is initially empty.
The CPU issues requests for memory blocks in the following sequence:

$\text{Reference Sequence} = 0, 7, 0, 1, 2, 0, 7, 2$

Assume block $b$ maps to set $s = b \pmod 2$.
Determine:

1. The total number of cache hits and cache misses.
2. The classification of each miss into Compulsory, Capacity, or Conflict misses.

Step-by-Step Solution:

1. Determine Set Mapping:
   $\text{Number of Sets } S = \frac{\text{Total Lines}}{\text{Associativity } K} = \frac{4}{2} = 2 \text{ Sets (Set 0 and Set 1)}$ $\text{Set Index } s = b \pmod 2$

   • Even blocks ($0, 2$) map to Set 0.
   • Odd blocks ($7, 1$) map to Set 1.

2. Cycle-by-Cycle Execution Trace:

• Access 1: Block 0 (Set 0)
  Set 0 is empty $\to$ MISS (Compulsory).
  Set 0 contains: $\{0\}$.

• Access 2: Block 7 (Set 1)
  Set 1 is empty $\to$ MISS (Compulsory).
  Set 1 contains: $\{7\}$.

• Access 3: Block 0 (Set 0)
  Block 0 is already in Set 0 $\to$ HIT.
  LRU state of Set 0: $\{0\}$ (marked most recently used).

• Access 4: Block 1 (Set 1)
  Block 1 is not in Set 1 $\to$ MISS (Compulsory).
  Set 1 had 1 free line. Set 1 now contains: $\{7, 1\}$. (1 is MRU, 7 is LRU).

• Access 5: Block 2 (Set 0)
  Block 2 is not in Set 0 $\to$ MISS (Compulsory).
  Set 0 had 1 free line. Set 0 now contains: $\{0, 2\}$. (2 is MRU, 0 is LRU).

• Access 6: Block 0 (Set 0)
  Block 0 is present in Set 0 $\to$ HIT.
  LRU state of Set 0: 0 becomes MRU, 2 becomes LRU. Contents: $\{2 (\text{LRU}), 0 (\text{MRU})\}$.

• Access 7: Block 7 (Set 1)
  Block 7 is present in Set 1 $\to$ HIT.
  LRU state of Set 1: 7 becomes MRU, 1 becomes LRU. Contents: $\{1 (\text{LRU}), 7 (\text{MRU})\}$.

• Access 8: Block 2 (Set 0)
  Block 2 is present in Set 0 $\to$ HIT.
  LRU state of Set 0: 2 becomes MRU, 0 becomes LRU.

3. Summary of Results: $\text{Total Requests} = 8, \quad \text{Hits} = 4, \quad \text{Misses} = 4$ $\text{Hit Ratio} = \frac{4}{8} = 50\%$ All 4 misses ($0, 7, 1, 2$) occurred on the very first reference to their respective blocks. Therefore, all 4 misses are Compulsory (Cold) misses. Zero conflict or capacity misses occurred because neither set ever needed to evict an existing block!

🔍 Live Cycle-by-Cycle Execution Trace for Example 2

Step through this exact sequence ($0, 7, 0, 1, 2, 0, 7, 2$) live in the simulator below to inspect how Set 0 and Set 1 update their resident blocks and LRU recency:

Cycle:0 / 8

Click any cycle column to inspect cache state

Hit (H) Miss (M) Current (t0)

Cycle	t1	t2	t3	t4	t5	t6	t7	t8
Block	0	7	0	1	2	0	7	2
Line 0	·	·	·	·	·	·	·	·
Line 1	·	·	·	·	·	·	·	·
Line 2	·	·	·	·	·	·	·	·
Line 3	·	·	·	·	·	·	·	·
Result	·	·	·	·	·	·	·	·

💡 Architectural Step Reasoning

Initial state: Cache is completely empty. Valid bits are 0. Click 'Step Next' to begin.

0

Hits

0

Misses

0%

Hit Ratio

0

Compulsory

0

Conflict

0

Capacity

---

Example 3: Multi-Level Cache Hierarchy with L1, L2, and Miss Penalty

Problem Statement:
A high-performance processor features a two-level cache hierarchy ($L_1$ and $L_2$) with hierarchical access:

• $L_1$ cache access time: $T_1 = 1\text{ clock cycle}$
• $L_2$ cache access time: $T_2 = 8\text{ clock cycles}$
• Miss penalty from $L_2$ to Main Memory: $T_m = 18\text{ clock cycles}$ (time to transfer block from Main Memory to $L_2$)
• The local miss rate of $L_1$ is twice that of $L_2$: $\text{MissRate}_1 = 2 \times \text{MissRate}_2$.
• The overall Average Memory Access Time (AMAT) of the system is measured to be $2.0\text{ clock cycles}$.

Determine:

1. The local miss rate of $L_2$ ($\text{MissRate}_2$).
2. The local hit ratio of $L_1$ ($H_1$).

Step-by-Step Solution:

1. State the Hierarchical AMAT Equation:
   $\text{AMAT} = T_1 + \text{MissRate}_1 \times \text{MissPenalty}_1$ Where the miss penalty of $L_1$ is the time required to service the request from the next levels: $\text{MissPenalty}_1 = T_2 + \text{MissRate}_2 \times T_m$

   Substituting $\text{MissPenalty}_1$ into the primary formula: $\text{AMAT} = T_1 + \text{MissRate}_1 \times \Big( T_2 + \text{MissRate}_2 \times T_m \Big)$

2. Express All Variables in Terms of $\text{MissRate}_2$ ($x$):
   Let $\text{MissRate}_2 = x$.
   Then $\text{MissRate}_1 = 2x$.
   Given values: $\text{AMAT} = 2.0$, $T_1 = 1$, $T_2 = 8$, $T_m = 18$.

3. Formulate and Solve the Quadratic Equation:
   $2.0 = 1 + (2x) \times \Big( 8 + x \times 18 \Big)$ $1.0 = 2x \times (8 + 18x)$ $1.0 = 16x + 36x^2$ $36x^2 + 16x - 1 = 0$

   Apply the quadratic formula $x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$: $x = \frac{-16 \pm \sqrt{16^2 - 4(36)(-1)}}{2 \times 36}$ $x = \frac{-16 \pm \sqrt{256 + 144}}{72} = \frac{-16 \pm \sqrt{400}}{72} = \frac{-16 \pm 20}{72}$

   Discarding the negative root: $x = \frac{-16 + 20}{72} = \frac{4}{72} = \frac{1}{18} \approx 0.0555 \quad (5.56\%)$

4. Calculate $L_1$ Metrics:
   $\text{MissRate}_2 = \frac{1}{18} \approx 0.0556$ $\text{MissRate}_1 = 2x = 2 \times \frac{1}{18} = \frac{1}{9} \approx 0.1111 \quad (11.11\%)$ $\text{Hit Ratio of } L_1 (H_1) = 1 - \text{MissRate}_1 = 1 - \frac{1}{9} = \frac{8}{9} \approx 88.89\%$

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

• Question 1: Why is Write-Allocate almost always paired with Write-Back, while No-Write-Allocate is paired with Write-Through?
  Answer: In a Write-Back cache, fetching a missing block on a write allows all subsequent writes to that block to be absorbed at full SRAM speed without touching the bus. In a Write-Through cache, loading the block on a write miss provides zero write-latency benefit because every subsequent write would still be forced to update Main Memory over the slow bus anyway! Therefore, Write-Through prefers No-Write-Allocate to avoid evicting useful cached lines.

• Question 2: What conditions are strictly required for the Multi-Level Inclusion Property ($L_1 \subset L_2$) to hold?
  Answer: For every block in $L_1$ to be guaranteed to reside in $L_2$:

  1. The capacity of $L_2$ must be substantially larger than $L_1$ ($S_2 \ge S_1$).
  2. The associativity of $L_2$ must be equal to or greater than $L_1$ ($K_2 \ge K_1$).
  3. Whenever a block is evicted from $L_2$, hardware must forcefully invalidate the corresponding block in $L_1$ (Back-invalidation).

• Question 3: Does the LRU replacement algorithm suffer from Belady's Anomaly?
  Answer: No. LRU is provably a Stack Algorithm. The contents of an $m$-line LRU cache are strictly the top $m$ most recently referenced unique items in the reference stack. For an $(m+1)$-line cache, the contents are the top $m+1$ items. Thus, $B(m) \subset B(m+1)$ always holds.

Common Interview Traps

• Trap 1: Confusing Hierarchical Access Time ($T_1 + T_2$) with Simultaneous Access Time ($T_2$).
  On an $L_1$ miss with hierarchical access, the CPU has already spent $T_1$ examining $L_1$. Servicing the request from $L_2$ therefore costs $T_1 + T_2$ total elapsed cycles. If the question explicitly states Simultaneous Access, $L_2$ was searched in parallel from cycle 0, meaning an $L_2$ hit costs only $T_2$! Always look for the keyword hierarchical vs simultaneous.

• Trap 2: Forgetting to Add the Dirty Bit When Sizing a Write-Back Tag Directory.
  If a problem asks for the total tag directory bits of a Write-Back cache, each line requires: $\text{Directory Entry} = \text{Tag Bits} + \text{Valid Bit} + \mathbf{\text{Dirty Bit}}$ Leaving out the dirty bit will result in losing all marks. Direct-mapped Write-Through caches require only the Valid Bit.

• Trap 3: Assuming Increasing Block Size Always Reduces Cache Misses.
  While increasing block size initially reduces compulsory misses through spatial locality, making blocks too large reduces the total number of lines in a fixed-size cache, causing severe conflict and capacity thrashing, while significantly increasing the miss penalty.

---

🗺️View Complete COA Roadmap & Syllabus

← Previous Topic2.3 Associative & Set-Associative Cache Mapping ArchitecturesNext Topic →3.1 Virtual Memory Foundations, Paging & Address Translation