In the previous chapter, Cache Memory, we saw why a small, fast cache sitting between the CPU and main memory makes programs run much faster, and we met the words block, line, hit and miss. But we skipped one very practical question: when a block comes from main memory into the cache, which cache line should it go into? And later, when the CPU asks for an address, where should the cache look to find out whether that block is present?
The rule that answers both questions is called the mapping technique. There are three of them: direct mapping, fully associative mapping and set-associative mapping. In this chapter we will understand each one, learn how to split a memory address into tag, index and offset fields (the single most common GATE numerical on caches), trace hits and misses by hand, and see what hardware each technique needs.
The Big Idea: Many Blocks, Few Lines
Main memory and the cache are both divided into equal-sized chunks:
A block is a chunk of main memory (for example 64 bytes).
A line (or slot) is a place in the cache that can hold exactly one block, plus some bookkeeping bits.
A 32 KB cache with 64-byte blocks has only 512 lines, while 4 GB of main memory has 226 (about 67 million) blocks. So many blocks must compete for the same lines. A mapping technique decides how much freedom a block has:
| Technique | Where can block B go? | Analogy |
|---|---|---|
| Direct mapped | Exactly one line, fixed by B's number | Assigned seat in an exam hall |
| Fully associative | Any line in the cache | Free seating in a cinema with no seat numbers |
| k-way set associative | Any of the k lines of one fixed set | Assigned row, but any seat in that row |
Because many blocks share the same line(s), the cache must remember which block it currently holds in each line. It does this by storing part of the address, called the tag, next to the data.
Tag: the high-order bits of the memory address that are stored with each cache line, so the cache can tell which of the many possible memory blocks is currently in that line.
Every line also has a valid bit (V). When the computer starts, all valid bits are 0, so random garbage in the tag array is never mistaken for a real block.
Splitting an Address: Offset, Index, Tag
All three techniques read the memory address as a set of fields. Start from the right:
Offset (word/byte field): selects the byte inside a block. If the block has 2b bytes, the offset is b bits.
Index (line field or set field): selects the line (direct mapped) or the set (set associative). If there are 2s lines or sets, the index is s bits. Fully associative caches have no index.
Tag: all remaining high-order bits.
physical address (n bits)
+----------------------+-----------------+--------------+
| TAG | INDEX | OFFSET |
+----------------------+-----------------+--------------+
n - s - b bits s bits b bits
block number = address / block size (= TAG and INDEX together)
index = block number mod (number of lines or sets)
tag = block number / (number of lines or sets)The block number is simply the address with the offset bits removed. Dividing by a power of two is a right shift, and "mod" by a power of two keeps the low bits. That is why caches use power-of-two sizes: the hardware needs no divider at all, it just picks wires.
Remember: number of lines = cache size / block size. Number of sets = number of lines / associativity. Always check whether the address is a byte address or a word address before computing the offset.
Direct Mapping
Direct mapping: each main-memory block j can be placed in exactly one cache line, line number = j mod L, where L is the number of lines.
How a Lookup Works
address: | tag | line | offset |
│ │
│ └──► select ONE line (decoder)
│ │
│ +-----+-----+-----------+
│ | V | tag | block |
│ +-----+-----+-----------+
│ │
└──────► [ = ? ] ◄┘ one comparator
│
hit = (tags equal) AND (V = 1)
if hit: offset picks the byte from the blockOnly one tag comparison is needed, so direct-mapped caches are the simplest, cheapest and fastest to look up. There is also no replacement decision to make: if the line is occupied, the old block is simply thrown out.
The Weakness: Conflict Misses
Two blocks whose numbers differ by a multiple of L map to the same line. If a program uses both of them alternately, they keep kicking each other out even if the rest of the cache is empty. This repeated eviction is called thrashing, and those misses are called conflict misses.
Fully Associative Mapping
Fully associative mapping: any main-memory block can be placed in any cache line. The whole block number is stored as the tag.
Since a block could be anywhere, a lookup must compare the address tag with the tags of all lines at the same time. That requires one comparator per line, built using associative (content-addressable) memory.
address: | tag | offset |
│
+-----------------+-----------------+----------------+
▼ ▼ ▼ ▼
[= line0?] [= line1?] [= line2?] ... [= lineL-1?]
└──────────── OR of all matches ─────────────────────┘
= hitAdvantage: no conflict misses. A block is evicted only when the whole cache is full.
Disadvantage: L comparators (512 in our 32 KB example) cost a lot of chip area and power, and the wide OR makes the hit signal slower.
It needs a replacement policy (such as LRU) to decide which line to evict when all lines are full. These policies are the topic of the next chapter, Cache Replacement & Write Policies. In this chapter we will use LRU: evict the line that was used least recently.
Fully associative organisation is practical only for small structures, for example a TLB with a few dozen entries.
Set-Associative Mapping
k-way set-associative mapping: the cache lines are grouped into sets of k lines each. Block j maps to exactly one set, set number = j mod S (S = number of sets), and can be placed in any of the k lines of that set.
This is the compromise used by almost every real CPU cache. The index picks a set (like direct mapping), and then only the k tags of that set are compared in parallel (like a small fully associative cache).
address: | tag | set | offset |
│ │
│ └──► select one SET (k lines)
│ +---------------+---------------+
│ | V tag block | V tag block | (2-way)
│ +---------------+---------------+
│ │ │
└──────────────► [= ?] [= ?] k comparators
└──── OR ───────┘ → hit
a k-to-1 multiplexer picks the data of the matching wayThe beauty of set associativity is that it generalises the other two:
| Associativity k | Number of sets S | What it really is |
|---|---|---|
| k = 1 | S = L | Direct mapped |
| 1 < k < L | S = L / k | Set associative |
| k = L | S = 1 | Fully associative |
Each doubling of associativity halves the number of sets, which removes one index bit and adds one tag bit. Real examples: many recent x86 cores use an 8-way or 12-way L1 data cache, and L2/L3 caches are commonly 8 to 16 ways.
Worked Example 1: The Same Cache, Three Ways
A byte-addressable machine has 32-bit addresses. The cache is 32 KB with 64-byte blocks. Find the tag, index and offset widths for (a) direct mapping, (b) 4-way set associative, (c) fully associative.
Offset bits = log2(64) = 6
Lines L = 32 KB / 64 B = 2^15 / 2^6 = 2^9 = 512
(a) Direct mapped: index = log2(512) = 9
tag = 32 - 9 - 6 = 17
(b) 4-way: sets = 512 / 4 = 128 → index = 7
tag = 32 - 7 - 6 = 19
(c) Fully assoc.: no index
tag = 32 - 6 = 26| Mapping | Tag | Index | Offset | Comparators | Comparator width |
|---|---|---|---|---|---|
| Direct mapped | 17 | 9 (line) | 6 | 1 | 17 bits |
| 4-way set associative | 19 | 7 (set) | 6 | 4 | 19 bits |
| Fully associative | 26 | 0 | 6 | 512 | 26 bits |
Where Does a Given Address Go?
Take the address 0x1234ABCD in the same cache. Write it in binary and cut it according to the field widths:
0x1234ABCD = 0001 0010 0011 0100 1010 1011 1100 1101
Direct mapped (17 | 9 | 6):
tag = 00010010001101001 = 0x2469
line = 010101111 = 175 (0x0AF)
offset = 001101 = 13 (0xD)
4-way (19 | 7 | 6):
tag = 0001001000110100101 = 0x91A5
set = 0101111 = 47 (0x2F)
offset = 001101 = 13
Fully associative (26 | 6):
tag = 0x48D2AF, offset = 13Notice that the offset never changes: it depends only on the block size. Also notice the direct-mapped line number 175 = 128 + 47: the 4-way set number is just the low 7 bits of the line number.
Worked Example 2: Tracing Hits and Misses
A tiny cache has 4 lines (one block per line). The CPU accesses memory blocks in this order: 3, 11, 3, 7, 11, 2, 3, 7. All lines start invalid. Count the hits for direct mapping, 2-way set associative (LRU) and fully associative (LRU).
(a) Direct Mapped: line = block mod 4
Blocks 3, 7 and 11 all give remainder 3, so they all fight over line 3.
| Access | Line | Result | Line 0 | Line 1 | Line 2 | Line 3 |
|---|---|---|---|---|---|---|
| 3 | 3 | Miss | - | - | - | 3 |
| 11 | 3 | Miss (evicts 3) | - | - | - | 11 |
| 3 | 3 | Miss (evicts 11) | - | - | - | 3 |
| 7 | 3 | Miss (evicts 3) | - | - | - | 7 |
| 11 | 3 | Miss (evicts 7) | - | - | - | 11 |
| 2 | 2 | Miss | - | - | 2 | 11 |
| 3 | 3 | Miss (evicts 11) | - | - | 2 | 3 |
| 7 | 3 | Miss (evicts 3) | - | - | 2 | 7 |
8 misses, 0 hits, even though lines 0 and 1 were never used. Classic thrashing.
(b) 2-Way Set Associative: 2 sets, set = block mod 2
Blocks 3, 7, 11 are odd, so all go to set 1. Set 1 can hold two of them at a time. On a miss in a full set we evict the least recently used block.
| Access | Set | Result | Set 0 | Set 1 (way 0, way 1) |
|---|---|---|---|---|
| 3 | 1 | Miss | - | 3, - |
| 11 | 1 | Miss | - | 3, 11 |
| 3 | 1 | Hit | - | 3, 11 |
| 7 | 1 | Miss (LRU is 11) | - | 3, 7 |
| 11 | 1 | Miss (LRU is 3) | - | 11, 7 |
| 2 | 0 | Miss | 2 | 11, 7 |
| 3 | 1 | Miss (LRU is 7) | 2 | 11, 3 |
| 7 | 1 | Miss (LRU is 11) | 2 | 7, 3 |
7 misses, 1 hit. Better, but three blocks still compete for two places.
(c) Fully Associative (LRU)
| Access | Result | Cache contents |
|---|---|---|
| 3 | Miss | 3 |
| 11 | Miss | 3, 11 |
| 3 | Hit | 3, 11 |
| 7 | Miss | 3, 11, 7 |
| 11 | Hit | 3, 11, 7 |
| 2 | Miss | 3, 11, 7, 2 |
| 3 | Hit | 3, 11, 7, 2 |
| 7 | Hit | 3, 11, 7, 2 |
4 misses, 4 hits. Only 4 distinct blocks are used and they all fit, so the only misses are the unavoidable first-time (compulsory) misses.
| Mapping | Misses | Hits | Hit ratio |
|---|---|---|---|
| Direct mapped | 8 | 0 | 0 / 8 = 0% |
| 2-way set associative | 7 | 1 | 1 / 8 = 12.5% |
| Fully associative | 4 | 4 | 4 / 8 = 50% |
Lesson: with the same capacity, more associativity can only remove conflict misses. It cannot remove compulsory misses (first touch) or capacity misses (working set bigger than the cache). These are the "three Cs" from Cache Memory; we measure them more carefully in Cache Performance & Multi-level Caches.
These traces were checked with a small simulator. You can write your own in a few lines:
def simulate(blocks, num_sets, ways):
sets = [[] for _ in range(num_sets)] # each set: list ordered LRU → MRU
hits = 0
for b in blocks:
s = sets[b % num_sets]
if b in s:
hits += 1
s.remove(b) # move to MRU position
elif len(s) == ways:
s.pop(0) # evict LRU
s.append(b)
return hits
seq = [3, 11, 3, 7, 11, 2, 3, 7]
print(simulate(seq, 4, 1), simulate(seq, 2, 2), simulate(seq, 1, 4))0 1 4Worked Example 3: Tag Directory Size
The tags, valid bits and other status bits are kept in a separate small memory called the tag directory (tag array). GATE often asks for its size.
A 64 KB direct-mapped cache has 32-byte blocks. Addresses are 32 bits. Each line has a valid bit and a dirty bit besides the tag. What is the size of the tag directory?
Offset = log2(32) = 5 bits
Lines = 64 KB / 32 B = 2048 = 2^11 → index = 11 bits
Tag = 32 - 11 - 5 = 16 bits
Bits per line in directory = 16 (tag) + 1 (valid) + 1 (dirty) = 18
Tag directory = 2048 × 18 = 36,864 bits = 4,608 bytes = 4.5 KBFor our 32 KB, 64-byte-block cache with only a valid bit per line: direct mapped needs 512 × (17 + 1) = 9,216 bits, 4-way needs 512 × (19 + 1) = 10,240 bits and fully associative needs 512 × (26 + 1) = 13,824 bits. More associativity means longer tags, so the directory grows. (Set-associative caches also need replacement bits per set; see the next chapter.)
Worked Example 4: Which Set Does a Block Go To?
A 2-way set-associative cache has 128 lines. Main-memory block number 1000 maps to which set?
Sets = 128 / 2 = 64
Set = 1000 mod 64 = 40 (1000 = 15 × 64 + 40)
Tag = 1000 div 64 = 15The block can occupy either of the 2 lines of set 40. If the cache were direct mapped with the same 128 lines, it would go to line 1000 mod 128 = 104.
Comparison of Mapping Techniques
| Feature | Direct mapped | k-way set associative | Fully associative |
|---|---|---|---|
| Places a block can go | 1 | k | All L lines |
| Address fields | Tag, line, offset | Tag, set, offset | Tag, offset |
| Tag comparators | 1 | k | L |
| Extra multiplexer | None | k-to-1 for data | L-to-1 for data |
| Replacement policy needed? | No | Yes (within a set) | Yes (whole cache) |
| Conflict misses | Most | Fewer | None |
| Hit time | Fastest | Medium | Slowest |
| Hardware cost and power | Lowest | Medium | Highest |
| Typical use | Very simple or very large caches | L1, L2, L3 caches | TLBs, small buffers |
Why is a direct-mapped cache faster? Its data can be read out while the single tag comparison is happening, because there is only one candidate. In a set-associative cache the multiplexer must wait for the comparators to decide which way hit. Designers trade this small hit-time increase for a lower miss rate.
Common Mistakes
Using the cache size instead of the number of lines. Index bits come from the number of lines (direct) or sets (set associative), not from the cache size in bytes.
Forgetting to divide by associativity. In a 4-way cache the index selects a set, so use sets = lines / 4.
Mixing word and byte addressing. If memory is word addressable with 4-byte words, a 32-byte block holds 8 words and the offset is 3 bits, not 5.
Giving a fully associative cache an index field. It has none; tag = address bits minus offset bits.
Thinking a set-associative cache searches the whole cache. It searches only the k lines of one set.
Ignoring the valid bit. A tag match on an invalid line is not a hit.
Assuming higher associativity always wins. It lowers conflict misses but increases hit time, power and tag storage.
GATE and Interview Questions
Q1. A 16 KB, 4-way set-associative cache has blocks of 8 words, each word 32 bits. Physical addresses are 32-bit byte addresses. How many tag bits are there?
Block size = 8 × 4 B = 32 B, so offset = 5 bits. Lines = 16 KB / 32 B = 512. Sets = 512 / 4 = 128, so set index = 7 bits. Tag = 32 − 7 − 5 = 20 bits.
Q2. An 8-way set-associative cache uses 20-bit tags. How many comparators are needed, and how wide is each?
One comparator per way: 8 comparators, each 20 bits wide. Only the 8 tags of the indexed set are compared.
Q3. In a direct-mapped cache with 256 lines and 16-byte blocks, two addresses 0x0000 and 0x1000 are accessed alternately. What happens?
Block numbers are 0x0000 / 16 = 0 and 0x1000 / 16 = 256. Lines: 0 mod 256 = 0 and 256 mod 256 = 0. Both map to line 0, so every access misses (thrashing), even though the cache has 255 other lines free. A 2-way set-associative cache of the same size would hold both.
Q4. If you double the associativity of a cache while keeping the size and block size the same, what happens to the tag and index widths?
The number of sets halves, so the index loses 1 bit and the tag gains 1 bit. The offset is unchanged.
Q5. Why don't L1 caches use fully associative mapping?
A 32 KB cache with 64-byte blocks has 512 lines, which would need 512 parallel tag comparisons on every access. That costs too much area and power and makes the hit time too long. 8-way or 12-way set associativity already removes most conflict misses at a fraction of the cost.
Q6. A direct-mapped cache and a fully associative cache have the same size. Which has the longer tag, and why?
The fully associative cache. It has no index field, so every bit of the block number must be stored in the tag. In a direct-mapped cache the line position itself "remembers" the index bits.
Summary
A mapping technique decides where a memory block may be placed in the cache and therefore where the cache must look on a lookup.
An address is split into tag | index | offset. Offset = log2(block size); index = log2(lines or sets); tag = the rest.
Direct mapped: line = block mod lines. One comparator, fastest and cheapest, but suffers from conflict misses and thrashing.
Fully associative: any line; no index; one comparator per line; no conflict misses; needs a replacement policy.
k-way set associative: set = block mod sets; k comparators; the practical compromise used in real CPUs. k = 1 is direct mapped, k = L is fully associative.
Doubling associativity removes one index bit and adds one tag bit. The tag directory size = lines × (tag + valid + other status bits).
Next, Cache Replacement & Write Policies answers two questions this chapter left open: which line to evict from a full set, and what to do when the CPU writes.