Memory hierarchy

Vocabulary

English	Meaning
memory hierarchy	memory hierarchy
locality	locality
direct-mapped cache	direct-mapped cache
tag/tæɡ/	tag
index/ˈɪndeks/	A position marker or lookup structure used to locate data within a collection or database.
block offset	block offset
average memory access time	average memory access time
evicts	evicts

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