The memory hierarchy

Programmers want memory that is huge, fast and cheap. No single technology is all three, so computers stack several, the fast small ones close to the processor:

From L1 to a disk, the time grows by a factor of ten million. If each L1 access were one second, a disk access would take almost four months.

Locality

Caches work because programs are predictable:

• Temporal locality: data used now is likely to be used again soon (a loop counter, a running total).
• Spatial locality: data near something just used is likely to be used soon (the next array element, the next instruction).

So each level keeps recently used data, and moves it in blocks (often 64 bytes), not single bytes. The order in which a program walks through an array matters a lot:

rows, cols, block = 4, 4, 4           # a 4 x 4 array stored row by row; 4 elements per cache block

def block_loads(by_rows):
    held, loads = None, 0                # a tiny cache that keeps one block
    for i in range(rows * cols):
        r, c = (i // cols, i % cols) if by_rows else (i % rows, i // rows)
        b = (r * cols + c) // block
        if b != held:
            loads += 1
            held = b
    return loads

print("row by row:", block_loads(True), "block loads")
print("column by column:", block_loads(False), "block loads")

Average memory access time

AMAT = hit time + miss rate × miss penalty

With two levels of cache, the L1 miss penalty is itself the L2's AMAT:

l1_hit, l1_miss = 1, 0.05        # ns, fraction of accesses
l2_hit, l2_miss = 10, 0.20       # of the accesses that reach L2
memory = 100

l2_amat = l2_hit + l2_miss * memory
amat = l1_hit + l1_miss * l2_amat
print("L2 average time:", l2_amat, "ns")
print("overall AMAT:", round(amat, 2), "ns")
print("without L2:", l1_hit + l1_miss * memory, "ns")

A small change in miss rate makes a big difference, because the miss penalty is so large. That is why caches are a central topic in processor design (next lesson).

Mark lesson complete