[解決済み】512x512の行列の転置は、513x513の行列の転置よりずっと遅いのはなぜ？

質問

さまざまな大きさの正方形の行列について実験を行った結果、あるパターンが浮かび上がってきました。必ずと言っていいほど サイズの行列を転置すると 2^n の転置より遅い。 2^n+1 . の値が小さい場合 n となり、大きな違いはありません。

しかし、512の値では大きな差が生じます。(少なくとも私にとっては）。

免責事項：この関数は、要素のダブルスワップのため、実際には行列を転置していないことは知っていますが、それは何の違いもありません。

コードに従います。

#define SAMPLES 1000
#define MATSIZE 512

#include <time.h>
#include <iostream>
int mat[MATSIZE][MATSIZE];

void transpose()
{
   for ( int i = 0 ; i < MATSIZE ; i++ )
   for ( int j = 0 ; j < MATSIZE ; j++ )
   {
       int aux = mat[i][j];
       mat[i][j] = mat[j][i];
       mat[j][i] = aux;
   }
}

int main()
{
   //initialize matrix
   for ( int i = 0 ; i < MATSIZE ; i++ )
   for ( int j = 0 ; j < MATSIZE ; j++ )
       mat[i][j] = i+j;

   int t = clock();
   for ( int i = 0 ; i < SAMPLES ; i++ )
       transpose();
   int elapsed = clock() - t;

   std::cout << "Average for a matrix of " << MATSIZE << ": " << elapsed / SAMPLES;
}

変更 MATSIZE を使えば、サイズを変更することができます（当たり前か！）。ideoneに2つのバージョンを投稿しました。

• サイズ512 - 平均 2.46ミリ秒 - http://ideone.com/1PV7m
• サイズ 513 - 平均 0.75ミリ秒 - http://ideone.com/NShpo

私の環境（MSVS 2010、完全最適化）では、違いは同じようなものです。

• サイズ 512 - 平均 2.19ミリ秒
• サイズ 513 - 平均 0.57ミリ秒

なぜこのようなことが起こるのでしょうか？

解決方法は？

のAgner Fogが解説しています。 C++でソフトウェアを最適化する で、データがどのようにアクセスされ、キャッシュに保存されるかに還元されます。

用語や詳細情報については キャッシュに関するWikiエントリ ということですが、ここでは絞り込みます。

キャッシュの構成は セット と ライン . 一度に使用されるのは1セットだけで、その中に含まれる行はどれでも使用可能です。1行がミラーリングできるメモリに行数を掛けたものがキャッシュサイズになります。

あるメモリアドレスに対して、どのセットをミラーリングすればよいかは、以下の式で計算できます。

set = ( address / lineSize ) % numberOfsets

この種の式は、理想的には、各メモリアドレスが読まれる可能性が同じくらい高いので、セット全体に一様な分布を与えます（私は 理想的には ).

オーバーラップが発生する可能性があることは明らかです。キャッシュミスの場合、キャッシュ内のメモリが読み込まれ、古い値が置き換えられます。各セットにはいくつかの行があり、そのうち最も最近使用された行が、新しく読み込まれたメモリで上書きされることを覚えておいてください。

アグナーの例をなんとなく追ってみる。

各セットには4つの行があり、それぞれ64バイトを保持していると仮定します。まず、アドレス 0x2710 で、これはセット 28 . そして、アドレスの読み取りも試みます 0x2F00 , 0x3700 , 0x3F00 と 0x4700 . これらはすべて同じ集合に属しています。を読む前に 0x4700 このとき、セット内のすべての行が使用されているはずです。そのメモリを読み出すと、セット内の既存の行、つまり最初に 0x2710 . 問題は、（この例では）アドレスの読み取りが 0x800 を離した。これは クリティカルストライド (この例でも)です。

クリティカルストライドは、計算することもできます。

criticalStride = numberOfSets * lineSize

変数の間隔 criticalStride または、同じキャッシュラインを複数個で奪い合う。

これが理論の部分です。次に解説です（こちらもアグナー、間違えないようにしっかり追っています）。

64x64の行列（キャッシュによって効果が変わることを忘れずに）、8kbのキャッシュ、1セット4ライン、ラインサイズ64バイトと仮定する。各行には行列の要素のうち8個を格納できる（64ビット int ).

クリティカルストライドは2048バイトとなり、これは行列の4行に相当します（メモリ上では連続的です）。

28行目を処理しているとします。この行の要素を取り出して、28列目の要素と入れ替えようとしているのです。行の最初の 8 要素は 1 つのキャッシュラインを構成しますが、それらは 28 列の 8 つの異なるキャッシュラインに入ります。クリティカルストライドは 4 行間隔（1 列に連続した 4 要素）であることを忘れないでください。

列で要素16に到達すると（1セット＆ampあたり4キャッシュライン、4列間隔＝トラブル）、元0の要素がキャッシュから退避することになります。列の終わりに到達すると、それまでのキャッシュラインはすべて失われ、次の要素へのアクセス時に再読み込みが必要になります（行全体が上書きされます）。

クリティカルストライドの倍数でないサイズを指定すると、次のような問題が発生します。 完璧なシナリオ というのも、縦方向にクリティカルストライド分離れた要素を扱わなくなったため、キャッシュの再読み込み回数が極端に減ったからです。

もう一つの免責事項 - 説明に頭を抱えただけで、釘を刺したつもりですが、勘違いしているかもしれません。とにかく、私は次のような回答（確認）を待っているのです。 ミスティカル . :)