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

行列転置におけるパフォーマンスの異常: 512x512 対 513x513

さまざまなサイズの正方行列を操作すると、特定のパフォーマンス パターンが現れ、興味深い結果が生じます。現象: 次の次元の行列を転置する2^n (例: 512x512) は、次元 2^n 1 (例: 513x513) の行列と比較して実行時間が一貫して遅いことがわかります。

メカニズムの詳細

パフォーマンスの差異は、データ アクセス パターン間の複雑な相互作用に起因します。そしてキャッシュ機能。具体的には、キャッシュはセットとラインに編成されます。

• Sets: データが一時的に保存されるキャッシュ セクション。
• Lines: 単位データの個々の部分を保持するセット内。

データ アドレスは特定のアドレスにマップされます。式を使って設定します。アドレス範囲が重複すると、セット占有の競合が発生し、キャッシュ ミスが発生する可能性があります。

クリティカル ストライド

この方程式の重要な要素は、「クリティカル ストライド」です。これは、キャッシュ ラインを効果的に競合するメモリ位置間の距離を測定します。データ要素がクリティカル ストライドに等しい間隔で保存されると、「偽のエイリアス」または「人工ストライド」として知られるキャッシュ競合が引き起こされます。

512x512 の行き詰まり

512x512 のマトリックス、1 セットあたり 4 ライン、ライン サイズが 1 つのキャッシュを占有64 バイトでは、この落とし穴に遭遇します。この構成の重要なストライドは 2048 バイト (4 ライン * 64 バイト) で、行列の 4 行ごとに位置合わせされます。

転置中に列内の連続する要素にアクセスすると、最初の操作からのキャッシュ ラインが追い出された。その結果、後続の行の重要なストライド間隔にある要素がキャッシュ ミスを起こし、パフォーマンスが低下します。

513x513 のエスケープ

対照的に、513x513 の行列では、奇妙な次元で、重要な進歩が妨げられます。要素は重要なストライド間隔で配置されなくなり、キャッシュ競合のリスクが軽減されます。これにより、転置中のパフォーマンスが向上します。

結論

2^n 1 と比較して 2^n の次元の行列転置が遅くなる現象は、キャッシュ メモリの特性に起因します。 。コード実行時間を最適化するには、クリティカル ストライドとデータ アライメントのキャッシュ使用率への影響を理解することが重要です。

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