FPGA開発日記

カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages , English Version https://fpgadevdiary.hatenadiary.com/

"Constructing a Weak Memory Model" を読む (4. GAMのOOOMPへの拡張)

Weak Memory Modelについてもう少し知識をつけたかったので、論文を読んでみることにした。

arxiv.org

基本的にDeepLに翻訳してもらったものを、自分で読み直しながら直しているだけなので、自分でまとめているわけではない。 冗長なのは無編集でブログに貼っている、ということで。

C. マルチプロセッサへの制約の拡張

複数のOOOUをアトミック・メモリ・システムに接続するマルチプロセッサOOOMPを考える。 図7のローカル実行順序に関する制約は、OOOMPの各OOOUにはまだ適用されるが、マルチプロセッサ全体の動作を記述するには不十分である。ユニプロセッサとマルチプロセッサの唯一の違いは、ロード値についてである。ユニプロセッサの設定では、ロードは常にロードより古いストアの値を取得する。しかしOOOMPでは、ロードがアトミック・メモリ・システムから値を取得する場合、その値は異なるプロセッサのストアから取得される可能性がある。

アトミック・メモリ・システムを介したこのような相互作用を理解するために、アトミック・メモリ・システムはモノリシック・メモリによって抽象化でき、ロード/ストア要求がアトミック・メモリ・システムのL1データ・アレイを読み書きする時間は、モノリシック・メモリにおける要求の瞬間的な処理に相当することを思い出してほしい（セクションII-B）。

したがって、すべてのメモリ命令を、その実行終了時間でもあるL1アクセス時間に基づいてアトミックメモリ順序に置くことができる。従って、アトミック・メモリ順序はローカル実行順序を尊重すべきであり（図10の制約LMOrdAtomic）、メモリにアクセスするロードは、アトミック・メモリ順序で同じアドレスの直前のストアから読み出すべきである（図10の制約LdValAtomic）。 ロードがメモリにアクセスしない場合、ロードは直前のストアから転送されたデータを取得する。 を取得する。図10の制約(LdForward）は、OOOUと同じである。

  • 図10. OOOMPにおけるロード値の制約
    • LMOrdAtomic（local-to-atomic-memory-order）制約： 同じプロセッサからの2つのメモリ命令のアトミックなメモリ順序は、そのプロセッサにおけるこれら2つの命令の実行順序と同じである。
    • LdValAtomic（atomic-memory-load-value）制約： メモリシステムに要求して実行されるロードは、アトミックメモリ順序でロードの前に順序付けられた同じアドレスの最も若いストアの値を取得する必要がある。
    • LdForward（load-forward）制約： フォワーディングによって実行されるロードは、コミット順で同じアドレスに対して、同じプロセッサから直前のストアの値を取得すべきである。

これらの3つの制約は、図11の2つの制約LMOrdとLdValとして再表現できる。そのために、ローカル・ストアから進むロードを含むすべてのメモリ命令を、OOOMPのすべてのアドレスに対するすべてのプロセッサから、その実行終了時間に従ってグローバル・メモリ順序に入れる。

したがって、グローバル・メモリ順序は、アトミック・メモリ順序と実行順序を尊重する必要がある（制約LMOrd）。

ロードLの実行方法は、コミット順序における、同じアドレスに対する同じプロセッサからのLとその直前のストアSのグローバル・メモリ順序によって区別できることに注意されたい。そうでない場合、Lはグローバルメモリ順序でSの後に順序付けられ、Lはアトミックメモリシステムにロード要求を送信することによって実行されなければならない。したがって、2つのケース（LdValAtomicとLdForward）におけるロード値の制約は、制約LdValにまとめることができる：

  1. 転送の場合、Sはコミット順序でLの前にあり、グローバルメモリ順序でLより古い（Lより前）ストアより若い（Lより後）。
  2. メモリシステムを読み出す場合、コミット順序でLより前にあるストアはすべて、グローバルメモリ順序でもLより前にある。 制約LdValは、RMO [44]とAlpha [45]にも登場する。
  3. 図11. OOOMPにおける追加制約
    • LMOrd（local-to-global-memory-order）制約： 同じプロセッサからの2つのメモリ命令のグローバルメモリ順序は、そのプロセッサにおけるこれら2つの命令の実行順序と同じである。
    • LdVal（ロード値）制約： ロードは、ロード先のプロセッサのグローバル・メモリ順序またはローカル・コミット順序のいずれかにおいて、ロードの前に順序付けられたグローバル・メモリ順序の同じアドレスの最年少ストアの値を取得しなければならない。

アトミック・リード・モディファイ・ライト（RMW）： RMWが守るべき制約には、複数の選択肢がある。 1つの単純な方法は、アドレスaに対するRMW命令は、ロードaまたはストアaに適用されるすべての制約に従うべきであり、RMWはメモリシステムにアクセスすることによって実行されなければならないと言うことである。スペースがないため、本稿の残りでRMWについてこれ以上詳しく説明することはしない。

D. プログラミングに必要な制約

これまで、OOOMPにおけるロードとストアの動作を記述するには、図7と図11の制約で十分であった。図7の制約では、ローカル実行順序においてどのローカルコミット順序を維持すべきかを指定し、制約LMOrdでは、メモリ命令のローカル実行順序をグローバルメモリ順序に変換し、最後に制約LdValでは、グローバルメモリ順序と各プロセッサのコミット順序が与えられたときの各ロードの値を指定する。しかし、これらの制約は、特にプログラマがSCを再現したい場合、並列プログラミングには十分ではない。メモリフェンス命令と強制可能な依存関係は、ロード／ストアの並び替えを制御する2つのメカニズムである。まず、フェンス命令とそれに関連する新しい制約を紹介し、次に、現在の制約によってすでに提供されている強制可能な依存関係について議論する。これらの新しい制約を含めることで、GAMの初期バージョンであるメモリモデルGAM0が出来上がる。

  1. オーダリングを制御するフェンス： ここでは、4つの基本的なフェンスを提供する： FenceLL, FenceLS, FenceSL, FenceSS これらのフェンスは、フェンスの前に指定された型のすべてのメモリ命令を、フェンスの後に別の指定された型のすべてのメモリ命令を実行順序で並べる。例えば、FenceLSは、すべてのロードをフェンスの前に、すべてのストアをフェンスの後に実行順序を並べる。各命令には実行終了時間があるというこれまでの説明と整合させるために、フェンスも実行する必要があるが、NOPとして機能すると考えることができる。フェンスは 図12のFenceOrd（フェンス順序付け）制約に従う。ただし フェンスはメモリ命令でのみ順序付けられ、2つのフェンスは互いに（直接）順序付けられないことに注意すべきである。制約LMOrdのため、フェンスによって強制される実行順序は、グローバル・メモリ順序にも適用される。
  2. 図12 フェンスの追加制約
    • 制約FenceOrd（フェンスの順序付け）： FenceXYは、実行順序において（同じプロセッサからの）タイプXのすべての古いメモリ命令の後に順序付けられ、実行順序において（同じプロセッサからの）タイプYのすべての若いメモリ命令の前に順序付けられなければならない。

フェンスの追加制約 これらのフェンスを組み合わせることで、より強力なフェンスを作り出すことができる。

  • Acquire Fence: FenceLL; FenceLS
  • Release Fence: FenceLS; FenceSS
  • Full Fence: FenceLL; FenceLS; FenceSL; FenceSS
  1. 順序付けを強制するデータ依存関係： プログラミングで最もよく使われる強制可能な依存関係は、データ依存関係である。図13aのリトマス・テストMP+addr（アドレスに依存するメッセージパッシング）を考えてみよう。I5のロードのアドレスはI4の結果に依存する（すなわち、I4とI5はデータ依存のロードであ る）ので、ほとんどのプログラマは、P2の2つのロードは順序を変更すべきではない と仮定し、したがって、P2の2つのロード間にFenceLLがなくても、非SC動作r1 = a, r2 = 0は決して起こらないはずである。GAM0は、制約RegRAWとLMOrdが、実行順序とグローバルメモリオーダーにおいて、I4をI5より前に保つので、プログラマのこの直感に一致する。 実際、プログラマは、データ依存のロードーロード順序の特徴を利用して、FenceLLを人工的なデータ依存性で置き換えることができる。図13bのプログラムを考えてみよう。 P2はロードa（I6）の前にロードb（I4）を実行すべきである。2つのロードの間にフェンスが挿入されるのを避けるために、最初のロードの結果から2つ目のロードのアドレスへの人為的な依存関係を作成することができる。 このようにしても、GAM0は非SC動作を禁止する。 この最適化は、I4に続く命令ではなく、I6のみをI4の後に順序付ける必要がある場合、すなわち、I6に続く命令の実行がいかなるフェンスによってもストールされない場合に有効である。P2は、I5をr2＝aに最適化すべきではないことに注意すべきである。そうでなければ、I4からI6への依存関係は存在しない。つまり、GAMの実装は、構文的なデータ依存性を尊重しなければならない。