E ExamMaster

AWS Cloud Architect & Developer · Computer Architecture

Cache and the Memory Hierarchy

Why caches work, where a block may live, and how to average the cost of a hit and a miss.

The MEM stage of LOAD R1, (R2) is not one trip to DRAM. A cache sits between the CPU and main memory. This topic is why that cache works, where a block may live, and how to average the cost of a hit and a miss. Address 0x1000 is still our load.

  • AWS Cloud Architect & Developer
  • Hard level
  • 5 concepts

1The memory hierarchy

A register answers in a fraction of a nanosecond. DRAM, the main memory that holds the word at 0x1000, answers in about 100 ns on the numbers this course uses — a hundred times slower. A cache is a small, fast SRAM copy of recently used DRAM blocks. The usual stack is registers, then L1 cache, then L2 (and maybe L3), then DRAM. Each level is larger and slower than the one above it.

The ISA still says "read the word at 0x1000". The microarchitecture decides whether that read is a cache hit or a walk down to DRAM. The figure below is not to scale: a bar drawn 100× shorter than DRAM would vanish, so the heights are schematic and the labels carry the nanoseconds.

Figure. L1 versus DRAM latency. Heights are schematic: drawing 100× honestly would make the L1 bar disappear, so the labels carry the real nanoseconds.

How it works

  1. RegistersInside the CPU. The destination of our LOAD is R1 — a register, not a cache line.
  2. CacheSmall SRAM that holds recent DRAM blocks. The MEM stage looks here first.
  3. DRAMMain memory that holds 0x1000. About a hundred times slower than L1 on the numbers this topic uses.

How much slower is DRAM than L1?

This topic's teaching numbers: L1 hit time = 1 ns, DRAM access = 100 ns. What is the slowdown if every load went to DRAM instead of L1?

  • DRAM / L1 = 100 ns / 1 ns100
  • Slowdown100×

Pro tip. These are course numbers, not a datasheet. The point is the gap: a cache exists because that factor is tens to hundreds, not 2×.

On the hierarchy this topic uses, a load that misses every cache and goes to DRAM is slower than an L1 hit by about
  1. 100×
  2. 2×
  3. the same — DRAM is just larger

100 ns versus 1 ns is a hundredfold. 2× would not justify a cache. Capacity and latency move together: DRAM is larger and slower.

2Locality of reference

Caches exploit locality — the tendency of programs to reuse data and instructions recently accessed. Temporal locality: if a word was referenced, it will likely be referenced again soon (loops, counters, the running total in R3). Spatial locality: if a word was referenced, nearby words will likely follow (the next price after 0x1000, sequential instruction fetch). A cache hit serves the request from fast cache SRAM and avoids the slower main-memory access.

Without locality, even a large cache cannot help — every reference would miss. The 64-byte block that holds 0x1000 also holds 0x1000 through 0x103F; a later load of 0x1004 is spatial locality on that same block.

Figure. One fetched block brings neighbours for free (spatial) and stays resident for reuse (temporal). A hit is served inside the cache; only a miss walks up to main memory.

How it works

  1. TemporalReuse the same block — keep it in cache across iterations.
  2. SpatialFetch a whole cache block on first touch — neighbours come free.
  3. MissNo locality → block evicted before reuse → every access pays miss penalty.
Scanning a large array element-by-element in order shows strong
  1. Spatial locality
  2. Temporal locality only
  3. Neither — arrays defeat caches

Sequential access touches consecutive addresses in one block before moving on — classic spatial locality. Temporal locality would dominate if the same element were revisited in a tight loop.

3Cache mapping and geometry

Cache mapping decides where a main-memory block may reside. Direct-mapped (1-way set associative): each memory block maps to exactly one cache line — cheap hardware, more conflict misses. Fully associative: any block can go in any line — one big set, flexible placement, expensive comparators. k-way set associative: the cache is divided into sets of k lines; a block maps to one set but may occupy any of its k ways — the usual compromise.

Geometry: number of blocks = cache size ÷ block size; number of sets = blocks ÷ associativity. Direct-mapped is 1-way; fully associative is one set containing all lines. The cache under our LOAD is 32 KB, 64-byte blocks, 4-way — 512 blocks and 128 sets.

Figure. Mapping chooses how many lines compete in a set — from one (direct) to all (fully associative).

How it works

  1. Block countCache size ÷ block size — how many lines the cache holds.
  2. Set countBlock count ÷ associativity — index bits select the set.
  3. PlacementWithin the set, tag bits distinguish which memory block occupies a way.
Mapping extremes
MappingWays per setSetsTrade-off
Direct-mapped1= block countCheapest; conflict misses
k-way set assoc.kblocks / kBalanced — typical L1/L2
Fully associativeall lines1Fewest conflicts; costly tags

Cache set count

A 32 KB cache uses 64 B blocks and is 4-way set associative. How many sets?

  • Blocks = 32 KB / 64 B = 32768 / 64512 blocks
  • Sets = blocks / associativity = 512 / 4128 sets

Pro tip. Direct-mapped = 1-way associative; fully associative = one big set. The extremes of set-associativity bracket every real cache.

A direct-mapped cache with 256 lines has how many sets?
  1. 256
  2. 1
  3. 128

Direct-mapped means 1 way per set, so sets = lines = 256. 1 set would be fully associative; 128 would imply 2-way associativity.

4Average memory access time

Effective memory access time averages what a typical load costs when some references hit the cache and some miss to main memory: \text{AMAT} = \text{Hit time} + \text{Miss rate} \times \text{Miss penalty}. Every access pays hit time — that is the cache lookup whether the line is present or not. Only the misses pay miss penalty on top, the extra latency to fetch the block from slower memory; always multiply miss penalty by the miss rate only, never add the full penalty to every access.

Multi-level caches nest the same formula: treat the level below as the miss penalty of the level above, then repeat until main memory is reached.

Figure. Every load reaches the cache and pays hit time. Only the fraction that miss continue to main memory and pay miss penalty on top — that is what the miss rate weights in AMAT.

How it works

  1. Hit timeEvery access pays the cache lookup latency, hit or miss.
  2. Miss fractionMultiply miss penalty by the miss rate — only that fraction pays the extra fetch cost.
  3. AddAMAT is hit time plus that weighted miss cost.

Average memory access time

Cache hit time = 2 ns, miss rate = 10%, miss penalty = 100 ns. Find AMAT.

  • AMAT = Hit time + Miss rate × Miss penalty2 + 0.10 × 100
  • 2 + 0.10 × 1002 + 10
  • AMAT12 ns

Pro tip. Miss penalty is the extra time on a miss; always multiply it by the miss rate only. For an L1 backed by L2, plug the L2 AMAT in as L1's miss penalty and run the formula again.

Cache hit time = 1 ns, miss rate = 5%, miss penalty = 80 ns. AMAT is
  1. 5 ns
  2. 81 ns
  3. 4 ns

AMAT = 1 + 0.05 × 80 = 5 ns. Adding 1 + 80 = 81 ns treats every access as a miss. 4 ns multiplies hit time by the hit rate instead of adding hit time to the weighted miss cost.

5The LOAD walks cache, then memory

`LOAD R1, (R2)` with R2 = 0x1000 now has a memory stage that is not one trip to DRAM. The cache in this topic is 32 KB with 64-byte blocks and 4-way associativity — 128 sets. Block size 64 B means the block that contains 0x1000 also contains 0x1000 through 0x103F. First touch is a miss: the cache looks up, then fetches 64 bytes from DRAM, and the load pays hit time plus miss penalty, 2 + 100 = 102 ns on these numbers.

A later load of 0x1004 is in the same block: hit, 2 ns. If one in ten loads miss, AMAT = 2 + 0.10 × 100 = 12 ns. That 12 ns is what the MEM stage of our LOAD costs on average — not 2 ns and not 102 ns. The ISA still says one load; the microarchitecture priced it.

Figure. The running LOAD always enters the cache. The first touch of 0x1000 continues on the dashed edge to DRAM and brings back the whole 64-byte block. The next load inside that block stops at the cache.

How it works

  1. First LOAD0x1000 is not in cache. Miss: fetch the 64 B block 0x1000–0x103F, pay 2 + 100 ns.
  2. NeighbourLOAD of 0x1004 is in that block. Hit: 2 ns.
  3. AverageIf one in ten loads miss, AMAT = 2 + 0.10 × 100 = 12 ns — the MEM-stage cost of our instruction on average.

First miss, then a neighbour hit

Hit time = 2 ns, miss penalty = 100 ns. Cost of the first LOAD to 0x1000 (miss), then a LOAD to 0x1004 (hit in the same 64 B block).

  • First LOAD (miss) = 2 + 100102 ns
  • LOAD 0x1004 (hit)2 ns
  • Two-load total104 ns

Pro tip. The second address is not magic: 0x1004 sits in 0x1000–0x103F. A first touch of 0x1080 would miss again — that is a different block.

After a miss on 0x1000 fills a 64 B block, a load of 0x1004 is
  1. A hit — same block
  2. A miss — every new address misses
  3. Uncacheable — only 0x1000 was fetched

64 B from 0x1000 covers 0x1000–0x103F. 0x1004 is inside that range. A later 0x1080 would be the next block and could miss.

Notes

  • The memory hierarchy is registers, then cache levels, then DRAM: each step is larger and slower.
  • Locality of reference (temporal and spatial) is why caches work; a cache hit avoids the slower main-memory access.
  • Cache mapping: direct-mapped (one line per set), fully associative (any line), and k-way set associative (k lines per set) trade cost vs miss rate.
  • AMAT = Hit time + Miss rate × Miss penalty; always weight the penalty by the miss rate only.
  • A 64 B block around 0x1000 also holds 0x1004 — that is spatial locality on the running LOAD.

Formulas

  • Effective (average) memory access time = Hit time + Miss rate * Miss penalty.
  • Cache blocks = cache size / block size; set count = blocks / associativity.
  • Direct-mapped = 1-way; fully associative = one set.

Exam traps & shortcuts

  • AMAT = Hit time + Miss rate x Miss penalty — plug directly; multi-level caches nest this formula.
  • Direct-mapped = 1-way associative; fully associative = one big set — the extremes of set-associativity.
  • Never add the full miss penalty to every access; only the miss fraction pays it.

Reference tables

Name the quantity before plugging numbers. Units on cache size and block size must match.

Formula sheet
QuantityFormulaWatch for
AMATHit time + Miss rate × Miss penaltyPenalty × rate, not full penalty
Cache blocksCache size / block sizeUnits must match (B, KB)
Cache setsBlocks / associativityDirect-mapped → associativity = 1

Recap

Hierarchy, locality, mapping, then AMAT on the running LOAD.

Hierarchy
Registers, then cache, then DRAM. ISA names the address; the chip picks the level.
Locality
Temporal reuses the same block; spatial prefetches neighbours.
Mapping
Direct = 1-way; fully assoc = one set; blocks = size/block; sets = blocks/ways.
AMAT
Hit time on every access + miss rate × miss penalty. Nest for multi-level caches.
0x1000
First LOAD misses and fills 0x1000–0x103F; 0x1004 then hits; average is 12 ns at 10% miss.

Practise Cache and the Memory Hierarchy

Reading is free and needs no account. Practice, mocks and progress live in the app.

  • A 4-question practice set that ends the chapter
  • 5 quick checks with worked explanations
  • Timed mocks scored with the real marking scheme
  • Readiness tracked per topic, kept on your device
Continue with Google — freeNo card, no trial. Works offline once installed.