通过缓存局部性提高 C 函数性能？

Question

我必须找到表示为二维数组的矩阵中的对角线差异，函数原型是

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

我必须使用二维数组，数据为 512x512。这是在 SPARC 机器上测试的：我当前的计时是 6 毫秒，但我需要低于 2 毫秒。

示例数据：

[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 字节的缓存行，而 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 1 相比，8 带来最大的速度提升 (2.5 倍)（与整个矩阵的原始迭代相比，约 5 倍）。 block_size 理想情况下应为 cache_line_size_in_bytes/sizeof(int)。

Answer 2

如果您有像 intel MKL 这样好的矢量/矩阵库，也可以尝试矢量化方式。

在matlab中非常简单：
结果 = sum(sum(abs(xx')));

我也在matlab中重现了Hans的方法和MSN的方法，结果是：

Elapsed time is 0.211480 seconds.  (Hans)

Elapsed time is 0.009172 seconds.  (MSN)

Elapsed time is 0.002193 seconds.  (Mine)

Answer 3

通过一项微小的更改，您可以让循环仅在所需的索引上运行。我刚刚更改了 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]);
    }
}