caching - 以 block 为单位拆分矩阵如何提高缓存命中率？

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 好 :)

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