c - 使用循环平铺转置大型二维矩阵没有性能提升

Question

使用平铺方法(缓存感知)转置大小为 1 gb 的全局二维方矩阵/数组在单线程执行中与普通转置方法相比没有性能提升。不讨论使用 AVX、SSE(SIMD) 或任何其他缓存不经意转置算法的转置加速 ( http://supertech.csail.mit.edu/papers/FrigoLePr12.pdf )

#include <stdio.h>
#include <sys/time.h>
#define SIZE 16384
float a[SIZE][SIZE], b[SIZE][SIZE];

void testNormalTranspose() {
int i, j, k, l;
b[0][9999] = 1.0;
for (i=0; i<SIZE; i++)
    for (j=0; j<SIZE; j++)
      a[i][j] = b[j][i];
}

void testTiledTranspose(){
    int i, j, k, l;
    b[0][9999] = 1.0;
    int blocksize = 16;
    for (i=0; i<SIZE; i+= blocksize) {
        for (j=0; j<SIZE; j+=blocksize) {
            for (int ii = i;ii <i + blocksize; ++ii) {
                for (int jj = j; jj < j + blocksize; ++jj) {
                    a[ii][jj] = b[jj][ii];
                }

            }
        }   
    }  
}

int main()
{
    struct timeval t1, t2;
    /*
      gettimeofday(&t1, NULL);
      testNormalTranspose();
      gettimeofday(&t2, NULL);
      printf("Time for the Normal transpose  is %ld milliseconds\n",
             (t2.tv_sec - t1.tv_sec)*1000 + 
             (t2.tv_usec - t1.tv_usec) / 1000);
    */
      gettimeofday(&t1, NULL);
      testTiledTranspose();
      gettimeofday(&t2, NULL);
      printf("Time for the Tiled transpose  is %ld milliseconds\n",
             (t2.tv_sec - t1.tv_sec)*1000 + 
             (t2.tv_usec - t1.tv_usec) / 1000);
      printf("%f\n", a[9999][0]);
}

Answer 1

如果数据被重复使用，循环平铺会有所帮助。如果您使用某个元素 SIZE 次，则最好使用它 SIZE 次，然后才继续处理下一个元素。

不幸的是，转置 2D 矩阵你没有重用矩阵 a 或 b 的任何元素。更重要的是，由于在循环中您混合了行和列访问(即 a[i][j] = b[j][i])，您将永远不会同时对 a 和 b 数组进行单位步幅内存访问时间，但只有其中一个。

因此，在这种情况下，平铺并不是那么有效，但如果出现以下情况，即使使用“随机”内存访问，您仍然可能会有一些性能改进:

• 您现在访问的元素与您之前访问的元素在同一缓存行上并且
• 该缓存行仍然可用。

因此，要看到任何改进，这种“随机”访问的内存占用必须适合您系统的缓存。基本上这意味着您必须仔细选择 blocksize，您在示例中选择的 16 可能在一个系统上运行得更好而在另一个系统上运行更差。

以下是我的计算机针对 2 block 大小和 SIZE 4096 的不同幂的结果:

---------------------------------------------------------------
Benchmark                        Time           CPU Iterations
---------------------------------------------------------------
transpose_2d              32052765 ns   32051761 ns         21
tiled_transpose_2d/2      22246701 ns   22245867 ns         31
tiled_transpose_2d/4      16912984 ns   16912487 ns         41
tiled_transpose_2d/8      16284471 ns   16283974 ns         43
tiled_transpose_2d/16     16604652 ns   16604149 ns         42
tiled_transpose_2d/32     23661431 ns   23660226 ns         29
tiled_transpose_2d/64     32260575 ns   32259564 ns         22
tiled_transpose_2d/128    32107778 ns   32106793 ns         22
fixed_tile_transpose_2d   16735583 ns   16729876 ns         41

如您所见，blocksize 8 的版本最适合我，性能几乎翻了一番。

以下是 SIZE 4131 和 3 block 大小的幂的结果:

---------------------------------------------------------------
Benchmark                        Time           CPU Iterations
---------------------------------------------------------------
transpose_2d              29875351 ns   29874381 ns         23
tiled_transpose_2d/3      30077471 ns   30076517 ns         23
tiled_transpose_2d/9      20420423 ns   20419499 ns         35
tiled_transpose_2d/27     13470242 ns   13468992 ns         51
tiled_transpose_2d/81     11318953 ns   11318646 ns         61
tiled_transpose_2d/243    10229250 ns   10228884 ns         65
fixed_tile_transpose_2d   10217339 ns   10217066 ns         67

关于 16384 尺寸问题。我无法重现它，即我仍然看到大矩阵的相同增益。请注意，16384 * 16384 * sizeof(float) 产生 4GB，这可能会暴露一些系统问题...