SyntaxPilot
Courses/CS Fundamentals for Placements/Lesson 9

CS Fundamentals for Placements · Lesson 9 of 90 · 15 min

Cache memory 1: mapping techniques with numericals

cache block/linecache hitcache misshit ratiomiss penaltyaverage memory access time (AMAT)tagindexoffset fieldsdirect-mapped cachefully associative cachek-way set-associative cacheaddress breakdown numericalstag directory size numericals

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, None plays 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

  1. lines = cache size ÷ block size
  2. sets = lines ÷ ways (direct-mapped: sets = lines; fully associative: sets = 1)
  3. offset bits = log₂(block size)
  4. index bits = log₂(sets)
  5. tag bits = address bits − index − offset
  6. 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 BLOCK to 32 and watch compulsory misses halve; give the big-array case 16 lines and watch the capacity misses vanish; move b to address 144.

Practice

  1. 100 accesses, 92 hits. Hit ratio and miss rate?
  2. Hit time 2 ns, miss penalty 80 ns, h = 0.9. AMAT?
  3. Hit time 1 ns, penalty 100 ns. What hit ratio keeps AMAT at or below 5 ns?
  4. 1 MiB cache, 2-way, 64-byte blocks, 32-bit address. Lines, sets, tag, index, offset? Tag directory size?
  5. Direct-mapped, 32 KiB, 32-byte blocks, 32-bit address. Field widths? Which line, offset and tag for address 0xABCD?
  6. Fully associative, 8 KiB, 16-byte blocks, 24-bit address. Tag bits and tag directory size?
  7. 32-bit address, 20-bit tag, 32-byte blocks, 4-way. Index bits, sets, lines, cache size?
  8. 64 KiB, 4-way, 64-byte blocks, 32-bit address, each line stores a valid and a dirty bit. Tag directory size?
  9. Word-addressable memory with 2²⁴ words; direct-mapped cache of 4K words; 8-word blocks. Tag, index, offset?
  10. h = 0.95, hit time 1 ns, penalty 100 ns. AMAT? Which helps more: halving the penalty, or halving the miss rate?
  11. In the a + b demo, move b to address 144. How many hits does direct-mapped get, and why?
  12. A direct-mapped cache has 2 lines. Block trace: 0, 2, 0, 2. Classify each access.
  13. How many tag comparators does a 4-way set-associative cache with 256 sets need per lookup?
  14. Why can't higher associativity remove capacity misses?
  15. 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
  1. h = 0.92, miss rate = 0.08.
  2. 2 + 0.1 × 80 = 10 ns.
  3. 1 + m × 100 ≤ 5 → m ≤ 0.04 → h ≥ 0.96.
  4. 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.
  5. 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.
  6. 512 lines, offset 4, no index → tag 24 − 4 = 20; directory 512 × 20 = 10,240 bits.
  7. Index = 32 − 20 − 5 = 7 → 128 sets × 4 = 512 lines × 32 B = 16 KiB.
  8. Tag 18 (from the worked example) + 2 → 1,024 × 20 = 20,480 bits.
  9. Address 24 bits; offset log₂(8) = 3; lines 4,096 ÷ 8 = 512 → index 9; tag 24 − 9 − 3 = 12.
  10. 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.
  11. 12/16. b[0..3] (address 144) is block 9 → line 1, so it no longer fights a[0..3] (block 0, line 0). It does share line 1 with a[4..7] (block 1), but by then b[0..3] is finished, so only the 4 compulsory misses remain. (Output of the modified demo: 1-way: 12/16 hits.)
  12. 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).
  13. 4. Only one set is read per lookup, so you need one comparator per way, not per set.
  14. 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.
  15. 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).