Chapter 25 of 39

Cache Memory

A chef in a busy restaurant does not walk to the storeroom every time a dish needs salt, onions or oil. The things used again and again are kept on the counter within arm's reach. The storeroom has everything, but the counter has what is needed right now, and most of the time that is enough.

A CPU has the same problem. Main memory (DRAM) holds everything, but each trip to it takes around 100 ns, which is hundreds of instruction slots for a modern core. So the processor keeps a small, very fast memory right next to it, filled with the data and instructions it has been using recently. That memory is the cache.

A cache is a small, fast memory (built from SRAM) placed between the CPU and main memory. It holds copies of recently used blocks of main memory, so that most memory accesses can be served at cache speed instead of main-memory speed. The cache is managed entirely by hardware and is invisible to the program.

In Memory Hierarchy we saw why such levels work (locality of reference) and how to compute the average access time of two levels. In this chapter we look at the cache itself: what it stores, how it is organized into lines, what exactly happens on a hit and on a miss, how an address is viewed as block number plus offset, and why misses happen. The question of where in the cache a block may be placed is big enough to have its own chapter, Cache Mapping Techniques.


Where the Cache Sits

   +-------+    word     +---------+    block     +--------------+
   |  CPU  | <---------> |  Cache  | <----------> | Main memory  |
   +-------+  (4-8 B,    |  (SRAM) |  (e.g. 64 B, |    (DRAM)    |
              ~1 ns)     +---------+   ~100 ns)   +--------------+

Two important facts are in this picture:

  • The CPU and cache exchange single words (what a load or store instruction asks for).

  • The cache and main memory exchange whole blocks (several consecutive words). When a word is missing, the cache fetches the entire block that contains it, betting on spatial locality: the neighbouring words will probably be needed soon.

The program never mentions the cache. A load instruction just gives an address; the cache hardware decides whether it can answer, or must fetch from memory first. That is why caches are called transparent to software (though, as we will see, software that respects locality runs much faster).


Key Terms

TermMeaning
BlockA fixed-size group of consecutive bytes of main memory, the unit of transfer between memory and cache (commonly 64 bytes today).
Line (cache line)A slot in the cache that can hold one block, plus its bookkeeping bits. Line size = block size. ("Block" and "line" are often used loosely for each other.)
TagPart of the address stored with each line, identifying which memory block the line currently holds.
Valid bitSays whether the line holds real data. At power-on all valid bits are 0, so the empty cache cannot produce false hits.
Dirty bit(In write-back caches) says the line was modified and must be written to memory before it is replaced.
HitThe requested word is in the cache.
MissIt is not; the block must be fetched from the next level.
Hit ratio (h)Hits / total accesses. Miss ratio = 1 − h.
Hit timeTime to access the cache and decide hit or miss.
Miss penaltyExtra time needed on a miss to bring the block from the next level.

So a cache line looks like this:

+-------+-------+-----------+----------------------------------------+
| Valid | Dirty |    Tag    |          Data block (e.g. 64 bytes)    |
+-------+-------+-----------+----------------------------------------+

The valid bit, dirty bit and tag are overhead: they take storage but hold no program data. We will count this overhead in the mapping chapter.


Main Memory as Blocks: Block Number and Offset

Since memory and cache exchange whole blocks, it is useful to view main memory as a sequence of numbered blocks. With block size B bytes (a power of 2), any byte address splits into two parts:

          +-------------------------+-------------------+
address = |      block number       |   block offset    |
          +-------------------------+-------------------+
                                     <-- log2(B) bits -->

block number = address / B      (integer division)
block offset = address mod B    (which byte inside the block)

Worked Example 1

A byte-addressable main memory of 64 KB has a 2 KB cache with 32-byte blocks. (a) How many blocks are in main memory? (b) How many lines are in the cache? (c) Split the address 0x1234.

(a) Main memory blocks = 64 KB / 32 B = 2048 blocks
(b) Cache lines        = 2 KB / 32 B  = 64 lines
(c) Address bits = log2(64 K) = 16; offset bits = log2(32) = 5; block number = 11 bits
    0x1234 = 0001 0010 0011 0100
           = 00010010001 | 10100
    block number = 0b00010010001 = 145
    offset       = 0b10100       = 20

So byte 0x1234 is byte 20 of memory block 145. Check: 145 × 32 + 20 = 4660 = 0x1234.

Notice that main memory has 2048 blocks but the cache has room for only 64 of them at a time. Deciding which of the 64 lines memory block 145 may go into, and how the hardware then finds it, is the job of the mapping function: direct, fully associative or set-associative, covered next in Cache Mapping Techniques. In each of those schemes, the block number is further divided into a tag and (usually) a line or set index.


How a Cache Read Works

        CPU issues address A
                 |
                 v
      Use A to find the candidate line(s) in the cache
                 |
                 v
      Valid bit = 1 AND stored tag == tag of A ?
            /                        \
          yes                         no
          /                             \
     CACHE HIT                       CACHE MISS
  Return the word at              1. Choose a line for the block
  offset (A mod B).                  (evicting one if needed; if it is
  Done in hit time.                  dirty, write it back first)
                                  2. Read the whole block containing A
                                     from main memory
                                  3. Store it, set tag, valid = 1
                                  4. Return the requested word to the CPU

Many processors forward the requested word to the CPU as soon as it arrives, even before the rest of the block is loaded (called early restart), and some ask memory for the needed word first (critical word first). These tricks shorten the effective miss penalty.

Which line to evict on a miss (when there is a choice) is decided by a replacement policy such as LRU or FIFO, and what to do on a write (update memory immediately or later) is decided by a write policy. Both are covered in Cache Replacement & Write Policies. In brief:

  • Write-through: every write updates both the cache and main memory.

  • Write-back: a write updates only the cache line and sets its dirty bit; memory is updated when the line is evicted.


Hit Ratio in Action: Walking Through an Array

Let's count hits and misses exactly. A program sums an array of 1024 ints (4 bytes each, 4 KB in total) starting at a block-aligned address. The cache has 64-byte blocks and is initially empty.

for (int i = 0; i < 1024; i++)
    sum += a[i];

One block holds 64 / 4 = 16 ints. Accessing a[0] misses and brings in a[0]–a[15]; the next 15 accesses hit. Then a[16] misses, and so on.

Misses    = 4096 bytes / 64 bytes per block = 64
Hits      = 1024 - 64 = 960
Hit ratio = 960 / 1024 = 0.9375  (93.75 %)

We verified these counts with a small cache simulator. Three variations show how much the access pattern matters:

Access pattern (cache empty at start)HitsMissesHit ratio
Sum 1024 ints once, stride 19606493.75%
Touch 1024 ints with stride 16 (one int per block, 64 KB span)010240%
Sum the 4 KB array twice, cache of 8 KB19846496.9%
Sum a 16 KB array twice, cache of 8 KB (fully associative, LRU)768051293.75%
  • Stride 1 uses spatial locality: 15 of every 16 accesses hit.

  • Stride 16 uses only one int from each block fetched, so every access misses.

  • When the array fits in the cache, the second pass hits every time: temporal locality pays off.

  • When the array is twice the cache size, the second pass gets no benefit: by the time we return to the start, those blocks have been evicted to make room for later ones. The cache is simply too small for this working set.


Seeing the Caches on a Real Machine

The C program below builds a random chain of pointers inside an array and follows it. Each load depends on the previous one, so the time per step is the true latency of wherever the data lives. As the array (the "working set") grows past each cache's size, the time jumps.

#define _POSIX_C_SOURCE 199309L
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* Follow a random chain of pointers through an array of the given size.
   Each load depends on the previous one, so we measure pure latency. */
static double ns_per_access(size_t bytes)
{
    size_t n = bytes / sizeof(void *);
    void **arr = malloc(n * sizeof(void *));
    size_t *perm = malloc(n * sizeof(size_t));

    for (size_t i = 0; i < n; i++) perm[i] = i;
    for (size_t i = n - 1; i > 0; i--) {          /* random shuffle */
        size_t j = (size_t)rand() % (i + 1);
        size_t t = perm[i]; perm[i] = perm[j]; perm[j] = t;
    }
    for (size_t i = 0; i < n; i++)                /* one big cycle  */
        arr[perm[i]] = &arr[perm[(i + 1) % n]];

    const long steps = 20000000;
    void **p = &arr[perm[0]];
    struct timespec a, b;
    clock_gettime(CLOCK_MONOTONIC, &a);
    for (long s = 0; s < steps; s++)
        p = (void **)*p;
    clock_gettime(CLOCK_MONOTONIC, &b);

    double ns = (b.tv_sec - a.tv_sec) * 1e9 + (b.tv_nsec - a.tv_nsec);
    if (p == NULL) printf("impossible\n");       /* keep p alive   */
    free(arr); free(perm);
    return ns / steps;
}

int main(void)
{
    size_t sizes_kb[] = { 16, 32, 128, 512, 1024, 4096, 8192, 32768, 131072 };
    for (int i = 0; i < 9; i++)
        printf("working set %7zu KB : %6.1f ns per access\n",
               sizes_kb[i], ns_per_access(sizes_kb[i] * 1024));
    return 0;
}

Output on an Intel Core i5-12400F (48 KB L1 data cache and 1.25 MB L2 per core, 18 MB shared L3), compiled with gcc -std=c17 -Wall -O2:

working set      16 KB :    1.2 ns per access
working set      32 KB :    1.2 ns per access
working set     128 KB :    2.7 ns per access
working set     512 KB :    3.8 ns per access
working set    1024 KB :    5.4 ns per access
working set    4096 KB :   14.9 ns per access
working set    8192 KB :   21.6 ns per access
working set   32768 KB :   76.4 ns per access
working set  131072 KB :   98.2 ns per access

Read it from top to bottom:

  • Up to 32 KB, everything fits in L1: about 1.2 ns (around 5 cycles).

  • 128 KB to 1 MB fits in L2: a few ns.

  • 4–8 MB lives in L3: roughly 15–40 ns (repeated runs vary noticeably here; at these sizes some time also goes into address-translation misses).

  • 32 MB and beyond is larger than L3, so most steps go to DRAM: about 100 ns, around 80 times slower than L1.

This is the memory hierarchy measured directly. The same instruction, p = *p, can take 1 ns or 100 ns depending only on where its data happens to be.


Average Access Time and Speedup

With hit ratio h, cache access time Tc and main-memory access time Tm, the formulas from Memory Hierarchy apply directly:

Hierarchical (check cache first):  T_avg = T_c + (1 - h) x T_m
Simultaneous (both at once):       T_avg = h x T_c + (1 - h) x T_m

Worked Example 2

Cache access time 5 ns, main memory 100 ns, hit ratio 0.95, hierarchical access. Find the average access time and the speedup over a system with no cache.

T_avg   = 5 + 0.05 x 100 = 10 ns
Speedup = 100 / 10       = 10

The cache makes memory look 10 times faster, even though it misses 1 time in 20.

Worked Example 3: From Counts to Time

A program makes 2000 memory references; 1900 hit in the cache. Cache access takes 2 ns. On a miss, the block is first brought into the cache (taking 50 ns) and then read from the cache. Find the average access time.

h = 1900 / 2000 = 0.95
Hit:  2 ns
Miss: 50 ns (bring block) + 2 ns (read from cache) = 52 ns

T_avg = 0.95 x 2 + 0.05 x 52 = 1.9 + 2.6 = 4.5 ns

Here we wrote the miss time directly from the description instead of plugging into a memorized formula. That habit avoids most mistakes; always ask "what exactly happens on a hit, and on a miss?" A full treatment of miss penalty, CPI with stalls and multi-level caches is in Cache Performance & Multi-level Caches.


Why Misses Happen: The Three Cs

Every cache miss falls into one of three categories (here is a first look; Cache Performance & Multi-level Caches analyses them in more depth):

TypeCauseReduced by
Compulsory (cold-start)The very first access to a block; it has never been in the cache.Larger blocks (each miss brings more useful data), prefetching.
CapacityThe working set is larger than the cache, so blocks are evicted and later needed again.A larger cache, better program locality.
Conflict (collision)Blocks are evicted because too many map to the same line or set, even though the cache as a whole could have held them. Precisely: misses that would not occur in a fully associative cache of the same size.Higher associativity (see the mapping chapter).

In the array table above: the 64 misses of the first pass are compulsory; the misses in the second pass over the 16 KB array are capacity misses. A fully associative cache has no conflict misses by definition.

(In multiprocessors a fourth C, coherence misses, appears; see Multicore Processors & Cache Coherence.)


Design Choices for a Cache

Cache Size

Bigger caches have fewer capacity misses but are slower (longer wires, bigger decoders) and costlier. This is why there are several levels: a small, very fast L1 backed by larger, slower L2 and L3.

Block Size

Larger blocks exploit spatial locality better, so the miss rate first drops as block size grows. But beyond a point:

  • For a fixed cache size, larger blocks mean fewer lines, so useful blocks get evicted sooner and the miss rate rises again.

  • Each miss transfers more bytes, so the miss penalty grows.

A moderate block size (32–128 bytes, commonly 64) balances the two.

Unified vs Split Caches

Unified cacheSplit cache (Harvard-style)
One cache holds both instructions and dataSeparate instruction cache (I-cache) and data cache (D-cache)
Space is shared automatically according to needEach has a fixed size
Instruction fetch and data access compete for one portAn instruction fetch and a data access can happen in the same cycle, which pipelines need
Typical for L2 and L3Typical for L1 (e.g. 32 KB L1i + 48 KB L1d on the machine above)

This is the "modified Harvard" design from Von Neumann vs Harvard Architecture: separate paths near the CPU, one unified memory behind them.

The Other Design Questions

  • Where can a block be placed? → mapping (Cache Mapping Techniques)

  • Which block is replaced on a miss? → replacement policy (Cache Replacement & Write Policies)

  • What happens on a write? → write policy (same chapter)

  • How many levels, and how fast? → Cache Performance & Multi-level Caches


Common Mistakes

  • Thinking the cache transfers single words from memory. Memory to cache is always a whole block; only cache to CPU is a word.

  • Forgetting the valid bit. Without it, the garbage tags in an empty cache could produce false hits.

  • Calling the cache "secondary memory" or "managed by the OS". It is primary memory, managed entirely by hardware.

  • Counting the offset in words when memory is byte-addressable. Offset bits = log2(block size in addressable units).

  • Assuming bigger blocks always help. Past a point they increase both miss rate (fewer lines) and miss penalty.

  • Plugging numbers into a formula without reading the miss scenario. Work out the time for a hit and for a miss from the question's description, then take the weighted average.

  • Labelling every miss a conflict miss. First-time misses are compulsory; misses because the working set is too big are capacity misses.


GATE / Interview Questions

Why does a cache improve performance even though it is much smaller than main memory?

Because of locality of reference: programs reuse recently accessed data (temporal locality) and access nearby data (spatial locality). The cache keeps recently used blocks, so most accesses hit at SRAM speed, and the average access time approaches the cache's access time.

A byte-addressable memory has 1 MB of memory and a cache with 64-byte blocks. How many bits are in the block offset, and how many in the block number?

Address = log2(1 M) = 20 bits. Offset = log2(64) = 6 bits. Block number = 20 − 6 = 14 bits (214 = 16384 memory blocks).

An array of 512 doubles (8 bytes each) is read once sequentially through an empty cache with 32-byte blocks. Assuming the array starts on a block boundary, what is the hit ratio?

Each block holds 32 / 8 = 4 doubles, so there is 1 miss per 4 accesses: 128 misses, 384 hits. Hit ratio = 384 / 512 = 0.75.

Cache access 10 ns, memory 80 ns, hit ratio 0.9, hierarchical access. What is the average access time?

T = 10 + 0.1 × 80 = 18 ns.

What are the three Cs of cache misses?

Compulsory (first access to a block), capacity (the cache cannot hold the whole working set), and conflict (too many blocks compete for the same line or set even though space exists elsewhere).

What is the purpose of the valid bit and the dirty bit?

The valid bit marks whether a line holds real data, preventing false hits from an empty or invalidated line. The dirty bit (write-back caches) marks a line modified since it was loaded, so it must be written to memory before being replaced.

Why are L1 caches usually split into instruction and data caches?

So that the pipeline can fetch an instruction and access data in the same cycle without a structural conflict, and each cache can be tuned for its access pattern. Lower levels are unified to share capacity flexibly.

Why doesn't increasing block size keep reducing the miss rate?

For a fixed cache size, larger blocks mean fewer lines, so blocks are replaced sooner (more capacity/conflict misses), and much of a large block may go unused. Larger blocks also raise the miss penalty.


Summary

  • A cache is a small, fast SRAM memory between the CPU and main memory, holding copies of recently used blocks. It is managed by hardware and is transparent to programs.

  • CPU ↔ cache transfers words; cache ↔ memory transfers blocks. Each cache line holds a block plus a tag, a valid bit and (for write-back) a dirty bit.

  • A byte address = block number (address / B) + offset (address mod B). Example: 0x1234 with 32-byte blocks is block 145, offset 20.

  • On a hit, the word is returned at cache speed. On a miss, the whole block is fetched (possibly evicting and writing back another) and then the word is supplied.

  • Sequentially summing 1024 ints with 64-byte blocks gives 64 misses and a 93.75% hit ratio; a stride of one block gives 0%.

  • Measured on a real PC: about 1.2 ns in L1, a few ns in L2, roughly 15–40 ns in L3 and about 100 ns in DRAM.

  • Average time: Tc + (1 − h)Tm (hierarchical); e.g. 5 ns, 100 ns, h = 0.95 gives 10 ns, a speedup of 10.

  • Misses are compulsory, capacity or conflict. Design choices: size, block size, unified vs split, plus mapping, replacement and write policies covered in the next chapters.

Next, in Cache Mapping Techniques, we answer the central question this chapter left open: given a memory block number, which cache line can it go to, and how does the hardware find it again using the tag?