Associativity and conflict misses

In a cache with one slot per line, two busy lines that share a slot throw each other out again and again. Give every slot several ways and the problem mostly disappears, unless the rows of your table are exactly 4096 bytes apart. This lecture builds a set-associative cache and shows how a power-of-two row size can make 100% of the reads miss.

In the direct-mapped cache of the last topic every memory line has exactly one slot. If your program keeps using two lines that map to the same slot, say line 0 and line 8 in an 8-slot cache, then every read of one evicts the other, although the other seven slots may be empty. Nothing is wrong with the size of the cache: the lines are fighting for a place that is too small. A miss of this kind is called a conflict miss.

The fix is to group slots. Slots are collected into sets, and each slot inside a set is a way. A memory line belongs to one set, found by the same remainder as before, but it may sit in any way of that set. Two colliding lines now share a set with room for both. The number of sets follows from the sizes:

An address now splits into three parts. The offset is the byte inside the line. The set index says which set the line belongs to. The tag is the rest of the line number, and it is what the cache compares to see whether a way holds this line. The function below splits an address for a cache with 64-byte lines and 64 sets.

def split_address(address, line_bytes, n_sets):    line = address // line_bytes    return line // n_sets, line % n_sets, address % line_bytes1print(split_address(74565, 64, 64))

(18, 13, 5)

1. 1Tag, set index and offset: each is one integer division or remainder of the address.

Address 74565 is byte 5 of line 1165. Line 1165 goes to set 13 (1165 modulo 64), and 18 is what is left of the line number, the tag. Any line that has set 13 will compete for the eight ways of that set, whatever its tag.

When a set is full and a new line arrives, one of the lines has to go. The usual rule is LRU: evict the line that was used least recently. We can keep each set as a Python list ordered from the least recently used to the most recently used.

1. 1
   Find the setThe line number modulo the number of sets.
2. 2
   Look in every wayOn a hit, move the line to the most recently used end.
3. 3
   Add on a missPut the new line at the most recently used end.
4. 4
   Drop the oldestIf the set now holds more lines than ways, remove the first one.

Here is the whole cache. The run at the bottom reads two lines, addresses 0 and 256, that collide in a 256-byte cache with 64-byte lines, first with one way and then with two.

class SetAssocCache:    def __init__(self, size_bytes, line_bytes, ways):        self.line_bytes = line_bytes        self.ways = ways        self.n_sets = size_bytes // (line_bytes * ways)        self.sets = [[] for _ in range(self.n_sets)]        self.hits = 0        self.misses = 0    def access(self, address):        line = address // self.line_bytes        lines = self.sets[line % self.n_sets]        if line in lines:            lines.remove(line)            lines.append(line)1            self.hits += 1            return True        self.misses += 1        lines.append(line)        if len(lines) > self.ways:            lines.pop(0)2        return Falsefor ways in (1, 2):    cache = SetAssocCache(size_bytes=4 * 64, line_bytes=64, ways=ways)    flags = [cache.access(a) for a in [0, 256, 0, 256, 0, 256]]    print(ways, "way:", flags)

1 way: [False, False, False, False, False, False]
2 way: [False, False, True, True, True, True]

1. 1Moving a hit line to the end keeps the list in order: the first entry is always the least recently used.
2. 2The full set loses its first entry, the least recently used line.

With one way the two lines evict each other and all six reads miss. With two ways both lines fit in their set: after the first two cold misses, every read hits. Adding a way removed all the conflict misses of this pattern.

Now the trap. A table of 512 float64 columns has rows of exactly 4096 bytes. Reading one column means reading addresses 0, 4096, 8192 and so on. In our cache a set index is the line number modulo 64, and 4096 bytes is exactly 64 lines, so every one of those addresses has the same set index. The code prints the set of the first six rows for a row size of 4096 bytes and for 4160 bytes, which is 4096 plus one extra line.

n_sets = 64for row_bytes in (4096, 4160):    sets = [(i * row_bytes // 64) % n_sets for i in range(6)]    print(row_bytes, "->", sets)

4096 -> [0, 0, 0, 0, 0, 0]
4160 -> [0, 1, 2, 3, 4, 5]

With 4096-byte rows all the closes of a column fight for set 0. With 4160-byte rows they march through sets 0, 1, 2, 3 and so on, using the whole cache. The next code reads 96 closes twice and measures the miss rate for 1, 2, 4 and 8 ways.

def column_trace(n_rows, row_bytes, passes):    return [i * row_bytes for i in range(n_rows)] * passesdef miss_rates_by_ways(trace, size_bytes, line_bytes, ways_list):    rates = {}    for ways in ways_list:        cache = SetAssocCache(size_bytes, line_bytes, ways)        for address in trace:            cache.access(address)        rates[ways] = cache.misses / len(trace)    return ratesfor row_bytes in (4096, 4160):    print(row_bytes, miss_rates_by_ways(column_trace(96, row_bytes, 2), 32768, 64, [1, 2, 4, 8]))

4096 {1: 1.0, 2: 1.0, 4: 1.0, 8: 1.0}
4160 {1: 0.5, 2: 0.5, 4: 0.5, 8: 0.5}

The padded table misses only on the first pass: 0.5 of all reads, whatever the number of ways. The aliased table misses on every read, even with 8 ways, because 96 lines need 96 places and the set has 8. Worse, LRU always evicts the line you will read next in a cyclic pattern, so the second pass finds nothing. More ways would only help once they reach the number of lines.

The lab follows the lecture: the address split, the LRU cache, the two kinds of trace, the comparison by number of ways and the study on the real SPY table.

• Function · questionBuilds on
• split_address(address, line_bytes, n_sets)Which tag, set and offset does an address have?Integer division
• SetAssocCache(size_bytes, line_bytes, ways).access(address)Is this read a hit in an LRU cache with several ways?Sets of lines in LRU order
• conflict_trace(n_lines, line_bytes, n_sets, rounds)Which addresses all collide in one set?Plain arithmetic
• column_trace(n_rows, row_bytes, passes)Which addresses does reading a column touch?Plain arithmetic
• miss_rates_by_ways(trace, size_bytes, line_bytes, ways_list)How do more ways change the miss rate?SetAssocCache
• study(bars)What do rows 4096 bytes apart cost?column_tracemiss_rates_by_ways

Next topic: the cache now holds the right lines when they do not collide, but how long do lines stay useful? In Temporal locality and working sets you measure how soon a value is read again, and find the cache size at which a program starts to fit.