Cache memory: hierarchy, locality and average access time

A modern processor executes an instruction in less than a nanosecond, but reading a value from main memory (DRAM) takes about 80 ns: without countermeasures it would spend nearly all its time waiting. The solution is a memory hierarchy: small, very fast memories close to the processor, large and slow ones further away. It works thanks to a property of programs, locality. In this lesson we see how a cache is built, how the average access time is computed and how the way code is written changes its effectiveness.

The hierarchy

Fast memories (SRAM, in caches) are expensive per bit and take a lot of area; large ones (DRAM, flash) are cheap but slow. Each level holds a copy of the most recently used parts of the level below.

Locality

• Temporal locality: a recently used item will probably be used again soon (the variables of a loop, the instructions of the loop itself).
• Spatial locality: if an item is used, nearby ones probably will be too (the next elements of an array, the next instructions).

To exploit the latter, the cache copies not single bytes but blocks (or lines) of 64 bytes: reading the first element of an array also brings the following ones into the cache.

The direct-mapped cache

Each memory block can live in only one cache line, chosen by part of the address. The address is split into three fields.

Example. A 32 KiB cache with 64-byte blocks and 32-bit addresses: there are lines.

• offset (6 bits, since ): which byte within the block;
• index (9 bits, since ): which cache line;
• tag (the remaining bits): which of the many blocks mapping to that line is present.

Each line holds the block, the tag and a valid bit. On access, the index picks the line and the tag is compared: if it matches (and the line is valid) it is a hit, otherwise a miss: the block is read from the level below and replaces the one present.

Average memory access time

where is the miss rate and the time to fetch the block.

Example. A 1-cycle cache, 5% misses, 100 cycles to reach DRAM: AMAT = cycles. Adding a 10-cycle second-level cache that finds 80% of the blocks missed in the first level: AMAT = cycles. The second level more than halves the average time.

Even miss rates that look small weigh heavily: going from 2% to 4% misses, with a 100-cycle penalty, takes AMAT from 3 to 5 cycles.

Associativity and types of miss

In a direct-mapped cache, two blocks used alternately that map to the same line keep evicting each other. -way set-associative caches let each block live in different lines (a set), comparing tags in parallel, and when the set is full they replace the least recently used block (LRU). First-level caches are typically 8-way.

Misses are classified as the “three Cs”: compulsory (the first access to a block), capacity (the data in use do not all fit), conflict (blocks competing for the same set).

Writes. With a write-through policy every write also goes to the level below; with write-back only the cache is written, and the modified block (marked by a “dirty” bit) is copied to memory when it is replaced. The latter greatly reduces memory traffic and is what processor caches use.

Code matters

In C, matrices are stored by rows: the elements of a row are contiguous.

/* fast: walks memory in order */
for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
        s += a[i][j];

/* slow: jumps N elements on every access */
for (j = 0; j < N; j++)
    for (i = 0; i < N; i++)
        s += a[i][j];

The two versions do exactly the same calculations, but with a large matrix the second can be several times slower: each access falls in a different block, and when the same row comes round again its block has already been replaced. Organising data and loops to exploit locality is one of the most effective optimisations of all, and the basis of fast numerical libraries (which work on blocks that fit in the cache).