Memory Hierarchy and Cache Mapping

A processor can execute an instruction in well under a nanosecond, but main memory takes tens of nanoseconds to answer. The memory hierarchy hides that gap by keeping recently used data in small, fast memories close to the CPU.

The hierarchy and locality

Caches work because programs show locality of reference:

• Temporal locality: data used now is likely to be used again soon (loop variables, the loop's own instructions).
• Spatial locality: data near recently used data is likely to be used soon (array elements, sequential instructions). That is why caches move whole blocks (lines), not single bytes.

Hit ratio and access time

The hit ratio h is the fraction of accesses found in the cache; the miss ratio is 1 − h.

• Average memory access time (AMAT) = hit time + miss rate × miss penalty.
• Hierarchical access (look in the cache first, then go to memory on a miss): T = h·T_c + (1 − h)(T_c + T_m) = T_c + (1 − h)T_m.
• Simultaneous access (start both at once, use whichever answers): T = h·T_c + (1 − h)T_m.
• Two levels: AMAT = T_L1 + m_L1 × (T_L2 + m_L2 × T_mem), where m_L2 is the local miss rate of L2 (misses in L2 / accesses to L2).

Read each question carefully to see which model it intends: with T_c = 10 ns, T_m = 100 ns and h = 0.9, hierarchical access gives 20 ns and simultaneous access 19 ns.

Mapping: where can a block go?

Memory is divided into blocks of the same size as the cache lines. Block number = address / block size.

Direct-mapped is 1-way set-associative, and fully associative is a single set containing all the lines.

Splitting the address

A memory address is divided into three fields:

• Offset bits = log₂(block size in bytes)
• Number of lines = cache size / block size; number of sets = lines / associativity
• Index bits = log₂(number of sets) (zero for fully associative)
• Tag bits = address bits − index bits − offset bits

from math import log2

def fields(address_bits, cache_bytes, block_bytes, ways):
    lines = cache_bytes // block_bytes
    sets = lines // ways
    offset, index = int(log2(block_bytes)), int(log2(sets))
    return address_bits - index - offset, index, offset

for ways, name in [(1, "direct-mapped"), (4, "4-way"), (1024, "fully associative")]:
    tag, index, offset = fields(32, 64 * 1024, 64, ways)
    print(f"64 KB, 64-byte blocks, {name:17}: tag {tag:2}, index {index:2}, offset {offset}")

64 KB, 64-byte blocks, direct-mapped    : tag 16, index 10, offset 6
64 KB, 64-byte blocks, 4-way            : tag 18, index  8, offset 6
64 KB, 64-byte blocks, fully associative: tag 26, index  0, offset 6

Doubling the associativity halves the number of sets, so the index loses one bit and the tag gains one.

Tag memory: each line stores its tag plus status bits (a valid bit, and a dirty bit for write-back caches). Tag memory size = number of lines × (tag bits + status bits). For a 16 KB direct-mapped cache with 64-byte lines and 32-bit addresses: 256 lines, a tag of 32 − 8 − 6 = 18 bits; with valid and dirty bits, 256 × 20 = 5120 bits.

Mapping in action

The program below runs the same sequence of block numbers through an 8-line cache organised three ways, with LRU replacement inside each set:

def simulate(blocks, lines, ways):
    sets = [[] for _ in range(lines // ways)]
    hits, log = 0, ""
    for b in blocks:
        s = sets[b % len(sets)]
        if b in s:
            hits += 1
            s.remove(b)                    # move to most-recently-used position
            log += "H"
        else:
            if len(s) == ways:
                s.pop(0)                   # evict the least recently used block
            log += "M"
        s.append(b)
    return hits, log

blocks = [0, 8, 0, 6, 8, 0, 16, 0, 8, 6]
for ways, name in [(1, "direct-mapped"), (2, "2-way"), (8, "fully associative")]:
    hits, log = simulate(blocks, 8, ways)
    print(f"{name:17} {log}  hits = {hits}")

direct-mapped     MMMMMMMMMH  hits = 1
2-way             MMHMHHMHMH  hits = 5
fully associative MMHMHHMHHH  hits = 6

Blocks 0, 8 and 16 all map to line 0 of the direct-mapped cache and keep evicting each other, while the associative organisations can hold them together.

Kinds of misses (the three Cs)

• Compulsory (cold) misses: the first access to a block. Even an infinite cache has them.
• Capacity misses: the program's working set does not fit in the cache.
• Conflict misses: blocks compete for the same set although other sets have room. Higher associativity removes them.

Practice questions