So far we know how a cache is organised (Cache Mapping Techniques) and how it chooses victims and handles writes (Cache Replacement & Write Policies). Now comes the question that matters in the end: how much faster does the cache actually make the program?
Cache Memory introduced the hit ratio and the basic average-access-time formula. In this chapter we go much further and turn cache behaviour into numbers. We will revisit the average memory access time (AMAT) formula and its two exam variants, see how cache misses inflate CPI and execution time, classify misses into the three Cs, work through a classic GATE problem on traversing a 2-D array, and finally understand why every modern processor has two or three levels of cache.
The Basic Quantities
| Term | Meaning |
|---|---|
| Hit ratio (h) | Fraction of accesses found in the cache = hits / total accesses |
| Miss ratio (miss rate) | 1 − h = misses / total accesses |
| Hit time | Time to access the cache and deliver data on a hit (includes tag check) |
| Miss penalty | Extra time to bring the block from the next level and deliver the data |
| Average memory access time (AMAT) | The average time per memory access, taking hits and misses into account |
The intuition: a cache is worth having when most accesses hit and the occasional miss is not too expensive. Because main memory is often 50 to 200 times slower than the L1 cache, even a few percent of misses can dominate the total time.
Average Memory Access Time
There are two ways the hardware can be organised, and they give two slightly different formulas. GATE uses both, so read the question carefully.
Model 1: Hierarchical (Look-Through) Access
The CPU first checks the cache. Only after a miss does it go to memory. So a miss costs the cache check plus the memory access.
Tavg = h × tc + (1 − h) × (tc + tm) = tc + (1 − h) × tm
This is the same as the famous form:
AMAT = Hit time + Miss rate × Miss penalty
Model 2: Simultaneous (Look-Aside) Access
The cache and memory are accessed in parallel. If the cache hits, the memory access is abandoned; if it misses, the memory result arrives after tm, with no extra tc.
Tavg = h × tc + (1 − h) × tm
Worked Example
tc = 10 ns, tm = 100 ns, h = 0.9. Find the average access time for both models.
Simultaneous: 0.9 × 10 + 0.1 × 100 = 9 + 10 = 19 ns
Hierarchical: 0.9 × 10 + 0.1 × (10 + 100) = 9 + 11 = 20 ns
(or) 10 + 0.1 × 100 = 20 nsIf a question says "the cache is checked first" or "on a miss the block is brought into the cache and then accessed", use the hierarchical model. If it says "accessed simultaneously" or "in parallel", use the simultaneous model. When the miss requires transferring a whole block, replace tm by the block transfer time given in the question.
Speedup Due to the Cache
Without a cache every access costs 100 ns. With the cache (hierarchical) it costs 20 ns, so the memory system is 100 / 20 = 5 times faster. With h = 0.99 the AMAT becomes 10 + 0.01 × 100 = 11 ns, a speedup of about 9.1. Notice how sensitive the result is to the miss rate: going from 10% to 1% misses nearly halves the AMAT.
How Cache Misses Affect CPU Time
The processor performance equation from earlier chapters is CPU time = Instruction count × CPI × Clock cycle time. Cache misses stall the pipeline, so they add memory stall cycles to the CPI:
CPIeffective = CPIbase + memory stall cycles per instruction
Memory stall cycles per instruction = (memory accesses per instruction) × miss rate × miss penalty (in cycles)
Here CPIbase is the CPI with a perfect cache that never misses. Every instruction is fetched (one instruction-cache access), and loads/stores make one data-cache access each.
Worked Example: How Much Slower Than Perfect?
A processor has CPIbase = 1.2. The instruction cache miss rate is 2% and the data cache miss rate is 5%. 30% of instructions are loads or stores. The miss penalty is 100 cycles. Find the effective CPI and how much faster a perfect cache would be.
Instruction-miss stalls = 1 × 0.02 × 100 = 2.0 cycles/instruction
Data-miss stalls = 0.30 × 0.05 × 100 = 1.5 cycles/instruction
Total stalls = 3.5 cycles/instruction
CPI_effective = 1.2 + 3.5 = 4.7
Perfect cache is faster by 4.7 / 1.2 = 3.92 timesAt 2 GHz, running 109 instructions takes 109 × 1.2 / (2 × 109) = 0.6 s with a perfect cache, but 109 × 4.7 / (2 × 109) = 2.35 s in reality. Almost three quarters of the time is spent waiting for memory!
Why a Faster Clock Does Not Help Much
Suppose the clock is doubled but memory stays equally slow in nanoseconds. What is the real speedup?
The miss penalty in nanoseconds is unchanged, so in cycles it doubles to 200.
Stalls = 1 × 0.02 × 200 + 0.30 × 0.05 × 200 = 4 + 3 = 7 cycles
CPI_new = 1.2 + 7 = 8.2
Speedup = (old CPI × old cycle) / (new CPI × new cycle)
= (4.7 × T) / (8.2 × T/2) = 4.7 / 4.1 ≈ 1.15Doubling the clock gives only a 15% speedup, not 100%. This is the famous memory wall: processor speed has grown much faster than DRAM latency, so cache misses, not the clock rate, often decide performance.
Why Misses Happen: The Three Cs
We met the three Cs briefly in Cache Memory. Here is the full picture, because to reduce misses we first need to know where they come from. Mark Hill's classification divides misses into three groups:
| Type | Cause | Would still happen in... | Main cure |
|---|---|---|---|
| Compulsory (cold-start) | First ever access to a block; it was never in the cache | An infinite cache | Larger blocks, prefetching |
| Capacity | The program's working set is larger than the cache; blocks are evicted and needed again | A fully associative cache of the same size | Larger cache |
| Conflict (collision) | Too many blocks map to the same set, even though other sets have room | Only in direct-mapped / set-associative caches | Higher associativity, victim cache, better data layout |
A practical way to classify the misses of a cache C: compulsory misses = misses of an infinite cache; capacity misses = misses of a fully associative cache of C's size minus compulsory; conflict misses = misses of C minus those of the fully associative cache. On multiprocessors a fourth C, coherence misses, appears when another core invalidates a block.
How Design Changes Affect the Three Cs
| Change | Compulsory | Capacity | Conflict | Side effect |
|---|---|---|---|---|
| Bigger cache | Same | Fewer | Fewer | Longer hit time, more power |
| Higher associativity | Same | Same | Fewer | Longer hit time |
| Bigger blocks | Fewer (more spatial locality) | Can increase (fewer blocks fit) | Can increase (fewer sets) | Larger miss penalty |
| Prefetching | Fewer | Same | Same | Wasted bandwidth if wrong |
The Block Size Trade-off
Larger blocks exploit spatial locality: one miss brings in neighbouring data that will soon be used. But for a fixed cache size, larger blocks mean fewer blocks, so useful data gets evicted sooner, and each miss transfers more bytes, so the miss penalty grows. Miss rate therefore first falls and then rises as block size grows. Most modern CPUs use 64-byte blocks.
GATE Classic: Traversing a 2-D Array
An array int a[64][64] (4-byte ints) is stored in row-major order starting at address 0. The data cache is 4 KB, direct mapped, with 64-byte blocks. Count the cache misses for (a) row-wise traversal and (b) column-wise traversal, assuming the cache starts empty and nothing else uses it.
/* (a) row-wise */ /* (b) column-wise */
for (i = 0; i < 64; i++) for (j = 0; j < 64; j++)
for (j = 0; j < 64; j++) for (i = 0; i < 64; i++)
sum += a[i][j]; sum += a[i][j];First, the basic numbers:
Array size = 64 × 64 × 4 B = 16 KB (4 times the cache)
Ints per block = 64 / 4 = 16
One row = 64 × 4 B = 256 B = 4 blocks
Cache lines = 4 KB / 64 B = 64
Address of a[i][j] = 256i + 4j
Block number = 4i + j/16 (integer division)
Line = (4i + j/16) mod 64(a) Row-Wise
Consecutive accesses are consecutive addresses. Each block is loaded once (miss) and then its next 15 ints hit. The block is never needed again after we move past it.
Misses = 4096 elements / 16 per block = 256 (miss ratio 1/16 = 6.25%)(b) Column-Wise
Successive accesses are 256 bytes apart, so each one touches a different block. For a fixed column, row i uses line (4i + j/16) mod 64. Rows i and i + 16 map to the same line, because 4 × 16 = 64. So the 64 rows of one column share only 16 lines, four rows per line. By the time we come back for column j + 1 (which is in the same block as column j for most j), the block for row i has already been evicted by rows i + 16, i + 32 and i + 48.
Misses = 4096 (every single access misses, miss ratio 100%)These numbers were confirmed with a cache simulator, which also shows how the misses should be classified:
| Cache (64-byte blocks) | Row-wise misses | Column-wise misses |
|---|---|---|
| 4 KB, direct mapped | 256 | 4096 |
| 4 KB, fully associative, LRU | 256 | 256 |
| 16 KB, direct mapped | 256 | 256 |
A fully associative 4 KB cache holds exactly the 64 blocks one column needs (one per row), so after the first column the next 15 columns all hit. That means the extra 3840 misses in the direct-mapped case are conflict misses, not capacity misses. The 256 misses that remain in every case are the compulsory misses (16 KB / 64 B = 256 blocks). The everyday lesson for programmers: in C, loop over the last index in the inner loop.
Multi-Level Caches
We face a dilemma. To keep hit time tiny (a few cycles), L1 must be small. But a small L1 misses often, and each miss to DRAM costs hundreds of cycles. The solution is to add another, bigger and slower cache between L1 and memory, so most L1 misses are caught by L2 instead of going to DRAM.
CPU core
│
+--+-------------------+
| L1-I 32 KB | L1-D | ~4-5 cycles, per core, split I/D
+----------------------+
│
+----------------------+
| L2 ~0.5-2 MB | ~12-20 cycles, usually per core, unified
+----------------------+
│
+----------------------+
| L3 few MB to 100+MB| ~40-70 cycles, shared by all cores
+----------------------+
│
Main memory (DRAM) ~200-400 cycles
(figures are typical orders of magnitude, they vary by processor)L1 is designed for hit time: small, often split into an instruction cache and a data cache so that fetch and load/store can happen in the same cycle (a Harvard-style arrangement inside a von Neumann machine).
L2/L3 are designed for low miss rate: bigger, more associative, and unified (instructions and data together).
Local vs Global Miss Rate
Local miss rate of a cache = misses in this cache / accesses to this cache.
Global miss rate of a cache = misses in this cache / total memory accesses made by the CPU.
For L1 the two are equal. For L2 they differ a lot, because L2 sees only the accesses that missed in L1:
Global miss rateL2 = Miss rateL1 × Local miss rateL2
The local miss rate of L2 often looks terrible (20-50%) because L1 has already removed the easy hits. The global miss rate is the number that tells you how often the CPU really goes to DRAM.
AMAT for Two Levels
AMAT = Hit timeL1 + Miss rateL1 × (Hit timeL2 + Local miss rateL2 × Miss penaltyL2)
The bracket is simply the "miss penalty of L1", which is now the AMAT of L2.
Worked Example 1: Is an L2 Worth It?
L1: hit time 1 cycle, miss rate 4%. L2: hit time 12 cycles, local miss rate 25%. Main memory: 200 cycles. Find the AMAT with and without L2, and the global miss rate of L2.
Without L2: AMAT = 1 + 0.04 × 200 = 9 cycles
With L2: L1 miss penalty = 12 + 0.25 × 200 = 62 cycles
AMAT = 1 + 0.04 × 62 = 3.48 cycles
Global miss rate of L2 = 0.04 × 0.25 = 0.01 = 1%The L2 cuts the AMAT from 9 to 3.48 cycles, a 2.6× improvement, even though its local miss rate is 25%. Only 1% of all accesses now pay the full 200-cycle trip to DRAM.
If the program makes 1.3 memory accesses per instruction, the stall cycles per instruction drop from 1.3 × 0.04 × 200 = 10.4 to 1.3 × 0.04 × 62 = 3.224.
Worked Example 2: From Counts to Rates
In 1000 memory references, there are 40 misses in L1 and 20 misses in L2. Hit times are 1 cycle (L1) and 10 cycles (L2); memory takes 100 cycles. Find the miss rates and the AMAT.
L1 miss rate = 40 / 1000 = 4%
L2 local miss rate = 20 / 40 = 50% (L2 only sees the 40 L1 misses)
L2 global miss rate = 20 / 1000 = 2% (check: 0.04 × 0.5 = 0.02)
AMAT = 1 + 0.04 × (10 + 0.5 × 100) = 1 + 0.04 × 60 = 3.4 cyclesWorked Example 3: Nanoseconds, Both Models
L1 access time is 2 ns with hit ratio 0.9. L2 access time is 15 ns and 80% of the requests reaching L2 hit there. Memory access time is 100 ns. Find the average access time for (a) hierarchical access and (b) simultaneous access.
(a) Hierarchical: each level is checked only after the previous one misses
T = 2 + 0.1 × (15 + 0.2 × 100)
= 2 + 0.1 × 35 = 5.5 ns
(b) Simultaneous: all levels start together; time is that of the level that hits
T = 0.9 × 2 + 0.1 × 0.8 × 15 + 0.1 × 0.2 × 100
= 1.8 + 1.2 + 2.0 = 5.0 nsInclusion Policies
When there are several levels, should a block in L1 also be kept in L2?
| Policy | Rule | Advantage | Disadvantage |
|---|---|---|---|
| Inclusive | Every block in L1 is also in L2 (and L3) | Coherence checks can look only at the outer level | Duplicated data wastes capacity; evicting from L2 forces eviction from L1 |
| Exclusive | A block is in L1 or L2, never both (L2 acts as a victim cache for L1) | Total capacity = L1 + L2 | Blocks move between levels more often |
| Non-inclusive (NINE) | No guarantee either way | Flexible, simpler eviction | Coherence may need to check more levels |
Real processors use all three. For example, many Intel client processors have long used an inclusive L3, while AMD's Zen cores use an L3 that is filled mainly by blocks evicted from L2 (a victim-cache design).
How Designers Improve Cache Performance
Every technique attacks one term of AMAT = hit time + miss rate × miss penalty:
| Goal | Techniques |
|---|---|
| Reduce miss rate | Larger caches, higher associativity, suitable block size, hardware prefetching, compiler optimisations (loop interchange, loop blocking/tiling) |
| Reduce miss penalty | Multi-level caches, critical-word-first and early restart, write buffers, victim caches, non-blocking caches that keep serving hits during a miss |
| Reduce hit time | Small, simple L1; way prediction; accessing the cache in parallel with address translation (see Virtual Memory & TLB (Hardware View)) |
Critical word first: on a miss, memory sends the word the CPU asked for first, and the CPU continues while the rest of the block arrives. Victim cache: a tiny fully associative buffer that holds recently evicted blocks, catching many conflict misses of a direct-mapped cache.
Common Mistakes
Mixing the two AMAT models. Hierarchical: miss costs tc + tm. Simultaneous: miss costs tm.
Multiplying the L2 miss penalty by the global miss rate inside the bracket. Inside the bracket use the local L2 miss rate; outside you already multiplied by the L1 miss rate.
Forgetting instruction fetches. Every instruction makes one instruction-cache access; only loads and stores add data accesses.
Keeping the miss penalty fixed in cycles when the clock changes. Memory latency is fixed in nanoseconds, so a faster clock means more penalty cycles.
Calling column-wise misses "capacity misses" without checking. Compare with a fully associative cache of the same size; if those misses vanish, they were conflict misses.
Assuming bigger blocks always help. Beyond a point they increase the miss rate and always increase the miss penalty.
GATE and Interview Questions
Q1. A cache has hit time 5 ns and hit ratio 0.95. Main memory access takes 80 ns. Find the average access time assuming the cache is checked first.
T = 5 + 0.05 × 80 = 5 + 4 = 9 ns. (Equivalently 0.95 × 5 + 0.05 × 85 = 4.75 + 4.25 = 9 ns.)
Q2. With the same numbers, what hit ratio is needed for an average of 7 ns?
5 + (1 − h) × 80 = 7 ⇒ (1 − h) = 2 / 80 = 0.025 ⇒ h = 0.975.
Q3. CPIbase = 1, 40% of instructions are loads/stores, I-cache miss rate 1%, D-cache miss rate 4%, miss penalty 50 cycles. Find the effective CPI.
Stalls = 1 × 0.01 × 50 + 0.4 × 0.04 × 50 = 0.5 + 0.8 = 1.3. CPI = 1 + 1.3 = 2.3.
Q4. The L1 miss rate is 5% and the L2 global miss rate is 1%. What is the local miss rate of L2?
Local = global / L1 miss rate = 0.01 / 0.05 = 20%.
Q5. Why is the local miss rate of L2 usually much higher than that of L1?
L1 already satisfies the accesses with good locality. L2 only sees the "hard" accesses that missed in L1, so a larger fraction of them miss again. That is why the global miss rate is the better measure of L2's usefulness.
Q6. Name the three Cs and one technique that reduces each.
Compulsory: larger blocks or prefetching. Capacity: a larger cache. Conflict: higher associativity (or a victim cache).
Summary
AMAT = hit time + miss rate × miss penalty. Hierarchical access: T = h·tc + (1 − h)(tc + tm). Simultaneous access: T = h·tc + (1 − h)·tm.
CPIeff = CPIbase + accesses per instruction × miss rate × miss penalty, summed over the instruction and data caches. In our example, CPI rose from 1.2 to 4.7.
Because DRAM latency is fixed in nanoseconds, a faster clock makes miss penalties larger in cycles: the memory wall.
Misses are compulsory, capacity or conflict (plus coherence on multiprocessors).
Access order matters: column-wise traversal of a row-major array gave 4096 misses versus 256 for row-wise in a 4 KB direct-mapped cache.
Multi-level caches keep L1 fast and let L2/L3 catch most L1 misses. AMAT = HTL1 + MRL1 × (HTL2 + local MRL2 × MPL2); global MRL2 = MRL1 × local MRL2.
Next, Virtual Memory & TLB (Hardware View) adds address translation to the picture and shows how it interacts with the caches.