我正在编写一个带有粒子-粒子相互作用的简单 N 体模拟。我注意到当我计算粒子之间的相对位置时，我的代码在执行较少的计算时实际上运行得更慢。
起初我尝试了直接的实现（为简单起见，假设是一维的）：
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
r_rel[i][j] = r[i]-r[j];
}
}
这就像填充 NxN 矩阵一样。这些循环对每个 r_rel 计算两次，事实上，r_rel[i][j] = -r_rel[j][i]. 因此，我尝试保留一些实现以下解决方案的计算：
for(int i=1; i<N; i++)
{
for(int j=0; j<i; j++)
{
r_rel[i][j] = r[i]-r[j];
r_rel[j][i] = -r_rel[i][j];
}
}
这样我实际上只计算了我的 NxN 相对位置矩阵中对角线下方的项。我预计代码会更快，因为它执行的计算较少，但是当我执行时，它的运行速度明显变慢。这怎么可能？谢谢！！
第一个循环r_rel以连续的内存顺序遍历，在继续下一行之前遍历每一行：它r_rel[i][j]在迭代j之前的每个值的同时访问i。
第二个循环遍历r_rel两个移动的访问点，一个以连续的内存顺序进行，然后通过矩阵的列进行，跨行跳转。后一种行为对缓存不利并且性能不佳。众所周知，沿列遍历行主数组对缓存性能不利。
缓存是昂贵的高性能内存，用于保存最近访问的数据或从内存中加载的数据的副本，以便在不久的将来使用。当程序以经常访问高速缓存中数据的方式使用内存时，它可能会受益于高速缓存的高性能。当程序经常访问不在缓存中的数据时，处理器必须访问普通内存中的数据，这比缓存慢得多。
缓存设计的典型特征包括：
aa…aaabbbcccccc。这六位c告诉我们这是缓存线中的哪个字节。(2 6 = 64。) 这三位b告诉我们这个字节必须进入哪个缓存集。这些a位与缓存行一起记录，记住它在内存中的位置。当一个进程r_rel[i][j]以连续的内存顺序工作时，每次访问 的成员时r_rel，它访问的成员要么是上次迭代中刚访问过的同一高速缓存行的一部分，要么是下一个高速缓存行的一部分。在前一种情况下，数据已经在缓存中，并且可以快速提供给处理器。在后一种情况下，它必须从内存中获取。（一些处理器已经启动了这个提取，因为它们在最近访问内存之前预取数据。它们被设计来这样做，因为这种内存访问是一种常见的模式。）
从上面可以看出，第一组代码必须为 中的每个缓存行执行一次缓存行加载r_rel。下面，我们将把这个数字与第二组代码的相似数字进行比较。
在第二组代码中，r_rel收益的一个用途与第一组代码相同，尽管它只遍历了数组的一半。对于r_rel[i][j]，它执行大约一半的第一个代码的缓存加载。由于沿对角线的一些低效使用，它执行了一些额外的加载，但我们可以忽略这一点。
然而，其他用途的r_rel，r_rel[j][i]是麻烦的。它通过r_rel.
这个问题没有给我们很多细节，所以我会补一些值来说明。假设 的元素r_rel每个是四个字节，并且N行或列中的元素数是 128 的倍数。还假设缓存是 32,768 字节，组织成 64 组，每组 8 行，每行 64 字节。使用这种几何结构，地址模 512 的余数（除法时的余数）确定必须将存储器分配给哪个高速缓存集。
因此，当r_rel[j][i]被访问时会发生什么，该地址周围的 64 字节内存被带入缓存并分配给特定的缓存集。当，当j递增时，该地址周围的内存被带入缓存并分配给特定的缓存集。这些是相同的缓存集。因为行是128个元素，每个元素是4个字节，所以正好相隔一行的两个元素之间的距离是128•4 = 512个字节，这与用于确定一行进入哪个缓存集的数字相同. 所以这两个元素被分配到同一个缓存集。
一开始没问题。缓存集有八行。不幸的是，代码继续迭代j。一旦j增加了八次，它就会访问 的第九个元素r_rel。由于高速缓存集只有八行，因此处理器必须从集合中删除前面的行之一。随着代码继续迭代j，更多的行被删除。最终，所有先前的行都被删除。当代码完成对j和 的迭代后i，它会返回到数组的开头附近。
回想一下，在第一组代码中，当r_rel[0][2]被访问时，它仍然在缓存中r_rel[0][1]。然而，在第二组代码中，r_rel[0][2]缓存早已不复存在。处理器必须再次加载它。
对于对 的访问r_rel[j][i]，第二组代码实际上没有从缓存中受益。它必须为每次访问从内存加载。由于在此示例中，每个缓存行中有 16 个元素（四字节元素，64 字节行），因此对于一半矩阵，它的内存访问次数大约是其 16 倍。
总共，如果整个数组中有x 条缓存线，第一组代码加载x 条缓存线，第二组代码加载大约x / 2 条缓存线用于r_rel[i][j]访问，大约x /2•16 = 8• x缓存线用于r_rel[i][j]访问，总共 8.5• x缓存线加载。
按列顺序遍历数组对于缓存性能来说很糟糕。
上面使用的示例数字。最灵活的一种是数组大小，N。我假设它是 64 的倍数。我们可以考虑一些其他值。如果它是 32 的倍数，则r_rel[j][i]和r_rel[j+1][i]将映射到不同的缓存集。但是，r_rel[j][i]和r_rel[j+2][i]映射到同一个集合。这意味着，经过 8 次迭代后j，每组中将只使用 4 行，因此还不需要驱逐旧行。不幸的是，这帮助很小，因为一旦i超过 16，代码就会迭代j足够多的值，以至于缓存集再次清空之前的行，因此每次循环都j必须加载它遇到的每个缓存行。
另一方面，设置N为 73 之类的值可能会减轻这种影响。当然，您不想仅仅为了适应计算机硬件而改变阵列的大小。然而，有一两件事可以做的就是在内存阵列的尺寸N由NP唯一的，即使N通过N使用元素。NP（代表“N Padded”）被选择以使行相对于缓存几何具有奇数大小。额外的元素只是浪费了。
这提供了一种快速更改程序的方法，以证明缓存效果使其变慢，但它通常不是首选解决方案。另一种方法是平铺对数组的访问。不是迭代i并遍历j整个数组，而是将数组分割成一定大小的瓦片，A逐行B。两个外循环遍历所有图块，两个内循环遍历每个图块内的数组元素。
A和B被选择，以便在内部循环进行时，一个图块的所有元素都将保留在缓存中。对于上面的样本数，A并且B必须为 8 或更少，因为在一个缓存集中只能保存阵列的 8 行。（可能还有其他考虑因素会使最佳平铺大小稍微小一些。或者，对于不同的元素大小或 的值N，最佳平铺大小可能更大。）
请注意，平铺会在编写代码时引发一些问题。当处理对角线上的瓷砖时，代码将处理来自同一瓷砖内两个点的元素。在处理对角线上的图块时，代码将从一个图块内的一个点和另一个图块内的转置点处理元素。这可能会影响操作数组索引的代码和内部循环的边界。对于对角线瓷砖，内部循环看起来与您的j < i条件相似，处理三角形。对于非对角瓷砖，内循环将处理一个完整的正方形（或矩形，如果A和B不同）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句