高速缓存高效矩阵转置程序？

小编典典

高速缓存高效矩阵转置程序？

algorithm

因此转置矩阵的明显方法是使用：

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

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

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

但是我想要一些可以利用局部性和缓存阻止功能的东西。我一直在查找它，找不到能够做到这一点的代码，但是我被告知这应该是对原始内容的非常简单的修改。有任何想法吗？

编辑：我有一个2000x2000矩阵，我想知道如何使用两个for循环来更改代码，基本上将矩阵分成我单独转置的块，例如2x2块或40x40块，并查看哪个块大小最有效。

Edit2：矩阵按列主顺序存储，也就是说对于矩阵

a1 a2    
a3 a4

存储为a1 a3 a2 a4。

阅读 348

2020-07-28

共1个答案

小编典典

您可能需要四个循环-
两个循环遍历这些块，然后另外两个循环执行单个块的转置复制。为了简单起见，假设块大小可以划分矩阵的大小，我想是这样的，尽管我想在信封的背面绘制一些图片以确保：

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

还有一个重要的重要见解，就是实际上有一个可以忽略缓存的算法（请参阅 http://en.wikipedia.org/wiki/Cache-
oblivious_algorithm，以该确切问题为例）。“忽略缓存”的非正式定义是，您无需尝试调整任何参数（在本例中为块大小）即可达到良好/最佳的缓存性能。在这种情况下，解决方案是通过将矩阵递归地分成两半，然后将两半移到它们在目标位置的正确位置来进行转置。

无论实际上缓存大小是多少，此递归都可以利用它。我希望与您的策略相比，会有一些额外的管理开销，这实际上是使用性能实验来直接跳到缓存真正开始的递归点，并且不再走下去。另一方面，您的性能实验可能会给您一个答案，该答案适用于您的计算机，但不适用于您客户的计算机。

2020-07-28