如何从用户模式代码中通用地检测缓存行关联性？

Question

我正在为valgrind中的cachegrind/callgrind工具组建一个小补丁，该补丁将使用完全通用的代码自动检测CPU指令和缓存配置（目前只有x86/x64自动配置，其他架构不提供CPUID类型配置给非特权代码）。此代码需要完全在非特权上下文中执行，即纯用户模式代码。它还需要在非常不同的POSIX实现之间进行移植，因此无法使用grokking /proc/cpuinfo，因为我们的某些目标系统没有这样的东西。

使用100％通用的POSIX代码可以检测CPU频率、缓存数量、大小甚至缓存行大小，其中没有任何CPU特定的操作码（只有许多合理的假设，例如，如果没有内存或寄存器依赖关系停顿，则将两个数字相加可能会在单个周期中执行）。这部分相当简单。

我询问StackOverflow的原因是如何检测给定缓存的缓存行关联性，这并不那么简单。关联性是缓存中可以包含来自主存储器的给定缓存行的位置数量。我可以看到L1缓存的关联性可以被检测出来，但是L2缓存呢？肯定会受到L1关联性的影响吧？

我知道这可能是一个无法解决的问题。但我将其提交到StackOverflow上，希望有人知道我不知道的东西。请注意，如果我们在这里失败，我将仅仅硬编码一个默认的四路关联性，假设这不会对结果产生太大影响。

谢谢， Niall

- Niall Douglas

---

考虑发起悬赏。 - 0x90

我所做的是在BlackBerry转型时开始了开源库发布流程。总有一天，我们会完全通用的配置检测库公开发布，届时我会在这里提供链接。该库将关联性硬编码为4。希望有一天会有人提交更好的补丁。- Niall - Niall Douglas

Answer 1

这里有一个方案： 创建一个具有步长S和访问的唯一元素数量N的内存访问模式。测试首先触碰每个唯一元素，然后通过多次访问相同的模式（非常大量），测量访问每个元素的平均时间。

例如：对于S = 2和N = 4，地址模式将是0,2,4,6,0,2,4,6,0,2,4,6,...。

考虑一个多级缓存层次结构。您可以做出以下合理的假设： 1.第n+1级高速缓存的大小是第n个缓存的二倍幂。 2.第n+1级缓存的关联性也是第n级缓存关联性的二倍幂。

这两个假设使我们能够说，如果两个地址映射到n+1级缓存中的相同组（比如L2），则它们必须映射到n级缓存（比如L1）中的相同组。

假设您知道L1、L2缓存的大小。您需要找到L2缓存的关联性。 1.设置步长S = L2缓存的大小（以便每个访问都映射到L2和L1中的同一组）。 2.变化N（按2的幂变化）。

您将获得以下几个阶段： 1.阶段1：N <= L1的关联性。 （所有访问都在L1中命中） 2.阶段2：L1的关联性 < N <= L2的关联性（所有访问都在L1中未命中，但在L2中命中） 3.阶段3：N > L2的关联性（所有访问都未在L2中命中）

因此，如果您根据N（当S = L2的大小）绘制平均访问时间，则会看到一个类似于步进图的情况。最低步骤的结束给出L1的关联性。下一步将给出L2的关联性。

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

- Neha Karanjkar

---

这基本上就是我尝试过的。不幸的是，在最近的英特尔芯片上，预取器会发现您在以固定间隔步进，并预取行，从而破坏结果。然后我尝试随机排列步长以混淆预取器，但即使在那里，英特尔也可以跟踪四个单独的步长流，所以它打败了我。 - Niall Douglas

我认为在大多数英特尔处理器上，可以关闭硬件预取。 - Subodh

关闭硬件预取：https://dev59.com/63RA5IYBdhLWcg3w6SRH - Subodh

那是一个仅限内核模式的指令。我问的是仅限用户模式的。而且它只在Sandy Bridge上有效。Ivy Bridge及以后就没有效果了。此外，最初的问题是关于完全通用代码的。 - Niall Douglas

Answer 2

你能写一个只访问同一组中的行的小程序吗？然后你可以增加访问之间的堆栈距离，当执行时间显著下降时，你可以假设已经达到了关联度。

这可能不是非常稳定，但也许可以提供一些线索，不知道。希望它能有所帮助。

- Maxime Chéramy

Answer 3

对于x86平台，您可以使用cpuid：

有关详细信息，请参见http://www.intel.com/content/www/us/en/processors/processor-identification-cpuid-instruction-note.html。

您需要类似以下的内容：

long _eax,_ebx,_ecx,_edx;
long op = func;

asm ("cpuid"
    : "=a" (_eax),
    "=b" (_ebx),
    "=c" (_ecx),
    "=d" (_edx)
    : "a" (op)
);

然后根据上面提到的链接中的文档使用信息。

- Shay

---

请再次阅读问题。我的问题是如何在不使用任何特定于CPU的内容的情况下完成此操作。 - Niall Douglas