The memory hierarchy and cache design

A processor that can start several instructions per nanosecond is useless if it waits a hundred nanoseconds for each value from main memory. Processor speeds rose far faster than memory speeds for decades, opening a gap often called the memory wall, and the memory hierarchy is the architect's answer. Small, fast memories near the processor hold copies of the data most likely to be needed next; larger, slower, cheaper memories further away hold everything else. If the guesses are good, the processor sees nearly the speed of the smallest memory and nearly the capacity of the largest. This lesson covers how caches are organized and the choices that determine how good their guesses are.

CMP-229 introduced the direct-mapped cache. The NS-5 candidates go further: Core A has 8 KiB instruction and 8 KiB data caches, both two-way set-associative, while Core B has 16 KiB caches of each kind, four-way set-associative, and both sit in front of a shared external memory. Jonah's task this week is to understand why the radar filter runs almost twice as fast on one cache configuration as on another, even though the code is identical.

Locality: why caches work

Caches work because programs exhibit locality. Temporal locality means that a recently accessed item is likely to be accessed again soon: loop counters, the instructions of a loop body, the coefficients of a filter. Spatial locality means that items near a recently accessed one are likely to be accessed soon: the next element of an array, the next instruction, the next field of a structure. Caches exploit temporal locality by keeping recently used data and spatial locality by moving data in blocks, also called lines, of 32 or 64 bytes, so that one miss brings in neighbours that will probably be needed next.

Cache organization

A cache is described by its capacity, its block size and its associativity. The block is the unit of transfer. Associativity is the number of places in the cache where a given block may be stored. In a direct-mapped cache each block has exactly one possible location; in an n-way set-associative cache the cache is divided into sets of n blocks and a block may go in any of the n ways of one particular set; in a fully associative cache a block may go anywhere. The set is chosen by some bits of the address, the remaining high bits are stored as a tag to identify which block occupies each way, and the low bits select the byte within the block.

On an access, the cache uses the index bits to select a set, reads the tags of all ways in that set in parallel, and compares them with the address tag. A match with the valid bit set is a hit, and the data are delivered from that way. With no match, the access is a miss: the block is fetched from the next level and placed in one of the set's ways, evicting whatever was there. Higher associativity means more comparators and a wider multiplexer, which costs area, energy and sometimes hit time, but it reduces misses caused by blocks competing for the same set.

Replacement policies

When a miss occurs in a set-associative cache whose set is full, one way must be evicted. Least recently used replacement evicts the block that has gone longest without an access, on the theory that temporal locality makes it the least likely to be needed. True LRU needs to track the order of use within each set, which is cheap for two ways but costly for eight or sixteen, so designs approximate it with pseudo-LRU trees or similar schemes. Random replacement is simpler and, for large associativity, performs nearly as well. Modern last-level caches use adaptive policies that detect streaming access patterns, data used once and never again, and insert such blocks at low priority so they do not flush out useful data.

Write policies

Writes raise two questions. When a store hits, is the next level updated at once? A write-through cache sends every write to the next level, usually through a write buffer so the processor need not wait; it keeps the levels consistent and is simple, but generates a lot of traffic. A write-back cache updates only its own copy and marks the block dirty, writing it to the next level only when the block is evicted; it saves bandwidth and energy when a block is written repeatedly, which is common. When a store misses, is the block brought into the cache? Write-allocate fetches the block and then writes it, which suits write-back caches and code that soon reads what it wrote; no-write-allocate sends the write onward without filling the cache, which suits write-through caches and streaming output.

For the NS-5, write-back matters for energy, because every transaction on the external memory bus costs far more energy than an access to on-chip SRAM. Core A's data cache is write-through with a four-entry write buffer; Core B's is write-back. The filter writes each output sample once per frame, so the difference shows up mainly in the energy measurements of lesson 12.

Classifying misses: the three Cs

Misses fall into three categories. Compulsory misses occur on the first access to a block, which cannot be in the cache yet; larger blocks and prefetching reduce them. Capacity misses occur because the cache cannot hold all the blocks a program uses in a period; only a larger cache, or a program that touches less data at a time, reduces them. Conflict misses occur in direct-mapped and set-associative caches when too many active blocks map to the same set, so that blocks are evicted even though the cache as a whole has room; higher associativity reduces them. A fourth C, coherence misses, appears in multiprocessors, where another core's write invalidates a block, as lesson 10 explains. Classifying misses this way tells the designer which change will help.

Jonah simulates the radar filter's data accesses. The filter computes y[i] += c[i mod 64] × x[i] over frames of 2,048 samples, and the linker has placed the three arrays exactly 4 KiB apart, a common result of aligning large arrays to page boundaries. The program compares a 4 KiB data cache with 32-byte blocks at several associativities.

# A set-associative cache simulator with LRU replacement
def simulate(trace, size=4096, block=32, ways=1):
    sets = size // (block * ways)
    cache = [[] for _ in range(sets)]          # each set: list of tags, most recent last
    hits = 0
    for addr in trace:
        blk = addr // block
        idx, tag = blk % sets, blk // sets
        s = cache[idx]
        if tag in s:
            hits += 1; s.remove(tag)
        elif len(s) == ways:
            s.pop(0)                            # evict least recently used
        s.append(tag)
    return hits / len(trace)

# Filter: y[i] += c[i % 64] * x[i] over 2048-sample frames; arrays placed 4 KiB apart
X, Y, C = 0x10000, 0x11000, 0x12000
trace = []
for frame in range(4):
    for i in range(2048):
        trace += [C + 4 * (i % 64), X + 4 * i, Y + 4 * i, Y + 4 * i]   # load c, load x, load y, store y

print("4 KiB, 32-byte blocks, direct mapped: offset 5 bits, index 7 bits (128 sets), tag 20 bits")
for ways in (1, 2, 4, 128):
    label = "fully associative" if ways == 128 else f"{ways}-way"
    print(f"{label:18s} hit rate {simulate(trace, ways=ways):.3f}")

4 KiB, 32-byte blocks, direct mapped: offset 5 bits, index 7 bits (128 sets), tag 20 bits
1-way              hit rate 0.507
2-way              hit rate 0.874
4-way              hit rate 0.938
fully associative  hit rate 0.938

The direct-mapped cache hits only about half the time. Because the arrays are 4 KiB apart and the cache is 4 KiB, element i of each array maps to the same set, so loading c evicts y, loading x evicts c, and so on: almost every access is a conflict miss. Two ways help a lot, raising the hit rate to 87 percent, but three arrays still compete for two ways in the sets that hold coefficients. Four ways remove the conflicts entirely: the hit rate of 93.8 percent equals that of a fully associative cache, and the remaining misses are compulsory, one per 32-byte block of x and of y. The same effect explains the near-doubling of speed Jonah saw: a two-line change to the linker script that offsets the arrays by 96 bytes lifts the direct-mapped hit rate to about 94.7 percent in the same simulation, as good as the four-way cache.

Average memory access time

The standard measure of a cache's effect on performance combines hit time, miss rate and miss penalty. Average memory access time, AMAT, is the hit time plus the fraction of accesses that miss times the time to service a miss from the next level. Lesson 8 extends it to several levels and uses it to evaluate cache optimizations.

With a hit time of 1 cycle and a miss penalty of 40 cycles, the direct-mapped filter's miss rate of about 0.49 gives an AMAT of about 20.7 cycles, while the four-way cache's miss rate of 0.062 gives about 3.5 cycles. Both numbers swamp the hit time, which is why miss rate, not hit time, dominates cache design for most workloads.

Instruction caches and split versus unified designs

Instruction fetch has excellent locality, because loops execute the same instructions repeatedly and straight-line code is sequential. Separate level 1 instruction and data caches let the pipeline fetch and load in the same cycle, avoiding the structural hazard a single cache would create, and each can be tuned to its access pattern. Lower levels are usually unified, holding both instructions and data, so that capacity is shared according to demand. Instruction caches are read-only from the core's point of view, which simplifies them: they never hold dirty data.