如何在块中拆分矩阵可以改善缓存命中？

Question

我试图理解缓存和矩阵中的阻塞的概念.我试图转置一个矩阵.

我理解行方式内存布局的概念,所以当我尝试逐行访问数据时,我得到的是,与列方式相比,我获得的缓存未命中次数更少.

  for( int i = 0; i < n; i++ )

    for( int j = 0; j < n; j++ )

      destination[j+i*n] = source[i+j*n];

因此对于源矩阵,我将有更少的缓存未命中,而对于目标,我将有更多的缓存未命中.

---

这是带阻塞的代码

for (int i = 0; i < n; i += blocksize) {
    for (int j = 0; j < n; j += blocksize) {
        // transpose the block beginning at [i,j]
        for (int k = i; k < i + blocksize; ++k) {
            for (int l = j; l < j + blocksize; ++l) {
                dst[k + l*n] = src[l + k*n];
            }
        }
    }
}

上面的代码使用了阻塞技术.我不太明白阻塞如何帮助提高性能？

Answer 1

是的，一侧的缓存命中率会高于另一侧。

不过，诀窍是将其分成足够小的碎片，以便在加工时可以“重复使用”它们。

例如，在上面的示例中，我们将在 src 矩阵上出现 1 次缓存未命中，在 dst 大小上出现 4 次缓存未命中（我选择了 4 个元素的缓存行大小和 4 个元素的块大小，但这只是巧合）。

如果缓存大小大于 5 行，我们在处理该行时将不会再出现任何未命中的情况。

如果缓存大小小于此值，则会出现更多未命中，因为行将相互挤压。在这种情况下，随着更多的使用，src 将保留在缓存中，而 dst 的将被删除，从而使 dst 端有 16 次未命中。5 看起来比 17 更好:)

因此，通过将块的大小控制得足够低，我们可以降低缓存未命中率。