Cache performance and optimizations

Lesson 7 described how a cache is built. This lesson asks how to make the memory system faster, using average memory access time as the scorecard. Every optimization attacks one of its three terms: it reduces the miss rate, reduces the miss penalty, or reduces the hit time, and many also try to overlap misses with useful work. Some of the most effective optimizations are not in hardware at all but in the order in which software touches memory. By the end of the lesson Jonah has cut the cache misses of the NS-5 radar's most memory-bound step by a factor of four and a half without changing the processor.

Memory stalls in the iron law

Cache misses enter the iron law through CPI. If a fraction of instructions access memory and some of those accesses miss, each miss adds the miss penalty in stall cycles, unless the processor can hide it. For an in-order core, which cannot hide misses, the contribution is straightforward to estimate.

Suppose a core has a base CPI of 1.0, makes 1.3 memory accesses per instruction counting instruction fetches, and misses on 2 percent of them with a 50-cycle penalty. Memory stalls add 1.3 × 0.02 × 50 = 1.3 cycles per instruction, more than doubling CPI. The example shows why even small miss rates matter, and why the gap between processor and memory speeds dominates design.

Multilevel caches

A larger cache misses less, but it is slower, so architects build several levels: a small, fast first level that keeps up with the pipeline, and larger second and third levels that catch most of the first level's misses before they reach main memory. AMAT then nests: the first level's miss penalty is itself the AMAT of the second level.

Two kinds of miss rate are used. The local miss rate of a level is its misses divided by the accesses that reach it; the global miss rate is its misses divided by all accesses from the processor. A second-level cache with a local miss rate of 30 percent may look poor, but if the first level misses only 5 percent of the time, the global miss rate is 1.5 percent, and the second level is filtering out 70 percent of the traffic that would otherwise go to memory. The second level's job is different from the first's: it can be slower and more associative, because it is accessed only on first-level misses, and its size matters more than its speed.

Multilevel hierarchies also choose an inclusion policy. In an inclusive hierarchy, every block in the first level is also in the second, which simplifies coherence checks in multiprocessors; an exclusive hierarchy keeps each block in only one level, making the total effective capacity larger. Many designs are neither strictly inclusive nor exclusive.

Reducing the miss rate

The direct ways to reduce misses follow from the three Cs. Larger blocks exploit spatial locality and cut compulsory misses, until they become so large that they waste bandwidth and reduce the number of blocks. Larger caches cut capacity misses at the cost of hit time, area and energy. Higher associativity cuts conflict misses, with diminishing returns: measurements across many programs have long suggested that an eight-way cache behaves almost like a fully associative one, and that a direct-mapped cache of size N misses about as often as a two-way cache of size N/2. A victim cache, a tiny fully associative buffer that holds recently evicted blocks, catches many conflict misses in a direct-mapped cache at low cost. Way prediction lets a set-associative cache guess which way will hit and read only that one, recovering most of the hit-time and energy advantage of a direct-mapped design.

Reducing the miss penalty

When a miss cannot be avoided, its cost can be cut. Critical word first fetches the word the processor asked for before the rest of the block and lets the pipeline restart as soon as it arrives. Giving reads priority over writes, by draining writes from a write buffer only when the memory bus is idle and checking the buffer for matching addresses on each read miss, keeps write traffic out of the way of loads, which the processor is waiting for. Merging write buffers combine several writes to the same block into one transfer. And the second-level cache itself is the largest single reduction in miss penalty.

Hiding miss latency

A blocking cache stops serving the processor during a miss. A non-blocking, or lockup-free, cache continues to serve hits during a miss, called hit under miss, and can track several outstanding misses at once in miss status holding registers. Out-of-order cores rely on this to overlap many misses, a property called memory-level parallelism: if eight independent loads miss at about the same time, their latencies overlap and the cost per miss falls nearly eightfold. In-order cores benefit less, but even they gain from hit under miss when the instruction after a missing load does not need its value.

Prefetching fetches blocks before they are requested. Hardware prefetchers watch the stream of miss addresses, detect sequential or strided patterns, and request the next blocks ahead of time; nearly every modern cache has at least a next-line or stride prefetcher. Software prefetch instructions let the compiler or programmer request data a known distance ahead in a loop. Prefetching works when it is accurate and timely: a prefetch that arrives too late saves little, and one that fetches unneeded data wastes bandwidth and may evict useful blocks.

Compiler and programmer optimizations

The order in which a program touches memory determines its locality, and simple code transformations can change miss rates dramatically without any new hardware. Loop interchange swaps nested loops so that the inner loop walks along consecutive addresses. C stores two-dimensional arrays in row-major order, so a loop over a[i][j] should have j in the inner loop; with i inner, each access jumps a whole row ahead and may touch a new block every time. Loop fusion combines loops that traverse the same arrays, so data loaded by the first is still cached for the second. Data layout changes, such as padding arrays to avoid the conflict alignment of lesson 7 or switching between arrays of structures and structures of arrays, match the layout to the access pattern.

Blocking, also called tiling, is the most powerful of these. When an algorithm must access a matrix both by rows and by columns, as in matrix multiplication or transposition, no loop order makes both accesses sequential. Blocking restructures the loops to work on small submatrices, tiles, that fit in the cache together, finishing all the work on a tile before moving on. Each block brought into the cache is then used many times before it is evicted. Dense linear algebra libraries are built around tiling at several levels of the hierarchy at once.

The NS-5 radar computes a range-Doppler map, a 64 by 64 matrix of samples, and must transpose it between two stages of processing, an operation radar engineers call a corner turn. Jonah also sums every element of the matrix to estimate noise. The program below measures the misses for both kernels in an 8 KiB two-way cache with 32-byte blocks, like Core A's, and ends with the two-level AMAT from the example.

# Loop order, blocking and two-level AMAT for a 64 x 64 matrix transpose-and-scale
def misses(trace, size=8192, block=32, ways=2):
    sets = size // (block * ways); cache = [[] for _ in range(sets)]; miss = 0
    for a in trace:
        b = a // block; s = cache[b % sets]; t = b // sets
        if t in s: s.remove(t)
        else:
            miss += 1
            if len(s) == ways: s.pop(0)
        s.append(t)
    return miss

N, A, B = 64, 0x20000, 0x30000          # 64 x 64 matrices of 4-byte samples, row-major
def addr(base, r, c): return base + 4 * (r * N + c)

# Kernel 1: sum every element of A, with the inner loop over columns or over rows
good = [addr(A, i, j) for i in range(N) for j in range(N)]
bad = [addr(A, i, j) for j in range(N) for i in range(N)]
for name, t in (("sum, inner loop over j", good), ("sum, inner loop over i", bad)):
    m = misses(t)
    print(f"{name:24s} misses {m:5d}   miss rate {m/len(t):.3f}")

# Kernel 2: B = transpose of A, three loop structures
row_order = [x for i in range(N) for j in range(N) for x in (addr(A, i, j), addr(B, j, i))]
col_order = [x for j in range(N) for i in range(N) for x in (addr(A, i, j), addr(B, j, i))]
tiled = [x for ii in range(0, N, 8) for jj in range(0, N, 8)
         for i in range(ii, ii + 8) for j in range(jj, jj + 8) for x in (addr(A, i, j), addr(B, j, i))]

for name, t in (("i outer (rows of A)", row_order), ("j outer (columns of A)", col_order), ("8 x 8 tiles", tiled)):
    m = misses(t)
    print(f"{name:24s} misses {m:5d}   miss rate {m/len(t):.3f}")

# Two-level AMAT for a server core: L1 1 ns, L2 4 ns, memory 80 ns
l1_hit, l2_hit, mem = 1.0, 4.0, 80.0
m1, m2_local = 0.05, 0.30
amat = l1_hit + m1 * (l2_hit + m2_local * mem)
print(f"two-level AMAT {amat:.2f} ns, global L2 miss rate {m1*m2_local:.3f}")

sum, inner loop over j   misses   512   miss rate 0.125
sum, inner loop over i   misses  4096   miss rate 1.000
i outer (rows of A)      misses  4608   miss rate 0.562
j outer (columns of A)   misses  4608   miss rate 0.562
8 x 8 tiles              misses  1024   miss rate 0.125
two-level AMAT 2.40 ns, global L2 miss rate 0.015

The sum shows loop interchange at work: with the inner loop running along rows, one miss brings in eight samples and the miss rate is 12.5 percent; with the inner loop running down columns, every access misses, because the 64 blocks of a column do not fit in the sets they map to before the next column needs them again. The transpose is harder. Whichever loop is outermost, one of the two matrices is read or written down a column, and the miss rate stays at 56 percent. Tiling the transpose into 8 by 8 blocks, each exactly one cache block wide, keeps both tiles resident while they are processed and brings the miss rate down to 12.5 percent, the compulsory minimum. The misses fall from 4,608 to 1,024, a factor of four and a half, and because the corner turn spends most of its time waiting on misses, its run time on Core A falls by nearly as much.

Measuring rather than guessing

Cache behaviour is notoriously hard to predict by intuition, because it depends on addresses, alignment and interactions between data structures. Hardware performance counters, available on nearly every modern processor including both NS-5 candidates, count cache accesses, misses, stall cycles and many other events while real code runs. Trace-driven simulation, like the programs in this lesson, lets designers explore configurations that do not yet exist. A good engineering habit is to form a hypothesis from the three Cs, test it with counters or simulation, and only then change code or hardware.