Memory hierarchy

Vocabulary

English	Meaning
memory hierarchy	Levels of storage with different speed, capacity and cost characteristics.
locality	The tendency to reuse recently accessed locations or nearby locations.
direct-mapped cache	A cache in which each memory block has exactly one possible cache location.
tag/tæɡ/	The address information used to identify which memory block occupies a cache location.
index/ˈɪndeks/	The address bits selecting a cache set or line in this architecture topic.
block offset	The address bits selecting a byte or position within a memory block.
average memory access time	The expected memory-access cost, combining hit time with miss probability and miss penalty.
evicts	Removes a cache block to make space for another block.

Split the address

The memory hierarchy stacks small-fast over big-slow and lets locality pay: a direct-mapped cache gives each block exactly one slot, so the address splits into tag | index | block offset.
Course cache: 4 KiB, 16-byte lines $\Rightarrow$ 256 lines $\Rightarrow$ offset 4 bits, index 8 bits, tag 20 bits. Address $0x4A8$: offset 8, index 74.

{exercise:uni-cs0604-split}

Practice

A 4 KiB direct-mapped cache with 16-byte lines has — index bits

Difficulty 1/5 · 100 coins + a small bonus on first completion today

Average memory access time $= t_{\text{hit}} + p_{\text{miss}} \times t_{\text{penalty}}$: with a 1-cycle hit, 2% miss ratio and 100-cycle penalty, AMAT $= 1 + 0.02 \times 100 = 3$ cycles — halve the misses to 1% and AMAT $= 2$.
Sensitivity is linear in misses, not hits: that is why the hierarchy lives or dies on locality. Any other block mapping to line 74 evicts the resident — direct-mapped's price for one comparator.

{exercise:uni-cs0604-amat}

Practice

Hit 1 cycle, miss ratio 2%, penalty 100: AMAT is —

Difficulty 1/5 · 100 coins + a small bonus on first completion today

Row-major scan of a $64 \times 64$ int array, 16-byte lines ($4$ ints per line): the first access misses, the next three hit — 25% miss rate, compulsory only.
Stride-16 access misses every time — 100%. Same array, same cache, four times the AMAT: layout is a performance feature.

{exercise:uni-cs0604-layout}

Practice

Row-major scanning of ints with 16-byte lines gives a miss rate of —

Difficulty 1/5 · 100 coins + a small bonus on first completion today