如何通过分块矩阵来提高缓存命中率？

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];
            }
        }
    }
}

上述代码使用了阻塞技术。我不太理解阻塞如何有助于提高性能？

- Max

---

我不能声称理解使用缓存的算法性能优化，但是Demaine教授在这个主题上有相当多的讲座。也许它们会有所帮助。 - MarcinKonowalczyk

Answer 1

是的，一个方向上的缓存命中次数会比另一个方向上多。

然而，诀窍在于将其分成足够小的块，以便在处理时可以“重用”它们。

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

如果缓存大小大于5行，则在处理该行时不会再有未命中。

如果缓存大小小于此值，则会出现更多未命中，因为行将互相挤占。在这种情况下，src将保留在缓存中作为更常用的对象，而dst则会被删除，从而在dst侧给我们带来16个未命中。5比17好：）

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

- Ivan

---

你能解释一下块大小是什么意思吗？实际上缓存中有块，对吧？这只是我们的表现形式。 - Max

块大小是您的算法中的blocksize。这是我们正在处理的子矩阵的大小。缓存中最小可缓存块称为缓存行。 - Ivan

Answer 2

这里最重要的方面是局部性，特别是对于你的例子空间局部性。简单来说，这意味着访问彼此靠近的数据。

每当访问矩阵的一个元素时，如果它还没有在缓存中，它总是会加载整个缓存行。例如，这个缓存行可以包含64字节或16个整数元素。如果您在缓存中不使用其他元素，则您的代码效率低下。

如果在访问之间加载了太多的数据，则缓存行将被驱逐。考虑从内部循环的第一次访问，它加载source[i]。内存中的下一个元素source[i + 1]在同一个缓存行上，并且已经被加载。但是，在整个内部循环完成之前，它只会在需要时才被使用。如果内部循环访问了太多的数据，则source[i + 1]将不再在缓存中。访问source[i]和source[i+1]之间的距离太大。

阻塞可以消除这种低效率。最内层循环比原来小得多，访问之间的距离缩短了。最内层循环处理的所有数据都适合于缓存中。

- Zulan