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

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

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

例

一部の出版物では、シーケンシャルパターンとリニアパターンが誤って対応するものとして描かれていますが、実際のワークロードにはほぼ無数のパターンが含まれています。[18]

一連

最も単純な極端な例はシーケンシャルアクセスパターンです。このパターンでは、データの読み取り、処理、書き込みは、単純なインクリメント/デクリメント方式のアドレス指定によって行われます。このアクセスパターンは、プリフェッチに非常に適しており、非常に扱いやすいです。

歩幅の広い

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

リニア

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

最も近い隣人

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

2D空間コヒーレント

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

散らばる

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

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

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

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

集める

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

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

収集と散布の組み合わせ

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

ランダム

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

アプローチ

データ指向設計

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

参照の局所性との対比

参照の局所性とは、メモリアクセスパターンが示す特性を指します。プログラマーは、参照の局所性を向上させるために（アルゴリズムを改良することによって）メモリアクセスパターンを変更します。 [29]また、並列処理の可能性を高めるためにも使用されます。[26] プログラマーやシステム設計者は、特定のメモリアクセスパターンをカプセル化するフレームワークや抽象化（例えば、 C++テンプレートや高階関数）を作成することがあります。[30] [31]

並列処理においては、参照の局所性を超えて、メモリアクセスパターンに関する様々な考慮事項、すなわち読み取りと書き込みの分離が重要になります。例えば、読み取りと書き込みが「完全に」局所的であっても、依存関係のために並列化が不可能になる場合があります。読み取りと書き込みを別々の領域に分離すると、メモリアクセスパターンが異なり、純粋な局所性の観点からは一見すると悪く見えるかもしれませんが、現代の並列ハードウェアを活用するためには望ましい結果となります。[26]

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

参照

参考文献

  1. ^ ab 「データ指向設計入門」(PDF)。2019年11月16日時点のオリジナル(PDF)からのアーカイブ。
  2. ^ Jang, Byunghyun; Schaa, Dana; Mistry, Perhaad & Kaeli, David (2010-05-27). 「データ並列アーキテクチャにおけるメモリパフォーマンス向上のためのメモリアクセスパターンの活用」IEEE Transactions on Parallel and Distributed Systems . 22 (1). ニューヨーク: IEEE : 105– 118. doi :10.1109/TPDS.2010.107. eISSN  1558-2183. ISSN  1045-9219. S2CID  15997131. NLM固有ID 101212014.
  3. ^ Jeffers, James; Reinders, James; Sodani, Avinash (2016-05-31). Intel Xeon Phi プロセッサー高性能プログラミング：Knights Landing 版（第2版）. Morgan Kaufmann. ISBN 9780128091951。
  4. ^ Jana, Siddhartha; Schuchart, Joseph; Chapman, Barbara (2014-10-06). 「PGASベースのデータアクセスパターンのエネルギーと性能の分析」(PDF) .第8回国際パーティション・グローバル・アドレス空間プログラミングモデル会議議事録. PGAS '14. ニューヨーク州ニューヨーク: Association for Computing Machinery. pp.  1– 10. doi :10.1145/2676870.2676882. ISBN 978-1-4503-3247-7。
  5. ^ Marandola, Jussara; Louise, Stéphane; Cudennec, Loïc; Acquaviva, Jean-Thomas; Bader, David (2012-10-11). 「組み込みメニーコアシステム向けアクセスパターンによるキャッシュコヒーレントアーキテクチャの強化」 2012 International Symposium on System on Chip (SoC) (PDF) . IEEE. pp.  1– 7. doi :10.1109/ISSoC.2012.6376369. ISBN 978-1-4673-2896-8。
  6. ^ 「インテル テラスケール」(PDF)。
  7. ^ブラウン、メアリー、ジェネヴェイン 、ロイ・M、ウラー、ナスル（1998年11月29日）。メモリアクセスパターン分析。WWC '98：ワークロード特性評価：方法論とケーススタディの議事録（1998年11月29日発行）。p. 105。ISBN 9780769504506。
  8. ^ Ostadzadeh, S. Arash; Meeuws, Roel J.; Galuzzi, Carlo; Bertels, Koen (2010). 「QUAD – メモリアクセスパターンアナライザー」(PDF) . Sirisuk, Phaophak; Morgan, Fearghal; El-Ghazawi, Tarek; Amano, Hideharu (編).リコンフィギュラブルコンピューティング：アーキテクチャ、ツール、アプリケーション. コンピュータサイエンス講義ノート. 第5992巻. ベルリン、ハイデルベルク：シュプリンガー. pp.  269– 281. doi :10.1007/978-3-642-12133-3_25. ISBN 978-3-642-12133-3。
  9. ^ Che, Shuai; Sheaffer, Jeremy W.; Skadron, Kevin (2011-11-12). 「Dymaxion: 異機種混在システムにおけるメモリアクセスパターンの最適化」(PDF) . 2011 International Conference for High Performance Computing, Networking, Storage and Analysis Proceedings . SC '11. ニューヨーク、ニューヨーク州、米国: Association for Computing Machinery. pp.  1– 11. doi :10.1145/2063384.2063401. ISBN 978-1-4503-0771-0。
  10. ^ ハリソン、ラディ (1996年1月1日). 「ポインタ集約型プログラムと数値プログラムのためのメモリアクセス分類スキームの検討」.第10回国際スーパーコンピューティング会議 (ICS '96) の議事録. ニューヨーク州ニューヨーク: 計算機協会. pp.  133– 140. doi :10.1145/237578.237595. ISBN 978-0-89791-803-9。
  11. ^ 松原 悠紀、佐藤 幸則 (2014). 「アプリケーションプロファイリングツールによるオンラインメモリアクセスパターン分析」. 2014年第2回国際コンピューティング・ネットワーキングシンポジウム. pp.  602– 604. doi :10.1109/CANDAR.2014.86. ISBN 978-1-4799-4152-0. S2CID  16476418。
  12. ^ 「データとコードを整理する: データとレイアウト」。
  13. ^ Kim, Yooseong; Shrivastava, Aviral (2011-06-05). 「CuMAPz: CUDAにおけるメモリアクセスパターン解析ツール」. Proceedings of the 48th Design Automation Conference . DAC '11. ニューヨーク、ニューヨーク州、米国: Association for Computing Machinery. pp.  128– 133. doi :10.1145/2024724.2024754. ISBN 978-1-4503-0636-2。
  14. ^ Kim, Yooseong; Shrivastava, Aviral (2011-06-05). 「CuMAPz: CUDAにおけるメモリアクセスパターン解析ツール」. Proceedings of the 48th Design Automation Conference . DAC '11. ニューヨーク、ニューヨーク州、米国: Association for Computing Machinery. pp.  128– 133. doi :10.1145/2024724.2024754. ISBN 978-1-4503-0636-2。
  15. ^ アン・カントー;ローラドゥー、セドリック。アンドレ・セズネック (2006)。キャッシュ攻撃を理解する (レポート論文)。インリア。ISSN  0249-6399。
  16. ^ Hardesty, Larry (2013-07-02). 「クラウド内のデータ保護」. MITニュース.
  17. ^ Rossi, Ben (2013年9月24日). 「oblivious RAMによるクラウドセキュリティの強化」. Information Age .
  18. ^ Chuck Paridon. 「ストレージパフォーマンスベンチマークガイドライン - パートI：ワークロード設計」（PDF）実際には、IOアクセスパターンは星の数ほどあります。
  19. ^ Kennedy, Ken; McKinley, Kathryn S. (1992-08-01). 「並列処理とデータ局所性の最適化」(PDF) .第6回国際スーパーコンピューティング会議 (ICS '92) の議事録. ニューヨーク州ニューヨーク: Association for Computing Machinery. pp.  323– 334. doi :10.1145/143369.143427. ISBN 978-0-89791-485-7。
  20. ^ Saidi, Selma; Tendulkar, P.; Lepley, Thierry; Maler, O. (2012). 「MPSoCにおけるDMA転送のための最適な2Dデータ分割」(PDF) . 2012 第15回Euromicroデジタルシステム設計会議. IEEE. pp.  584– 591. doi :10.1109/DSD.2012.99. ISBN 978-0-7695-4798-5。
  21. ^ ab CITRIS and the Banatao Institute (2013-09-05). Partitioned Global Address Space Programming - Kathy Yelick . 2024年11月2日閲覧– YouTube経由。PGAS が有効なケース、つまり、データがまだソートされていない可能性があるケース (複雑なグラフの処理など) をカバーします (「不規則性スペクトル全体の科学」を参照)。
  22. ^ Weinberg, Jonathan; McCracken, Michael O.; Snavely, Allan; Strohmaier, Erich (2005年11月12日～18日). 「HPCアプリケーションのメモリアクセスパターンにおける局所性の定量化」(PDF) . ACM/IEEE SC 2005 Conference (SC'05). シアトル, ワシントン州, 米国: IEEE. p. 50. doi :10.1109/SC.2005.59. ISBN 1-59593-061-2. 2016年8月3日時点のオリジナル（PDF）からアーカイブ。クラスター内の最近傍アクセスパターンについて言及する
  23. ^ Hakura, Ziyad S.; Gupta, Anoop (1997-05-01). 「テクスチャマッピングのためのキャッシュアーキテクチャの設計と分析」(PDF) .第24回コンピュータアーキテクチャ国際シンポジウム議事録. ISCA '97. ニューヨーク州ニューヨーク: Association for Computing Machinery. pp.  108– 120. doi :10.1145/264107.264152. ISBN 978-0-89791-901-2。
  24. ^ Nocentino, Anthony E.; Rhodes, Philip J. (2010-04-15). 「GPUにおけるメモリアクセスの最適化：モートン順序インデックス法」(PDF) .第48回南東部地域会議議事録. ACMSE '10. ニューヨーク州ニューヨーク: Association for Computing Machinery. pp.  1– 4. doi :10.1145/1900008.1900035. ISBN 978-1-4503-0064-3. 2022年12月8日時点のオリジナル（PDF）からアーカイブ。
  25. ^ Wise, David S.; Frens, Jeremy D. (1999). 「モートン階乗行列はコンパイラのサポートを必要とする 技術レポート 533」. S2CID  17192354. {{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
  26. ^ abcd Harris, Mark (2005年4月). 「GPU Gems 2」. 31.1.3 ストリーム通信：Gather vs. Scatter. 2016年6月14日時点のオリジナルよりアーカイブ。2016年6月13日閲覧。
  27. ^ abc GPU gems. エルゼビア. 2011年1月13日. ISBN 9780123849892。本文中の「メモリアクセスパターンの分散」と「メモリアクセスパターンの収集」について述べる。
  28. ^ Wichmann, Nathan (2005). CrayとHPCC：過去1年間のベンチマーク開発と成果(PDF) . CUG 2005 Proceedings.Cray X1のグローバルランダムアクセス結果を参照してください。レイテンシを隠すためのベクトルアーキテクチャで、キャッシュコヒーレンスにそれほど敏感ではありません。
  29. ^ 「データ構造とメモリアクセスパターンを最適化してデータの局所性を向上させる」。
  30. ^ 「SoC のアクセラレータ向けテンプレートベースのメモリ アクセス エンジン」(PDF)。
  31. ^ 「MTPS C++ 汎用ライブラリを使用したマルチターゲットベクトル化」(PDF)。最適化されたメモリアクセスパターンを生成するためのC++テンプレートライブラリ