使用環路平鋪

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，這可能會暴露一些的系統問題...