[解決済み] 2048x2048と2047x2047の配列の乗算では、なぜ大きなパフォーマンスヒットがあるのでしょうか？

質問

私はいくつかの行列の乗算のベンチマークを作成しています。 なぜMATLABは行列の乗算で速いのですか？

さて、もう一つ問題があって、2048x2048の行列を2つ掛けるとき、C#と他で大きな違いがあります。2047x2047の行列だけを乗算してみると、正常のようです。比較のために他のものも追加しました。

1024x1024 - 10秒です。

1027x1027 - 10秒

2047x2047 - 90秒。

2048x2048 - 300秒。

2049x2049 - 91 秒。(更新)

2500x2500 - 166 秒

2k×2kのケースで3分半の差です。

2dim配列を使って

//Array init like this
int rozmer = 2048;
float[,] matice = new float[rozmer, rozmer];

//Main multiply code
for(int j = 0; j < rozmer; j++)
{
   for (int k = 0; k < rozmer; k++)
   {
     float temp = 0;
     for (int m = 0; m < rozmer; m++)
     {
       temp = temp + matice1[j,m] * matice2[m,k];
     }
     matice3[j, k] = temp;
   }
 }

どのように解決するのですか？

これはおそらく、L2 キャッシュの競合と関係があります。

matice1 のキャッシュミスは、順次アクセスされるため、問題ではありません。 しかし matice2 については、もし完全な列が L2 に収まるなら（つまり matice2[0, 0], matice2[1, 0], matice2[2, 0] ... などにアクセスしたとき、何も退避されない）、matis2 についてもキャッシュミスの問題は発生しないのです。

キャッシュの仕組みをもう少し詳しく説明すると、変数のバイトアドレスが X の場合、そのキャッシュラインは (X >> 6) & (L - 1) となります。ここで、L はキャッシュの総ライン数です。L は常に 2 のべき乗です。 6 はキャッシュラインの標準サイズである 2^6 == 64 bytes から来ています。

さて、これは何を意味するのでしょうか？つまり、アドレスXとアドレスYがあるとして (X >> 6) - (Y >> 6) が L で割り切れる場合、それらは同じキャッシュラインに格納されるということです（つまり、大きな 2 のべき乗）。

さて、あなたの問題に戻りますが、2048 と 2049 の違いは何でしょうか。

2048があなたのサイズであるとき。

とすると、(&matice2[x,k] &matice2[y,k]) の差は、2048 * 4 (float のサイズ) で割り切れることになります。つまり、2の大きな累乗です。

このように、L2 のサイズによっては、多くのキャッシュラインの競合が発生し、L2 のごく一部しか列の保存に利用できないため、実際には列全体をキャッシュに保存することができず、パフォーマンスが低下することになります。

サイズが 2049 の場合、その差は 2049 * 4 で、2の累乗ではありません。したがって、競合は少なく、カラムは安全にキャッシュに収まります。

さて、この理論を検証するために、いくつかのことを行うことができます。

matice2 配列を matice2 [razmor, 4096] のように割り当て、razmor = 1024, 1025 または任意のサイズで実行すると、以前と比較して非常に悪いパフォーマンスが表示されるはずです。これは、すべての列を強制的に整列させ、互いに衝突させるためです。

次に、matice2 [razmor, 4097]を試して、任意のサイズで実行すると、はるかに良いパフォーマンスが表示されるはずです。