c++ - 如何确定缓存的阻塞因子

Question

我正在尝试找到一种方法来为使用最近对 算法(目前是蛮力)的应用程序缓存我的元素数组。根据The Cache Performance and Optimization of Blocked Algorithm纸上写着:

Blocking is a general optimization technique for increasing the effectiveness of a memory hierarchy. By reusing data in the faster level of the hierarchy, it cuts down the average access latency. It also reduces the number of references made to slower levels of the hierarchy. Blocking is thus superior to optimization such as prefetching, which hides the latency but does not reduce the memory bandwidth requirement. This reduction is especially important for multiprocessors since memory bandwidth is often the bottleneck of the system. Blocking has been shown to be useful for many algorithms in linear algebra.

论文给出了一个矩阵乘法代码，修改为blocking以减少cache misses:

for kk = 1 to N by B
  for j = 1 to N by B
    for i = 1 to N
      for k = kk to min(kk + B-1, N)
         r = X[i,k];  // register allocated
         for j = jj to min(jj + B-1, N)
           Z[i,j] += r * Y[k,j];

这里，B 是blocking factor 但我们如何确定呢？有没有通用的方法来找到 cpu 缓存可以处理的特定限制？可能不是所有的 cpu 都有相同的缓存。通用程序说:

• 首先是重组代码以阻止那些进行重用的循环。
• 其次是选择最大化局部性的分块因子。

最近对算法(蛮力)是:

minDist = infinity
for i = 1 to length(P) - 1
  for j = i + 1 to length(P)
    let p = P[i], q = P[j]
    if dist(p, q) < minDist:
      minDist = dist(p, q)
      closestPair = (p, q)
return closestPair

总结:

• 如何在不必手动测试特定 CPU 缓存大小的限制的情况下优化 B 因子。有没有办法用C语言返回当前可用的缓存？
• 如何优化使用一维数组的最近对算法？我的意思是，应该存储和重用哪些元素，因为它是一个包含 x、y 坐标的结构元素的一维数组，并且每个点都必须与所有其他点进行比较(让我们继续使用蛮力算法)。

提前致谢!

Answer 1

第一个问题:

如果不在您打算优化的机器上进行实际测试，就没有确定 B 的简单方法。话虽如此，您可能可以通过一些实验找到一些“对大多数系统都有利”的数字(大约 12-15 年前我在这类事情上做了很多工作)，我发现使用大约 8-16KB block 的东西有效很好。 “只遍历所有出现的内存”和“遍历 block ”之间的效果非常显着，如果你从非常小的 block 开始，当你开始变大时，你会看到一些很大的改进。然后“返回”下降，直到您达到 B 大到您回到开始位置的水平(丢弃良好的缓存以获取其他您在它之前不会使用的东西被扔掉了)。

我非常确定，如果您为代码选择 B 的“大小”，并测试您获得的性能，并且绘制图表，您可能会如果绘制“花费的时间”(或倒置的浴缸，如果绘制“每单位时间处理的项目数”)，会发现它看起来像一个“浴缸”。只需在浴缸的“平坦”部分找到一些点即可。但是，请在几台不同的机器上尝试一下，以确保您在所有(或至少大多数)机器上都处于“平坦位”。

对于你的第二个问题，是这样的:

minDist = infinity
for i = 1 to length(P) - 1 by B
  for j = i + 1 to length(P) by B
    for ib = i to i+B-1
      for jb = j to j+B-1
       let p = P[ib], q = P[jb]
       if dist(p, q) < minDist:
         minDist = dist(p, q)
         closestPair = (p, q)
return closestPair

如果 length(P) 不是 B 的倍数，处理最后几个元素需要一些额外的工作，所以不用 i +B-1 在 ib 循环中你可能需要 max(length(P), i+B-1) 和类似的 jb 循环。

编辑:

缓存将自行决定将哪些数据保存在缓存中，您几乎无法改变这里发生的事情。您可以更改的是您正在处理的数据 block 。

“阻塞”的关键是将正在处理的数据保留在 (L1) 缓存中。

假设整个数据锁有 100000 个元素，每个元素有 4 个字节，所以大约 400KB。这不适合任何现代处理器的 L1 高速缓存，因为它最多为 64KB，通常为 32KB。因此，当我们使用 i 遍历项目时，j 循环将通过加载数组的后面部分来“丢弃”所有良好的 L1 缓存内容。当然，当 j 循环在下一次开始时，当前缓存中的数据都没有用，因为它们都是数组的高位索引。

如果我们改为一次处理一点数组，以 block 为单位，我们可以在每个循环中处理 B 大小的数组 - 其中 B 元素不会占用超过缓存所能容纳的空间。所以 jb 循环不会丢弃 ib 循环的数据(反之亦然)。这意味着每个内部循环的运行速度都明显加快(我已经看到执行速度提高了 3 倍以上，而且这是在已经被认为是“好”的代码上)。