Memory hierarchy and performance (AMAT)

Why it exists

Fast memory is small and expensive; large memory is cheap and slow. No single technology gives all three of large, fast and cheap. A computer therefore uses a hierarchy: a few very fast registers, a small fast cache, a larger and slower main memory, and a very large and very slow disk. The hierarchy works because programs do not use memory at random: they reuse what they used recently and use what is near it. With that behaviour most accesses are served by the fast levels, so the average access is nearly as fast as the fastest level while the total capacity and cost are those of the slowest and cheapest. GATE asks for the average access time, the effect of hit ratios, and how two or three levels combine.

Prerequisites

None. This is a starting point.

No earlier page is needed beyond ordinary arithmetic with ratios.

Precise definitions

The levels (smaller, faster and more expensive per bit toward the top):

Principle of locality. Programs tend to access a small part of their address space at any time.

• Temporal locality: an item used recently is likely to be used again soon (loop variables, instructions of a loop).
• Spatial locality: items near a recently used item are likely to be used soon (sequential instructions, array elements).

Hardware exploits temporal locality by keeping recently used items in the fast level and spatial locality by moving data in blocks (lines) rather than single words.

Hit and miss. A hit is an access satisfied by the level being examined; a miss is one that must go to the next level. Hit ratio $h$ = hits / accesses, miss ratio $= 1 - h$. The hit time is the time to access the level on a hit and the miss penalty is the extra time to fetch the block from the next level.

Average memory access time (AMAT) for one cache in front of memory:

$\text{AMAT} = \text{hit time} + \text{miss rate} \times \text{miss penalty} .$

Two levels, two ways of counting. Let $t_1$ and $t_2$ be the access times of level 1 and level 2 and $h_1$ the hit ratio of level 1.

• Hierarchical (sequential) access: level 2 is accessed only after level 1 has missed, so a miss costs $t_1 + t_2$: $T = h_1 t_1 + (1 - h_1)(t_1 + t_2) = t_1 + (1 - h_1)\,t_2$.
• Simultaneous (parallel) access: both levels are started together and level 2's result is used on a miss: $T = h_1 t_1 + (1 - h_1)\,t_2$.

The first form equals AMAT with hit time $t_1$ and miss penalty $t_2$. A GATE question states which of the two to use; "simultaneous" and "hierarchical" are the usual words.

Several levels. With local miss rates $m_1$ (of L1 accesses) and $m_2$ (of L2 accesses):

$\text{AMAT} = t_{L1} + m_1\,(t_{L2} + m_2\,t_{\text{mem}}) .$

The global miss rate of L2 (misses per CPU access) is $m_1 m_2$.

Inclusion. In an inclusive hierarchy everything in a level is also in the level below it. The bottom level (disk, via virtual memory) holds everything.

What a hierarchy buys. The average access time approaches that of the top level when hit ratios are high, while the cost per bit approaches that of the bottom level.

How it works

The animation is a direct-mapped cache serving 14 reads. The cache counts cycles: 1 for a hit, 11 for a miss (hit time 1 plus miss penalty 10). The running "avg cycles per access" is the measured AMAT. At the end it is $84/14 = 6$, which equals $1 + 0.5 \times 10$: hit time plus miss rate (7 misses in 14) times the penalty.

Worked examples

#include <stdio.h>
 
/* average memory access time for one cache level and for a hierarchy */
static double amat(double hit_time, double miss_rate, double miss_penalty) { return hit_time + miss_rate * miss_penalty; }
 
int main(void) {
    /* the 14 accesses of the direct-mapped animation: 7 hits, 7 misses, hit time 1, miss penalty 10 */
    int hits = 7, accesses = 14;
    double m = 1.0 - (double)hits / accesses;
    printf("measured: %d cycles in total = %.2f per access; formula 1 + %.2f x 10 = %.2f\n", hits * 1 + (accesses - hits) * 11, (hits * 1.0 + (accesses - hits) * 11.0) / accesses, m, amat(1, m, 10));
    /* two levels, hit ratio h1 = 0.9, t1 = 2, t2 = 20 */
    double h1 = 0.9, t1 = 2, t2 = 20;
    printf("hierarchical access (level 2 only after a miss): %.1f\n", h1 * t1 + (1 - h1) * (t1 + t2));
    printf("simultaneous access (both started together):     %.1f\n", h1 * t1 + (1 - h1) * t2);
    printf("hit time + miss rate x miss penalty:             %.1f\n", amat(t1, 1 - h1, t2));
    /* three levels: L1 1 ns, 5%% local miss; L2 10 ns, 10%% local miss; memory 100 ns */
    double l1 = 1, l2 = 10, mem = 100, m1 = 0.05, m2 = 0.10;
    printf("three levels: AMAT = %.2f ns, global miss rate of L2 = %.3f\n", l1 + m1 * (l2 + m2 * mem), m1 * m2);
    /* what the hierarchy buys: without the caches every access would cost 100 ns */
    printf("speed-up over main memory alone: %.1f\n", mem / (l1 + m1 * (l2 + m2 * mem)));
    /* locality in the numbers: a miss rate of 1/16 (sequential access, 16 words per block) */
    printf("sequential access, 16 words per block: miss rate %.4f, AMAT %.2f cycles with a 100-cycle penalty\n", 1.0 / 16, amat(1, 1.0 / 16, 100));
    return 0;
}

measured: 84 cycles in total = 6.00 per access; formula 1 + 0.50 x 10 = 6.00
hierarchical access (level 2 only after a miss): 4.0
simultaneous access (both started together):     3.8
hit time + miss rate x miss penalty:             4.0
three levels: AMAT = 2.00 ns, global miss rate of L2 = 0.005
speed-up over main memory alone: 50.0
sequential access, 16 words per block: miss rate 0.0625, AMAT 7.25 cycles with a 100-cycle penalty

Cheat box

Traps and GATE patterns

Connections

The cache is the next topic, starting with how blocks are placed, then replacement and writes and multilevel performance. The main memory is built from chips by memory interfacing, and the disk level is in disk structure. The same formulas drive the performance equations.

PYQs

Self-check

Revision card

References