Cache Memory

Why caches exist

A modern processor core can finish several instructions every nanosecond. Main memory (DRAM) needs tens of nanoseconds to return a single value. If every load had to wait for DRAM, the core would spend almost all of its time idle. A cache is a small, fast memory placed between the core and main memory that keeps copies of recently used data, so most loads and stores are served in a few cycles instead of a few hundred.

Caches are the single most important reason that real programs run fast, and they are the topic in computer architecture where interviewers most often ask for numbers. Expect to be asked to split an address into tag, index and offset bits, to say whether an access sequence hits or misses, to compare direct-mapped and set-associative caches, to explain write-back versus write-through, and to compute average memory access time (AMAT). Software interviews also probe the practical side: why iterating a 2D array row by row is faster than column by column, and what "cache-friendly" code means.

This lesson builds all of that from the ground up. Every number in the worked examples has been checked with a short Python script.

The memory hierarchy

There is no memory technology that is simultaneously fast, large and cheap. Fast memory (SRAM, the kind used for registers and caches) costs a lot per byte and uses a lot of chip area. Large memory (DRAM, flash, disks) is cheap per byte but slow. Computers therefore stack several levels, each one larger and slower than the one above it.

              fastest, smallest, most expensive per byte
                   +------------------+
                   |    Registers     |  under 1 ns
                   +------------------+
                   |     L1 cache     |  about 1 ns
                 +----------------------+
                 |       L2 cache       |  about 3-5 ns
               +--------------------------+
               |    L3 (last-level) cache |  about 10-20 ns
             +------------------------------+
             |       Main memory (DRAM)     |  about 50-100 ns
           +----------------------------------+
           |      SSD (NVMe flash)            |  about 10-100 us
         +--------------------------------------+
         |      Hard disk                       |  about 5-10 ms
         +--------------------------------------+
              slowest, largest, cheapest per byte

These latencies are approximate orders of magnitude, not specifications. They vary by processor generation, clock speed and vendor. What matters is the ratio: each level down is roughly 3 to 10 times slower than the level above it, and the jump from cache to DRAM is the painful one.

Locality: why a small cache works

A cache holds a tiny fraction of memory, yet it typically serves well over 90 percent of accesses. That works only because real programs do not access memory randomly. They show locality of reference, which comes in two kinds.

Temporal locality

Temporal locality means that if you access a location now, you are likely to access the same location again soon. Loop counters, accumulators, the top of the stack and frequently called functions all show it.

int sum = 0;
for (int i = 0; i < n; i++) {
    sum += a[i];      /* sum and i are touched every iteration */
}

The variables sum and i are reused on every iteration (they usually live in registers, which is the extreme case of temporal locality). The machine instructions of the loop body are fetched again on every iteration too, so the instruction cache keeps them.

Spatial locality

Spatial locality means that if you access a location, you are likely to access nearby locations soon. Walking through an array, reading a struct's fields one after another, and executing straight-line code all show it.

In the loop above, a[0], a[1], a[2] sit next to each other in memory. Caches exploit this by never fetching a single byte: they fetch a whole block (typically 64 bytes on x86 and many ARM cores, 128 bytes on Apple M-series cores). One miss on a[0] brings in a[0] to a[15] for 4-byte integers in a 64-byte block, so the next 15 accesses are hits.

A counter-example

/* Linked list: each node may live anywhere in memory */
struct node { int value; struct node *next; };

int sum_list(struct node *p) {
    int sum = 0;
    while (p) { sum += p->value; p = p->next; }
    return sum;
}

If the nodes were allocated at scattered addresses, each p->next jumps to an unrelated block. There is little spatial locality, and the hardware cannot easily guess the next address because it depends on the data just loaded. This is the main reason an array often beats a linked list in practice even when both are O(n) to traverse.

Cache terminology

Before the mechanics, here are the terms you must use precisely.

• Block (also called a line): the unit of data moved between a cache and the next level, for example 64 bytes. A cache is organised as a set of line slots, each holding one block.
• Hit: the requested data is present in the cache.
• Miss: the data is not present; the cache must fetch the whole block from the next level.
• Hit ratio (hit rate): hits ÷ total accesses. Miss ratio = 1 − hit ratio.
• Hit time: time to access the cache when the data is there, including the time to determine that it is a hit.
• Miss penalty: extra time to bring the block in from the next level and deliver the data.
• Valid bit: one bit per line that says whether the line holds real data. At power-on every line is invalid.
• Tag: the high-order address bits stored alongside each line, used to tell which of the many possible blocks is currently in that slot.
• Dirty bit: in a write-back cache, says the line has been modified and must be written to memory before it is evicted.
• Eviction (replacement): removing a line to make room for a new one.

One cache line (64-byte block):

+---+---+----------+---------------------------------------+
| V | D |   Tag    |          Data: 64 bytes               |
+---+---+----------+---------------------------------------+
 valid dirty  which block       the cached copy

The tag, valid and dirty bits are overhead. The "64 KB" in "a 64 KB cache" counts only the data bytes.

Mapping: where can a block go?

When a block comes from memory, which slot does it go into? There are three answers, and they trade hardware cost against miss rate.

How an address is split

Every mapping scheme interprets the memory address as three fields:

 most significant bits                     least significant bits
+-------------------+----------------+------------------+
|        Tag        |     Index      |  Block offset    |
+-------------------+----------------+------------------+
  which block in      which set to     which byte inside
  this set (compare)  look in          the block

The formulas, for an address of A bits:

• offset bits = log2(block size in bytes)
• number of lines = cache size ÷ block size
• number of sets = number of lines ÷ associativity (ways)
• index bits = log2(number of sets)
• tag bits = A − index bits − offset bits

Associativity (number of ways) is how many lines a block may choose between. A set is a group of that many lines.

Direct-mapped cache

In a direct-mapped cache each block can live in exactly one line. Associativity is 1, so the number of sets equals the number of lines. The index picks the line; the stored tag is compared with the address tag; if they match and the valid bit is set, it is a hit.

Address:  | tag | index | offset |
                    |
                    v
   line 0  [V|tag|data....]
   line 1  [V|tag|data....]
   line k  [V|tag|data....] --> compare stored tag with address tag
   ...                          match and V=1 -> hit

Direct-mapped caches are simple and fast: one comparator, no choice to make on replacement. Their weakness is conflict misses: two hot blocks that share an index keep evicting each other even when the rest of the cache is empty.

Fully associative cache

In a fully associative cache a block may go into any line. There is one set containing all lines, so there are zero index bits, and the tag is everything except the offset. A lookup must compare the address tag with every line's tag in parallel, which needs one comparator per line. That is expensive in area and power, so fully associative designs are used for small structures such as TLBs (covered in the next lesson), not for large data caches.

Set-associative cache

An N-way set-associative cache is the compromise every real L1, L2 and L3 uses. Lines are grouped into sets of N. The index chooses a set; the block may sit in any of the N ways of that set; N comparators check the N tags in parallel.

4-way set-associative, index selects one set:

          way 0        way 1        way 2        way 3
set 0  [V|tag|data] [V|tag|data] [V|tag|data] [V|tag|data]
set 1  [V|tag|data] [V|tag|data] [V|tag|data] [V|tag|data]
set k  [V|tag|data] [V|tag|data] [V|tag|data] [V|tag|data]
          |            |            |            |
          +------ 4 tag comparisons in parallel -+--> hit / way

Direct-mapped is simply 1-way set-associative, and fully associative is "number of lines"-way set-associative with one set. Seeing the three as points on one scale is the cleanest way to explain them in an interview.

Worked example: address breakdown for six configurations

Configuration 1. 32-bit addresses, 64 KB direct-mapped cache, 64-byte blocks.

1. Offset bits = log2(64) = 6.
2. Lines = 65,536 ÷ 64 = 1,024. Direct-mapped, so sets = 1,024.
3. Index bits = log2(1,024) = 10.
4. Tag bits = 32 − 10 − 6 = 16.

| tag: 16 | index: 10 | offset: 6 |   = 32 bits

Configuration 2. Same cache but 4-way set-associative.

1. Offset bits = 6, lines = 1,024 (unchanged).
2. Sets = 1,024 ÷ 4 = 256, so index bits = 8.
3. Tag bits = 32 − 8 − 6 = 18.

Making the cache more associative moves bits from the index to the tag: each doubling of associativity removes one index bit and adds one tag bit.

Configuration 3. Same cache, fully associative.

1. One set, so index bits = 0.
2. Tag bits = 32 − 0 − 6 = 26.

Configuration 4. A typical modern L1 data cache: 48-bit physical addresses, 32 KB, 8-way, 64-byte blocks.

1. Offset bits = 6.
2. Lines = 32,768 ÷ 64 = 512. Sets = 512 ÷ 8 = 64. Index bits = 6.
3. Tag bits = 48 − 6 − 6 = 36.

Notice that index + offset = 12 bits. That equals the offset inside a 4 KB page, which is a deliberate design choice you will meet again with VIPT caches in the next lesson.

Configuration 5. 32-bit addresses, 1 MB, 16-way, 128-byte blocks (a plausible L2).

1. Offset bits = log2(128) = 7.
2. Lines = 1,048,576 ÷ 128 = 8,192. Sets = 8,192 ÷ 16 = 512. Index bits = 9.
3. Tag bits = 32 − 9 − 7 = 16.

Configuration 6. 32-bit addresses, 8 KB, 2-way, 32-byte blocks.

1. Offset bits = 5.
2. Lines = 8,192 ÷ 32 = 256. Sets = 128. Index bits = 7.
3. Tag bits = 32 − 7 − 5 = 20.

Worked example: decoding one address

Take the address 0x1234ABCD. In binary it is:

0x1234ABCD = 0001 0010 0011 0100 1010 1011 1100 1101

In configuration 1 (tag 16, index 10, offset 6):

• Offset = low 6 bits = 001101 = 13.
• Index = next 10 bits. Shifting right by 6 and keeping 10 bits gives 0x2AF = 687.
• Tag = top 16 bits = 0x1234.

So the byte is at offset 13 of line 687, and line 687 must hold tag 0x1234 for a hit.

In configuration 2 (tag 18, index 8, offset 6): offset 13, index 0xAF = 175, tag 0x48D2. The index lost its top two bits to the tag: 0x1234 shifted left by 2 plus those two bits (10 binary) gives 0x48D2.

In configuration 3 (fully associative): offset 13, no index, tag 0x48D2AF.

In configuration 6 (tag 20, index 7, offset 5): offset = low 5 bits = 13, index = 0x5E = 94, tag = 0x1234A.

Config 1:  0x1234      | 1010101111 (687) | 001101 (13)
Config 2:  0x48D2      | 10101111 (175)   | 001101 (13)
Config 6:  0x1234A     | 1011110 (94)     | 01101 (13)

Worked example: tracing hits and misses

A tiny direct-mapped cache: 16-bit addresses, 256 bytes total, 16-byte blocks. Offset = 4 bits, lines = 16, index = 4 bits, tag = 8 bits. In hexadecimal that is convenient: the last hex digit is the offset, the second-to-last is the index, and the first two are the tag.

One hit in seven accesses. Notice that 0x1234 and 0x2234 fight over line 3 although 13 other lines are empty. That is exactly the conflict miss that associativity removes.

Worked example: same trace, three organisations

Now think in block numbers rather than byte addresses. A cache has 4 lines and the processor touches blocks 3, 11, 3, 19, 11, 3, 7. The set for a block is (block number) mod (number of sets). LRU replacement where there is a choice.

Direct-mapped (4 sets): 3, 11, 19 and 7 all give remainder 3, so every block maps to set 3.

7 misses out of 7.

2-way set-associative (2 sets): all blocks are odd, so all map to set 1, which has two ways.

6 misses.

Fully associative (1 set, 4 ways): 3 miss, 11 miss, 3 hit, 19 miss, 11 hit, 3 hit, 7 miss. 4 misses, and all four are first-time accesses that no cache could avoid.

The same 4-line cache gives 7, 6 or 4 misses depending only on where blocks are allowed to go.

Replacement policies

When a set is full and a new block arrives, the cache must pick a victim line to evict. Direct-mapped caches have no choice. For the others:

• LRU (least recently used): evict the line that has gone longest without being accessed. It exploits temporal locality well. Exact LRU for N ways must track an ordering of N items, which costs about log2(N!) bits per set and update logic on every access. That is cheap for 2 ways (1 bit) and costly for 16.
• FIFO (first in, first out): evict the line that was filled earliest, regardless of how often it has been used since. Simple (a round-robin pointer per set) but can evict a hot line.
• Random: pick any way at random (in hardware, a cheap pseudo-random counter). Surprisingly competitive for large, highly associative caches, and it has no pathological worst case for looping patterns.
• Pseudo-LRU (PLRU): approximates LRU cheaply. The common tree-PLRU keeps N − 1 bits per set arranged as a binary tree. Each bit points towards the half that was used less recently. On an access, the bits on the path to the used way are flipped to point away from it; on a miss, you follow the bits to find the victim.

Tree-PLRU for 4 ways (3 bits per set)

               [b0]            b0 = 0: victim is in left half
              /    \           b0 = 1: victim is in right half
          [b1]      [b2]
          /  \      /  \
        w0   w1   w2   w3

Access w1: set b0 = 1 (point right), b1 = 0 (point to w0)
Victim search: follow b0 -> right, then b2 -> w2 or w3

Modern last-level caches often use adaptive policies (for example, variants that insert new lines at low priority so a one-off scan cannot flush the whole cache), but the four above are what interviews cover.

Worked example: LRU versus FIFO

A fully associative cache with 4 lines receives blocks 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

• LRU: misses on 1, 2, 3, 4 (compulsory), hits on 1, 2; 5 evicts 3 (least recently used); hits on 1, 2; 3 evicts 4; 4 evicts 5; 5 evicts 1. 8 misses.
• FIFO: misses on 1, 2, 3, 4, hits on 1, 2; 5 evicts 1 (oldest fill); then 1 misses (evicts 2), 2 misses (evicts 3), 3 misses, 4 misses, 5 misses. 10 misses.

FIFO ignored that blocks 1 and 2 were just reused, and paid for it.

Write policies

Reads are simple: on a hit, return the data. Writes force two independent decisions.

On a write hit: write-through or write-back?

• Write-through: update the cache line and the next level on every write. Memory is always up to date, which simplifies coherence and recovery, but every store generates traffic. A write buffer (a small queue of pending writes) lets the processor continue without waiting for each write to finish; if stores arrive faster than the buffer drains, the processor stalls.
• Write-back: update only the cache line and set its dirty bit. The block is written to the next level only when it is evicted, and only if dirty. Repeated writes to the same line cost one memory write in total. Almost all modern L1, L2 and L3 data caches are write-back.

On a write miss: allocate or not?

• Write-allocate (fetch on write): bring the block into the cache, then perform the write as a hit. Good when the program will soon read or write nearby data.
• No-write-allocate (write-around): send the write straight to the next level and leave the cache unchanged. Good for data that is written once and not read soon.

The natural pairings are write-back + write-allocate and write-through + no-write-allocate.

Worked example: counting memory writes

A loop stores to the same 4-byte variable 1,000 times while its block stays in the cache, and the block is evicted once at the end.

• Write-through: 1,000 writes go to the next level.
• Write-back: 0 writes during the loop, 1 block write at eviction.

That ratio is why write-back is the default for anything close to the core.

Average memory access time (AMAT)

The figure of merit for a cache is not the hit rate alone but the average memory access time:

AMAT = hit time + miss rate × miss penalty

A higher hit rate is useless if the cache is so large that its hit time doubles. AMAT captures the trade-off.

Worked example: single level

L1 hit time 4 cycles, L1 miss rate 5 percent, and a miss goes straight to DRAM costing 200 cycles.

AMAT = 4 + 0.05 × 200 = 4 + 10 = 14 cycles

Worked example: adding an L2

Same L1, but now misses go to an L2 with a 12-cycle hit time and a local miss rate of 20 percent. L2 misses cost 200 cycles to reach DRAM.

The local miss rate of a level is misses at that level ÷ accesses that reach that level. The global miss rate is misses at that level ÷ all accesses made by the processor.

1. L1 miss penalty = L2 hit time + L2 local miss rate × L2 miss penalty = 12 + 0.2 × 200 = 52 cycles.
2. AMAT = 4 + 0.05 × 52 = 4 + 2.6 = 6.6 cycles.
3. Global L2 miss rate = 0.05 × 0.2 = 0.01, so only 1 percent of all accesses go to DRAM.

Adding the L2 cut the AMAT from 14 to 6.6 cycles.

Worked example: three levels

L1: hit 4 cycles, local miss rate 10 percent. L2: hit 14 cycles, local miss rate 40 percent. L3: hit 40 cycles, local miss rate 25 percent. DRAM: 250 cycles.

1. L3 miss penalty term: 40 + 0.25 × 250 = 40 + 62.5 = 102.5.
2. L2 level: 14 + 0.4 × 102.5 = 14 + 41 = 55.
3. L1 level: AMAT = 4 + 0.1 × 55 = 4 + 5.5 = 9.5 cycles.
4. Global L3 miss rate = 0.1 × 0.4 × 0.25 = 0.01.

A 40 percent L2 local miss rate looks bad in isolation, but the L2 only sees the 10 percent of accesses that L1 missed. Always ask whether a quoted miss rate is local or global.

Worked example: effect on CPI

CPI (cycles per instruction) with a perfect cache is 1.0. Every instruction is fetched (one instruction-cache access each), and 30 percent of instructions are loads or stores (one data-cache access each). The I-cache miss rate is 2 percent, the D-cache miss rate is 4 percent and the miss penalty is 100 cycles.

Instruction-fetch stalls per instruction = 1    × 0.02 × 100 = 2.0
Data stalls per instruction              = 0.30 × 0.04 × 100 = 1.2
CPI = 1.0 + 2.0 + 1.2 = 4.2

The program runs 4.2 times slower than it would with a perfect memory system. That number explains why architects work so hard on caches.

Types of misses: the 3 Cs

Classifying misses tells you which fix will help.

1. Compulsory (cold) misses: the first access to a block ever. Even an infinite cache would miss. Reduced by larger blocks and prefetching.
2. Capacity misses: the program's working set is larger than the cache, so blocks are evicted and later needed again. These would happen even in a fully associative cache of the same size. Reduced by a bigger cache or by restructuring code to use less data at once (blocking).
3. Conflict misses: blocks are evicted because too many map to the same set, although the cache as a whole has room. These disappear in a fully associative cache of the same size. Reduced by higher associativity.

A fourth C, coherence misses, occurs in multiprocessors when another core's write invalidates your copy. That is covered in the parallelism and multicore lesson.

Worked example: classifying misses

Use the direct-mapped trace from earlier (blocks 3, 11, 3, 19, 11, 3, 7 in a 4-line cache). The method: a miss on a never-seen block is compulsory; otherwise, if a fully associative LRU cache of the same size would also miss, it is capacity; otherwise it is conflict.

Four compulsory, zero capacity, three conflict. Raising associativity would help; a bigger cache with the same mapping would not, since all blocks still collide.

Design trade-offs in one table

Cache-friendly code

All of the above becomes concrete the moment you write a nested loop over a 2D array.

C stores 2D arrays in row-major order: a[i][j] and a[i][j+1] are adjacent in memory, while a[i][j] and a[i+1][j] are a whole row apart. (Fortran and MATLAB use column-major order, so the advice flips there.)

int a[3][4] in memory (row-major):

address:  0    4    8    12   16   20   24   28   32 ...
element: a00  a01  a02  a03  a10  a11  a12  a13  a20 ...
         |------ row 0 -----||------ row 1 -----|

The following program sums a 4096 × 4096 int array (64 MB) twice: once row by row and once column by column.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 4096

static double seconds(void) {
    struct timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec + t.tv_nsec / 1e9;
}

int main(void) {
    int *a = malloc(sizeof(int) * N * N);
    for (long i = 0; i < (long)N * N; i++) a[i] = (int)(i & 7);

    long sum = 0;
    double t0 = seconds();
    for (int i = 0; i < N; i++)          /* row by row: consecutive addresses */
        for (int j = 0; j < N; j++)
            sum += a[(long)i * N + j];
    double t1 = seconds();
    for (int j = 0; j < N; j++)          /* column by column: jumps N*4 bytes */
        for (int i = 0; i < N; i++)
            sum += a[(long)i * N + j];
    double t2 = seconds();

    printf("row-major:    %.3f s\n", t1 - t0);
    printf("column-major: %.3f s\n", t2 - t1);
    printf("checksum %ld\n", sum);
    free(a);
    return 0;
}

Compiled with gcc -O2 (Apple clang) and run on an Apple M2 laptop, three runs gave:

row-major:    0.002 - 0.004 s
column-major: 0.058 - 0.059 s

Column order was roughly 15 to 30 times slower for exactly the same arithmetic. At -O1, where the compiler does not vectorise the row loop, the figures were 0.013 s versus 0.069 s, still about 5 times apart. Your numbers will differ by machine; the direction will not.

Why: in row order, each 128-byte block (the M2's line size) serves 32 consecutive int reads, and the hardware prefetcher (logic that detects a regular stride and fetches upcoming blocks early) keeps the stream flowing. In column order, consecutive reads are 16 KB apart, so each one touches a different block; by the time the loop returns to the next column, the blocks it loaded have long been evicted. Nearly every access is a miss.

Practical rules that follow:

• Traverse arrays in the order they are laid out. In C, Java and Python's NumPy (default), make the last index the innermost loop.
• Prefer contiguous containers (arrays, std::vector, ArrayList of primitives) over pointer-linked ones when you iterate a lot.
• Keep data that is used together close together; split rarely used fields out of hot structs.
• Process data in chunks that fit in cache (blocking or tiling), which the modern processors lesson demonstrates on matrix multiplication.
• Beware of power-of-two strides: walking an array with a stride equal to (number of sets × block size) maps every access to the same set.

Other cache details interviewers mention

• Split versus unified caches. L1 is usually split into an instruction cache (I-cache) and a data cache (D-cache) so an instruction fetch and a data access can happen in the same cycle (the pipeline's structural hazard from the pipelining lesson). L2 and L3 are usually unified.
• Inclusive versus exclusive. In an inclusive hierarchy, everything in L1 is also in L2 (and L3), which makes it easy to check whether any core has a block. In an exclusive hierarchy, a block lives in only one level, which gives more total capacity. Many designs are neither strictly (non-inclusive).
• Critical word first / early restart. On a miss, the cache returns the requested word as soon as it arrives instead of waiting for the whole block, so the processor resumes sooner.
• Non-blocking caches. A cache that keeps serving hits (and even more misses) while an earlier miss is outstanding. The structures that track outstanding misses are called MSHRs (miss status holding registers).
• Victim cache. A small fully associative buffer that holds recently evicted lines from a direct-mapped or low-associativity cache, catching many conflict misses cheaply.

Interview questions

Q1. What is the principle of locality, and how do caches exploit each kind?

Temporal locality means a recently used location is likely to be used again soon; caches exploit it by keeping recently used blocks and evicting the least recently used. Spatial locality means nearby locations are likely to be used soon; caches exploit it by fetching whole blocks (for example 64 bytes) on a miss and by prefetching the next blocks in a stream.

Q2. A 32 KB, 4-way set-associative cache has 64-byte blocks and 32-bit addresses. How many tag, index and offset bits?

Offset = log2(64) = 6. Lines = 32,768 ÷ 64 = 512, sets = 512 ÷ 4 = 128, so index = 7. Tag = 32 − 7 − 6 = 19.

Q3. Why do real caches use set associativity instead of fully associative mapping?

Fully associative lookup needs a comparator for every line and must search all of them each access, which costs area, power and hit time. Set associativity with 4 to 16 ways removes most conflict misses while needing only a handful of comparators, so it captures most of the benefit for a fraction of the cost.

Q4. What happens on a read miss in a write-back cache?

The cache picks a victim in the set. If the victim is dirty, its block is written back to the next level (often via a write-back buffer so the read is not delayed). The requested block is fetched, installed with valid set and dirty clear, its tag stored, and the requested word returned to the processor, often as soon as it arrives (critical word first).

Q5. Compare write-through and write-back.

Write-through updates the next level on every store, keeping it always current but generating heavy traffic; it relies on a write buffer to avoid stalling. Write-back updates only the cache and marks the line dirty, writing it out once on eviction; this saves bandwidth for repeated writes but needs a dirty bit and makes some evictions slower. Write-back is standard for modern data caches.

Q6. What is the difference between write-allocate and no-write-allocate?

They decide what happens on a write miss. Write-allocate fetches the block into the cache and then writes it, betting the program will touch nearby data soon. No-write-allocate writes directly to the next level without caching the block. Write-back caches normally use write-allocate; write-through caches often use no-write-allocate.

Q7. Define AMAT and compute it for hit time 2 ns, miss rate 3 percent, miss penalty 80 ns.

AMAT = hit time + miss rate × miss penalty = 2 + 0.03 × 80 = 2 + 2.4 = 4.4 ns. It is a better measure than hit rate alone because it accounts for how long hits and misses each take.

Q8. Explain the 3 Cs of cache misses and how you would reduce each.

Compulsory misses occur on the first access to a block; reduce them with larger blocks or prefetching. Capacity misses occur because the working set is bigger than the cache; reduce them with a larger cache or by restructuring the algorithm to work on smaller chunks. Conflict misses occur when too many blocks map to one set; reduce them with higher associativity or a victim cache.

Q9. Does increasing block size always reduce the miss rate?

No. Larger blocks exploit more spatial locality, so the miss rate falls at first. But for a fixed cache size, larger blocks mean fewer lines, so conflict and capacity misses rise, and each miss takes longer to fill. Past some point the miss rate and especially AMAT get worse; 64 bytes is a common sweet spot.

Q10. What is the difference between local and global miss rate?

Local miss rate is misses at a level divided by the accesses that reach that level. Global miss rate is misses at that level divided by all processor accesses, equal to the product of local miss rates down to that level. An L2 with a 40 percent local miss rate under an L1 with a 10 percent miss rate has a global miss rate of only 4 percent.

Q11. Why is iterating a C 2D array column by column slow?

C stores arrays row by row, so walking down a column jumps by a whole row on each access. Each access lands in a different cache line, giving almost no spatial locality, and with a large array the lines are evicted before the loop comes back for neighbouring elements. Swapping the loops so the last index is innermost turns most accesses into hits.

Q12. How does LRU work, and why do caches often use pseudo-LRU instead?

LRU evicts the line in the set that has been unused the longest, which tracks temporal locality well. Exact LRU needs to maintain a full ordering of N ways and update it on every access, which gets expensive as N grows. Tree pseudo-LRU uses only N − 1 bits per set and usually picks a victim close to the true LRU one.

Q13. What is a dirty bit and when is it used?

It is a per-line flag in a write-back cache that is set when the line is modified. On eviction, a dirty line must be written back to the next level; a clean line can simply be discarded because memory already has the same data.

Q14. What are split L1 caches and why are they used?

The L1 is divided into a separate instruction cache and data cache. A pipelined processor fetches an instruction and accesses data in the same cycle, so separate caches avoid a structural hazard and let each be tuned (the I-cache is read-only from the core's view). Lower levels are usually unified so capacity is shared flexibly.

Key takeaways

• Caches work because programs have temporal and spatial locality; the memory hierarchy gives near-SRAM speed at near-DRAM cost.
• Latencies grow by roughly 3 to 10 times per level; the cache-to-DRAM jump (hundreds of cycles) dominates performance.
• Address = tag | index | offset. Offset = log2(block), index = log2(lines ÷ ways), tag = the rest.
• Direct-mapped and fully associative are the two ends of set associativity; real caches use 4 to 16 ways.
• LRU tracks recency, FIFO tracks fill order, random is cheap, and tree pseudo-LRU approximates LRU with N − 1 bits.
• Write-back + write-allocate is the standard pairing for data caches; write-through needs a write buffer.
• AMAT = hit time + miss rate × miss penalty, applied recursively for each level; distinguish local and global miss rates.
• Misses are compulsory, capacity or conflict (plus coherence on multicores), and each has a different remedy.
• Cache-friendly code walks memory in layout order and works on chunks that fit; a column-wise walk of a C array can be over ten times slower.

Next lesson

Continue with Main memory and virtual memory hardware.