These are the notes for CS Fundamentals for Placements, episode 9. Last episode we met the cache: a small, fast memory that sits right next to the CPU and keeps copies of the data the CPU is using. But a cache is tiny and RAM is huge. When the CPU asks for an address, where in the cache should it look? Here you invent the answer one problem at a time: cache blocks and lines, hits, misses, hit ratio, miss penalty and AMAT; splitting an address into tag, index and offset; direct-mapped, fully associative and k-way set-associative caches; address-breakdown and tag-directory-size numericals; and the 3 Cs of cache misses. Every term is explained in plain words, and there is a full glossary at the end. All outputs below are real: every program was run with Python 3.13. Every cache in these notes is made up, to keep the numbers simple.
A quick refresher from earlier episodes: a bit is one 0 or 1, a byte is 8 bits. RAM (main memory) is a long row of numbered byte boxes; a box's number is its address. A KiB (kibibyte) is 2¹⁰ = 1,024 bytes, a MiB is 2²⁰ bytes. log₂(n) is "how many bits do I need to count n things": log₂(64) = 6 because 2⁶ = 64. In Python, a // b is whole-number division, a % b is the remainder ("mod"), a >> n shifts the bits of a right by n places (dropping the lowest n bits), and a & mask keeps only the bits that are 1 in mask.
The five problems
| Problem | What it teaches |
|---|---|
| How good is a cache? | Block, line, hit, miss, hit ratio, miss rate, miss penalty, AMAT |
| Finding a block fast | Why searching every line is costly; direct mapping; tag, index, offset; valid bit |
| Two blocks keep fighting | Conflict misses; k-way set-associative and fully associative caches; ways and sets |
| Numericals | Field widths, tag directory size, reverse questions, word addressing |
| Why misses happen | Compulsory, capacity and conflict misses (the 3 Cs) |
Problem 1: how good is a cache? (block, line, hit, miss, AMAT)
Think of a kirana shop (a small neighbourhood grocery).
| A kirana shop | A cache |
|---|---|
| The small rack behind the counter, within arm's reach | Cache: small, fast memory next to the CPU |
| The godown (storeroom) at the back: big, slow to walk to | RAM: big, slow main memory |
| He brings a whole carton of biscuits, not one packet, because the next customer will probably want one too | Block: a fixed-size chunk of memory moved as one unit (here 16 or 64 bytes) |
| One slot on the rack that holds one carton | Cache line: one slot in the cache that holds one block (plus its tag and status bits) |
| It's on the rack: hand it over at once | Cache hit: the data is already in the cache |
| Not on the rack: walk to the godown, the customer waits | Cache miss: the data isn't in the cache, so the block must be brought from RAM |
| The extra walking time | Miss penalty: the extra time a miss costs to fetch the block from RAM |
Why a whole block? Because of spatial locality (last episode): if a program uses address 100, it will very likely use 101, 102, 103 soon. Bringing the whole block turns those next accesses into hits. The words block and line are often mixed up: strictly, a block is the chunk of memory, and a line is the cache slot that holds it. Block size = line size.
Hit ratio, miss rate, AMAT
- Hit ratio (h) = hits ÷ total accesses. 90 hits out of 100 → h = 0.9.
- Miss rate = 1 − h = misses ÷ total accesses. Here 0.1.
- Hit time: time to look in the cache (paid by every access).
- Miss penalty: the extra time a miss pays to bring the block from RAM.
- AMAT (average memory access time) = hit time + miss rate × miss penalty.
Example: hit time 1 ns, miss penalty 100 ns, h = 0.9 → AMAT = 1 + 0.1 × 100 = 11 ns. (A nanosecond, ns, is 10⁻⁹ seconds.)
Exam note: some questions describe a hierarchical access, where a miss costs "cache time + memory time", and others a simultaneous access, where cache and memory are searched at the same time, so AMAT = h × cache time + (1 − h) × memory time. Read which one the question describes. The formula above, with the penalty as extra time, is the hierarchical form.
# AMAT = hit time + miss rate x miss penalty
hit_time = 1 # ns to read the cache
penalty = 100 # extra ns to fetch from RAM on a miss
for hit_ratio in [0.80, 0.90, 0.95, 0.99]:
miss_rate = 1 - hit_ratio
amat = hit_time + miss_rate * penalty
print(f"hit ratio {hit_ratio:.0%}: AMAT = {amat:.0f} ns")
Output:
hit ratio 80%: AMAT = 21 ns
hit ratio 90%: AMAT = 11 ns
hit ratio 95%: AMAT = 6 ns
hit ratio 99%: AMAT = 2 ns
Going from 80% to 99% hits makes memory about ten times faster (21 ns → 2 ns). A small change in hit ratio is a big change in speed. So the whole game is getting more hits, and that depends on where blocks are allowed to sit in the cache.
Problem 2: finding a block fast (direct mapping, tag, index, offset)
The failing attempt: put a block anywhere, then search every line
The obvious idea: put a block in any free line. But then, to find a block, you must check every line.
# obvious idea: a block may sit in ANY line,
# so to find it, check every line one by one
lines = [None] * 1024 # a 1024-line cache
lines[1023] = 77 # block 77 is in the last line
def lookup(block):
checks = 0
for i, b in enumerate(lines):
checks += 1
if b == block:
return f"hit in line {i}", checks
return "miss", checks
print(lookup(77))
print(lookup(5))
Output:
('hit in line 1023', 1024)
('miss', 1024)
1,024 checks to find block 77, and a miss (block 5) also costs 1,024 checks: you only know it's missing after looking everywhere. This happens on every memory access. Hardware can do all the checks at the same time, but that needs 1,024 comparators (a comparator is a small circuit that says whether two numbers are equal). That is a lot of chip area and power. We want the answer in one check.
The fix: every block gets exactly one line (direct mapping)
Think of the parcel room in a housing society with 10 cubbies.
| Parcel room | Direct-mapped cache |
|---|---|
| Rule: a parcel goes in the cubby of the flat's last digit. Flat 104 → cubby 4, always | Index: the low bits of the block number pick the one line the block may use |
| Flats 104, 204, 304 share cubby 4, so the guard writes the rest of the flat number (10, 20, 30) on the parcel | Tag: the rest of the block number, stored in the line to say whose block is there |
| Which item inside the parcel box you want | Offset: which byte inside the block |
A direct-mapped cache gives every block exactly one allowed line:
- block number = address ÷ block size (whole-number division)
- line (index) = block number mod number of lines
- tag = block number ÷ number of lines
Slicing the address: tag | index | offset
Because block size and number of lines are powers of two, the divisions are just "cut the bits":
| ------------- tag ------------- | ---- index ---- | -- offset -- |
the rest which line which byte
- offset bits = log₂(block size)
- index bits = log₂(number of lines) (later: number of sets)
- tag bits = address bits − index bits − offset bits
Example: 32-bit address, 64-byte blocks, 256 lines → offset 6, index 8, tag 32 − 8 − 6 = 18.
# 32-bit address, 64-byte blocks, 256-line direct-mapped cache
OFFSET_BITS = 6 # 2**6 = 64 bytes in a block
INDEX_BITS = 8 # 2**8 = 256 lines
addr = 0x12345678
offset = addr & 0b111111 # lowest 6 bits
index = (addr >> 6) & 0b11111111 # next 8 bits
tag = addr >> (OFFSET_BITS + INDEX_BITS) # the rest
print(f"address {addr:032b}")
print(f"tag {tag:018b}")
print(f"index {'':18}{index:08b}")
print(f"offset {'':26}{offset:06b}")
print(f"tag = {tag:#x}, line = {index}, byte = {offset}")
Output:
address 00010010001101000101011001111000
tag 000100100011010001
index 01011001
offset 111000
tag = 0x48d1, line = 89, byte = 56
The 32 bits split cleanly into 18 + 8 + 6. Address 0x12345678 (the 0x prefix means hexadecimal, episode 2) lives in line 89, at byte 56 of its block. In hardware this costs nothing: the index wires simply go to the line selector and the tag wires go to the comparator.
The failing attempt: a line that stores no tag
Do we really need to store the tag? Try without it: 8 lines of 16 bytes; address 0 holds a[0] = 5, address 128 holds b[0] = 9.
# direct-mapped: line = block number % 8. Enough?
BLOCK, LINES = 16, 8
memory = {0: "a[0]=5", 128: "b[0]=9"}
cache = [None] * LINES # each line: one block's data
def read(addr):
block = addr // BLOCK
line = block % LINES
if cache[line] is not None:
return f"addr {addr}: HIT -> {cache[line]}"
cache[line] = memory[addr]
return f"addr {addr}: miss -> {cache[line]}"
print(read(0))
print(read(128))
print(read(0))
Output:
addr 0: miss -> a[0]=5
addr 128: HIT -> a[0]=5
addr 0: HIT -> a[0]=5
Address 128 says HIT and returns a[0]=5: wrong data. Block 8 (address 128) and block 0 both map to line 0 (8 mod 8 = 0), and the cache can't tell them apart. A real program would silently read the wrong value.
The fix: store the tag (and a valid bit)
# direct-mapped: line = block % 8, and a TAG = block // 8
BLOCK, LINES = 16, 8
memory = {0: "a[0]=5", 128: "b[0]=9"}
cache = [None] * LINES # each line: (tag, data)
def read(addr):
block = addr // BLOCK
line, tag = block % LINES, block // LINES
if cache[line] is not None and cache[line][0] == tag:
return f"addr {addr}: HIT -> {cache[line][1]}"
cache[line] = (tag, memory[addr])
return f"addr {addr}: miss -> {cache[line][1]}"
print(read(0))
print(read(128))
print(read(0))
Output:
addr 0: miss -> a[0]=5
addr 128: miss -> b[0]=9
addr 0: miss -> a[0]=5
- Now 128 is a correct miss and we get
b[0]=9. - Hit = the line is valid AND its stored tag equals the address's tag.
- Valid bit: one extra bit per line, 1 when the line holds a real block. At power-on every line holds garbage, and the valid bits (all 0) stop garbage from looking like a hit. In the program,
Noneplays this role. - But the last line: address 0 misses again. Loading b threw a out, because both need line 0. That's Problem 3.
Problem 3: two blocks keep fighting (set-associative caches)
The parcel room again: flats 104 and 204 both get parcels every day, and both need cubby 4. Each new parcel pushes the other back to the store room: ping-pong, forever. Meanwhile nine other cubbies sit empty. The room isn't full; the fixed rule is the problem. Fix: give shelf 4 two cubbies and let a parcel use either one.
The failing attempt: c[i] = a[i] + b[i] on a direct-mapped cache
Array b starts exactly 128 bytes after a, and 128 bytes is the whole cache (8 lines × 16 bytes). The loop reads a[0], b[0], a[1], b[1], .... Ints are 4 bytes, so a 16-byte block holds 4 of them. run(ways) simulates a cache with that many ways; run(1) is direct-mapped. When a set is full, it throws out the oldest block (pop(0); choosing which block to throw out is next episode's topic).
# c[i] = a[i] + b[i]: 8-line cache, 16-byte blocks
BLOCK, LINES = 16, 8
trace = []
for i in range(8): # 4-byte ints
trace += [4 * i, 128 + 4 * i] # a at 0, b at 128
def run(ways):
sets = LINES // ways
cache = [[] for _ in range(sets)] # tags per set
hits = 0
for addr in trace:
block = addr // BLOCK
s, tag = block % sets, block // sets
if tag in cache[s]: hits += 1
else:
cache[s].append(tag)
if len(cache[s]) > ways: cache[s].pop(0)
print(f"{ways}-way: {hits}/{len(trace)} hits")
run(1)
Output:
1-way: 0/16 hits
Zero hits out of 16, even though each block holds four ints we use one after another. a[0..3] is block 0 and b[0..3] is block 8; both map to line 0, so every access throws the other out. A miss caused only by two blocks fighting over one place (when there was room elsewhere) is a conflict miss.
The fix: let a block sit in any of k lines
Change the last line so it runs 1, 2 and 8 ways:
for ways in (1, 2, 8): run(ways)
Output (whole program):
1-way: 0/16 hits
2-way: 12/16 hits
8-way: 12/16 hits
From 0 to 12 hits (75%) with the same cache size and the same program. The only misses left are the first touch of each of the 4 blocks.
k-way set-associative cache
- Group the lines into sets of k lines each. Each line inside a set is called a way.
- number of sets = lines ÷ k
- set = block number mod number of sets; index bits = log₂(sets) pick the set.
- The block may sit in any of the k ways of its set.
- Lookup reads the whole set and compares all k tags in parallel (k comparators), then a multiplexer (a selector circuit, episode 5) passes on the data from the way that matched.
Example: 8 lines, 2-way → 4 sets → 2 index bits. Block 8 → set 8 mod 4 = 0, tag 8 ÷ 4 = 2; block 0 → set 0, tag 0. Both fit in set 0's two ways.
One idea covers all three mappings:
| Mapping | Ways (k) | Sets | Index bits | Comparators | Conflict misses | Typical use |
|---|---|---|---|---|---|---|
| Direct-mapped | 1 | = lines | log₂(lines) | 1 | most | simplest, fastest hit time |
| k-way set-associative | 2, 4, 8, 16 ... | lines ÷ k | log₂(lines ÷ k) | k | few | the common choice |
| Fully associative | = lines | 1 | 0 | one per line | none | only small caches |
A fully associative cache is one big set: any block can go in any line, there is no index, and the tag is everything above the offset. It has no conflict misses, but needs a comparator per line, so it is only practical for small caches. More ways means fewer conflict misses but more comparators, more power and a slightly slower hit.
Problem 4: numericals (field widths and tag directory size)
Recipe
- lines = cache size ÷ block size
- sets = lines ÷ ways (direct-mapped: sets = lines; fully associative: sets = 1)
- offset bits = log₂(block size)
- index bits = log₂(sets)
- tag bits = address bits − index − offset
- tag directory size = lines × tag bits (add valid, dirty or other bits per line if the question says so)
The tag directory (tag memory, tag store) is the extra memory that holds every line's tag; it sits beside the data memory of the cache.
Worked example: three mappings
32-bit address, 64 KiB cache, 64-byte blocks.
- lines = 64 KiB ÷ 64 B = 2¹⁶ ÷ 2⁶ = 1,024; offset = 6
- direct-mapped: index = log₂(1024) = 10, tag = 32 − 10 − 6 = 16; directory = 1024 × 16 = 16,384 bits = 2 KiB
- 4-way: sets = 256, index = 8, tag = 18; directory = 1024 × 18 = 18,432 bits
- fully associative: index = 0, tag = 26; directory = 1024 × 26 = 26,624 bits
# address breakdown + tag directory size
from math import log2
def split(addr_bits, cache_bytes, block_bytes, ways):
lines = cache_bytes // block_bytes
sets = lines // ways
offset = int(log2(block_bytes))
index = int(log2(sets))
tag = addr_bits - index - offset
print(f"{ways:>4}-way: tag={tag} index={index} "
f"offset={offset} dir={lines * tag} bits")
# 32-bit address, 64 KiB cache, 64-byte blocks
for ways in [1, 4, 1024]:
split(32, 64 * 1024, 64, ways)
Output:
1-way: tag=16 index=10 offset=6 dir=16384 bits
4-way: tag=18 index=8 offset=6 dir=18432 bits
1024-way: tag=26 index=0 offset=6 dir=26624 bits
Every doubling of the ways moves one bit from the index to the tag, so the tag directory grows. That is the hidden storage cost of associativity.
Exam extras
- Extra bits per line: if each line also stores a valid bit (and, for write-back caches, a dirty bit, next episode), directory = lines × (tag + extra bits). Direct-mapped with a valid bit: 1024 × 17 = 17,408 bits.
- Word-addressable memory: if each address names a word (e.g. 4 bytes) instead of a byte, count block and cache sizes in words, and the address has fewer bits.
- Reverse questions: 32-bit address, 20-bit tag, 32-byte blocks → offset 5, index = 32 − 20 − 5 = 7 → 128 sets. If it's 4-way: 512 lines × 32 B = 16 KiB of cache.
- Which line does an address go to? Line = (address ÷ block size) mod sets. Or: write the address in binary and read the index bits.
- KiB vs KB: cache sizes in these questions are powers of two. 64 KB in a cache question means 64 × 1024 bytes.
Problem 5: why misses happen (the 3 Cs)
| Miss type | Plain meaning | Example | What reduces it |
|---|---|---|---|
| Compulsory (cold) miss | The first time a block is ever touched. Even an infinitely big cache misses | the 4 misses left in the a + b demo with 2 ways | bigger blocks (more neighbours come along), prefetching |
| Capacity miss | The data in use is bigger than the whole cache, so blocks are thrown out before they're used again, whatever the mapping | looping twice over a 256-byte array with a 128-byte cache | a bigger cache |
| Conflict miss | Caused only by the mapping: a fully associative cache of the same size would have hit | the a and b ping-pong in a direct-mapped cache | more ways (higher associativity) |
How to classify a miss: if the block was never touched before → compulsory. Otherwise, if a fully associative cache of the same size would also have missed → capacity. Otherwise → conflict. The mini project below does exactly this.
Common mistakes (and the real output)
| Mistake | Real output | Fix |
|---|---|---|
| A line that stores no tag | addr 128: HIT -> a[0]=5 |
Hit = valid AND tag matches |
| Index taken from the byte address | wrong index: 4 right index: 6 |
index = (address ÷ block size) mod sets |
| AMAT with the hit ratio instead of the miss rate | wrong AMAT = 96 ns right AMAT = 6 ns |
AMAT = hit time + (1 − h) × penalty |
| Decimal KB in a cache numerical | log2(64 KB = 64000) = 15.965784284662087 log2(64 KiB) = 16.0 |
Cache sizes are powers of two: 64 KB = 64 × 1024 |
| Fully associative with an index | FA tag bits if you wrongly keep a 10-bit index: 16 correct: 26 |
One set → 0 index bits |
| Expecting more ways to fix capacity misses | 8 lines, 8-way: hits 96/128 (75%) compulsory 16 capacity 16 (mini project) |
Only a bigger cache fixes capacity misses |
| Two arrays a cache-size apart in a direct-mapped cache | 1-way: 0/16 hits |
More ways, or move one array (pad it) |
The program behind rows 1 to 5:
# common mistakes, measured
from math import log2
BLOCK, LINES = 16, 8
# 1. index from the byte address instead of the block number
addr = 100 # block 6, byte 4 inside it
print("wrong index:", addr % LINES, " right index:", (addr // BLOCK) % LINES)
# 2. a direct-mapped cache that stores no tag
line_valid = [False] * LINES
for a in [0, 128]: # blocks 0 and 8 -> both line 0
i = (a // BLOCK) % LINES
print(f"addr {a}: {'HIT (wrong data!)' if line_valid[i] else 'miss'}")
line_valid[i] = True
# 3. AMAT with the hit ratio where the miss rate belongs
hit_time, penalty, h = 1, 100, 0.95
print(f"wrong AMAT = {hit_time + h * penalty:.0f} ns right AMAT = {hit_time + (1 - h) * penalty:.0f} ns")
# 4. decimal KB instead of KiB
print("log2(64 KB = 64000) =", log2(64000), " log2(64 KiB) =", log2(64 * 1024))
# 5. a fully associative cache still 'has an index'
lines = 1024
print("FA tag bits if you wrongly keep a 10-bit index:", 32 - 10 - 6, " correct:", 32 - 0 - 6)
Output:
wrong index: 4 right index: 6
addr 0: miss
addr 128: HIT (wrong data!)
wrong AMAT = 96 ns right AMAT = 6 ns
log2(64 KB = 64000) = 15.965784284662087 log2(64 KiB) = 16.0
FA tag bits if you wrongly keep a 10-bit index: 16 correct: 26
Mini project: a cache simulator that labels every miss
A set-associative cache simulator that prints, for each access, the block, set, tag and offset, and labels every miss with its C. To tell capacity from conflict, it runs a fully associative cache of the same size alongside (using the same "throw out the oldest" rule; textbooks usually use LRU, next episode, for this reference cache).
# mini project: a set-associative cache simulator that labels every miss
# with its "C": compulsory, capacity or conflict
BLOCK = 16
def simulate(trace, lines, ways, show=False):
sets = lines // ways
cache = [[] for _ in range(sets)] # per set: tags, oldest first
full = [] # fully associative, same size (FIFO)
seen = set() # every block ever touched
counts = {"hit": 0, "compulsory": 0, "capacity": 0, "conflict": 0}
for addr in trace:
block = addr // BLOCK
s, tag = block % sets, block // sets
offset = addr % BLOCK
# the fully associative cache of the same size, to tell capacity from conflict
fa_hit = block in full
if not fa_hit:
full.append(block)
if len(full) > lines:
full.pop(0)
if tag in cache[s]:
kind = "hit"
else:
if block not in seen:
kind = "compulsory" # first touch ever
elif not fa_hit:
kind = "capacity" # even a fully associative cache missed
else:
kind = "conflict" # only the mapping caused it
cache[s].append(tag)
if len(cache[s]) > ways:
cache[s].pop(0)
seen.add(block)
counts[kind] += 1
if show:
print(f"addr {addr:4} block {block:3} set {s} tag {tag:2} offset {offset:2} {kind}")
total = len(trace)
print(f"{lines} lines, {ways}-way: hits {counts['hit']}/{total} "
f"({counts['hit'] / total:.0%}) compulsory {counts['compulsory']} "
f"capacity {counts['capacity']} conflict {counts['conflict']}")
# 1) c[i] = a[i] + b[i] with b exactly 128 bytes after a
ab = []
for i in range(8):
ab += [4 * i, 128 + 4 * i]
simulate(ab[:6], 8, 1, show=True)
print()
for ways in (1, 2, 8):
simulate(ab, 8, ways)
print()
# 2) loop twice over a 256-byte array with a 128-byte cache: too big to fit
big = [4 * i for i in range(64)] * 2
for ways in (1, 8):
simulate(big, 8, ways)
Output:
addr 0 block 0 set 0 tag 0 offset 0 compulsory
addr 128 block 8 set 0 tag 1 offset 0 compulsory
addr 4 block 0 set 0 tag 0 offset 4 conflict
addr 132 block 8 set 0 tag 1 offset 4 conflict
addr 8 block 0 set 0 tag 0 offset 8 conflict
addr 136 block 8 set 0 tag 1 offset 8 conflict
8 lines, 1-way: hits 0/6 (0%) compulsory 2 capacity 0 conflict 4
8 lines, 1-way: hits 0/16 (0%) compulsory 4 capacity 0 conflict 12
8 lines, 2-way: hits 12/16 (75%) compulsory 4 capacity 0 conflict 0
8 lines, 8-way: hits 12/16 (75%) compulsory 4 capacity 0 conflict 0
8 lines, 1-way: hits 96/128 (75%) compulsory 16 capacity 16 conflict 0
8 lines, 8-way: hits 96/128 (75%) compulsory 16 capacity 16 conflict 0
- a + b: direct-mapped has 12 conflict misses; with 2 ways they all disappear. The 4 compulsory misses stay at every associativity.
- Big array: 256 bytes = 16 blocks, the cache holds 8. The first pass has 16 compulsory misses; on the second pass the first block of each group of four is gone again: 16 capacity misses. Going fully associative (8-way) doesn't help at all: only a bigger cache would.
- The other 96 accesses hit thanks to spatial locality: each 16-byte block holds 4 ints, so 1 miss is followed by 3 hits.
- Try it: change
BLOCKto 32 and watch compulsory misses halve; give the big-array case 16 lines and watch the capacity misses vanish; movebto address 144.
Practice
- 100 accesses, 92 hits. Hit ratio and miss rate?
- Hit time 2 ns, miss penalty 80 ns, h = 0.9. AMAT?
- Hit time 1 ns, penalty 100 ns. What hit ratio keeps AMAT at or below 5 ns?
- 1 MiB cache, 2-way, 64-byte blocks, 32-bit address. Lines, sets, tag, index, offset? Tag directory size?
- Direct-mapped, 32 KiB, 32-byte blocks, 32-bit address. Field widths? Which line, offset and tag for address
0xABCD? - Fully associative, 8 KiB, 16-byte blocks, 24-bit address. Tag bits and tag directory size?
- 32-bit address, 20-bit tag, 32-byte blocks, 4-way. Index bits, sets, lines, cache size?
- 64 KiB, 4-way, 64-byte blocks, 32-bit address, each line stores a valid and a dirty bit. Tag directory size?
- Word-addressable memory with 2²⁴ words; direct-mapped cache of 4K words; 8-word blocks. Tag, index, offset?
- h = 0.95, hit time 1 ns, penalty 100 ns. AMAT? Which helps more: halving the penalty, or halving the miss rate?
- In the a + b demo, move
bto address 144. How many hits does direct-mapped get, and why? - A direct-mapped cache has 2 lines. Block trace: 0, 2, 0, 2. Classify each access.
- How many tag comparators does a 4-way set-associative cache with 256 sets need per lookup?
- Why can't higher associativity remove capacity misses?
- Why are block sizes and numbers of sets powers of two?
Solutions
Numbers computed with a Python 3.13 script; its output:
Q1 92 hits / 100: h = 0.92 miss rate = 0.08
Q2 AMAT = 10 ns
Q3 need miss rate <= 0.04 -> h >= 0.96
Q4 1 MiB 2-way 64 B: lines 16384 sets 8192 tag 13 index 13 offset 6; dir 212992 bits = 26 KiB
Q5 32 KiB DM 32 B: tag 17 index 10 offset 5; 0xABCD -> block 1374 line 350 offset 13 tag 1
Q6 8 KiB FA 16 B 24-bit: lines 512 tag 20 offset 4; dir 10240 bits
Q7 tag 20, offset 5 -> index 7, sets 128, lines 512, cache 16 KiB
Q8 64 KiB 4-way 64 B + valid + dirty: 1024 x (18+2) = 20480 bits
Q9 word-addr 2^24 words, 4K-word DM cache, 8-word blocks: tag 12 index 9 offset 3
Q10 AMAT h=0.95 hit 1 penalty 100 -> 6 ns; halve penalty -> 3.5 ns; h=0.975 -> 3.5 ns
- h = 0.92, miss rate = 0.08.
- 2 + 0.1 × 80 = 10 ns.
- 1 + m × 100 ≤ 5 → m ≤ 0.04 → h ≥ 0.96.
- 2²⁰ ÷ 2⁶ = 16,384 lines, ÷ 2 = 8,192 sets → index 13, offset 6, tag 32 − 13 − 6 = 13. Directory 16,384 × 13 = 212,992 bits = 26 KiB.
- 1,024 lines → index 10, offset 5, tag 17. 0xABCD = 43,981; block = 43,981 ÷ 32 = 1,374; line = 1,374 mod 1,024 = 350; offset = 43,981 mod 32 = 13; tag = 1,374 ÷ 1,024 = 1.
- 512 lines, offset 4, no index → tag 24 − 4 = 20; directory 512 × 20 = 10,240 bits.
- Index = 32 − 20 − 5 = 7 → 128 sets × 4 = 512 lines × 32 B = 16 KiB.
- Tag 18 (from the worked example) + 2 → 1,024 × 20 = 20,480 bits.
- Address 24 bits; offset log₂(8) = 3; lines 4,096 ÷ 8 = 512 → index 9; tag 24 − 9 − 3 = 12.
- AMAT 6 ns. Halving the penalty → 1 + 0.05 × 50 = 3.5 ns; halving the miss rate → 1 + 0.025 × 100 = 3.5 ns. Here they help equally, because AMAT depends on the product miss rate × penalty.
- 12/16.
b[0..3](address 144) is block 9 → line 1, so it no longer fightsa[0..3](block 0, line 0). It does share line 1 witha[4..7](block 1), but by thenb[0..3]is finished, so only the 4 compulsory misses remain. (Output of the modified demo:1-way: 12/16 hits.) - Blocks 0 and 2 both map to line 0 (0 mod 2 = 2 mod 2 = 0). Access 1: compulsory, 2: compulsory, 3: conflict, 4: conflict (a 2-line fully associative cache would hold both and hit).
- 4. Only one set is read per lookup, so you need one comparator per way, not per set.
- A capacity miss happens because the data in use is bigger than the whole cache. Even if any block can go anywhere, there still isn't room for all of them.
- So that offset and index are just bit fields of the address: no division hardware, only wires.
Quick quiz
A 32-bit byte address, a 16 KiB cache, 32-byte blocks, 4-way set-associative. How many tag bits?
- A. 18
- B. 19
- C. 20
- D. 22
Answer
C, 20. 16 KiB ÷ 32 B = 512 lines; ÷ 4 ways = 128 sets → 7 index bits; offset = log₂(32) = 5; tag = 32 − 7 − 5 = 20.
Interview questions
- What is a cache and why does it work? A small, fast memory near the CPU holding copies of recently used blocks. It works because of temporal and spatial locality: programs reuse data and use neighbouring data.
- Block vs line? A block is a fixed-size chunk of memory; a line is a cache slot that holds one block plus its tag and status bits.
- Define hit ratio, miss penalty and AMAT. Hit ratio = hits ÷ accesses; miss penalty = extra time to fetch a block on a miss; AMAT = hit time + miss rate × miss penalty.
- How is an address split for a cache lookup? Tag | index | offset: offset = log₂(block size), index = log₂(sets), tag = the rest.
- Why store a tag? Why a valid bit? Many blocks map to one line; the tag says which one is there. The valid bit says whether the line holds a real block at all (not power-on garbage).
- Direct-mapped vs fully associative vs set-associative? One allowed line per block / any line / any line within one set of k. They trade comparators and hit time against conflict misses.
- Is direct-mapped a special case of set-associative? Yes, 1-way. Fully associative is (number of lines)-way, with one set.
- What happens to the field widths when you double associativity at the same size? Sets halve, the index loses one bit and the tag gains one bit.
- What is the tag directory and how big is it? The memory holding all tags: lines × (tag bits + any status bits).
- What are the 3 Cs? Compulsory (first touch), capacity (working data bigger than the cache), conflict (mapping collisions). Bigger blocks, bigger cache and more ways reduce them respectively.
- Why might two arrays in a loop thrash a direct-mapped cache? If their addresses are a multiple of the cache size apart, matching elements map to the same line and evict each other on every access.
Glossary
| Term | Plain meaning | Example |
|---|---|---|
| Cache | Small, fast memory near the CPU holding copies of recently used blocks | the kirana shop's counter rack |
| RAM / main memory | Big, slower memory with numbered byte boxes | the godown |
| Address | Number of a memory box | 128 |
| Block | Fixed-size chunk of memory moved between RAM and cache as one unit | 16 bytes = 4 ints |
| Cache line | A cache slot holding one block, its tag and status bits | line 0 |
| Block size / line size | Bytes in one block | 64 B |
| Block number | Address ÷ block size (whole-number division) | 128 ÷ 16 = 8 |
| Cache hit | The requested data is already in the cache | addr 0: HIT |
| Cache miss | The data isn't in the cache; the block must come from RAM | addr 128: miss |
| Hit ratio (h) | Hits ÷ total accesses | 90 of 100 → 0.9 |
| Miss rate | 1 − hit ratio | 0.1 |
| Hit time | Time to look in the cache | 1 ns |
| Miss penalty | Extra time a miss costs to fetch the block from RAM | 100 ns |
| AMAT | Average memory access time = hit time + miss rate × miss penalty | 1 + 0.1 × 100 = 11 ns |
| Nanosecond (ns) | 10⁻⁹ seconds | 11 ns |
| Hierarchical vs simultaneous access | Miss pays cache + memory time / cache and memory searched together | two AMAT formulas in exams |
| Spatial locality | Using an address makes nearby addresses likely to be used soon | a[0] then a[1] |
| Temporal locality | Using an address makes it likely to be used again soon | a loop counter |
| Comparator | Circuit that says whether two numbers are equal | compares stored tag vs address tag |
| Multiplexer | Selector circuit that passes one of several inputs | picks the matching way's data |
| Mapping | The rule for which line(s) a block may use | direct, set-associative, fully associative |
| Direct-mapped cache | Each block has exactly one allowed line | line = block mod lines |
| Fully associative cache | Any block can go in any line; one set, no index | tag = all bits above the offset |
| Set | A group of k lines that a block may choose between | set 0 of a 2-way cache |
| Way | One line inside a set | 2 ways per set |
| k-way set-associative cache | Lines grouped into sets of k; a block may use any way of its set | 4-way, 256 sets |
| Associativity | The number of ways, k | 1, 2, 4, 8 ... |
| Offset (field) | Low address bits: which byte inside the block | 6 bits for 64 B blocks |
| Index (field) | Middle address bits: which line (or set) | 8 bits for 256 lines |
| Tag (field) | High address bits stored in the line to identify the block | 18 bits |
| Address breakdown | Splitting an address into tag, index and offset widths | 18 | 8 | 6 |
| Valid bit | Per-line bit: 1 if the line holds a real block | all 0 at power-on |
| Dirty bit | Per-line bit: the block was changed in the cache (next episode) | write-back caches |
| Tag directory (tag memory) | Memory holding every line's tag | 1024 × 16 = 16,384 bits |
| Tag directory size | Lines × (tag bits + extra bits per line) | 1024 × 17 = 17,408 bits |
| Byte-addressable / word-addressable | Each address names one byte / one word | 4-byte words |
| KiB / MiB | 2¹⁰ / 2²⁰ bytes | 64 KiB = 65,536 bytes |
| log₂(n) | Bits needed to count n things | log₂(64) = 6 |
| Hexadecimal (0x) | Base-16 notation | 0x48d1 |
| Bit shift (>>) / mask (&) | Drop the lowest n bits / keep chosen bits | addr >> 6, addr & 0b111111 |
| Conflict miss | Miss caused only by the mapping; a fully associative cache of the same size would hit | a and b ping-pong |
| Compulsory (cold) miss | First access ever to a block | 4 misses in the a + b demo |
| Capacity miss | Miss because the data in use is bigger than the cache | 256-byte loop, 128-byte cache |
| 3 Cs | Compulsory, capacity, conflict: the three causes of misses | mini project labels |
| Thrashing (cache) | Blocks repeatedly evicting each other so almost every access misses | 1-way: 0/16 hits |
| Eviction | Throwing a block out of the cache to make room | pop(0) |
| Trace | The list of addresses a program accesses, in order | 0, 128, 4, 132 ... |
Summary
- A cache keeps blocks of RAM in lines. Hit = already there, miss = fetch from RAM and pay the miss penalty.
- Hit ratio = hits ÷ accesses; AMAT = hit time + miss rate × miss penalty. 80% → 99% hits took AMAT from 21 ns to 2 ns.
- Searching every line costs one comparator per line. Direct mapping gives each block one line: line = block mod lines.
- An address splits into tag | index | offset: offset = log₂(block size), index = log₂(sets), tag = the rest.
- Without a tag the cache returns wrong data; a hit needs valid AND tag match.
- Two blocks on one line ping-pong (conflict misses: 0/16 hits). A k-way set-associative cache lets a block use any of k ways in its set (12/16 hits). Direct-mapped = 1-way; fully associative = one set.
- Numericals: lines = size ÷ block; sets = lines ÷ k; tag directory = lines × tag bits (+ extra bits if asked). Doubling ways moves one bit from index to tag.
- 3 Cs: compulsory (bigger blocks help), capacity (bigger cache helps), conflict (more ways help).
Next episode: Cache memory 2. When a set is full, which block do we throw out (LRU, FIFO, random, LFU)? What happens on a write (write-through, write-back, dirty bit)? Multilevel caches (L1, L2, L3) and keeping many cores' caches in sync (coherence, MESI).