4.2.2 Fully associative and set-associative mapping; comparators and multiplexers

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

32-bit, 32 KB direct-mapped, 64 B blocks: tag | line | offset? from Lesson 4.2.1
Why does a direct-mapped cache need no replacement policy? from Lesson 4.2.1
What does a 2ᵏ-to-1 MUX need? from Lesson 0.2.3

1 · The Hook

🎣

Direct mapping can thrash: two hot blocks that share a line keep evicting each other while the rest of the cache sits idle. The cure is choice: let a block sit in any line of a small group (a set). The price: more comparators, a multiplexer and a replacement policy. Every GATE cache question starts by working out this split.

2 · Predict First

🤔

The same 32 KB cache with 64-byte blocks becomes 4-way set-associative: lines are grouped into sets of 4, and a block may use any line of its set. How many sets, and how do the tag and index widths change?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

512 lines / 4 = 128 sets → 7 set bits (2 fewer than 9), so the tag grows by 2 to 19 bits. Offset stays 6.

Fully associative

A block may go in any line.

Tag	Offset

Tag = address bits − offset (no index field).
Lookup compares the tag with every line's tag in parallel: L comparators.
Needs a replacement policy (Lesson 4.2.5). No conflict misses, highest hardware cost.

k-way set-associative

Lines are grouped into S = L / k sets of k lines. Block j goes into set j mod S, in any of that set's k lines.

Tag	Set index	Offset

Set bits = log₂ S; tag = address bits − set bits − offset.
Lookup: the set index picks one set; its k tags are compared in parallel (k comparators); a k-to-1 multiplexer passes the data of the line that hit.
Needs a replacement policy within the set.

One family

Organisation	Ways k	Sets S	Index bits	Comparators
Direct-mapped	1	L	log₂ L	1
k-way set-associative	k	L/k	log₂(L/k)	k
Fully associative	L	1	0	L

Each doubling of associativity moves one bit from the index to the tag.

Example (32-bit address, 32 KB, 64 B blocks, 512 lines):

	Tag	Index	Offset
Direct	17	9	6
2-way	18	8	6
4-way	19	7	6
Fully associative	26	0	6

Hit latency

A direct-mapped hit needs one tag comparison. A k-way hit needs the comparisons (in parallel) plus the k-to-1 MUX that selects the data. Model used in GATE: a t-bit comparator takes t/10 ns; a 2-to-1 MUX takes 0.6 ns.

64 KB, 64 B blocks, 32-bit addresses. Direct: tag 16 → 1.6 ns.
Same, 2-way: tag 17 → 1.7 + 0.6 = 2.3 ns.

Multiplexers

To deliver w bits of output from the hitting way, the cache needs w multiplexers of k-to-1 (one per output bit).

4 · Visual

Diagram: set index · tag (19) | set (7) | offset (6) · set 37: 4 lines · =? way 0 · =? way 1 · =? way 2 · =? way 3 · 4-to-1 MUX → data

4-way set-associative lookup: index picks a set; 4 tag comparisons in parallel; a MUX selects the hitting way.

5 · Worked Examples

Example 1 Easy

32-bit addresses, 16 KB 4-way set-associative cache, 32-byte blocks. Tag bits?

Solution

Lines 512; sets 128 → 7 bits; offset 5; tag 32 − 12 = 20.

Example 2 Medium

A 20-bit word address, 4-way set-associative cache of 128 lines, each line 64 words. Tag, set and word fields?

Solution

Word offset log₂ 64 = 6; sets 128/4 = 32 → 5; tag 20 − 11 = 9 | 5 | 6.

Example 3 GATE

32 KB, 32-byte blocks, 32-bit addresses. A t-bit comparator takes t/10 ns; a 2-to-1 MUX 0.6 ns. Hit latency of the 2-way set-associative version vs the direct-mapped version?

Solution

Lines 1024. 2-way: 512 sets → 9 index, 5 offset, tag 18 → 1.8 + 0.6 = 2.4 ns. Direct: 10 index, tag 17 → 1.7 ns.

6 · GATE Traps

⚠️

Sets = lines ÷ ways (not cache size ÷ ways).
Fully associative has no index field: tag = address − offset.
k-way needs k comparators and a k-to-1 MUX per output bit.
More associativity → longer tags, fewer index bits.

7 · Memory Hook

🧠

"Ways up, index down, tag up." Doubling the ways moves one bit from index to tag.

8 · Connect the Dots

Lesson 4.2.1 split the address for direct mapping; this lesson did it for every associativity and costed the hardware. Next: the storage the tags themselves need, the tag directory, with valid, dirty and replacement bits.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markSet bits

A 64 KB 8-way set-associative cache with 32-byte blocks. How many set-index bits?

Numerical answer: ________

Q2NAT2 marksTag bits

32-bit addresses, 256 KB 4-way set-associative cache, 64-byte blocks. Tag bits?

Numerical answer: ________

Q3NAT1 markFully associative tag

32-bit addresses, fully associative cache with 128-byte blocks. Tag bits?

Numerical answer: ________

Q4NAT2 marksHit latency

A 16 KB cache with 16-byte blocks and 32-bit addresses. A t-bit comparator takes t/10 ns; a 2-to-1 MUX takes 0.6 ns. Hit latency (ns) of its 2-way set-associative version?

Numerical answer: ________

Q5MSQ2 marksHardware

An 8-way set-associative cache delivers 32-bit words. Which are needed for hit detection and data selection?

(A) 8 tag comparators
(B) 32 multiplexers of 8-to-1
(C) 1 tag comparator
(D) A replacement policy for choosing a way on a miss

10 · Rule Card

k-way: sets S = L/k; set bits log₂ S; tag = address − set − offset; block j → set j mod S.
Fully associative: tag = address − offset; L comparators.
Comparators = k; data MUXes = output width × (k-to-1).
Doubling ways: index −1 bit, tag +1 bit. Hit latency adds MUX delay for k > 1.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

fully associative mappingk-way set-associative mappingsetset indexparallel tag comparatorsway-select multiplexerhit latencyassociativity vs tag width

12 · Answer Vault

Answer Vault

Try the questions first. Open when you are ready to check.

Recall Warm-up

17 | 9 | 6.
Each block has exactly one possible line.
k select lines.