Chapter 26 of 39

Cache Mapping Techniques

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:

TechniqueWhere can block B go?Analogy
Direct mappedExactly one line, fixed by B's numberAssigned seat in an exam hall
Fully associativeAny line in the cacheFree seating in a cinema with no seat numbers
k-way set associativeAny of the k lines of one fixed setAssigned 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:

  1. Offset (word/byte field): selects the byte inside a block. If the block has 2b bytes, the offset is b bits.

  2. 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.

  3. 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 block

Only 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 ─────────────────────┘
                         = hit
  • Advantage: 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 way

The beauty of set associativity is that it generalises the other two:

Associativity kNumber of sets SWhat it really is
k = 1S = LDirect mapped
1 < k < LS = L / kSet associative
k = LS = 1Fully 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
MappingTagIndexOffsetComparatorsComparator width
Direct mapped179 (line)6117 bits
4-way set associative197 (set)6419 bits
Fully associative260651226 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 = 13

Notice 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.

AccessLineResultLine 0Line 1Line 2Line 3
33Miss---3
113Miss (evicts 3)---11
33Miss (evicts 11)---3
73Miss (evicts 3)---7
113Miss (evicts 7)---11
22Miss--211
33Miss (evicts 11)--23
73Miss (evicts 3)--27

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.

AccessSetResultSet 0Set 1 (way 0, way 1)
31Miss-3, -
111Miss-3, 11
31Hit-3, 11
71Miss (LRU is 11)-3, 7
111Miss (LRU is 3)-11, 7
20Miss211, 7
31Miss (LRU is 7)211, 3
71Miss (LRU is 11)27, 3

7 misses, 1 hit. Better, but three blocks still compete for two places.

(c) Fully Associative (LRU)

AccessResultCache contents
3Miss3
11Miss3, 11
3Hit3, 11
7Miss3, 11, 7
11Hit3, 11, 7
2Miss3, 11, 7, 2
3Hit3, 11, 7, 2
7Hit3, 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.

MappingMissesHitsHit ratio
Direct mapped800 / 8 = 0%
2-way set associative711 / 8 = 12.5%
Fully associative444 / 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 4

Worked 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 KB

For 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 = 15

The 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

FeatureDirect mappedk-way set associativeFully associative
Places a block can go1kAll L lines
Address fieldsTag, line, offsetTag, set, offsetTag, offset
Tag comparators1kL
Extra multiplexerNonek-to-1 for dataL-to-1 for data
Replacement policy needed?NoYes (within a set)Yes (whole cache)
Conflict missesMostFewerNone
Hit timeFastestMediumSlowest
Hardware cost and powerLowestMediumHighest
Typical useVery simple or very large cachesL1, L2, L3 cachesTLBs, 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.