c - 您一般如何从用户模式代码中检测缓存行关联性？

Question

我正在为 the cachegrind/callgrind tool in valgrind 打一个小补丁它将自动检测，使用完全通用的代码、CPU 指令和缓存配置(目前只有 x86/x64 自动配置，其他架构不向非特权代码提供 CPUID 类型配置)。此代码将需要完全在非特权上下文中执行，即纯用户模式代码。它还需要在非常不同的 POSIX 实现之间可移植，所以 grokking/proc/cpuinfo 不会做，因为我们的目标系统之一没有这样的东西。

检测 CPU 的频率、缓存的数量、它们的大小，甚至缓存行大小都可以使用 100% 通用的 POSIX 代码来完成，它没有任何 CPU 特定的操作码(只是很多合理的假设，比如因为将两个数字加在一起，如果没有内存或寄存器依赖性停顿，可能会在一个周期内执行)。这部分相当简单。

有什么不那么简单，也是我问 StackOverflow 的原因，是如何检测给定缓存的缓存行关联性？关联性是缓存中有多少位置可以包含来自主存储器的给定缓存行。我可以看到可以检测到 L1 缓存关联性，但是 L2 缓存？ L1 结合性肯定会妨碍吗？

我明白这可能是一个无法解决的问题。但我把它扔到 StackOverflow 上，希望有人知道我不知道的事情。请注意，如果我们在这里失败了，我将简单地以四种方式的关联性默认值进行硬编码，假设它不会对结果产生巨大影响。

谢谢，
尼尔

Answer 1

这是一个方案:

具有步幅为 S 的内存访问模式，访问的唯一元素数 = N。测试首先接触每个唯一元素，然后通过非常大次访问相同模式来测量访问每个元素的平均时间。

示例:对于 S = 2 和 N = 4，地址模式将为 0,2,4,6,0,2,4,6,0,2,4,6,...

考虑一个多级缓存层次结构。您可以做出以下合理假设:

• 第n+1级缓存的大小是第n级缓存大小的两倍
• 第n+1个缓存的关联度也是第n个缓存的关联度的2倍幂。

这两个假设让我们可以说，如果两个地址映射到第 n+1 个缓存(比如 L2)中的同一个集合，那么它们必须映射到第 n 个缓存(比如 L1)中的同一个集合。

假设您知道 L1、L2 缓存的大小。 需要找到二级缓存的关联性。

• 设置步幅 S = L2 缓存的大小(这样每次访问都映射到 L2 和 L1 中的同一组)
• 改变 N(按 2 的幂)

你得到以下制度:

• 方案 1: N <= L1 的结合性。 (所有访问 L1 中的 HIT)
• 规则 2:L1 的关联性 < N <= L2 的关联性(所有访问在 L1 中未命中，但在 L2 中命中)
• 规则 3:N > L2 的结合性(L2 中的所有访问都未命中)

因此，如果您绘制平均访问时间与 N 的关系(当 S = L2 的大小时)，您将看到阶梯状图。最低步骤的末尾给出了 L1 的结合律。下一步为您提供 L2 的结合性。

您可以在 L2-L3 之间重复相同的过程，依此类推。如果有帮助，请告诉我。通过改变内存访问模式的步长来获取缓存参数的方法类似于 LMBENCH 基准测试所使用的方法。我不知道 lmbench 是否也推断出结合性。