Cache Memory Mapping

Why have a cache?

The CPU can do an operation in under a nanosecond, but main memory (RAM) takes ~100 ns to answer. A cache is a small, very fast memory close to the CPU that keeps copies of recently used data. If the data is there — a hit — it arrives in a few cycles. If not — a miss — it must be fetched from RAM.

Caches work because of locality:

• Temporal locality — data used now will probably be used again soon (loop variables).
• Spatial locality — data near it will probably be used soon (array elements). So caches load whole blocks (e.g. 64 bytes), not single bytes.

The mapping problem

Memory has many more blocks than the cache has lines. In the model, 16 memory blocks share 4 cache lines. The mapping decides which line(s) each block is allowed to use. To find a block later, each line also stores a tag — the part of the address that says which block is there — and a valid bit.

1. Direct mapping

Each block has exactly one possible line:

line = block mod (number of lines)
tag  = block div (number of lines)

The block address splits into tag | index. Lookup is cheap — check one line — but two busy blocks that map to the same line keep evicting each other (conflict misses), even if other lines are empty. With requests 0, 8, 0, 8, … blocks 0 and 8 both need line 0: every request misses.

2. Fully associative mapping

A block can go in any line. The whole block number is the tag, and lookup compares the tag with every line at once. No conflict misses, but the comparison hardware is expensive, so this is used only for small caches (like the TLB).

3. Set-associative mapping (the compromise)

Lines are grouped into sets of k lines (k-way). A block maps to one set but can use any line inside it:

set = block mod (number of sets)
tag = block div (number of sets)

With 2 ways, blocks 0 and 8 can live side by side in set 0. Most real CPU caches are 4- to 16-way set associative.

Note that direct mapped = 1-way, and fully associative = one set with all the lines.

Replacement: LRU

When a block must go into a full set, which one is evicted? LRU (Least Recently Used) evicts the block unused for the longest time. Others: FIFO and random. Direct mapping has no choice to make.

Address breakdown (with bytes)

A real address also has an offset — which byte inside the block:

tag	index (set)	offset

Example: 32-bit addresses, 64-byte blocks, 256 sets → offset = 6 bits, index = 8 bits, tag = 32 − 8 − 6 = 18 bits.

Code: a set-associative cache simulator

def simulate(refs, lines=4, ways=1):
    sets = lines // ways
    cache = [[] for _ in range(sets)]      # each set: list of blocks, LRU first
    hits = 0
    for b in refs:
        s = cache[b % sets]
        if b in s:
            hits += 1
            s.remove(b)                    # move to most-recently-used position
        elif len(s) == ways:
            s.pop(0)                       # evict the LRU block
        s.append(b)
    return hits

refs = [0, 8, 0, 8, 1, 5, 1, 5, 0, 1]
print(simulate(refs, ways=1), simulate(refs, ways=2), simulate(refs, ways=4))   # 0 6 6

Common mistakes

• Forgetting that the index bits are the low bits of the block number and the tag is the high bits.
• Thinking a bigger associativity always wins — it costs power and time per lookup.
• Mixing up block numbers and byte addresses — divide the byte address by the block size first.