6

我正在尝试优化大型 2D（好吧，将 1D 视为 2D）字节数组的索引，以最大限度地从 64 字节大小的同一高速缓存行中连续查找的数量。每个查找都与前一个查找相差一个，在水平和垂直移动之间交替。运动是积极的还是消极的都可以被视为随机的（实际上它遵循兰顿的蚂蚁规则字符串 RLR，但我不认为该信息是严格相关的），这意味着路径混乱地蜿蜒曲折，倾向于在同一大区域停留一段时间相当长的时间。

在一次正常索引一行的情况下，水平移动可能在同一缓存行内，但垂直移动永远不会。我的解决方案是在 8x8 块中索引数组，这是一个示例，就好像缓存行大小为 9 和 6x6 数组一样：

 24 25 26 33 34 35
 21 22 23 30 31 32
 18 19 20 27 28 39
  6  7  8 15 16 17
  3  4  5 12 13 14
  0  1  2  9 10 11

它在 3x3 块中表现不佳，但它应该允许缓存行被更多地重用：

  .
  .
  .
 56 57 58 59 60 61 62 63
 48 49 50 51 52 53 54 55
 40 41 42 43 44 45 46 47
 32 33 34 35 36 37 38 39
 24 25 26 27 28 29 30 31
 16 17 18 19 20 21 22 23
  8  9 10 11 12 13 14 15
  0  1  2  3  4  5  6  7 ...

我用普通索引和这个索引进行了基准测试，这个索引比较慢。这可能是因为它必须做更多的工作才能计算出所需的索引（它处于一个紧密的循环中，请参阅此处了解正常的索引版本：如何优化这个 Langton's ant sim?）。我不能完全排除这种索引更有效的可能性（制定新索引可能是可优化的，考虑缓存对我来说是新的，我可能做的很糟糕）。

1）健全性检查：我正在尝试做的事情是否明智，它可能会奏效吗？它会在不同的条件下工作吗？

2) Longshot：是否有一个神奇的 gcc 编译器标志可以为您重新排序索引，以尝试优化 2D 数组而不是 1D？

3) 我可以（或者我需要）做些什么来尝试在 CPU 中保留某些高速缓存行吗？目前我假设最新的数据被保留直到被覆盖。

4）如果您有更好的解决方案，请描述它。

64 位 Linux、gcc、i5-2500k

编辑：事实证明：1）这种思维方式是不明智的，2）不适用，3）见接受的答案，4）见接受的答案

4

2 回答 2

8

我没有看到最大化连续使用一个高速缓存行的理由。高速缓存不是“一次一行”运行的，与使用高速缓存中的任何一条高速缓存相比，重复使用一条高速缓存线通常没有优势。

更好的目标是最大化从 L1 缓存中的一行提供的访问次数，而不是需要从较慢的缓存或内存中获取。只要访问“命中”当前缓存中的一行，我们就不会关心它是哪个缓存行。

i5-2500K 是 Sandy Bridge 处理器。Sandy Bridge L1 数据高速缓存为 32 KiB，具有 8 路关联，具有 64 字节高速缓存行。这意味着 32,768 字节的高速缓存有 512 行，它们被组织成 64 组，每组 8 行。每个内存地址都映射到一组，如下所示。在每个集合中，保留了八个缓存行，来自该集合中最近使用的行。（替换算法不是最近最少使用的，但它是一种有用的尝试，可能与最近最少使用的结果相似。）

缓存查找以这种方式工作：

  • 给定一个字节地址 x，让 t = floor(x/64)（由于缓存行大小）。
  • 让 s = t % 64（选择集合）。
  • 检查集合 s 以查看它是否包含地址 x 处的字节。

考虑行长度对这些缓存查找的影响。对于 65,536 字节的行长度，数组元素 a[i][j] 和 a[i+1][j] 的地址相差 65,536 字节。这意味着它们在上述查找过程中的 t 值正好相差 1024，并且它们的 s 值相同。因此，它们映射到同一个集合。

一旦算法向上或向下移动超过八行，而不更改缓存行之外的列，正在使用的单个缓存集将无法处理九个最近使用的缓存行。其中之一必须被驱逐。实际上，缓存大小是 8 行（512 字节）而不是 512 行（32,768 字节）。

解决此问题的一种简单方法是填充数组，使行的长度为 65,536+p 个字节，填充量为 p。该数组将被分配额外的空间，并使用比正常更长的行来定义。通常可以忽略额外的列。无需初始化它们；我们不关心它们的内容，只关心它们对地址的影响。（或者，如果对程序方便，它们可以用于补充数据。）

有了这个padding，a[i][j]和a[i+1][j]的距离是65536+p字节，所以t值的差是1024+p/64，s值的差是p/64 % 64。例如，如果 p 为 64 或 320，则 s 值的差异分别为 1 或 5。

我建议为 p 测试 9*64。任何 64 或更大的值都将确保连续行中同一列中的数组元素映射到不同的缓存集。但是，问题中描述的算法在列和行中徘徊。因此，如果 p 很小，我们将连续行映射到不同缓存集的修复可能会被蜿蜒回同一个缓存集的列漂移所否定。p 的其他值也应该尝试。

这并不是一个完整的问题解决方案，因为有许多因素会影响性能。

于 2013-07-13T11:07:14.863 回答
3

这可能没用，但可能很有趣。

您可以使用Z 顺序寻址。它将对齐的 8x8 块映射到缓存行，因此只要您停留在一个对齐的 8x8 块内，您就始终使用相同的缓存行。但是当你从一个街区穿越到下一个街区时，有时会发生奇怪的事情。

从 (x, y) 对生成 Z 顺序地址有点烦人：

static uint Interleave(uint x, uint y)
{
    y = (y | (y << 1)) & 0x00FF00FF;
    y = (y | (y << 2)) & 0x0F0F0F0F;
    y = (y | (y << 4)) & 0x33333333;
    y = (y | (y << 8)) & 0x55555555;

    x = (x | (x << 1)) & 0x00FF00FF;
    x = (x | (x << 2)) & 0x0F0F0F0F;
    x = (x | (x << 4)) & 0x33333333;
    x = (x | (x << 8)) & 0x55555555;

    return x | (y << 1);
}

（这是 C#，应该很容易转换为 C）

如果你有一个支持 PDEP 的 CPU，那么就不会那么烦人了，到目前为止，只有 Haswell。

但是您可能不需要经常这样做。您可以直接递增或递减 Z 顺序地址的 x 或 y 部分（可以推广到将任何一对常量 (c1, c2) 添加到 Z 地址，如果它们都是非零则需要更多代码），像这样：（那些不做任何边界检查）

static uint IncX(uint z)
{
    uint xsum = (z | 0xAAAAAAAA) + 1;
    return (xsum & 0x55555555) | (z & 0xAAAAAAAA);
}

static uint IncY(uint z)
{
    uint ysum = (z | 0x55555555) + 2;
    return (ysum & 0xAAAAAAAA) | (z & 0x55555555);
}

static uint DecX(uint z)
{
    uint xsum = (z & 0x55555555) - 1;
    return (xsum & 0x55555555) | (z & 0xAAAAAAAA);
}

static uint DecY(uint z)
{
    uint ysum = (z & 0xAAAAAAAA) - 2;
    return (ysum & 0xAAAAAAAA) | (z & 0x55555555);
}

你甚至可以加入一些边界检查。我有饱和增量/减量的例程，但我只有大约 90% 的把握它们可以工作。以二的幂为模包装是微不足道的，只需对结果进行二进制与。

Z 坐标的寻址很简单，只需将其添加到数组的底部即可。移动比 (x, y) 空间中的移动稍微复杂一些，但是如果您将其与其他帖子（查找区域）中的想法结合起来，您甚至不需要移动（显然，除了在该查找表的计算中） . 打包一个好的周边区域可能更难。但是有一个不太好的周边区域变得微不足道：在两个方向上直接在 Z 空间中偏移 Z 坐标并取其间的所有内容（例如，从 Z-8 到 Z+7）。这将平均一次模拟更少的步骤，因为它通常不是方形块并且当前位置通常不在中间，但是查找表的索引会更容易计算。

编辑：最好采用对齐的块而不是范围，因为蚂蚁永远不能从未对齐范围的“部分”之一走到另一个“部分”（这些部分充其量是对角连接的，所以它必须走出去）。这也很容易，只需将 Z 坐标中的最低有效位与最低有效位相加即可获得对齐块的开始。查找表将需要那些最低有效位，因此它们必须成为索引的一部分。

我不希望这种方法获胜。但这很有趣，IMO。

于 2013-07-13T14:23:09.427 回答