使用环路平铺

Question

移调大小1 GB与平铺方法（高速缓存感知）的全球2D方阵/阵列大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]); 
} 

Answer 1

环路平铺有助于情况下，数据正被重用。如果使用SIZE元素次数，则最好使用SIZE次数，然后才能继续下一个元素。

遗憾的是，转置2D矩阵你不重用既不的基质中的任何元件，也不是B。更重要的是，由于在循环中混合了行和列的访问（即a [i] [j] = b [j] [i]），所以在a和b数组中都不会获得单位步跨内存访问时间，但只限于其中一个。

所以，在这种情况下平铺是不是有效的，但你仍然可能有一些性能方面的改进甚至“随机”的内存访问，如果：

• 您现在访问的元素是在同一高速缓存行与之前访问的元素AND
• 缓存行仍然可用。

因此，要查看任何改进，此“随机”访问的内存占用量必须适合您系统的缓存。基本上这意味着你必须仔细选择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/7778 ns6793 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（浮动），使4GB，这可能会暴露一些的系统问题...