Joh*_*ith 4 c optimization cpu-cache
我正在尝试优化大型2D(井,1D处理为2D)字节数组的索引,以最大化来自相同高速缓存行的大小为64字节的连续查找次数.每次查找都与前一次相同,在水平和垂直之间交替.运动是正面的还是负面的可以被视为随机的(实际上它遵循Langton的蚂蚁规则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的蚂蚁sim？).我不能完全排除这种索引更有效的可能性(制定新索引可能是可以优化的,考虑缓存对我来说是新的,我可能做得很糟糕).
1)理智检查:我正在努力做到明智,是否可能有效？它会在不同的条件下工作吗？
2)Longshot:是否有一个神奇的gcc编译器标志为你重新排序索引,尝试优化2D阵列而不是1D？
3)我可以(或者我是否需要)尝试在CPU中保留某些缓存行吗？目前我假设最新的数据一直保留到被覆盖.
4)如果您有更好的解决方案,请描述一下.
64位linux,gcc,i5-2500k
编辑:事实证明:1)这种思维方式不合理,2)N/A,3)见接受答案,4)见接受答案
我没有看到最大化连续使用一个缓存行的理由.高速缓存不"一次一行"操作,并且与使用高速缓存中的任何行相比,重复使用一个高速缓存行通常没有优势.
更好的目标是最大化从L1缓存中的一行提供的访问次数,而不是需要从较慢的缓存或内存中获取.只要访问"命中"当前在缓存中的一行,我们就不关心它是哪个缓存行.
i5-2500K是Sandy Bridge处理器.Sandy Bridge L1数据高速缓存为32 KiB,是八路关联的,具有64字节高速缓存行.这意味着32,768字节的高速缓存有512行,它们被组织成64组,每组8行.每个内存地址都映射到一组,如下所示.在每个集合中,从最近在该集合中使用的行中保留八个高速缓存行.(替换算法至少是最近使用的,但它是一种有用的尝试,并且可能具有与最近最少使用的类似的结果.)
缓存查找以这种方式工作:
考虑行长度对这些缓存查找的影响.行长度为65,536字节时,数组元素a [i] [j]和[i + 1] [j]的地址相差65,536字节.这意味着它们在上述查找过程中的t值恰好相差1024,并且它们的s值相同.因此,它们映射到同一组.
一旦算法向上或向下移动超过八行,而不更改高速缓存行之外的列,正在使用的单个高速缓存集不能处理最近使用的九个高速缓存行.其中一个必须被驱逐.实际上,高速缓存大小是八行(512字节)而不是512行(32,768字节).
解决此问题的一种简单方法是填充数组,使得行长度为65,536 + p字节,对于某些填充量p.该阵列将分配额外的空间,并定义为比正常行更长的行.通常可以忽略额外的列.没有必要初始化它们; 我们不关心他们的内容,只关心他们对地址的影响.(或者,如果方便的话,它们可以用于补充数据.)
使用此填充,a [i] [j]和a [i + 1] [j]之间的距离为65,536 + p字节,因此t值的差值为1024 + p/64,s值的差异为p/64%64.例如,如果p为64或320,则s值的差异分别为1或5.
我建议测试9*64的p.任何64或更大的值将确保连续行中同一列中的数组元素映射到不同的缓存集.但是,问题中描述的算法在列和行中都会出现问题.因此,如果p很小,我们修复连续行映射到不同的缓存集可能会被列游荡所抵消,这会蜿蜒回到相同的缓存集.还应尝试其他p值.
这不是一个完整的问题解决方案,因为有许多因素会影响性能.
这可能没用，但可能很有趣。
您可以使用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% 确定它们有效。以 2 的幂为模进行换行很简单，只需对结果执行二进制 AND 操作即可。
Z 坐标的寻址很简单，只需将其添加到数组的基数即可。移动比在 (x, y) 空间中稍微复杂一些，但是如果将其与其他帖子中的想法（查找区域）结合起来，您甚至不需要移动（显然，除了在查找表的计算中） 。打包一个好的周边区域可能会更困难。但有一个不太好的周围区域变得微不足道：直接在 Z 空间中在两个方向上偏移 Z 坐标，并获取中间的所有内容（例如，从 Z-8 到 Z+7）。平均而言，这将模拟更少的步骤，因为它通常不是方形块，并且当前位置通常不在中间，但查找表中的索引将更容易计算。
编辑：最好采用对齐的块而不是范围，因为蚂蚁永远无法从未对齐范围的“部分”之一走到另一个“部分”（这些部分最多是对角连接的，所以它必须走到外面）。这也很简单，只需与 Z 坐标的最低有效位相与即可获得对齐块的开头。不过，查找表将需要那些最低有效位，因此它们必须成为索引的一部分。
我不认为这种方法会获胜。但这很有趣，国际海事组织。