使用缓存局部性提高C函数性能？
我必须在表示为二维数组的矩阵中找到对角线差，函数原型为
int diagonal_diff(int x[512][512])我必须使用二维数组，数据是512x512。这是在SPARC机器上测试的:我当前的计时是6ms，但我需要低于2ms。
示例数据：
[3][4][5][9]
[2][8][9][4]
[6][9][7][3]
[5][8][8][2]区别在于：
|4-2| + |5-6| + |9-5| + |9-9| + |4-8| + |3-8| = 2 + 1 + 4 + 0 + 4 + 5 = 16为了做到这一点，我使用了以下算法：
int i,j,result=0;
for(i=0; i<4; i++)
for(j=0; j<4; j++)
result+=abs(array[i][j]-[j][i]);
return result;但是这种算法一直在访问列、行、列、行等，这使得缓存的使用效率很低。
有什么方法可以改善我的功能吗？
回答 3
Stack Overflow用户
发布于 2011-10-12 12:44:15
编辑:为什么面向块的方法更快？我们利用CPU的数据缓存，确保无论我们是逐行还是按列迭代一个块，我们都能保证整个块都能放入缓存中。
例如，如果您有一个32字节的缓存线，而一个int是4个字节，那么您可以将一个8x8的int矩阵放入8个缓存线。假设您有足够大的数据缓存，您可以按行或按列迭代该矩阵，并确保不会颠簸缓存。考虑它的另一种方式是，如果你的矩阵适合缓存，你可以以任何你想要的方式遍历它。
如果你有一个更大的矩阵，比如说512x512，那么你需要调整你的矩阵遍历，这样你就不会颠簸缓存。例如，如果您以与矩阵布局相反的顺序遍历矩阵，则几乎总是会错过所访问的每个元素的缓存。
面向块的方法可确保在CPU必须刷新该缓存行之前，只对最终要访问的数据进行缓存未命中。换句话说，调整到缓存线大小的面向块的方法将确保您不会颠簸缓存。
因此，如果您正在尝试针对正在运行的机器的缓存线大小进行优化，您可以迭代块形式的矩阵，并确保每个矩阵元素只访问一次：
int sum_diagonal_difference(int array[512][512], int block_size)
{
int i,j, block_i, block_j,result=0;
// sum diagonal blocks
for (block_i= 0; block_i<512; block_i+= block_size)
for (block_j= block_i + block_size; block_j<512; block_j+= block_size)
for(i=0; i<block_size; i++)
for(j=0; j<block_size; j++)
result+=abs(array[block_i + i][block_j + j]-array[block_j + j][block_i + i]);
result+= result;
// sum diagonal
for (int block_offset= 0; block_offset<512; block_offset+= block_size)
{
for (i= 0; i<block_size; ++i)
{
for (j= i+1; j<block_size; ++j)
{
int value= abs(array[block_offset + i][block_offset + j]-array[block_offset + j][block_offset + i]);
result+= value + value;
}
}
}
return result;
}您应该尝试使用block_size的各种值。在我的机器上，与block_size为1相比，8带来了最大的速度提升(2.5倍)(与整个矩阵的原始迭代相比~5倍)。理想情况下，block_size应该是cache_line_size_in_bytes/sizeof(int)。
Stack Overflow用户
发布于 2012-12-12 19:01:47
如果你有一个很好的向量/矩阵库，比如英特尔MKL，也可以试试矢量化的方法。
在matlab中很简单: result =sum(sum(abs(x-x‘)；
我还在matlab中重现了Hans的方法和MSN的方法，结果是：
Elapsed time is 0.211480 seconds. (Hans)
Elapsed time is 0.009172 seconds. (MSN)
Elapsed time is 0.002193 seconds. (Mine)Stack Overflow用户
发布于 2011-10-12 11:41:36
通过一个小的改变，你可以让你的循环只在你想要的索引上运行。我刚刚更改了j循环初始化。
int i, j, result = 0;
for (i = 0; i < 4; ++i) {
for (j = i + 1; j < 4; ++j) {
result += abs(array[i][j] - array[j][i]);
}
}https://stackoverflow.com/questions/7734693
复制相似问题
腾讯云开发者
