131

行列の乗算でMATLABが非常に高速である理由で前述したように、行列の乗算のベンチマークを作成してい ます。

ここで別の問題があります。2つの2048x2048行列を乗算する場合、C＃と他の行列には大きな違いがあります。2047x2047の行列だけを乗算しようとすると、正常に見えます。比較のために他にもいくつか追加しました。

1024x1024-10秒。

1027x1027-10秒。

2047x2047-90秒。

2048x2048-300秒。

2049x2049-91秒。（アップデート）

2500x2500-166秒

これは、2kx2kの場合の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;
   }
 }
4

10 に答える 10

63

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

matice1のキャッシュミスは、順次アクセスされるため、問題にはなりません。ただし、matice2の場合、列全体がL2に収まる場合（つまり、matice2 [0、0]、matice2 [1、0]、matice2 [2、0] ...などにアクセスすると、何も削除されません）、問題はありません。 matice2でもキャッシュミス。

次に、変数のバイトアドレスがXの場合、そのキャッシュラインよりもキャッシュの動作を詳しく説明します（X >> 6）＆（L-1）。ここで、Lはキャッシュ内のキャッシュラインの総数です。Lは常に2の累乗です。6は、2 ^ 6==64バイトがキャッシュラインの標準サイズであるという事実に由来します。

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

ここで問題に戻ると、2048と2049の違いは何ですか。

2048があなたのサイズの場合：

＆matice2 [x、k]と＆matice2 [y、k]を使用すると、差（＆matice2 [x、k] >> 6）-（＆matice2 [y、k] >> 6）は2048 * 4（サイズフロートの）。つまり、2の大きな累乗です。

したがって、L2のサイズによっては、キャッシュラインの競合が多くなり、L2のごく一部のみを使用して列を格納するため、実際には列全体をキャッシュに格納できないため、パフォーマンスが低下します。 。

サイズが2049の場合、差は2049 * 4であり、2の累乗ではないため、競合が少なくなり、列がキャッシュに安全に収まります。

この理論をテストするために、できることがいくつかあります。

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

次に、matice2 [razmor、4097]を試して、任意のサイズで実行すると、パフォーマンスが大幅に向上するはずです。

于 2011-05-19T17:58:09.167 に答える
21

おそらくキャッシュ効果。行列の次元が2の累乗であり、キャッシュサイズも2の累乗であるため、L1キャッシュのごく一部しか使用できず、処理速度が大幅に低下します。単純な行列の乗算は、通常、データをキャッシュにフェッチする必要があるために制約されます。タイリング（またはキャッシュを無視するアルゴリズム）を使用して最適化されたアルゴリズムは、L1キャッシュをより有効に活用することに重点を置いています。

他のペア（2 ^ n-1,2 ^ n）の時間を計ると、同様の効果が見られると思います。

より完全に説明すると、matice2 [m、k]にアクセスする内側のループでは、matice2 [m、k]とmatice2 [m + 1、k]が2048 * sizeof（float）だけ互いにオフセットされている可能性があります。したがって、L1キャッシュ内の同じインデックスにマップします。N-wayアソシアティブキャッシュを使用すると、通常、これらすべてに対して1〜8個のキャッシュロケーションがあります。したがって、これらのアクセスのほとんどすべてがL1キャッシュの削除をトリガーし、低速のキャッシュまたはメインメモリからデータをフェッチします。

于 2011-05-19T15:31:57.193 に答える
16

これは、CPUキャッシュのサイズに関係している可能性があります。行列行列の2行が収まらない場合は、RAMから要素を交換する時間が失われます。追加の4095要素は、行が収まらないようにするのに十分な場合があります。

あなたの場合、2047 2dマトリックスの2行は16KBのメモリ内にあります（32ビットタイプを想定）。たとえば、64KBのL1キャッシュ（バス上のCPUに最も近い）がある場合、一度に少なくとも4行（2047 * 32）をキャッシュに収めることができます。行が長くなると、行のペアを16KBを超えてプッシュするパディングが必要になると、問題が発生し始めます。また、キャッシュを「見逃す」たびに、別のキャッシュまたはメインメモリからデータをスワップインすると処理が遅れます。

私の推測では、さまざまなサイズのマトリックスで見られる実行時間の変動は、オペレーティングシステムが使用可能なキャッシュをどれだけ効果的に利用できるかによって影響を受けます（一部の組み合わせは問題があります）。もちろん、これはすべて私の側の大幅な単純化です。

于 2011-05-19T15:26:00.460 に答える
11

Louis Brandyは、この問題を正確に分析する2つのブログ投稿を作成しました。

より多くのキャッシュの狂気と計算パフォーマンス-いくつかの興味深い統計を使用した初心者のケーススタディであり、動作をより詳細に説明しようとしていますが、実際にはキャッシュサイズの制限に帰着します。

于 2011-05-19T21:29:53.277 に答える
5

より大きなサイズで時間が減少していることを考えると、特に問題のある行列サイズの2の累乗では、キャッシュの競合が発生する可能性が高くなりませんか？私はキャッシュの問題の専門家ではありませんが、キャッシュ関連のパフォーマンスの問題に関する優れた情報はここにあります。

于 2011-05-19T16:34:01.610 に答える
4

アレイに垂直にアクセスしているためmatice2、キャッシュの内外でさらに多くのスワップが行われます。[k,m]配列を斜めにミラーリングして、の代わりにを使用して配列にアクセスできるようにする[m,k]と、コードの実行速度が大幅に向上します。

これを1024x1024マトリックスでテストしたところ、約2倍の速度です。2048x2048マトリックスの場合、約10倍高速です。

于 2011-05-19T17:09:31.700 に答える
4

キャッシュエイリアシング

または、用語を作成できる場合は、キャッシュスラッシング。

キャッシュは、下位ビットでインデックスを作成し、上位ビットでタグ付けすることで機能します。

キャッシュに4ワードがあり、マトリックスが4 x 4であることをイメージします。列にアクセスし、行の長さが2の累乗である場合、メモリ内の各列要素は同じキャッシュ要素にマップされます。

2プラス1の累乗は、実際にはこの問題にほぼ最適です。新しい各列要素は、行でアクセスする場合とまったく同じように、次のキャッシュスロットにマップされます。

実際には、タグは連続して増加する複数のアドレスをカバーし、隣接する複数の要素を連続してキャッシュします。新しい各行がマップされるバケットをオフセットすることにより、列をトラバースしても前のエントリは置き換えられません。次の列がトラバースされると、キャッシュ全体が異なる行で埋められ、キャッシュに収まる各行セクションが複数の列にヒットします。

キャッシュはDRAMよりもはるかに高速であるため（主にオンチップであるため）、ヒット率がすべてです。

于 2011-05-21T06:17:32.363 に答える
2

キャッシュサイズの制限に達したようです。または、タイミングの再現性に問題がある可能性があります。

問題が何であれ、C＃で行列の乗算を自分で作成するのではなく、BLASの最適化されたバージョンを使用する必要があります。最近のマシンでは、そのサイズの行列を1秒未満で乗算する必要があります。

于 2011-05-19T15:33:12.767 に答える
1

キャッシュ階層を効果的に活用することは非常に重要です。多次元配列にデータが適切に配置されていることを確認する必要があります。これは、タイリングによって実現できます。これを行うには、2D配列をインデックスメカニズムとともに1D配列として格納する必要があります。従来の方法の問題は、同じ行にある2つの隣接する配列要素がメモリ内で互いに隣接しているにもかかわらず、同じ列内の2つの隣接する要素がメモリ内のW要素によって分離されることです。ここでWは列の数です。 。タイリングは、パフォーマンスに10分の1の違いをもたらす可能性があります。

于 2011-05-19T16:16:57.717 に答える
0

「シーケンシャルフラッディング」と呼ばれるものの結果だと思います。これは、キャッシュサイズよりもわずかに大きいオブジェクトのリストをループしようとしているため、リスト（配列）へのすべてのリクエストはRAMから実行する必要があり、単一のキャッシュを取得することはありません。打つ。

あなたの場合、配列2048インデックスを2048回ループしていますが、2047のスペースしかないため（おそらく配列構造からのオーバーヘッドが原因で）、配列posにアクセスするたびに、この配列posを取得する必要があります。ラムから。その後、キャッシュに保存されますが、再度使用される直前にダンプされます。したがって、キャッシュは本質的に役に立たず、実行時間がはるかに長くなります。

于 2011-05-19T17:25:10.820 に答える