Cache hierarchies: multilevel AMAT, prefetching and blocking
Multilevel average access time with proof, local and global rates, inclusive and exclusive caches, write-back, non-blocking caches and prefetching, blocking proved.
A modern processor can execute an instruction in a third of a nanosecond, while a DRAM access takes about a hundred. Between the two lies a multi-level cache hierarchy, and performance depends on its effectiveness more than on anything else. The Computer Systems course introduced the cache, locality and average access time. In this lesson we look at multi-level hierarchies with the proof of the average access time formula, local and global miss rates, write policies, non-blocking caches and prefetching, and the blocking technique with the proof of the traffic saved.
The multi-level hierarchy
A typical processor has a level-one (L1) cache of 32-64 KB for data and one for instructions, accessible in 4-5 cycles; a private L2 per core of 1-2 MB, in about fifteen cycles; an L3 shared among the cores of tens of megabytes, in 40-60 cycles; then DRAM.
Theorem. With access times 
and local miss rates 
(the fraction of accesses reaching level 
that do not find the data there), the average memory access time of a three-level hierarchy is
![\[ AMAT = t_1 + m_1\big(t_2 + m_2(t_3 + m_3\,t_{mem})\big) \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-b496091deaed05a5181d9149a4656570_l3.png "Rendered by QuickLaTeX.com")
Proof. Every access spends 
in L1. With probability 
it does not find the data and continues: from there the expected time is the average access time of the hierarchy starting at L2, i.e. 
plus, with probability 
, the average time of the hierarchy starting at L3, and so on down to memory, where the data is always present. Applying the same rule at every level gives the nested expression. ∎
Example. With 
ns, 
, 
ns, 
, 
ns, 
, 
ns:
![\[ AMAT = 1 + 0.05\big(4 + 0.3(12 + 0.4\cdot 80)\big) = 1 + 0.05\cdot 17.2 \approx 1.86\ \text{ns} \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-feec7a1e48908b00e62705cfaeb14a84_l3.png "Rendered by QuickLaTeX.com")
The average time is close to that of L1, even though DRAM is 80 times slower.
Local and global rates
The local rate of a level often looks high: 30-40 % for an L2 or L3. It is not a defect: only the accesses that L1 has already missed, i.e. the difficult ones, reach those levels. What matters is the global rate, the fraction of all the processor’s accesses that reach memory: 
, in the example 
. To compare two L2s one must look at how many global accesses they save.
Caches are called inclusive if every datum of one level is also in the level below (it simplifies coherence), exclusive if a datum is in one level only (it makes better use of total capacity).
Writes
A write-through cache writes every change to the level below as well: simple and always coherent, but it generates a lot of traffic, mitigated by a write buffer that queues the writes. A write-back cache writes to memory only when the modified block is evicted, marking it with a “dirty” bit: much less traffic, because a datum modified a hundred times is written only once. Almost all processor caches are write-back; coherence among the cores then becomes the problem of the dedicated lesson.
To the three classic causes of misses (compulsory, capacity, conflict) multicores add a fourth: coherence misses, when another core has invalidated the block.
Non-blocking caches and prefetching
An out-of-order processor does not stop at a miss: it continues with independent instructions, and may generate further accesses. Non-blocking caches handle several misses at once, tracking them in dedicated registers (MSHRs): the waits overlap and the time lost on each shrinks. Memory-level parallelism matters as much as instruction-level parallelism.
Prefetching brings data into the cache before it is needed. Hardware prefetchers recognise constant-stride accesses (an array read sequentially, a column of a matrix) and request the following blocks in advance. Compilers can insert explicit prefetch instructions. It works if it is timely (the data arrives in time) and accurate (it does not evict useful data for useless data).
Writing cache-friendly code
The programmer can do a lot. The product of two 
matrices in the classic three-loop form reads one of the two matrices by columns: if 
is large, every element read is in a different block, and the number of misses is of the order of 
.
Blocking (or tiling) divides the matrices into 
submatrices small enough to fit in the cache together (
elements less than the capacity) and computes the product block by block.
Theorem. With blocking the number of elements transferred from memory is of the order of 
, instead of .
Proof. The product decomposes into 
products of blocks: for each block of the result 
products are added, and there are 
result blocks. Each block product loads one block of each matrix, 
elements, and then works in the cache, performing 
multiplications with no further transfers. The total is 
, plus the 
elements of the result. ∎
Traffic is reduced by a factor proportional to 
: with a 32 KB L1 and 8-byte numbers, 
, an order of magnitude less. Optimised linear algebra libraries apply blocking at several levels, one per cache, and come close to the processor’s peak performance. It is the same principle as arithmetic intensity in the roofline model (lesson on SIMD and GPUs).
