我不知道如何在非常低的级别优化缓存性能,考虑缓存行大小或关联性.这不是你可以在一夜之间学到的东西.考虑到我的程序将在许多不同的系统和架构上运行,我认为无论如何都不值得.但是,我可能会采取一些措施来减少缓存缺失.
这是我的问题的描述:
我有一个3d数组的整数,表示空间中的点,如[x] [y] [z].每个尺寸都是相同的尺寸,所以它就像一个立方体.从那里我需要制作另一个3d数组,其中这个新数组中的每个值都是7个参数的函数:原始3d数组中的相应值,以及在空间中"触摸"它的6个索引.我现在不担心立方体的边角.
这就是我在C++代码中的意思:
void process3DArray (int input[LENGTH][LENGTH][LENGTH],
int output[LENGTH][LENGTH][LENGTH])
{
for(int i = 1; i < LENGTH-1; i++)
for (int j = 1; j < LENGTH-1; j++)
for (int k = 1; k < LENGTH-1; k++)
//The for loops start at 1 and stop before LENGTH-1
//or other-wise I'll get out-of-bounds errors
//I'm not concerned with the edges and corners of the
//3d array "cube" at the moment.
{
int value = input[i][j][k];
//I am expecting crazy cache misses here:
int posX = input[i+1] [j] [k];
int negX = input[i-1] [j] [k];
int posY = input[i] [j+1] [k];
int negY = input[i] [j-1] [k];
int posZ = input[i] [j] [k+1];
int negZ = input[i] [j] [k-1];
output [i][j][k] =
process(value, posX, negX, posY, negY, posZ, negZ);
}
}
但是,似乎LENGTH足够大,当我获取参数时,我会得到大量的缓存未命中process.是否有更好的缓存方式,或者更好的方式来表示除3d数组以外的数据？
如果你有时间回答这些额外的问题,我是否必须考虑LENGTH的价值？就像LENGTH是20还是100而不是10000一样,它是不同的.另外,如果我使用的不是整数,我可能还需要做其他事情,比如64字节的结构吗？
@ ildjarn:
对不起,我不认为生成我传递的数组的代码很process3DArray重要.但如果确实如此,我想知道原因.
int main() {
int data[LENGTH][LENGTH][LENGTH];
for(int i = 0; i < LENGTH; i++)
for (int j = 0; j < LENGTH; j++)
for (int k = 0; k < LENGTH; k++)
data[i][j][k] = rand() * (i + j + k);
int result[LENGTH][LENGTH][LENGTH];
process3DArray(data, result);
}
这里有类似问题的答案:https://stackoverflow.com/a/7735362/6210(由我!)
优化多维数组遍历的主要目的是确保您访问数组,以便您倾向于重用从前一个迭代步骤访问的缓存行.要只访问一次数组的每个元素,只需按内存顺序访问(就像在循环中一样).
由于您正在执行比简单元素遍历(访问元素加上6个邻居)更复杂的事情,因此您需要分解遍历,以便不会一次访问太多缓存行.由于缓存抖动主要是遍历j和遍历k,因此您只需要修改遍历,以便一次访问块而不是一次访问行.
例如:
const int CACHE_LINE_STEP= 8;
void process3DArray (int input[LENGTH][LENGTH][LENGTH],
int output[LENGTH][LENGTH][LENGTH])
{
for(int i = 1; i < LENGTH-1; i++)
for (int k_start = 1, k_next= CACHE_LINE_STEP; k_start < LENGTH-1; k_start= k_next; k_next+= CACHE_LINE_STEP)
{
int k_end= min(k_next, LENGTH - 1);
for (int j = 1; j < LENGTH-1; j++)
//The for loops start at 1 and stop before LENGTH-1
//or other-wise I'll get out-of-bounds errors
//I'm not concerned with the edges and corners of the
//3d array "cube" at the moment.
{
for (int k= k_start; k<k_end; ++k)
{
int value = input[i][j][k];
//I am expecting crazy cache misses here:
int posX = input[i+1] [j] [k];
int negX = input[i-1] [j] [k];
int posY = input[i] [j+1] [k];
int negY = input[i] [j-1] [k];
int posZ = input[i] [j] [k+1];
int negZ = input[i] [j] [k-1];
output [i][j][k] =
process(value, posX, negX, posY, negY, posZ, negZ);
}
}
}
}
这样做可以确保您不会通过以面向块的方式访问网格来破坏缓存(实际上,更像是由缓存行大小限制的以胖列为导向的时尚).它并不完美,因为在列之间存在跨越缓存行的重叠,但您可以调整它以使其更好.
最重要的事情你已经拥有了。如果您使用 Fortran，那么您的做法就完全错误了，但那是另一回事了。你所拥有的权利是，你正在内部循环中沿着内存地址最接近的方向进行处理。一次内存读取（超出缓存）将提取多个值，对应于 k 的一系列相邻值。在循环内，缓存将包含 i,j 中的一些值；i+/-1、j 和 i,j+/-1 中的类似数字。所以你基本上有五个不相交的内存部分处于活动状态。对于较小的 LENGTH 值，这些仅是内存的 1 或 3 个部分。根据缓存构建方式的本质，您的活动集中可以拥有超过这么多不相交的内存部分。
我希望 process() 很小，并且是内联的。否则这可能微不足道。此外，它还会影响您的代码是否适合指令缓存。
由于您对性能感兴趣，因此初始化五个指针（您只需要一个用于 value、posZ 和 negZ），然后在循环内使用 *(p++) 几乎总是更好。
input[i+1] [j] [k];
要求编译器生成 3 个加法和两个乘法，除非你有一个非常好的优化器。如果您的编译器对寄存器分配特别懒，您还会获得四次内存访问；否则一。
*inputIplusOneJK++
要求一个添加和一个内存引用。