2.3 Associative & Set-Associative Cache Mapping Architectures

Back to DBMS Notes

📚02Topic 2.3⏱️15 min

🎯High-Yield For:Every modern smartphone, laptop, server CPU, and GPU uses Set-Associative Caching to strike the optimal mathematical balance between hit rates, hardware silicon cost, and access latency.

💡 Core Intuition: Unreserved Seating & Reserved Rows

In Topic 2.2, we discovered the fatal limitation of Direct Mapping: Conflict Misses. If two frequently accessed main memory blocks map to the exact same cache line, they continuously evict each other, causing the CPU to grind to a halt even when $99\%$ of the cache lines sit completely empty!

To resolve this bottleneck, computer architects developed two progressively flexible placement strategies: Fully Associative Mapping and Set-Associative Mapping.

🍳 The Everyday Analogy: The Movie Theater Seating Dilemma

Consider three distinct seating policies at a 100-seat cinema:

1. Strictly Assigned Seat (Direct Mapping):

   • Your ticket number dictates your exact seat: $\text{Seat} = \text{Ticket} \pmod{100}$.
   • If two guests arrive with tickets ending in 42, the second guest kicks the first guest out of the theater, even if 98 other seats are empty!
   • Fastest seating check, worst conflict thrashing.

2. Open General Admission (Fully Associative Mapping):

   • Any guest can sit in any free seat in the entire theater!
   • No guest is ever turned away until all 100 seats are completely filled.
   • Zero conflict thrashing, but the usher must scan all 100 seats simultaneously to locate any specific person.

3. Section-Assigned Seating (K-Way Set-Associative Mapping):

   • The theater is divided into 25 rows (Sets), with 4 seats per row ($K = 4$ lines per set).
   • Your ticket assigns you to a specific row ($\text{Row} = \text{Ticket} \pmod{25}$), but within that row, you can sit in any of the 4 seats!
   • You can accommodate up to 4 conflicting guests in that row before anyone is evicted.
   • The usher only needs to scan 4 seats in parallel. Blazing fast, highly flexible!

💻 Bridging to Computer Science

Modern processor caches represent this exact trade-off spectrum:

• Direct Mapping ($K = 1$): 1 line per set $\implies 1$ comparator, high conflict misses.
• Fully Associative ($K = N$): All lines in 1 set $\implies N$ parallel comparators, zero conflict misses.
• $K$-Way Set-Associative ($1 < K < N$): The industry sweet spot (typically $K = 4, 8, 16$), providing $98\%$ of the hit-rate benefits of fully associative caches with only $K$ hardware comparators!

📑Table of Contents

• ⚡ Fully Associative Mapping: Zero Conflict Misses
  • Physical Address Decomposition: Why the Line Index Vanishes
  • Hardware Architecture: The N-Comparator Cost
  • 🎮 Interactive Fully Associative Cache Simulator
• 🎛️ K-Way Set-Associative Mapping Architecture
  • The Two-Level Placement Rule
  • 🎮 Interactive K-Way Set-Associative Mapping Simulator
• 🪄 The Golden Bit-Transfer Law: Moving Bits from Index to Tag
  • The Mathematical Bit-Transfer Derivation
• 🔬 Hardware Comparator Scaling & Datapath Complexity
  • Key Hardware Architectural Invariants
• 📊 Comprehensive 3-Way Architectural Comparison Matrix
• 🏭 Real-World Production Context: Modern CPU Caches & VIPT Caching
  • 1. Cache Associativity in Commercial Processors
  • 2. VIPT: Virtually Indexed, Physically Tagged Caches
• 📐 Numerical Applications & Worked Examples
  • Example 1: 3-Way Comparative Mapping & Bit-Transfer Law
  • Example 2: Set-Associative Conflict Resolution Trace
  • Example 3: Reverse-Engineering Associativity from Address Bits
• 🎯 Exam & Interview Pitfall Check

---

⚡ Fully Associative Mapping: Zero Conflict Misses

In Fully Associative Mapping, a main memory block can be loaded into any freely available line anywhere in the cache:

Main Memory Blocks	Mapping Logic	Target Cache Lines
Block $B_0, B_1, B_2, \dots$	Any block can map to any freely available line	Line $C_0, C_1, C_2, \dots, C_{N-1}$

Physical Address Decomposition: Why the Line Index Vanishes

In direct mapping, the Line Index field ($c$ bits) guided the hardware to a specific line. In fully associative mapping, because any block can occupy any line, there is no concept of a predetermined line index!

The physical address decomposes into only two fields:

Fully Associative FormatTotal Frame: n Bits

Fully Associative Physical Address Decomposition

Decomposition of an n-bit CPU address into Tag (Block Number) and Word Offset fields

Tag Field

t Bits

[n-1 : w]

Word / Block Offset

w Bits

[w-1 : 0]

t BitsTag Field

Stores the entire Block Number; distinguishes the block across all cache lines (t = n - w).

📐Fully Associative Address Invariantformula

$$\text{Tag Bits } (t) = n - w = \log_2\left(\frac{\text{Main Memory Size}}{B}\right) = \text{Total Block Number Bits}$$$$\mathbf{\text{Tag}} = \mathbf{\text{Block Number}}$$

Hardware Architecture: The $N$-Comparator Cost

Because a requested block could reside in Line 0, Line 1, Line 2, ..., or Line $N-1$, the hardware must check all $N$ cache lines simultaneously in parallel:

📐Fully Associative Hardware Sizingprinciple

• Number of Comparators Required: Exactly $N$ parallel comparators (where $N = \text{Total Cache Lines}$).
• Width of Each Comparator: Exactly $t = (n - w)\text{ bits}$ (the widest tag of any mapping!).
• Search Complexity: $O(1)$ parallel associative search, but requires massive silicon area, high power dissipation, and extensive wire routing.
• Replacement Policy Mandatory: When the cache is full, the controller must choose which line to evict using algorithms like LRU (Least Recently Used) or FIFO.

Because of the massive hardware cost of $N$ parallel comparators, pure fully associative mapping is economically restricted to very small structures, such as Translation Lookaside Buffers (TLB) holding 32 to 128 entries.

🎮 Interactive Fully Associative Cache Simulator

Experience pure associative placement below. Any memory block can be loaded into any freely available cache line without line index restrictions. Because there are no fixed sets, conflict misses are completely eliminated ($100\%$ zero conflict misses):

Presets:

Cycle:0 / 5

Click any cycle column to inspect cache state

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

Cycle	t1	t2	t3	t4	t5
Block	0	4	8	0	4
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

---

🎛️ K-Way Set-Associative Mapping Architecture

$K$-Way Set-Associative Mapping divides the total cache of $N$ lines into distinct groups called Sets, where each set contains exactly $K$ cache lines:

📐Set-Associative Geometry Formulasformula

$$\text{Number of Sets } (S) = \frac{\text{Total Number of Cache Lines } (N)}{\text{Lines per Set } (K)}$$$$\text{Set Index } (s) = (\text{Block Number } b) \pmod{\text{Total Sets } S}$$

Set Index	Contained Cache Lines (for $K = 4$)	Placement Rule
Set 0	Line $C_0$, Line $C_1$, Line $C_2$, Line $C_3$	Freely placed in any line within Set 0
Set 1	Line $C_4$, Line $C_5$, Line $C_6$, Line $C_7$	Freely placed in any line within Set 1
Set 2	Line $C_8$, Line $C_9$, Line $C_{10}$, Line $C_{11}$	Freely placed in any line within Set 2
Set $S-1$	Line $C_{N-4}$, Line $C_{N-3}$, Line $C_{N-2}$, Line $C_{N-1}$	Freely placed in any line within Set $S-1$

The Two-Level Placement Rule

1. At the Macro Level (Direct Mapped): A main memory block is strictly assigned to one specific set: $s = b \pmod S$.
2. At the Micro Level (Fully Associative): Within that set, the block can reside in any of the $K$ cache lines!

Core Architectural Axiom: "Block ke liye set fix hai, but us set mein kisi bhi cache line mein ja sakta hai." (The set is strictly fixed for any given block, but within that designated set, it can freely occupy any line!)

🎮 Interactive K-Way Set-Associative Mapping Simulator

Observe the two-level placement rule live below: the block number determines the destination Set ($s = b \pmod S$), and within that target set, the block freely occupies any of the $K$ parallel lines:

Presets:

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

---

🪄 The Golden Bit-Transfer Law: Moving Bits from Index to Tag

One of the most celebrated and high-yield principles in computer architecture examinations is the Bit-Transfer Law:

Set-Associative FormatTotal Frame: n Bits

K-Way Set-Associative Physical Address Decomposition

Decomposition of an n-bit CPU address into Tag, Set Index, and Word Offset fields

Tag Field

t Bits

[n-1 : s+w]

Set Index

s Bits

[s+w-1 : w]

Word / Block Offset

w Bits

[w-1 : 0]

t BitsTag Field

Expands as associativity K increases; absorbs bits transferred from the index (t = n - s - w).

The Mathematical Bit-Transfer Derivation

Let $c = \log_2(N)$ be the line index bits in a direct-mapped cache. In a $K$-way set-associative cache:

$S = \frac{N}{K} = \frac{2^c}{2^{\log_2 K}} = 2^{c - \log_2 K}$

$\text{Set Index Bits } s = \log_2(S) = c - \log_2(K)$

Since the total address length $n$ and block offset $w$ remain constant:

$t_{\text{set-assoc}} = n - s - w = n - (c - \log_2 K) - w = (n - c - w) + \log_2(K)$

📐The Golden Bit-Transfer Theoremprinciple

$$t_{\text{set-assoc}} = t_{\text{direct}} + \log_2(K)$$$$s = c - \log_2(K)$$

Whenever associativity is multiplied by $K$, exactly $\log_2(K)$ bits are transferred from the Line/Set Index field into the Tag field!

• For 2-Way ($K = 2 = 2^1$): Exactly $1\text{ bit}$ transfers from index to tag.
• For 4-Way ($K = 4 = 2^2$): Exactly $2\text{ bits}$ transfer from index to tag.
• For 8-Way ($K = 8 = 2^3$): Exactly $3\text{ bits}$ transfer from index to tag.
• For 16-Way ($K = 16 = 2^4$): Exactly $4\text{ bits}$ transfer from index to tag.

---

🔬 Hardware Comparator Scaling & Datapath Complexity

How many comparators does a $K$-way set-associative cache require during a lookup?

Architecture Flow

K-Way Set-Associative Lookup Datapath

Hardware execution stages executing K parallel tag comparisons within a selected set

🔍Stage 1

Address Decode

Extract Tag (t bits), Set Index (s bits), and Word Offset (w bits) from CPU address.

→

Set Index

⚡Stage 2

Set Activation

s-bit index activates all K lines belonging to that set in parallel SRAM arrays.

→

K Stored Tags

⚖️Stage 3

Parallel Comparison

K parallel t-bit comparators compare address tag with all K stored tags simultaneously.

→

Hit Vector

🎯Stage 4

Hit MUX Selection

If any comparator matches and V=1, MUX routes matching line data word to CPU.

Key Hardware Architectural Invariants

• Number of Comparators: Exactly $K$ comparators running in parallel.
• Width of Each Comparator: Exactly $t$ bits (the Tag field width).
• Hardware Cost: Far lower than Fully Associative ($K \ll N$), while reducing conflict misses to near zero.

---

📊 Comprehensive 3-Way Architectural Comparison Matrix

The table below contrasts the three cache mapping architectures across all dimensions:

Architectural Metric	Direct Mapping	$K$-Way Set-Associative	Fully Associative
Associativity ($K$)	$K = 1$	$1 < K < N$	$K = N$
Number of Sets ($S$)	$S = N$	$S = N / K$	$S = 1$
Block Placement	Exactly 1 line ($c = b \pmod N$)	Any line in set $s = b \pmod S$	Any line in entire cache
Address Fields	$\text{Tag } \mid \text{Line } \mid \text{Offset}$	$\text{Tag } \mid \text{Set } \mid \text{Offset}$	$\text{Tag } \mid \text{Offset}$
Tag Field Width ($t$)	Smallest: $n - c - w$	Moderate: $n - s - w$	Largest: $n - w$ (Full Block No.)
Number of Comparators	$1$ comparator	$K$ comparators	$N$ comparators
Conflict Misses	Highest (frequent thrashing)	Extremely low	Zero (no conflict misses)
Hit Latency	Fastest (minimal circuit delay)	Fast (small MUX delay)	Slower (large fan-out delay)
Hardware Silicon Cost	Minimal	Moderate (Industry standard)	Highest (prohibitive for large cache)
Replacement Algorithm	None (deterministic overwrite)	Required within set (LRU/FIFO)	Required across all lines

---

🏭 Real-World Production Context: Modern CPU Caches & VIPT Caching

1. Cache Associativity in Commercial Processors

Modern microarchitectures utilize set-associative caching tiered by latency sensitivity:

• Level-1 Data Cache (L1D): Typically 8-way set associative ($48\text{ KB}$, 64-byte lines). Low latency (4-5 cycles) while avoiding loop thrashing.
• Level-2 Cache (L2): Typically 8-way or 16-way set associative ($1\text{ MB} - 2\text{ MB}$ per core). Balances medium latency (12-14 cycles) with high capacity.
• Level-3 Last-Level Cache (LLC): Typically 16-way to 24-way set associative ($32\text{ MB} - 96\text{ MB}$ shared across cores). High associativity is essential to prevent conflict misses among concurrent multi-threaded workloads.

2. VIPT: Virtually Indexed, Physically Tagged Caches

A legendary hardware innovation in modern CPUs is VIPT (Virtually Indexed, Physically Tagged) caching:

• The CPU instruction pipeline generates a Virtual Address (VA), which the MMU/TLB must translate into a Physical Address (PA).
• In a naive system, the cache cannot be indexed until the TLB finishes address translation (serial bottleneck).
• In a VIPT cache, because the lowest $12\text{ bits}$ of a virtual address (page offset) are identical to physical address bits, the cache uses the untranslated virtual page offset as the Set Index!
• The cache SRAM lookup and the TLB address translation proceed simultaneously in parallel. When the TLB finishes delivering the physical tag, the cache lines are already waiting to be compared!

---

📐 Numerical Applications & Worked Examples

The following worked engineering problems demonstrate step-by-step bit-transfer applications, 3-way mapping comparisons, and LRU set-associative execution tracing.

Example 1: 3-Way Comparative Mapping & Bit-Transfer Law

Problem Statement:
A computer system possesses a byte-addressable main memory of $128\text{ KB}$, an on-chip cache memory of $16\text{ KB}$, and a block size of $256\text{ bytes}$.

1. Calculate the physical address bus width ($n$).
2. Determine the bit breakdown (Tag, Index, Offset) for:
   • Direct Mapping
   • Fully Associative Mapping
   • 4-Way Set-Associative Mapping
3. Verify the Golden Bit-Transfer Law between Direct and 4-Way mapping.
4. Calculate the Tag Directory Size in bits for the 4-way set-associative cache assuming each entry includes $1$ Valid Bit.

Step-by-Step Solution:

1. Calculate Global Physical Geometry:
   $\text{Main Memory} = 128\text{ KB} = 128 \times 2^{10}\text{ bytes} = 2^7 \times 2^{10} = 2^{17}\text{ bytes} \implies n = \mathbf{17\text{ bits}}$ $\text{Block Size } B = 256\text{ bytes} = 2^8\text{ bytes} \implies \text{Word Offset } w = \mathbf{8\text{ bits}}$ $\text{Total Cache Lines } N = \frac{16\text{ KB}}{256\text{ B}} = \frac{16 \times 2^{10}}{2^8} = \frac{2^{14}}{2^8} = 2^6 = \mathbf{64\text{ lines}}$

2. Case A: Direct Mapping:

   • Line Index bits: $c = \log_2(N) = \log_2(64) = \mathbf{6\text{ bits}}$
   • Tag bits: $t = n - c - w = 17 - 6 - 8 = \mathbf{3\text{ bits}}$
   • Address format: $[Tag]_{3} \ [Line]_{6} \ [Offset]_{8}$

3. Case B: Fully Associative Mapping:

   • No index field: $c = 0\text{ bits}$
   • Tag bits: $t = n - w = 17 - 8 = \mathbf{9\text{ bits}}$ (Entire Block Number)
   • Address format: $[Tag]_{9} \ [Offset]_{8}$

4. Case C: 4-Way Set-Associative Mapping ($K = 4$):

   • Number of sets: $S = \frac{N}{K} = \frac{64}{4} = 16\text{ sets} = 2^4\text{ sets} \implies s = \mathbf{4\text{ bits}}$
   • Tag bits: $t = n - s - w = 17 - 4 - 8 = \mathbf{5\text{ bits}}$
   • Address format: $[Tag]_{5} \ [Set]_{4} \ [Offset]_{8}$

5. Verify the Bit-Transfer Law:
   $\text{Associativity } K = 4 = 2^2 \implies \log_2(K) = 2\text{ bits}$

   • Set bits: $s = c - \log_2(K) = 6 - 2 = \mathbf{4\text{ bits}}$ (Exact match!)
   • Tag bits: $t_{\text{set}} = t_{\text{direct}} + \log_2(K) = 3 + 2 = \mathbf{5\text{ bits}}$ (Exact match!)

6. Calculate Tag Directory Size (4-Way Set-Associative):

   • Total entries across all sets: $N = 64\text{ lines}$
   • Bits per entry: $\text{Tag} + \text{Valid} = 5 + 1 = 6\text{ bits}$
   • Total Directory Size: $\text{Directory Size} = 64 \times 6\text{ bits} = \mathbf{384\text{ bits}} \ (48\text{ bytes})$

---

Example 2: Set-Associative Conflict Resolution Trace

Problem Statement:
Consider a 2-way set-associative cache containing $4\text{ total lines}$ (organized as $2\text{ sets}$: Set $0$ containing lines $\{L_0, L_1\}$ and Set $1$ containing lines $\{L_2, L_3\}$). The cache uses the LRU (Least Recently Used) replacement policy. Initially, all lines are empty.

Trace the cache state and determine the Hit/Miss outcome for the exact sequence that previously caused a $100\%$ miss rate in Direct Mapping (Topic 2.2): $B_0, \ B_4, \ B_8, \ B_0, \ B_4, \ B_1, \ B_5, \ B_2$

Step-by-Step Solution:

Calculate Set Index for each block: $\text{Set Index } s = b \pmod 2$.

• Blocks with even index ($B_0, B_4, B_8, B_2$) map to Set 0 ($0 \pmod 2 = 0$).
• Blocks with odd index ($B_1, B_5$) map to Set 1 ($1 \pmod 2 = 1$).

Each set has $K = 2$ slots. When a set is full, the least recently referenced block is evicted.

1. Step-by-Step LRU Trace:

Step	Access	Target Set	Set State Before Access	Outcome	Set State After Access (Most to Least Recent)
1	$B_0$	Set 0	Empty	MISS (Cold)	Set 0: $[B_0, -]$
2	$B_4$	Set 0	$[B_0, -]$	MISS (Cold)	Set 0: $[B_4, B_0]$ (Both slots now full)
3	$B_8$	Set 0	$[B_4, B_0]$	MISS (Capacity/Conflict)	Set 0: $[B_8, B_4]$ ($B_0$ evicted via LRU)
4	$B_0$	Set 0	$[B_8, B_4]$	MISS (Conflict)	Set 0: $[B_0, B_8]$ ($B_4$ evicted via LRU)
5	$B_4$	Set 0	$[B_0, B_8]$	MISS (Conflict)	Set 0: $[B_4, B_0]$ ($B_8$ evicted via LRU)
6	$B_1$	Set 1	Empty	MISS (Cold)	Set 1: $[B_1, -]$
7	$B_5$	Set 1	$[B_1, -]$	MISS (Cold)	Set 1: $[B_5, B_1]$ (Both slots now full)
8	$B_2$	Set 0	$[B_4, B_0]$	MISS (Conflict)	Set 0: $[B_2, B_4]$ ($B_0$ evicted via LRU)

2. Now Consider a Loop Re-Execution (Accesses 9 through 12: $B_4, B_2, B_5, B_1$):
   • Access 9 ($B_4 \to \text{Set 0}$): Already present in Set 0 $\implies$ HIT! Set 0 becomes $[B_4, B_2]$.
   • Access 10 ($B_2 \to \text{Set 0}$): Already present in Set 0 $\implies$ HIT! Set 0 becomes $[B_2, B_4]$.
   • Access 11 ($B_5 \to \text{Set 1}$): Already present in Set 1 $\implies$ HIT! Set 1 becomes $[B_5, B_1]$.
   • Access 12 ($B_1 \to \text{Set 1}$): Already present in Set 1 $\implies$ HIT! Set 1 becomes $[B_1, B_5]$.

Architectural Takeaway: In Direct Mapping, alternating accesses to $B_4$ and $B_2$ caused endless $100\%$ thrashing because both targeted Line 0. In 2-Way Set Associative, both blocks co-exist simultaneously inside Set 0, achieving a $100\%$ hit rate on loop iterations!

---

Example 3: Reverse-Engineering Associativity from Address Bits

Problem Statement:
A 40-bit physical address machine employs a $16\text{ KB}$ cache with a block size of $32\text{ bytes}$. The processor hardware architect discovers that the width of the Tag field is $27\text{ bits}$.
Determine:

1. The number of sets ($S$) in the cache.
2. The degree of associativity ($K$).
3. The number of parallel comparators required by the hardware.

Step-by-Step Solution:

1. Calculate Word Offset Bits ($w$):
   $B = 32\text{ bytes} = 2^5\text{ bytes} \implies w = \log_2(2^5) = \mathbf{5\text{ bits}}$

2. Calculate Set Index Bits ($s$):
   Total physical address width $n = 40\text{ bits}$. Tag field $t = 27\text{ bits}$. $s = n - t - w = 40 - 27 - 5 = 40 - 32 = \mathbf{8\text{ bits}}$

3. Calculate Number of Sets ($S$):
   $S = 2^s = 2^8 = \mathbf{256\text{ sets}}$

4. Calculate Total Lines in Cache ($N$):
   $N = \frac{\text{Cache Size}}{\text{Block Size}} = \frac{16\text{ KB}}{32\text{ B}} = \frac{16 \times 1,024}{32} = \frac{16,384}{32} = \mathbf{512\text{ lines}}$

5. Calculate Degree of Associativity ($K$):
   $K = \frac{\text{Total Lines } (N)}{\text{Total Sets } (S)} = \frac{512}{256} = \mathbf{2}$ Architectural Conclusion: The cache is 2-Way Set Associative, requiring exactly 2 parallel comparators of width $27\text{ bits}$!

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

• Why does a 2-way or 4-way set-associative cache achieve nearly the same hit rate as a fully associative cache of identical capacity?
  Empirical research in computer architecture (often formalized as the 2:1 Cache Rule of Thumb) demonstrates that program working sets rarely contain more than 4 to 8 conflicting memory references mapping to the same index during any brief time window. A 4-way or 8-way set provides enough flexibility to absorb these localized conflicts, capturing over $95\%$ of the conflict-reduction benefit of fully associative mapping without requiring hundreds of expensive comparators.

• What happens to the number of comparators and tag bits as a cache transitions from Direct Mapping to Fully Associative?
  As associativity increases from $K = 1$ to $K = N$:

  1. The number of comparators scales from $1$ to $N$.
  2. The Tag field expands by $\log_2(N)$ bits, absorbing the entire index field until $\text{Tag} = \text{Block Number}$.

Common Interview Traps

• Trap: Forgetting to Divide Total Lines by K to Find Sets.
  Candidates frequently calculate $s = \log_2(N)$ instead of $s = \log_2(N / K)$. Always remember: the Set field indexes Sets, not lines! If a cache has 512 lines and is 4-way set-associative, there are $512 / 4 = 128$ sets, requiring $7$ set bits (not $9$).

• Trap: Applying Replacement Policies to Direct-Mapped Caches.
  If an interview problem asks “Which replacement policy (LRU vs FIFO) produces fewer page faults/misses in a direct-mapped cache?”, the correct answer is: Neither! In a direct-mapped cache, there is only one line per set; a new block has no choice and must deterministically overwrite whatever is currently in that line. Replacement algorithms only exist when $K \ge 2$.

---

🗺️View Complete COA Roadmap & Syllabus

← Previous Topic2.2 Cache Memory Architecture & Direct Mapping MechanicsNext Topic →2.4 Cache Write Policies, Replacement Algorithms & Multi-Level AMAT