メモリアクセスパターン

コンピューティングにおいて、メモリ アクセス パターンまたはIO アクセス パターンは、システムまたはプログラムが二次記憶装置上のメモリを読み書きするパターンです。これらのパターンは参照の局所性のレベルが異なり、キャッシュのパフォーマンスに劇的な影響を及ぼします。 ^[1]また、並列処理へのアプローチ^{[2] [3]や}共有メモリ システムにおける作業負荷の分散にも影響を及ぼします。^[4] さらに、キャッシュの一貫性の問題はマルチプロセッサのパフォーマンスに影響を及ぼす可能性があります。^[5]つまり、特定のメモリ アクセス パターンは並列処理に上限を設けます (メニーコアアプローチはこれを打破しようとします)。^[6]

コンピュータのメモリは通常「ランダムアクセス」と表現されますが、ソフトウェアによるトラバーサルは効率化のために利用できるパターンを示します。システム設計者^[7]やプログラマーがメモリアクセスパターンを理解、分析、改善するのに役立つさまざまなツールが存在し、VTune や Vectorization Advisor [8] [9] [10] [11] [12] などがあり、GPUメモリアクセスパターン^{に対処するツールも}含まれています。^[13]

メモリアクセスパターンはセキュリティにも影響を及ぼし^{[14] [15]、}プライバシー上の理由からプログラムの活動を隠そうとする人もいます^{[16] [17] 。}

最も単純な極端な例は、シーケンシャル アクセスパターンです。このパターンでは、データは、単純な増分/減分アドレス指定によって読み取られ、処理され、書き出されます。これらのアクセス パターンは、プリフェッチに非常に適しています。

ストライドまたは単純な2D、3Dアクセスパターン（多次元配列のステップ実行など）も同様に予測が容易で、線形代数アルゴリズムや画像処理の実装に見られます。ループタイリングは効果的なアプローチです。^[19] DMAを備えた一部のシステムでは、より大きな2D配列のサブタイルとスクラッチパッドメモリ間でデータを転送するためのストライドモードが提供されていました。^[20]

線形アクセス パターンは、メモリ アドレスが何らかのインデックスの線形結合から計算される「ストライド」と密接に関連しています。線形パターンを使用してインデックスを順番にステップ実行すると、ストライド アクセスが生成されます。書き込みの線形アクセス パターン (重複しない読み取りのアクセス パターンを含む) により、アルゴリズムを並列化できることが保証され、コンピューティング カーネルをサポートするシステムで活用されます。

最近傍メモリアクセスパターンはシミュレーションに現れ、シーケンシャルパターンまたはストライドパターンに関連しています。アルゴリズムは、データ要素の最近傍（1次元以上）からの情報を使用してデータ構造を走査し、計算を実行します。これらは、グリッド上で動作する物理シミュレーションで一般的です。^[21]最近傍は、クラスター内のノード間通信を指すこともあります。このようなローカルアクセスパターンに依存する物理シミュレーションは、データをクラスターノードに分割して並列化することができ、それらの間で純粋に最近傍通信を行うため、レイテンシと通信帯域幅の点で利点があります。このユースケースは、トーラスネットワークトポロジによく対応します。^[22]

3Dレンダリングでは、テクスチャマッピングや小さなプリミティブ（複雑な表面の任意の歪みを含む）のラスタライズのアクセスパターンは線形からは程遠いが、空間的局所性（たとえば、スクリーン空間またはテクスチャ空間）を示すことができる。これは、テクスチャマップとフレームバッファデータのモートン順序^[23]とタイリング（空間領域をキャッシュラインにマッピングする）の組み合わせ、またはタイルベースの遅延レンダリングによるプリミティブのソートによって、良好なメモリ局所性に変換できる。^[24]線形代数ライブラリで行列をモートン順序で格納することも有利な場合がある。^[25]

スキャッターメモリアクセスパターンは、シーケンシャル読み取りと書き込み用のインデックス/ランダムアドレス指定を組み合わせたものです。 ^{[26]ギャザーと比較すると、}処理要素が「ファイアアンドフォーゲット」方式（キャッシュを完全にバイパスする）で書き込みをディスパッチし、ソースデータに対して予測可能なプリフェッチ（またはDMA）を使用するため、キャッシュ階層にかかる負荷が少なくなる可能性があります。

しかし、書き込みが相互作用しないという保証がないため、並列化が難しくなる可能性があり、^[27]多くのシステムは依然としてハードウェアキャッシュが多数の小さな書き込みを結合して大きな書き込みを行うことを前提に設計されています。

これまで、フォワード テクスチャ マッピングでは、ソース テクスチャ情報を順番に読み取りながら、「書き込み」によってランダム性を処理しようとしていました。

PlayStation 2コンソールは従来の逆テクスチャ マッピングを使用していましたが、スキャッター/ギャザー処理は EDRAM を使用して「オンチップ」で処理され、メイン メモリからの 3D モデル (および大量のテクスチャ データ) は DMA によって順次供給されていました。このため、インデックス付きプリミティブのサポートがなく、ディスプレイ リストでテクスチャを「事前に」管理する必要がある場合がありました。

ギャザーメモリアクセスパターンでは、読み取りはランダムにアドレス指定またはインデックス付けされ、書き込みはシーケンシャル（または線形）に行われます。^[26]一例は逆テクスチャマッピングで、データはスキャンラインにわたって線形に書き出され、ランダムアクセステクスチャアドレスはピクセルごとに計算されます。

スキャッターと比較した場合の欠点は、小さな要素を効率的に読み取るためにキャッシュ（および遅延の回避）が不可欠になることですが、書き込みが重複しないことが保証されているため、並列化が容易になります。そのため、ギャザーアプローチはGPGPUプログラミングでより一般的であり、^[27]並列処理によって可能になる大規模なスレッドを使用して読み取り遅延を隠します。^[27]

アルゴリズムは、1 つのソースからデータを収集し、ローカルまたはオンチップ メモリで計算を実行し、結果を他の場所に分散します。これは、インデックス付き頂点とテクスチャを収集し、スクリーン スペースにシェーディングされたピクセルを分散するという、 3D レンダリングを実行するときのGPUパイプラインの基本的な操作です。深度バッファを使用した不透明プリミティブのラスタライズは「可換」であり、並べ替えが可能で、並列実行が容易になります。一般的なケースでは、同期プリミティブが必要になります。

反対の極端にあるのが、真にランダムなメモリアクセスパターンです。いくつかのマルチプロセッサシステムは、これらに対処するように特化されています。[ ^28] PGASアプローチは、オンザフライでデータによる操作をソートすることで役立つ場合があります（問題がソートされていないデータの局所性を見つけることである場合に便利です）。^[21]ポインタ追跡に大きく依存するデータ構造は、参照の局所性が低下することがよくありますが、ソートが役立つこともあります。真にランダムなメモリアクセスパターンが与えられれば、それを細分化（スキャッターステージやギャザーステージ、またはその他の中間ソートを含む）して、全体的な局所性を改善できる可能性があります。これは、多くの場合、並列化の前提条件です。

データ指向設計は、より一般的なオブジェクト指向アプローチ（つまり、データレイアウトがアクセスパターンを明示的に反映するように構成する）とは対照的に、プログラムのさまざまな段階でデータがどのように走査されるかに応じてデータを編成することにより、参照の局所性を最大化することを目的としたアプローチです。^[1]

参照の局所性とは、メモリアクセスパターンが示す特性のことである。プログラマーは、参照の局所性を改善したり、並列処理の可能性を高めたりするために、メモリアクセスパターンを変更する（アルゴリズムを改良する）ことがある。 [ ^{29 ]}プログラマーやシステム設計者は、特定のメモリアクセスパターンをカプセル化する フレームワークや抽象化（C++テンプレートや高階関数など）を作成することがある。 ^{[30] [31]}

メモリアクセスパターンに関するさまざまな考慮事項は、参照の局所性を超えた並列性、つまり読み取りと書き込みの分離に現れます。たとえば、読み取りと書き込みが「完全に」ローカルであっても、依存関係のために並列化が不可能になる場合があります。読み取りと書き込みを別の領域に分離すると、異なるメモリアクセスパターンが生成され、純粋な局所性の観点からは最初は悪く見えるかもしれませんが、最新の並列ハードウェアを活用するには望ましいものです。^[26]

参照の局所性は個々の変数（たとえば、コンパイラがそれらをレジスタにキャッシュする機能）を指す場合もありますが、メモリ アクセス パターンという用語は、インデックス可能なメモリ（特にメイン メモリ）に保持されるデータのみを指します。

• ギャザースキャッター（ベクトルアドレッシング）
• 参照の地域
• 並列コンピューティング
• ワーキングセット