513x513 の行列転置が 512x512 行列転置よりも速いのはなぜですか?

行列サイズ 512x512 と 513x513 の行列転置におけるパフォーマンスの違いを理解する

さまざまなサイズの正方行列は、次の場合に固有の時間差を示します。それらを転置します。興味深いことに、次元 2^n の行列は、次元 2^n 1 の行列と比較して転置時間が遅くなる傾向があります。これらの違いは、n の値が小さい場合は重要ではないように見えますが、MATSIZE 512 で明らかなように、次元が大きくなると重要になります。 .

このパフォーマンス格差の根本的な理由を理解するために、次の概念を詳しく掘り下げます。 caching.

キャッシュの構成とセット マッピング

キャッシュはセットと行に編成されます。各セットには、データを保存できる複数の行が含まれています。特定のメモリ アドレスが属するセットを見つけるには、次の式を使用します。

set = (address / lineSize) % numberOfsets

その結果、メモリ アドレスはある程度均一な方法でセットにマップされます。

キャッシュミスとラインエビクション

メモリの場所にアクセスするとき、キャッシュはデータがすでに存在するかどうかを確認します。そうでない場合は、キャッシュ ミスが発生し、対応するラインがメモリから読み取られてキャッシュに配置されます。ただし、キャッシュがいっぱいになると、新しいデータを収容するために最も最近使用されていない (LRU) 行が削除されます。

クリティカル ストライド

クリティカル ストライドは間隔を表します。同じキャッシュラインを競合する変数間で。これは次のように計算されます:

criticalStride = numberOfSets * lineSize

クリティカル ストライドまたはその倍数だけ離れた変数は、キャッシュのエビクションを引き起こす可能性が高くなります。

行列の転置とクリティカル ストライド

8kB キャッシュを備えた 64x64 行列を想像してください。 1セットに4行。各ラインは 8 つの 64 ビット整数を保持できます。このシナリオにおける重要なストライドは 2048 バイトで、行列の 4 行に相当します。

行列を転置するときは、行と列を交換します。各行を処理して対応する列と交換すると、クリティカル ストライド (4 行) で区切られた要素がキャッシュの削除に遭遇します。これにより、大量のキャッシュのリロードが発生し、転置が遅くなります。

結論

512x512 行列と 513x513 行列の間の転置時間の差は、行列間の関係に起因します。マトリックスの次元とキャッシュのクリティカル ストライド。クリティカル ストライドの倍数ではない次元を持つ行列では、キャッシュの削除が減少し、その結果、転置時間が短縮されました。

以上が513x513 の行列転置が 512x512 行列転置よりも速いのはなぜですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。