Memory Hierarchy and Cache — Locality, Hit Ratio, AMAT and Direct, Associative and Set-Associative Mapping

A modern CPU can do an addition in well under a nanosecond, but fetching data from main memory takes around a hundred times longer. If the CPU waited for RAM every time, it would sit idle most of the time. The memory hierarchy — especially caches — is how computers hide that gap. Cache questions are the single most common COA numerical in GATE.

1. The hierarchy

Faster memory is smaller and costlier per byte. The goal: make the whole system feel as fast as the top level and as big as the bottom one.

2. Why caches work: locality

• Temporal locality — data used now will probably be used again soon (loop variables, counters).
• Spatial locality — data near what's used now will probably be used soon (array elements, sequential instructions).

So caches keep recently used data and fetch memory in blocks (cache lines, e.g. 64 bytes) rather than single bytes. That's why iterating an array row by row is much faster than column by column in C/Java.

3. Hit ratio and AMAT

• Hit — data found in the cache. Miss — must go to the next level.
• Hit ratio h = hits / accesses; miss ratio = 1 − h.
• Average memory access time: AMAT = hit time + miss rate × miss penalty.

Two-level cache: AMAT = T_L1 + m_L1 × (T_L2 + m_L2 × T_mem).

(Some textbooks use h·Tc + (1−h)·(Tc + Tm) — the same thing when a miss first checks the cache. Read which model the question uses.)

def amat(hit_time, miss_rate, miss_penalty):
    return hit_time + miss_rate * miss_penalty

print("L1 only: ", amat(1, 0.05, 100), "ns")
print("L1 + L2: ", 1 + 0.05 * (10 + 0.20 * 100), "ns")
print("no cache:", 100, "ns")

L1 only:  6.0 ns
L1 + L2:  2.5 ns
no cache: 100 ns

A 95% hit rate turns 100 ns memory into a 6 ns average; adding an L2 brings it to 2.5 ns.

4. Cache mapping: where can a block go?

Main memory is divided into blocks; the cache into lines of the same size. Mapping decides which line(s) a block may occupy.

5. Splitting an address: tag | index | offset

• Offset bits = log₂(block size)
• Index bits = log₂(number of lines) for direct-mapped, log₂(number of sets) for set-associative, 0 for fully associative
• Tag bits = address bits − index − offset

Worked example. 32-bit addresses, 64 KB cache, 64-byte blocks.

import math

def split(address_bits, cache_bytes, block_bytes, ways):
    lines = cache_bytes // block_bytes
    sets = lines // ways
    offset = int(math.log2(block_bytes))
    index = int(math.log2(sets))
    tag = address_bits - index - offset
    return lines, sets, tag, index, offset

for name, ways in [("direct-mapped", 1), ("4-way set-assoc", 4), ("fully associative", 64 * 1024 // 64)]:
    lines, sets, tag, index, offset = split(32, 64 * 1024, 64, ways)
    print(f"{name:18} lines={lines} sets={sets:5}  tag={tag:2} index={index:2} offset={offset}")

direct-mapped      lines=1024 sets= 1024  tag=16 index=10 offset=6
4-way set-assoc    lines=1024 sets=  256  tag=18 index= 8 offset=6
fully associative  lines=1024 sets=    1  tag=26 index= 0 offset=6

Notice: more associativity → fewer sets → fewer index bits → more tag bits (and more comparators).

Tag memory size (a common follow-up): tag bits × number of lines. For the direct-mapped case: 16 × 1024 = 16,384 bits = 2 KB of tags (plus valid/dirty bits if the question includes them).

6. A working direct-mapped cache simulator

def simulate(addresses, lines=4, block=16):
    cache = [None] * lines            # stores the tag in each line
    hits = 0
    for a in addresses:
        blk = a // block
        idx, tag = blk % lines, blk // lines
        if cache[idx] == tag:
            hits += 1
            result = "hit"
        else:
            result = "miss" + ("" if cache[idx] is None else " (evict)")
            cache[idx] = tag
        print(f"addr {a:3} -> block {blk:2} line {idx} tag {tag}: {result}")
    print(f"hit ratio = {hits}/{len(addresses)} = {hits / len(addresses):.2f}")

simulate([0, 4, 8, 64, 0, 16, 64, 4])

addr   0 -> block  0 line 0 tag 0: miss
addr   4 -> block  0 line 0 tag 0: hit
addr   8 -> block  0 line 0 tag 0: hit
addr  64 -> block  4 line 0 tag 1: miss (evict)
addr   0 -> block  0 line 0 tag 0: miss (evict)
addr  16 -> block  1 line 1 tag 0: miss
addr  64 -> block  4 line 0 tag 1: miss (evict)
addr   4 -> block  0 line 0 tag 0: miss (evict)
hit ratio = 2/8 = 0.25

Addresses 0 and 64 are in blocks 0 and 4, which both map to line 0 in a 4-line direct-mapped cache — they keep evicting each other (conflict misses). A 2-way set-associative cache would hold both.

7. Types of misses (the 3 Cs)

8. Writes and replacement

• Write-through — write to cache and memory every time (simple, more memory traffic); usually with a write buffer.
• Write-back — write only to cache, mark the line dirty, write to memory when evicted (less traffic).
• Replacement (set-associative/fully associative): LRU (least recently used), FIFO, random.

Common mistakes

• Using the number of lines instead of sets for index bits in set-associative caches.
• Forgetting that fully associative has no index bits.
• Mixing up the two AMAT formulas — check whether the miss time already includes the cache check.
• Computing offset from the cache size instead of the block size.

Quick recap

• Hierarchy: registers → L1 → L2 → L3 → RAM → SSD/disk; caches work because of temporal and spatial locality.
• AMAT = hit time + miss rate × miss penalty (apply recursively for multi-level).
• Direct (1 place), fully associative (anywhere), k-way set-associative (k places in one set).
• Address = tag | index | offset; offset = log₂(block), index = log₂(lines or sets), tag = rest.
• Misses: compulsory, capacity, conflict. Write-through vs write-back; LRU replacement.