与普通转置方法相比，使用分块方法（缓存感知）转置大小为1 gb的全局2D方阵/数组在单线程执行中没有性能提升。没有讨论使用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]);
}
最佳答案
循环平铺有助于防止重复使用数据。如果您使用元素SIZE次，则最好使用它SIZE次，然后再继续下一个元素。
不幸的是，转置2D矩阵既不会重用矩阵a或b的任何元素。更重要的是，由于在循环中您混合使用行和列访问（即a [i] [j] = b [j] [i]），所以您将永远不会在相同的a和b数组上获得跨步内存访问时间，但只有其中之一。
因此，在这种情况下，平铺并不是那么有效，但是即使在以下情况下，即使使用“随机”内存访问，您仍然可以在性能上有所提高：
您现在访问的元素与您先前访问的元素在同一行中，并且
该缓存行仍然可用。
因此，要查看任何改进，此“随机”访问的内存空间必须适合您系统的缓存。基本上，这意味着您必须仔细选择blocksize，在示例中选择的16在一个系统上可能效果更好，而在另一个系统上效果更差。
这是我的计算机针对2块大小和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块大小的幂的结果：---------------------------------------------------------------
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空间，这可能会暴露一些系统问题...