相联度与冲突缺失

在每行只有一个槽位的缓存里，共用一个槽位的两条热点行会一次又一次地把对方挤出去。给每个槽位多几条“路”，问题基本就消失了，除非你表的行间距恰好是 4096 字节。本讲搭建一个组相联缓存，并说明为什么 2 的幂的行大小会让 100% 的读取都未命中。

在上一主题的直接映射缓存里，每条内存行恰好只有一个槽位。如果程序不断使用两条映射到同一个槽位的行，比如 8 个槽位的缓存里的第 0 行和第 8 行，那么读其中一条就会把另一条挤出去，哪怕其余七个槽位都是空的。问题不在缓存的大小：这些行在争一个太小的位置。这样的缺失叫作冲突缺失。

办法是把槽位分组。槽位被归入若干组，组内的每个槽位叫一条路。一条内存行属于某一个组，用和以前一样的取余求出，但它可以放进该组的任意一路。于是互相冲突的两条行共用一个有两个位置的组。组数由各个大小决定：

地址现在分成三部分。偏移是行内的字节位置；组索引说明这条行属于哪个组；标签是行号剩下的部分，缓存靠比较它来判断某一路里装的是不是这条行。下面的函数为 64 字节行、64 个组的缓存拆分一个地址。

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. 1标签、组索引和偏移，各自都是对地址做一次整数除法或取余。

地址 74565 是第 1165 行的第 5 个字节。第 1165 行进入第 13 组（1165 对 64 取模），行号剩下的 18 就是标签。凡是落在第 13 组的行，不管标签是什么，都要争这一组的八条路。

当一个组已满而又来了新行，就得有一条行离开。常用的规则是LRU：替换最近最少使用的那条。我们可以把每个组存成一个 Python 列表，按从最久未用到最近使用的顺序排列。

1. 1
   找到组行号对组数取模。
2. 2
   查每一路命中就把这条行移到最近使用的一端。
3. 3
   未命中就加入把新行放在最近使用的一端。
4. 4
   丢弃最旧的如果组里的行比路数多，就删掉最前面的那条。

这就是完整的缓存。最后的运行读两条行，地址 0 和 256，它们在 256 字节、64 字节行的缓存里冲突，先用一路，再用两路。

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. 1把命中的行移到末尾，列表就保持有序：第一项永远是最近最少使用的。
2. 2满了的组会丢掉第一项，也就是最近最少使用的那条行。

一路时两条行互相挤掉，六次读全部未命中。两路时两条行都放得进它们的组：最初两次冷缺失之后，每次读都命中。多加一路，就消除了这个访问模式里所有的冲突缺失。

陷阱来了。一张有 512 列 float64 的表，每行恰好 4096 字节。读一列就是读地址 0、4096、8192 等等。在我们的缓存里，组索引是行号对 64 取模，而 4096 字节恰好是 64 条缓存行，所以这些地址的组索引全都一样。代码打印行大小为 4096 字节和 4160 字节（即 4096 再加一条缓存行）时前六行所在的组。

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]

行大小为 4096 字节时，一列里所有收盘价都在争第 0 组。行大小为 4160 字节时，它们依次落在第 0、1、2、3……组，用上了整个缓存。下面的代码把 96 个收盘价读两遍，并测量 1、2、4、8 路时的缺失率。

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}

加了填充的表只在第一遍未命中：占全部读取的 0.5，与路数无关。对齐的表每次读都未命中，哪怕有 8 路，因为 96 条行需要 96 个位置，而这个组只有 8 个。更糟的是，在循环访问模式里 LRU 总是把你接下来要读的那条行替换掉，所以第二遍什么都找不到。只有路数增加到行数那么多，多加路才有用。

实验沿着本讲的顺序走：拆分地址、LRU 缓存、两种访问轨迹、按路数比较，最后是对真实 SPY 表的研究。

• 函数 · 问题依赖
• split_address(address, line_bytes, n_sets)地址的标签、组和偏移是什么？整数除法
• SetAssocCache(size_bytes, line_bytes, ways).access(address)在多路 LRU 缓存里这次读取是否命中？按 LRU 顺序排列的行组
• conflict_trace(n_lines, line_bytes, n_sets, rounds)哪些地址全部撞在同一个组里？简单算术
• column_trace(n_rows, row_bytes, passes)读一列会碰到哪些地址？简单算术
• miss_rates_by_ways(trace, size_bytes, line_bytes, ways_list)多加几路缺失率怎么变？SetAssocCache
• study(bars)行距 4096 字节要付出多少代价？column_tracemiss_rates_by_ways

下一个主题：不冲突时缓存现在能留住正确的行，但一条行能保持有用多久？在时间局部性与工作集里，你要测量一个值多快会被再次读取，并找出程序开始“装得下”的缓存大小。