Skip to content
Tutorials Center
My learning

Topics

Lesson 41 of 67 ยท Memory Hierarchy

Cache Memory Basics

Learn what a CPU cache is, how hits, misses and AMAT are calculated, and how an address splits into tag, index and offset, with a Python address tool.

A cache is a small, fast memory that holds copies of data from a larger, slower one. The CPU asks the cache first; if the data is there, the answer comes back in a cycle or a few. If not, the request goes to the next level, and the cache keeps a copy for next time. Because of locality, a cache a thousand times smaller than main memory can answer the large majority of requests.

This lesson introduces the vocabulary (hit, miss, block, hit rate, AMAT), shows how a memory address is cut into tag, index and offset, and gives you Python tools to compute the split and to watch a tiny cache work. The next lesson, Direct, Associative and Set-Associative Mapping, studies the placement rules in depth.

Hits, misses and the numbers that describe them

  • Hit: the requested data is in the cache.
  • Miss: it is not, and must be fetched from the next level.
  • Hit rate = hits / accesses. Miss rate = 1 - hit rate.
  • Hit time: time to deliver data on a hit (including checking for it).
  • Miss penalty: extra time to fetch the block from the next level on a miss.

The number that combines them is the average memory access time (AMAT):

TEXT
AMAT = hit time + miss rate x miss penalty

Suppose a hit takes 1 cycle and a miss costs 100 extra cycles. At a 5% miss rate, AMAT is 1 + 0.05 x 100 = 6 cycles. At 2% it is 3 cycles. Small changes in miss rate matter a great deal, because the miss penalty is so large. The same formula applies at every level: the "miss penalty" of L1 is the AMAT of L2, which you will use in Cache Performance and the Three Cs.

AMAT also shows the trade-off in cache design. A bigger or more associative cache lowers the miss rate but raises the hit time. If a 2-cycle cache with a 2% miss rate (AMAT 4 cycles) replaces a 1-cycle cache with a 5% miss rate (AMAT 6 cycles), the slower hit is worth it.

Blocks: the unit of caching

A cache does not store single bytes. It stores blocks (also called lines): aligned chunks of consecutive memory, commonly 64 bytes. On a miss, the whole block containing the requested byte is copied in. This exploits spatial locality: after the first access to a block, the next 63 bytes are already there.

Memory addresses are therefore split into a block number (which block) and a byte offset within the block. Two addresses in the same aligned 64-byte block always hit or miss together.

Each cache line holds:

  • Data: the block's bytes.
  • Tag: identifies which memory block currently occupies the line (since many blocks compete for each line).
  • Valid bit: says whether the line contains anything yet (all lines are invalid at power-on).
  • (Later lessons add dirty and replacement bits.)

Tag, index and offset

When the CPU issues an address, the cache hardware slices it into three fields:

flowchart LR
  A["Address (32 bits)"] --> T["Tag<br/>the high bits"]
  A --> I["Index<br/>selects the set / line"]
  A --> O["Offset<br/>byte within the block"]
  I --> L["Cache line selected"]
  L --> C{"Valid and<br/>tag equal?"}
  T --> C
  C -->|yes| H["Hit: use offset<br/>to pick the bytes"]
  C -->|no| M["Miss: fetch block<br/>from next level"]

The index finds where to look, the tag confirms it is the right block, the offset finds the byte.

  • Offset has log2(block size) bits. A 64-byte block needs 6 offset bits.
  • Index has log2(number of sets) bits. It says which line (or set of lines) to inspect.
  • Tag is everything left over: address bits - index bits - offset bits.

Only the tag has to be stored with each line, because the index is implied by the line's position and the offset by the data layout. That keeps the overhead small.

For a direct-mapped cache (one line per set) with 32 KB capacity and 64-byte blocks, there are 32768 / 64 = 512 lines, so 9 index bits, 6 offset bits and 32 - 9 - 6 = 17 tag bits.

An address breakdown tool

The code below computes the field widths for any cache geometry and splits real addresses. The ways parameter will matter in the next lesson: with more ways per set there are fewer sets, hence fewer index bits and more tag bits.

Python Split addresses into tag, index and offset

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the second and third addresses in the output. 0x1234 and 0x11234 have the same index (72) but different tags (0 and 2): they are exactly 64 KB apart, a multiple of the number of sets times the block size (512 x 64 = 32 KB), so they map to the same line and cannot both be in a direct-mapped cache at once. The first and second addresses differ only in their index (72 and 73): they sit in adjacent blocks and coexist peacefully. Notice also that adding ways shifts bits from the index to the tag: 8 ways leaves 64 sets, 6 index bits and 20 tag bits.

Watching a cache work

Now a very small direct-mapped cache: 8 lines of 16 bytes (128 bytes total), with 12-bit addresses. The first trace has the access pattern of two arrays that fall on the same lines; the second is a sequential walk through 64 words.

Python A tiny direct-mapped cache, step by step

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first accesses show the two kinds of "first time" behaviour. 0x000 is a miss into an empty line, and 0x004 and 0x00C then hit because they share its 16-byte block: spatial locality at work. Then 0x080 arrives. It has index 0 as well (128 bytes is the cache size, so addresses 128 apart collide), so it evicts the block that 0x000 loaded, and a moment later 0x000 evicts it back. These conflicts drive the hit rate down to 20% even though the working set is just two blocks, and they are exactly the problem that associativity solves in the next lesson. The sequential walk, in contrast, hits 75% of the time: four 4-byte words per 16-byte block means one miss followed by three hits.

Computing AMAT

The formula is simple enough to explore directly. This snippet shows how sharply AMAT falls with the miss rate, and why a slower but better cache can win.

Python Average memory access time

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With a 100-cycle penalty, going from a 5% to a 2% miss rate saves 3 cycles per access, so the big cache can afford a hit time up to 4 cycles longer before it stops paying off (the last lines show AMAT 6.0 at a hit time of 4). This is why real L1 caches stay small (to keep hit time to a few cycles) while L2 and L3 trade speed for capacity.

Cache terms you will meet next

  • Mapping decides which lines a block may occupy: any (fully associative), exactly one (direct-mapped) or a small group (set-associative). See the next lesson.
  • Replacement policy picks the victim when a set is full, and the write policy says when modified data goes back to memory: see Replacement and Write Policies.
  • Split caches: the L1 is usually separate for instructions (I-cache) and data (D-cache), so fetch and load/store do not compete.
  • Multilevel caches: L1, L2, L3, each backing the previous one.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A cache has hit time 2 cycles, miss rate 4% and miss penalty 50 cycles. What is the AMAT?

    AMAT = 2 + 0.04 x 50 = 4 cycles.
  2. 2. A 16 KB direct-mapped cache has 32-byte blocks and 32-bit addresses. How many offset, index and tag bits are there?

    32-byte blocks need 5 offset bits. 16 KB / 32 B = 512 lines, so 9 index bits. The tag is 32 - 9 - 5 = 18 bits.
  3. 3. Why does a cache fetch a whole block rather than a single byte on a miss?

    After one access to a block, accesses to its other bytes are likely, so fetching it all converts them into hits.
  4. 4. What is the tag used for?

    Many memory blocks share each index, so the stored tag is compared with the address tag to confirm a hit. The index chooses the line, the offset the byte, and a dirty bit records modification.
  5. 5. In the tiny cache of the lesson (8 lines of 16 bytes), why do addresses 0x000 and 0x080 conflict?

    128 bytes is the cache size, so addresses 128 apart map to the same line (index 0) while holding different blocks (tags 0 and 1).

Summary

  • A hit is served by the cache; a miss fetches the whole block from the next level. AMAT = hit time + miss rate x miss penalty.
  • Caches store blocks (typically 64 bytes), each line with a valid bit, a tag and the data.
  • An address splits into tag (high bits), index (which line or set) and offset (byte in the block); offset bits = log2(block size), index bits = log2(sets).
  • Different memory blocks with the same index compete for the same line and evict each other: a conflict.
  • Sequential access gets many hits from each fetched block, so spatial locality is rewarded.
  • Larger or slower caches can still lower AMAT if they cut the miss rate enough.

Next, see how the placement rule changes conflicts in Direct, Associative and Set-Associative Mapping.