1

我正在尝试找到一种方法来为使用最近对算法（暂时是蛮力）的应用程序缓存我的元素数组。根据阻塞算法的缓存性能和优化论文，它说：

阻塞是一种提高内存层次结构有效性的通用优化技术。通过在更快的层次结构中重用数据，它减少了平均访问延迟。它还减少了对层次结构较慢级别的引用数量。因此，阻塞优于诸如预取之类的优化，它隐藏了延迟但不会降低内存带宽需求。这种减少对于多处理器来说尤其重要，因为内存带宽通常是系统的瓶颈。分块已被证明对线性代数中的许多算法很有用。

该论文给出了一个矩阵乘法代码，并将其修改为减少缓存未命中的阻塞：

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是阻塞因子，但我们如何确定呢？有没有一种通用的方法来找到 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

总结一下：

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

提前致谢！

4

1 回答 1

4

第一个问题：

如果没有在您打算优化的机器上实际测试它，就没有确定B的简单方法。话虽如此，您可能可以通过一些实验找到一些“对大多数系统都有益”的数字（大约 12-15 年前我在这类事情上做了很多工作），我发现使用大约 8-16KB 块有效很好。在“只运行所有内存”和“通过块工作”之间的效果非常显着，如果你从非常小的块开始，当你开始变大时，你会看到一些很大的改进。然后“返回”下降，直到你达到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并且循环类似。ibmax(length(P), i+B-1)jb

编辑：

缓存将自行决定将哪些数据保存在缓存中，您几乎无法更改此处发生的内容。您可以更改的是您正在处理的数据块。

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

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

如果我们一次处理一点数组，以块为单位，我们可以在每个循环中处理一个B大小的数组 - 其中B元素使用的空间不会超过缓存的容量。所以jb循环不会抛出循环的数据ib（反之亦然）。这意味着每个内部循环的运行速度都快得多（我已经看到执行速度快了 3 倍以上，而且那是在本来应该是“好”的代码上）。

于 2013-04-29T09:43:05.630 回答