Cache Replacement, Writes and Access Patterns

Replacement policies

When a miss occurs in a full set, one block must be evicted. (A direct-mapped cache has no choice.)

No policy wins on every sequence. On the block sequence 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 with a 3-block fully associative cache, LRU gets 2 hits and FIFO 3:

def hits(sequence, capacity, policy):
    cache, count = [], 0
    for b in sequence:
        if b in cache:
            count += 1
            if policy == "LRU":
                cache.remove(b)
                cache.append(b)
            continue
        if len(cache) == capacity:
            cache.pop(0)                      # LRU and FIFO both evict the front of the list
        cache.append(b)
    return count

seq = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
for policy in ("LRU", "FIFO"):
    print(policy, hits(seq, 3, policy), "hits")

LRU 2 hits
FIFO 3 hits

Write policies

When the CPU writes a word that is in the cache:

When the CPU writes a word that is not in the cache:

• Write-allocate (fetch on write): bring the block into the cache, then write. Usually paired with write-back.
• No-write-allocate (write around): write directly to memory without loading the block. Usually paired with write-through.

Timing models vary from question to question, so set them up carefully. A common one: with write-through, every write costs a memory access, so for a fraction w of writes and hit ratio h for reads, the average time is (1 − w)[h·T_c + (1 − h)(T_c + T_m)] + w·T_m. With write-back, a miss may need to write a dirty block back first, so the miss penalty becomes T_m × (1 + fraction of evicted blocks that are dirty).

Access patterns: row-major versus column-major

C stores a 2-D array row by row (row-major): a[i][j] and a[i][j + 1] are adjacent in memory. Looping in the same order as the layout uses every byte of each block loaded; looping across it can miss on every access.

Take int a[64][64] (4-byte ints, 16 KB in all) starting at address 0, and a direct-mapped cache with 64-byte blocks (16 ints per block):

def count_misses(addresses, cache_bytes, block_bytes):
    lines = cache_bytes // block_bytes
    tags, misses = [None] * lines, 0
    for a in addresses:
        block = a // block_bytes
        if tags[block % lines] != block:
            tags[block % lines] = block
            misses += 1
    return misses

N, size = 64, 4
row_major = [(i * N + j) * size for i in range(N) for j in range(N)]   # for i: for j: a[i][j]
col_major = [(i * N + j) * size for j in range(N) for i in range(N)]   # for j: for i: a[i][j]
for cache_kb in (4, 16):
    print(f"{cache_kb:2} KB cache: row-wise loop {count_misses(row_major, cache_kb * 1024, 64)} misses, "
          f"column-wise loop {count_misses(col_major, cache_kb * 1024, 64)} misses")

 4 KB cache: row-wise loop 256 misses, column-wise loop 4096 misses
16 KB cache: row-wise loop 256 misses, column-wise loop 256 misses

• Row-wise: one miss per block, then 15 hits: 4096 / 16 = 256 misses, whatever the cache size.
• Column-wise with a 4 KB cache: consecutive accesses are 256 bytes apart, so each touches a new block, and by the time the loop returns to a block (the next column), 64 other blocks have been loaded into the 64-line cache, and those that share its line have evicted it: every access misses, 4096 misses.
• Column-wise with a 16 KB cache: the whole array fits, so each block is loaded only once: 256 misses again.

This is why loop order matters so much for performance, and why GATE likes these questions: compute the stride, the number of blocks touched, and whether they survive until reuse.

Practice questions