使用缓存局部性提高C函数性能？

Question

我必须在表示为2d数组的矩阵中找到对角线差异,函数原型是

int diagonal_diff(int x[512][512])

我必须使用2d数组,数据是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;

但是这种算法不断访问列,行,列,行等,这使得缓存的使用效率低下.

有没有办法改善我的功能？

Answer 1

编辑:为什么面向块的方法更快？我们通过确保无论是逐行还是按列迭代来利用CPU的数据缓存,我们保证整个块都适合缓存.

例如,如果您有一个32字节的缓存行和一个int4字节的缓存行,则可以将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.在我的机器上,8与block_size1的相比,导致最大的加速(2.5倍)(与整个矩阵的原始迭代相比,约为5倍).在block_size理想情况下应cache_line_size_in_bytes/sizeof(int).