Memory Hierarchy: Cache & Main Memory

Memory technology forces an unavoidable trade: fast memory is expensive and therefore small, and large memory is cheap and therefore slow. No single technology gives capacity and speed together.

The hierarchy is the response. Several levels are stacked, each larger and slower than the one above, and the goal is to make the whole stack behave as though it had the capacity of the largest level and the speed of the smallest.

That goal is achievable only because programs do not access memory randomly. Locality of reference is what makes the entire hierarchy work, and without it a cache would be useless.

Temporal locality means a location accessed once is likely to be accessed again soon — loop variables, a stack top, a frequently called function.

Spatial locality means a location near one just accessed is likely to be accessed soon — array traversal, sequential instruction fetch, fields of a structure.

Every design decision in a cache is a bet on one of these two. Block size bets on spatial locality. Replacement policy bets on temporal locality. Associativity bets on how many competing addresses map to the same place.

So the way to reason about any cache question is to ask which locality the design is exploiting and where the address bits go.

1. The Address Split

A cache holds blocks copied from main memory. An address is divided into fields that answer three questions: which set, which block within it, and which byte within the block.

$\text{Address}=\underset{\text{which block}}{\underbrace{\text{tag}}}\mid \underset{\text{which set}}{\underbrace{\text{index}}}\mid \underset{\text{which byte}}{\underbrace{\text{offset}}}$

The offset field is determined by the block size: a block of $B$ bytes needs ${\log }_{2}B$ offset bits.

The index field is determined by the number of sets: $S$ sets need ${\log }_{2}S$ index bits.

The tag is whatever remains, and it must be stored alongside each cached block so that a hit can be confirmed.

Getting these three widths right is the foundation of every cache calculation, and the number of sets depends on the mapping scheme.

2. Mapping Schemes

Direct mapping is fastest to check — one comparison — and suffers most from conflict misses, because two heavily used addresses mapping to the same line evict each other repeatedly.

Fully associative mapping has no conflict misses at all, since a block may go anywhere, but checking requires comparing the tag against every line simultaneously. That comparator array is what limits it to small caches.

Set associative mapping is the compromise that real caches use. A block maps to one set and may occupy any line within it, so $k$ comparators suffice and conflicts require $k+1$ competing addresses rather than 2.

Note that direct mapping is 1-way set associative and fully associative mapping is $N$-way for a cache of $N$ lines, so the three are points on one scale rather than three separate ideas.

3. Replacement Policies

A replacement policy is needed only when a block may go in more than one place, so direct-mapped caches need none.

LRU is a bet on temporal locality and performs well because recent use predicts near-future use in real programs.

The optimal policy is not implementable, since it requires knowing the future, but it is used as a benchmark: no online policy can beat it, so it bounds how much a better policy could possibly gain.

FIFO suffers from Belady's anomaly, in which increasing the number of lines can increase the number of misses. LRU and optimal are stack algorithms and cannot exhibit it, which is a standard examination point.

4. Write Policies

Reads and writes are handled differently because a write creates an inconsistency between cache and memory.

Write-through updates both cache and memory on every write. Memory is always current, so a cache line may be discarded without further action, but write traffic to memory is heavy.

Write-back updates only the cache and marks the line dirty, writing it to memory only when it is evicted. Traffic falls dramatically, since a line written many times is transferred once, at the cost of a dirty bit per line and a more complex eviction path.

A write buffer sits between a write-through cache and memory to absorb bursts, letting the processor continue while the write drains.

On a write miss, two further choices exist.

Write-allocate fetches the block into the cache and then writes it, betting that more accesses to the block will follow. It pairs naturally with write-back.

No-write-allocate writes straight to memory without loading the block, which pairs naturally with write-through, since the cache would gain nothing from holding a block it is not going to read.

5. The Three Kinds of Miss

Classifying misses tells you which design change would help.

Compulsory misses occur on the first reference to a block, and no cache organisation avoids them. Larger blocks reduce them by prefetching neighbours, which is a bet on spatial locality.

Capacity misses occur because the cache cannot hold the program's working set. Only a larger cache helps.

Conflict misses occur because too many blocks map to the same set, even though the cache has room elsewhere. Higher associativity reduces them, and a fully associative cache has none by definition.

The classification is diagnostic. A cache with many conflict misses should be made more associative; one with many capacity misses should be made larger; one dominated by compulsory misses should use larger blocks or prefetching.

6. Performance

Average memory access time combines the hit case and the miss case:

$AMAT=T_{hit}+m\times T_{penalty}$

where $m$ is the miss rate and $T_{penalty}$ is the extra time a miss costs.

The miss penalty is usually so large that a small change in miss rate outweighs a large change in hit time. A hit time of 1 cycle with a 5 per cent miss rate and a 100-cycle penalty gives an AMAT of 6 cycles, so the misses account for five-sixths of the time.

For a multi-level hierarchy the formula nests: the miss penalty of level 1 is the average access time of level 2.

$AMAT=T_{L1}+m_{L1}(T_{L2}+m_{L2}\times T_{mem})$

Two miss rates must be distinguished. The local miss rate of a level is misses at that level divided by accesses to that level. The global miss rate is misses at that level divided by all processor accesses.

Since only level-1 misses reach level 2, the level-2 local miss rate is typically high while its global miss rate is low, and confusing the two is a standard error.

Block size has an optimum. Increasing it exploits spatial locality and reduces compulsory misses, but beyond some point it reduces the number of blocks, raising conflict and capacity misses, and it lengthens the miss penalty because more bytes must be transferred.

A related question is whether the cache is indexed by virtual or physical addresses, and it decides what happens on a context switch.

A virtually indexed cache can begin its lookup before address translation completes, which removes the translation from the critical path. The cost is that the same virtual address in two processes refers to different data, so the cache must either be flushed on a context switch or tagged with a process identifier.

A physically indexed cache has no such ambiguity but must wait for translation. The standard compromise indexes with the page-offset bits, which translation leaves unchanged, and compares physical tags — giving the speed of virtual indexing with the correctness of physical tagging.

7. Main Memory Organisation

Main memory is built from DRAM, which stores a bit as charge on a capacitor and therefore must be refreshed periodically. SRAM stores a bit in a latch, needs no refresh, and is faster and larger per bit — which is why caches are SRAM and main memory is DRAM.

DRAM is organised as a two-dimensional array addressed in two phases, sending a row address and then a column address on the same pins. This halves the pin count at the cost of an extra timing step, and it is why the row access strobe and column access strobe signals exist.

Once a row is open, successive accesses within it are fast, which is what burst transfers exploit — and it is another instance of spatial locality being converted into speed.

Interleaving increases bandwidth by spreading consecutive addresses across independent banks. With $n$ banks, $n$ accesses can proceed concurrently, so a sequential read stream achieves close to $n$ times the bandwidth of a single bank.

The addressing detail matters: low-order interleaving puts consecutive addresses in different banks, which suits sequential access, while high-order interleaving puts consecutive addresses in the same bank, which suits independent processes using separate regions.

8. Worked Examples

Example 1. A byte-addressable machine has a 32-bit address, a 64 KB cache with 32-byte blocks, 4-way set associative. Find the tag, index and offset widths.

Start with the offset, determined by the block size.

Block size is 32 bytes, so the offset is ${\log }_{2}32=5$ bits.

Next the number of lines: cache size divided by block size is $65536/32=2048$ lines.

Next the number of sets: lines divided by associativity is $2048/4=512$ sets.

So the index is ${\log }_{2}512=9$ bits.

The tag is whatever remains: $32-9-5=18$ bits.

Check the total: $18+9+5=32$, which confirms the arithmetic. Performing this check catches almost every slip in cache field questions.

Example 2. For the cache above, how much storage is used for tags and valid bits, as a fraction of the data storage?

Each line needs its 18-bit tag plus 1 valid bit, so 19 bits of overhead per line.

With 2048 lines, the overhead is $2048\times 19=38,912$ bits, which is 4,864 bytes.

The data storage is 64 KB, which is 65,536 bytes.

The overhead is $4864/65536\approx 7.4$ per cent.

A dirty bit would add one more bit per line if the cache were write-back, taking the overhead to 20 bits per line and about 7.8 per cent.

Note how the overhead scales: halving the block size doubles the number of lines and roughly doubles the overhead, which is one of the practical arguments against very small blocks.

Example 3. A processor has a 1-cycle hit time, a 4 per cent miss rate and a 120-cycle miss penalty. Compute the AMAT, and the AMAT if a second-level cache with a 12-cycle access time and a 25 per cent local miss rate is added.

Without the second level:

$AMAT=1+0.04\times 120=1+4.8=5.8\text{ cycles}$

With the second level, the level-1 miss penalty becomes the level-2 access time plus the level-2 miss rate times the memory time.

$AMAT=1+0.04\times (12+0.25\times 120)=1+0.04\times 42=1+1.68=2.68\text{ cycles}$

The second-level cache reduces the AMAT from 5.8 to 2.68 cycles, a speedup of about 2.16.

Note the two miss rates. The 25 per cent figure is the local miss rate of level 2, meaning a quarter of the accesses that reach it also miss. The global miss rate of level 2 is $0.04\times 0.25=1$ per cent, meaning only one per cent of all processor accesses reach main memory.

Using the global rate in place of the local one in the formula would understate the level-2 contribution by a factor of 25.

Example 4. A direct-mapped cache with 4 lines receives the block reference string 0, 4, 0, 4, 0, 4. How many misses occur, and what happens with 2-way set associativity?

With 4 lines and direct mapping, block $b$ maps to line $b\mathrm{mod}4$.

Block 0 maps to line 0, and block 4 also maps to line 0 since $4\mathrm{mod}4=0$.

The two blocks therefore evict each other on every access.

Reference 0: miss, load into line 0. Reference 4: miss, evict 0, load 4. Reference 0: miss, evict 4, load 0.

And so on. All 6 references miss.

Now make the cache 2-way set associative with the same total of 4 lines, giving 2 sets of 2 lines each. Block $b$ maps to set $b\mathrm{mod}2$.

Block 0 maps to set 0 and block 4 also maps to set 0, since $4\mathrm{mod}2=0$. But set 0 has two lines, so both blocks fit simultaneously.

Reference 0: miss, load. Reference 4: miss, load into the other line of the set. All four subsequent references hit.

Only 2 misses, both compulsory.

This is exactly the conflict-miss phenomenon, and it shows why associativity is the right fix for it: the cache had room all along, and only the mapping restriction prevented its use.

Example 5. Show that FIFO exhibits Belady's anomaly on the reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 with 3 and 4 frames.

With 3 frames under FIFO:

1 miss, 2 miss, 3 miss (frames 1,2,3). 4 miss evicting 1 (2,3,4). 1 miss evicting 2 (3,4,1). 2 miss evicting 3 (4,1,2). 5 miss evicting 4 (1,2,5). 1 hit. 2 hit. 3 miss evicting 1 (2,5,3). 4 miss evicting 2 (5,3,4). 5 hit.

Counting: 9 misses.

With 4 frames under FIFO:

1 miss, 2 miss, 3 miss, 4 miss (1,2,3,4). 1 hit. 2 hit. 5 miss evicting 1 (2,3,4,5). 1 miss evicting 2 (3,4,5,1). 2 miss evicting 3 (4,5,1,2). 3 miss evicting 4 (5,1,2,3). 4 miss evicting 5 (1,2,3,4). 5 miss evicting 1 (2,3,4,5).

Counting: 10 misses.

More frames produced more misses, which is Belady's anomaly. It arises because FIFO's eviction choice ignores usage, so a larger set of frames can change the eviction order in a way that discards a block just before it is needed.

LRU cannot do this because it is a stack algorithm: the contents with $n$ frames are always a subset of the contents with $n+1$ frames, so any hit with $n$ frames is also a hit with $n+1$.

Example 6. A main memory has 8 banks with low-order interleaving and a bank cycle time of 80 ns. What is the peak bandwidth for sequential 4-byte accesses, and what changes with high-order interleaving?

Low-order interleaving places consecutive addresses in different banks, so a sequential stream touches bank 0, then bank 1, and so on.

With 8 banks, 8 accesses can be in flight simultaneously, and once the pipeline is full one access completes every $80/8=10$ ns.

Peak bandwidth is 4 bytes per 10 ns, which is 400 MB per second — eight times the 50 MB per second a single bank would deliver.

With high-order interleaving, consecutive addresses fall in the same bank, since the bank is selected by the high-order address bits.

A sequential stream then hits one bank repeatedly and achieves only single-bank bandwidth, 50 MB per second, with the other seven banks idle.

High-order interleaving is not simply worse; it suits a different pattern. Several independent processes working in separate memory regions land in different banks and proceed concurrently, and a failed bank takes out one contiguous region rather than every eighth word of the whole address space.

Summary

The hierarchy exists because fast memory is small and large memory is slow, and it works only because programs exhibit temporal and spatial locality.

An address splits into tag, index and offset. The offset comes from block size, the index from the number of sets, and the tag is the remainder — always check that the three sum to the address width.

Direct mapping is one comparison and many conflict misses; fully associative has no conflicts but needs a comparator per line; set associative is the practical compromise, and the three are points on one scale.

Replacement policies matter only when a block may go in more than one place. LRU bets on temporal locality, optimal bounds what any policy could achieve, and FIFO can exhibit Belady's anomaly while stack algorithms cannot.

Write-through keeps memory current at the cost of traffic; write-back marks lines dirty and writes once on eviction. Write-allocate pairs with write-back, no-write-allocate with write-through.

Misses are compulsory, capacity or conflict, and the classification tells you whether to enlarge blocks, enlarge the cache or raise associativity.

AMAT is hit time plus miss rate times penalty, and it nests for multiple levels. Local and global miss rates differ, and only level-1 misses reach level 2.

DRAM needs refresh and is addressed in row and column phases; SRAM does not and is used for caches. Low-order interleaving accelerates sequential access, while high-order interleaving suits independent regions.