Cache memory

A cache keeps copies of recently used memory blocks. When the processor asks for an address, the cache must answer one question fast: is that block here? (A hit, or else a miss: fetch it from the level below.)

Splitting the address

With blocks of B bytes, a cache of L lines, and S sets, an address splits into three fields:

Each line stores a valid bit and the tag of the block it holds. A hit means: the line is valid and its tag matches.

address_bits, block, lines, ways = 16, 16, 8, 2
sets = lines // ways
offset_bits = block.bit_length() - 1
index_bits = sets.bit_length() - 1
tag_bits = address_bits - index_bits - offset_bits
print("offset", offset_bits, "bits, index", index_bits, "bits, tag", tag_bits, "bits")

address = 0x1234
offset = address & (block - 1)
index = (address >> offset_bits) & (sets - 1)
tag = address >> (offset_bits + index_bits)
print(hex(address), "-> tag", tag, " set", index, " offset", offset)

Where may a block go?

• Direct-mapped: each block has exactly one possible line (block number mod lines). Simple and fast, but two blocks that map to the same line throw each other out again and again (conflict misses).
• Set-associative: lines are grouped into sets of k (k-way). A block may go in any line of its set; all k tags are compared at once. 4- to 16-way is common.
• Fully associative: one set; a block may go anywhere. Fewest conflicts, but every tag must be compared.

When a set is full, a replacement policy chooses the block to throw out, usually the least recently used (LRU).

Try the same addresses with each kind of placement:

Addresses 0 and 16 fall in blocks 0 and 4, which share line 0 of this direct-mapped cache. Switch to 2-way and the conflict disappears.

lines, block = 4, 4
cache = [None] * lines              # the block number held by each line
result = ""
for address in [0, 4, 16, 0, 8, 20, 4, 0]:
    b = address // block
    line = b % lines
    if cache[line] == b:
        result += "H"
    else:
        result += "M"
        cache[line] = b
print("hits and misses:", result)
print("hits:", result.count("H"), "of", len(result))

Writes

• Write-through: every write goes to the cache and to memory. Simple, but slow without a write buffer.
• Write-back: writes go only to the cache, and a dirty bit marks the block; it is written to memory when it is thrown out. Less traffic; used by most caches today.

Misses come in three kinds, the "three Cs": compulsory (the first use of a block), capacity (the cache is too small) and conflict (too many blocks compete for one set).

Mark lesson complete