FPGA開発日記

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

FPGA開発日記 カテゴリ別インデックス

RISC-VにおけるRVWMOの仕様について読み直す

続きを読む

"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つのケース(LdValAtomicLdForward)におけるロード値の制約は、制約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は、制約RegRAWLMOrdが、実行順序とグローバルメモリオーダーにおいて、I4をI5より前に保つので、プログラマのこの直感に一致する。 実際、プログラマは、データ依存のロードーロード順序の特徴を利用して、FenceLLを人工的なデータ依存性で置き換えることができる。図13bのプログラムを考えてみよう。 P2はロードa(I6)の前にロードb(I4)を実行すべきである。2つのロードの間にフェンスが挿入されるのを避けるために、最初のロードの結果から2つ目のロードのアドレスへの人為的な依存関係を作成することができる。 このようにしても、GAM0は非SC動作を禁止する。 この最適化は、I4に続く命令ではなく、I6のみをI4の後に順序付ける必要がある場合、すなわち、I6に続く命令の実行がいかなるフェンスによってもストールされない場合に有効である。P2は、I5をr2=aに最適化すべきではないことに注意すべきである。そうでなければ、I4からI6への依存関係は存在しない。つまり、GAMの実装は、構文的なデータ依存性を尊重しなければならない。

"Constructing a Weak Memory Model" を読む (3. モデルの構築)

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

arxiv.org

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


III. GAMの直感的な構築

まず、高度に最適化されたアウト・オブ・オーダー・ユニプロセッサOOOUを研究し、そのようなアグレッシブな実装であっても、シングル・スレッド・セマンティクスを維持するためにいくつかの順序制約を守ることを示す。複数のOOOUがアトミック・メモリ・システムを介して接続され、マルチプロセッサOOOMPを形成する場合、これらの制約を拡張して、OOOMPの動作を特徴付け、ユニプロセッサ最適化を維持するという目標を満たすベース・メモリ・モデルを形成することができる。

しかし、すべてのマルチスレッド・プログラムに対してSCをリストアする方法がないため、基本モデルはプログラム不可能である。

そのため、OOOMPの排他順序を制御するフェンス命令を導入する。すなわち、ウィーク・メモリ・モデルを持つマシンをプログラミングする場合でも、プログラマが一般的に想定する順序を壊さないようにする。プログラマーの直感に合わせるために、我々は構築されたモデルにさらなる制約を導入する。これらの制約が性能に与える影響についてはセクションVで検討する。

A. アウトオブオーダー・ユニプロセッサ(OOOU)

図6に、ライト・バック・キャッシュ階層に接続されたOOOUの構造を示す。メモリアクセスがキャッシュミスになった場合、プロセッサはその行をL1にフェッチしてからアクセスする。メモリ・システムは、複数の要求を並列に処理することができるが、同じアドレスに対する要求は、メモリ・システムに発行された順に処理される。説明を簡単にするため、メモリモデルに関係のない詳細は省略する。OOOUは次の命令を投機的にフェッチし、フェッチされた命令はすべて順番にROBに挿入される。ロードとストアも、それぞれロードバッファ(LB)とストアバッファ(SB)に同じ順序で挿入される。

OOOUは命令を順序を無視して投機的に実行するが、投機に関して以下の2つの制限を仮定する:

  1. メモリ・システムに送られたストア要求は撤回できず、その効果を取り消すこともできない。
  2. 命令の次の PC 以外の宛先レジスタの値は決して予測されない(すなわち、OOOU は値予測を行わない[72]-[78])。

最初の制限は受け入れやすいが、2 番目の制限はセクション III-D2 で正当化される。投機に関する制限は、命令を発行して実行を開始できる必要条件を意味する。例えば、すべてのソース・オペランドがレディになるまで(すなわち、古い命令によって計算されるまで)、命令は発行できない。命令(特にストア)を発行する際の他の制約については、後述する。発行された後、reg-to-reg命令または分岐命令は、ローカル計算だけで実行される。ストアの実行は、メモリシステムにストア要求を送る。転送が不可能な場合、ロードはメモリシステムに要求を送る。

アウト・オブ・オーダ実行にもかかわらず、OOOUは依然としてROBからの命令を順番にコミットする。ストアは、コミット時にメモリシステムへのストア要求を完了する必要はないが、ロード、reg-to-reg、ブランチ命令は、コミット時にその値を取得している必要がある。以下では、ある命令I1が別の命令I2より古いという場合、デフォルトでは、コミット順序においてI1がI2より前にある(あるいは、I1がI2より前にROBに挿入されている)ことを意味する。

ユニプロセッサにおける命令の並べ替え: 命令の並び替えとは、2つの命令の実行順序がコミット順序と異なることを意味する。実行順序とは、命令の実行が終了する時刻の順序のことである。 reg-to-reg命令や分岐命令は、それぞれ目的レジスタの値を計算したり、次のPCを解決したりした時点で実行を終了する。ロード命令は、SBから転送を受けるか、L1からデータを読み出すときに実行を終了する。ストアは、ストアデータをL1キャッシュのデータ配列に書き込んだ時点で実行を終了する。コミットされる前に(例えばミススペックのために)つぶされた命令は、実行順序のメンバーではない。

B. OOOUにおける制約

OOOUの実行順序に関するすべての制約を図7に列挙し、1つずつ導出する。

これらの制約は、2つのカテゴリーに分類できる。最初の制約セット(SAMemStSAStLd)は、同じアドレスに対するメモリ命令間の制約であり、シングルスレッドの正しさを維持するために不可欠である。第2の制約セット(RegRAWBrStAddrSt)は、命令を発行して実行を開始する前に満たす必要がある必要条件を反映している。投機的実行は、このような条件の多くを取り除くことができるが、投機に関するいくつかの制約を仮定しているため、いくつかはまだ残っている。

  • SAMemSt(same-address-memory-access-to-store)制約: ストアは、同じアドレスに対する古いメモリ命令の後に命令されなければならない。
  • SAStLd(同一アドレス-ストア-ロード)制約: ロードは、同じアドレスに対して直前のストアのアドレスまたはデータを生成するすべての命令の後に命令されなければならない。
  • RegRAW(register-read-after-write)制約: 命令は、PC以外のソースオペランドの1つを生成する古い命令の後に命令されなければならない。
  • BrSt(分岐-ストア)制約: ストアは、古い分岐の後に命令されなければならない。
  • AddrSt(アドレスからストア)制約: ストアは、ストアよりも古いメモリ命令のアドレスを生成する命令の後に命令されなければならない。

同じアドレスのメモリ命令に対する制約: I1とI2が同じアドレスaに対する2つのメモリ命令で、I1の方がI2より古いとする。I1とI2の両方がロードであれば、それらの実行を順序付ける必要はない。I2がストアの場合、I1がロードであろうとストアであろうと、I1の実行が終了する前にL1を書き込むことはできない。したがって、図7のSAMemSt制約がある。

次に、I1がストア、I2がロードの場合を考える。I2がL1をリードして実行される場合、I1がL1を書き込む前に実行することはできない。従って、これら2つの命令が並び替えられる唯一の方法は、図8に示すように、I2がストアSから転送を受けるときである。SはI2より古い最も若いストアでなければならない。フォワーディングのためにI1とI2の間に直接的な順序制約が存在することはできないが、I2が潰されることなく最終的にコミットされた場合、I2はSのアドレスとデータが古い命令によって計算される前に実行を開始することはできない。これにより、図7のSAStLd制約が得られる。

実行開始命令の制約 すべてのソースオペランドが準備できていなければ、命令を実行に移すことはできないので、図7にRegRAW制約がある。この制約ではPCを除外していることに注意されたい。

これは、OOOUが分岐予測を行うためであり、フェッチされた命令はすでにPCを知っており、実行に使用することができる。

制約RegRAWは、reg-to-reg命令、分岐命令、ロード命令の発行要件をすでにカバーしている。特に、ロードの発行に関しては、投機のためこれ以上の制約はない。例えば、図9のプログラムを考える。OOOUは、I2のアドレスがI3と同じであることが判明しても、I2のストア・アドレスが計算される前(すなわち、I1が実行を終了する前)に、I3のロードを発行することができる。I1がr1に値bを本当に書き込んだ場合、OOOUはI3をつぶして再実行する。I1とI3の間の実行順序は、制約SAStLdによって捕捉された。

次に、投機的ストアの発行禁止という制約によって引き起こされる制約を考える。単純なケースは、古い分岐が実行されていないときにはストアを発行できないというもので、図7の制約BrStである。これは、分岐がフェッチ時に誤って予測され、将来ROBスクワッシュを引き起こす可能性があるためである。もう1つのケースは、古いメモリ命令のアドレスが準備できていないときにストアを発行できないこと、すなわち図7の制約AddrStである。これは、ストアを発行し、後で古いメモリ命令のアドレスがストアのアドレスと同じであることが判明した場合、シングルスレッドの正しさ(すなわち制約SAMemSt)に違反する可能性があるためである。

"Constructing a Weak Memory Model" を読む (2. 背景と形式的定義)

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

arxiv.org

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


II. 背景と関連研究

A. メモリモデルの形式的定義

ここでは、SC[31]を例にして、操作的定義と公理的定義の概念を説明する。

SCの運用上の定義:図1はSCの抽象的なマシンを示しており、すべてのプロセッサはモノリシック・メモリに直接接続されている。このマシンの動作は単純で、1ステップで任意のプロセッサを選び、そのプロセッサ上で次の命令をアトミックに実行する。つまり、命令がreg-to-reg(すなわちALU演算)または分岐命令であれば、プロセッサのローカルレジスタの状態を変更するだけであり、ロードであれば、モノリシックメモリから瞬時に読み出し、レジスタの状態を更新し、ストアであれば、モノリシックメモリを瞬時に更新し、PCをインクリメントする。2つのプロセッサが同じステップで命令を実行することはないことに注意すべきである。

例として、図2のリトマス・テスト・Dekkerを考えてみよう。I1→I2→I3→I4の順に命令を実行して抽象マシンを動作させると、SCの合法的な動作r1=0、r2=1が得られるが、マシンを動作させてもr1=r2=0は得られない。

リトマス・テスト: 本稿の残りの部分では、図2のようなリトマス・テストを使って、メモリ・モデルの特性を示したり、2つのメモリ・モデルを区別したりする。リトマス・テストはプログラムのスニペットであり、このプログラムの特定の動作が各メモリ・モデルで許容されるかどうかに注目する。我々はウィーク・メモリ・モデルを研究しているので、非SC動作(例えば、図2のr1 = 0, r2 = 0)に興味がある。

SCの公理的定義:SCが許容するプログラム動作が満たさなければならない公理を与える前に、まず、公理的設定におけるプログラム動作とは何かを定義する必要がある。

本稿のすべての公理的定義において、プログラム動作は以下の3つの関係によって特徴付けられる:

  • プログラム順序$<_{po}$: プログラム論理に従って1つのプロセッサ上で実行される命令の局所的順序。
  • グローバル・メモリ順序$<_{mo}$: 全プロセッサからの全メモリ命令の総順序であり、メモリ命令の実際の実行順序を反映する。
  • リードフロム関係 $rf →$: 各ロードが読み出すストアを特定する関係(すなわち、ストア$rf→$ロード)。

$<{po}$, $<{mo}$, $rf→i$ で表されるプログラム動作は、メモリモデルの公理をすべて満たす場合、メモリモデルによって許容される。

図3にSCの公理を示す。公理InstOrderSCは、すべてのメモリ命令のペア(I1とI2)間のローカル順序は、グローバル順序で保存されなければならない、すなわち、SCではリローダリングはない。公理LoadValueSCは、各ロードの値を指定する。ロードは、$<_{mo}$のロードより古いストアの中で最も若いストア、すなわちmax<mo{ストアの集合}しか読み出すことができない。

B. アトミック・メモリと非アトミック・メモリ

実装におけるコヒーレント・メモリ・システムは、アトミック・メモリ・システムと非アトミック・メモリ・システムの2種類に分類することができるので、別々に説明する。

アトミック・メモリ: アトミック・メモリ・システムでは、発行されたストアはすべてのプロセッサに同時に通知される。

このようなメモリシステムは、ロードとストアを瞬時に処理するモノリシック・メモリに抽象化できる。アトミック・メモリ・システムの実装はよく理解されており、実際に広く使われている。例えば、MSI/MESIプロトコルを持つコヒーレントなライトバック・キャッシュ階層は、アトミック・メモリ・システムとなり得る[32]、[33]。このようなキャッシュ階層では、ストア要求がL1データ・アレイに書き込まれた瞬間が、モノリシック・メモリ抽象におけるストアの瞬時処理に相当し、ロード要求がその値を取得した瞬間が、モノリシック・メモリにおけるロードの瞬時処理に相当する。

アトミック・メモリの抽象化は、コヒーレント・キャッシュ階層の上にプロセッサごとにプライベート・ストア・バッファを追加すれば、少し緩和できる。ストア・バッファリングにより、ストアの発行元プロセッサは他のどのプロセッサよりも先にストアを見ることができるが、発行元プロセッサ以外のプロセッサからも同時にストアが見えるようになる。

非アトミック・メモリー:非アトミックメモリシステムでは、1つのストアが異なるタイミングで異なるプロセッサから見えるようになる。

我々の知る限り、現在ではPOWERプロセッサーのメモリ・システムのみが非アトミックである。(GPUにも非アトミック・メモリがあるかもしれないが、CPUのメモリモデルのみを扱う本稿の範囲外である)。メモリ・システムが非アトミックになるのは、通常、共有ストア・バッファや共有ライトスルー・キャッシュがあるためである。

図4aのマルチプロセッサを考えてみよう。2つの物理コアC1とC2が2レベルのキャッシュ階層を介して接続されている。L1キャッシュは各物理コアのプライベートであり、L2は最終レベルの共有キャッシュである。各物理コアは同時マルチスレッディング(SMT)を有効にしており、プログラマには2つの論理プロセッサとして見える。つまり、論理プロセッサP1とP2はC1とそのストアバッファを共有し、論理プロセッサP3とP4はC2を共有する。P1がストアを発行すると、ストアはC1のストア・バッファにバッファリングされる。この場合、P2はストアの値を読み出すことができるが、P3とP4は読み出すことができない。さらに、P3またはP4が同じアドレスに対してストアを発行した場合、P1によるストアがストア・バッファに残っている間に、この新しいストアがC2のL1にヒットする可能性がある。従って、P3またはP4による新たなストアは、ストア・アドレスのコヒーレンス順序において、P1によるストアよりも前に順序付けられる。その結果、共有ストア・バッファはキャッシュ階層とともに非アトミック・メモリ・システムを形成する。

各論理プロセッサに、共有ストア・バッファ内のストアにタグを付けさせ、他のプロセッサがストア・バッファ内のストアを読み出さないようにすることができる。しかし、L1がライトスルー・キャッシュの場合、同様の理由でメモリシステムは非アトミックとなり、L1に値をタグ付けすることは現実的ではない。

L1をライトバックにしたとしても、図4bに示すようにDASHコヒーレンス・プロトコル[34]を使用すれば、メモリ・システムはアトミック・メモリ・システムにならない可能性がある。両方のL1がアドレスaを共有状態に保持し、P1がaへのストアを発行している場合を考える。この場合、コアC1のL1は、共有されているL2に対して排他的許可のリクエストを送信する。この要求を見たL2は、C1への応答とC2への無効化要求を同時に送信する。C1のL1は応答を受け取ると、C2からの無効化応答を待つことなく、直接キャッシュにストアデータを書き込むことができる。この瞬間、P2はC1のL1から最新のストアデータを読み出すことができるが、P3はaの元のメモリ値しか読み出すことができない。この瞬間、P3またはP4がaに対して別のストアを発行した場合、この新しいストアは、アドレスaのコヒーレンス順序において、P1によるストアの後に順序付けられなければならない。これは、共有ストア・バッファや共有ライトスルー・キャッシュを持つ非アトミック・メモリ・システムとは異なる。

アトミック・メモリ・モデルと非アトミック・メモリ・モデル:ほとんどのメモリ・モデルはアトミック・メモリ・モデルであり、例えばSC、TSO、RMO、Alpha、ARMv8などがある。現在、非アトミック・メモリ・モデルは POWERメモリモデルだけである。一般に、非アトミック・メモリ・モデルははるかに複雑である。実際、ARMは最近、バージョン8でメモリ・モデルを非アトミックからアトミックに変更した。アトミック・メモリ・モデルが普及しているため、本稿ではアトミック・メモリ・モデルのみを取り上げる。

C.既存のメモリ・モデルの問題点

ここで、既存のウィーク・メモリ・モデルを概観し、その問題点を説明する。

データ・レース・フリー(DRF)のSC: データ・レース・フリー0(DRF0)は、共有変数のレースがロックに制限されるソフトウェア・プログラムの重要なクラスである[35]。Adveら[35]は、DRF0プログラムの動作がSCに含まれることを示した。DRF0は、DRF-1[36]、DRFx[37]、DRF-rlx[38]に拡張され、より多くのプログラミングパターンをカバーしている。

また、DRFプログラムを高速化するハードウェア方式[39]~[41]もある。DRFは非常に有用なプログラミング・パラダイムであるが、ISAのメモリモデルは、非DRFプログラムを含むすべてのプログラムの動作を規定する必要がある。

リリース・コンシステンシ(RC): RC [42]も重要なソフトウェア・プログラミング・モデルである。プログラマは、同期メモリ・アクセスを通常のものと区別し、同期アクセスにacquireまたはreleaseというラベルを付ける必要がある。

直感的には、プロセッサP1のロード・acquireがプロセッサP2のストア・releaseの値を読み出す場合、P1のロード・acquireより若いメモリ・アクセスは、P2のストア・releaseより古いメモリ・アクセスの後に発生する。Gharachorlooら[42]は、適切にラベル付けされたプログラムとは何かを定義し、そのようなプログラムの動作がSCであることを示した。

RCの定義は、全てのプログラムの動作をイベントの並び替えで定義しようとするものであり、イベントとはプロセッサに対してメモリ・アクセスを行うことを指す。しかし、特にプログラムが適切にラベル付けされていない場合、イベントの順序に基づいて各負荷が得るべき値を導出することは容易ではない。Zhangら[43]は、RC定義(RCSCとRCPCの両方)が非アトミック・メモリ・モデルに特有な動作をいくつか認めていることを示したが、それでも実装上、すべての非アトミック・メモリ・システムをサポートしているわけではない(例えば、共有ストア・バッファや共有ライトスルー・キャッシュをサポートしていない)。 RMOとAlpha: RMO[44]とAlpha[45]は、アトミック・メモリ・モデルのクラスにおけるRCの亜種と見なすことができる。

両者とも4つのロード/ストアの並べ替えをすべて許容する。しかし、依存する命令の順序に関しては、両者には異なる問題がある。RMOは特定のケースで依存命令のリオーダリングを意図しているが、その定義は、実装が投機的ロード実行とストア転送を同時に実行することを禁じている[43]。Alphaは、依存命令のリオーダリングができる点でより自由である。しかし、これはOOTA(out-of-thin-air)問題を引き起こす[46]。図5は、値42が空中から生成されるOOTA動作の例を示している。すべてのロード/ストアのリオーダリングを許可することが、単にSCの公理的定義からInstOrderSC公理を削除することであるならば、この動作は合法である。このような問題を回避するために、Alphaは複雑な公理を導入している。この公理は、周期的な依存関係を回避するために、若いストアが古いロードと一緒に並び替えられるべきでないかどうかを判断するために、すべての可能な実行パスを調べることを要求している[45, Chapter 5.6.1.7]。

依存性とOOTAの問題に対処するために、最近提案されたウィーク・メモリ・モデルWMM [43]は、依存性を指定する際の複雑さを避けるために、依存性の順序付けを完全に緩和しているが、OOTAの問題を避けるために、常にロードからストアへの順序付けを強制している。これに対して本稿では、GAMの構築手順を通じて、依存関係の順序制約がどこから来るかを説明する。

ARM:セクションIで述べたように、ARMはメモリモデルを変更し続けている。加えて、ARMのメモリモデルは、同じアドレスに対するロードの順序に複雑さをもたらしている。

D. その他の関連研究

Adveらによるチュートリアル[47]は、上記で説明したいくつかのモデルと、その他のモデル [48]、[49]の関係を説明している。最近では、GPU[50]~[55]や不揮発性メモリ[56]~[59]などの新しいコンピューティング・リソースのためのプログラミング・モデルに関する研究が盛んである。また、C/C++[1]、[29]、[60]~[64]、Java[65]~[67]などの高級言語のセマンティクスを規定する取り組みも行われている。本稿では、CPU のメモリモデルについてのみ述べる。モデル検査ツールは、メモリ・モデルに関連するバグを発見するのに有用である。[23]、 [28]、[68]~[71]は、メモリ・モデル・テストの様々な側面のためのツールを提示している。

"Constructing a Weak Memory Model" を読む (1. 概要 / Introduction)

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

arxiv.org

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


概要

ウィーク・メモリ・モデルは、共有メモリ・マルチプロセッサを構築する際に、ユニ プロセッサの最適化をすべて維持したいというアーキテクト側の要望の結果である。

過去数十年にわたるARMやPOWERのウィーク・メモリ・モデルを形式化する努力は、そのほとんどが経験的なものであり、経験的に観察された動作を捕らえようとするもので、結局、ウィーク・メモリ・モデルの本質的な性質についての洞察は得られなかった。

本論文では、ウィーク・メモリ・モデルの共通基盤を見出すための建設的なアプローチをとる。すなわち、ユニプロセッサの最適化をすべて維持するという明確な目標を掲げてウィーク・メモリを構築した場合、どのようなものになるかを探る。プログラマの直感を非常に予期せぬ形で壊すような最適化は認めないことにする。一般原子メモリモデル(General Atomic Memory Model: GAM)と呼ぶこのモデルは、4つのロード/ストアの並べ替えをすべて許容する。GAMの構築手順を示し、その操作的意味論と公理的意味論を定義するための洞察を提供する。GAMを既存のウィーク・メモリモデルと比較する試みは行っていないが、シミュレーションによりGAMが他のモデルと同等の性能を持つことを示す。この論文を読むのにメモリモデルに関する深い知識は必要ない。

I. はじめに

ソフトウェア・プログラマは、ウィーク・メモリ・モデルを求めたことはない。しかし、ARMやPOWERのような重要な商用マシンでは、ウィークメモリ・モデルの結果として生じる動作に対処しなければならない。高級言語(C++11 など)の複雑な機能の多くは、ウィークメモリモデルを持つ ARM や POWER 向けに効率的なコードを生成する必要性から生じている[1]。

アーキテクチャ・コミュニティがウィーク・メモリ・モデルの亡霊を世に解き放った以上、以下の2つの問いに答えるべきである:

  1. ウィーク・メモリ・モデルはストロングモデルよりも PPA(性能/消費電力/面積)を向上させるか?
  2. ウィーク・メモリ・モデルには共通の意味論的基盤があるのか?この疑問は実用上重要である。というのも、専門家でさえ、さまざまな弱いモデルの正確な定義や、モデル間の違いについて合意できないからである。

最初の質問に答えるのは、2番目の質問よりもはるかに難しい。ARMやPOWERがウィーク・モデルを持っているのに対し、数十年にわたってCPU市場を支配してきたインテルはTSOを堅持している。ISCA/MICRO/HPCA[2]~[20]には、ストロング・メモリ・モデルの実装がウィーク・モデルの実装と同程度に高速である可能性を主張する論文が多数ある。この問題については、特に各社の利害が凝り固まっているため、短期的にコンセンサスが得られる可能性は低い。また、あるウィーク・メモリ・モデルがPPAの点で他のモデルより優れていることを示す研究は、我々が知る限り存在しない。

本稿では、2つ目の疑問、すなわちウィーク・メモリ・モデルに共通する基盤を見出そうとするものである。これまでの研究では、経験的なアプローチ、つまり、既存のマシンから出発して、メモリモデルの開発者がマシンの観測可能な動作にマッチする公理やルールのセットを考え出そうとしてきた。しかし、このアプローチでは、すべてのウィーク・モデルに共通する固有の性質についての洞察を得ることなく、市販のマシンで観察される微妙に異なる動作に研究者が溺れてしまっていることが観察される。例えば、Sarkar ら[21]は 2011 年に POWER の運用モデルを発表し、Mador-Haim ら[22]は 2012 年に運用モデルと一致することが証明された公理モデルを発表した。しかし、2014 年に Alglave ら[23]は、対応する公理モデルと同様に、元の運用モデルも POWER マシンで新たに観測された動作を除外することを示した。別の例としては、2016年にFlurら[24]がARMの運用モデルを示したが、対応する公理モデルはなかった。その1年後、ARMはISAマニュアルの改訂を発表し、Flurのモデルで許容される動作を明示的に禁止した[25]。

ウィーク・メモリ・モデルを経験的に定式化することは、明らかにエラーが発生しやすく、困難である。

本稿では、ウィーク・メモリ・モデルの共通基盤を見つけるために、異なる、より建設的なアプローチをとる。

マルチプロセッサは、原子共有メモリシステムにユニプロセッサを接続することで形成されると仮定し、すべてのプロセッサが従わなければならない最小制約を導出する。

同じアドレスのロード・ロード順序や依存ロード順序のような選択肢がまだ残っており、それぞれがわずかに異なるメモリモデルになることを示す。驚くことではないが、ARM、Alpha、RMOはこれらの選択において異なっている。

これらの選択肢の中には、モデルの運用定義と公理的定義を一致させることを困難にし、混乱を招くものもある。これらの選択肢を慎重に評価した結果、我々は一般的な原子メモリモデル(GAM)を導き出した。この洞察が、アーキテクトが実装前にメモリ・モデルを選択する際に役立ち、ISAがサポートするモデルのリバース・エンジニアリングに数え切れないほどの時間を費やすことを回避できることを期待している。

また、GAMの正式な演算定義と公理的定義を示すが、これらは等価であることが証明されている。

公理的定義は、すべての正当なプログラム動作が満たさなければならない公理の集合であり、充足可能性モジュロ理論ソルバーと組み合わせて、特定のプログラム動作が許されるか許されないかをチェックすることができる[23]、[27]、[28]。プログラムを実行する抽象的なマシンである演算定義は、実際のハードウェア動作の非常に自然な表現であり、プログラム[29]とハードウェア[30]の両方について、帰納法に基づく形式的証明で使用できる。

GAMを既存のモデルと完全に一致させることは試みないが、GAMが他のモデルに匹敵する性能を持つことをシミュレーションによって示す。

要約すると、本論文は以下の貢献をする:

  1. 全てのウィーク・メモリ・モデルに共通する制約
  2. 直感的なプログラム動作を回避するための共通制約に基づくメモリモデル、GAM
  3. GAMの等価な公理的定義と操作定義
  4. GAMの性能が他のウィーク・メモリ・モデルと遜色ないことを示す評価。

論文の構成 セクションIIでは、メモリ・モデルの背景と関連研究を紹介する。セクション III では GAM の構築手順を示す。セクションIVでは、GAMの正式な定義(すなわち、公理的定義と操作的定義)を示す。セクションVではGAMの性能を評価する。セクションVIでは結論を述べる。

自作CPUとサイクルモデルシミュレータのサイクル性能比較

自作CPUとサイクル精度シミュレータのサイクル比較を行っている。

モデルのパラメータが違っているので、いろいろと調整が必要だが、おおむね大きな流れとしては間違っていないように見える。 あとは分岐予測だな。RTL側の分岐予測がやはりうまく動いていないケースが散見されるように見える。 これは、自分のCPUがある程度モデルに近い性能を出すことができるようになってきたということかな。

自作CPUの命令発行ポリシの最適化検討 (1. 初期改良とその評価)

現在、自作CPUにおけるLSUのIQ(命令発行キュー)は、LSUパイプライン毎に分割されている。 これ自体を修正することも考えられるのだが、問題はIQへのディスパッチが偏りすぎていることだ。

現在の実装は非常にサボっていて、一度に発行できるメモリアクセス命令の数を4とし、LSUのパイプラインの数を2とすると、2つのIQへの命令の割り当ては "0, 1", "2, 3" としている。 これはLSU0側に命令が非常に偏るのは当たり前だ。

次に、2つのIQへの命令の割り当ては "0, 2", "1, 3" とすることを考える。 一見平等そうに見えるが、実はディスパッチグループ内で1命令しかメモリアクセス命令が存在しない場合には常に0側が使用されるため、バランスとしては非常にイマイチになる。

では、2つのIQへの割り当てをPCの下位インデックスを用いてみてはどうだ。 一見平等そうに割り当てられるように見えるが、例えば小ループで1つのメモリアクセス命令をひたすら繰り返す場合、これも同じLSU側にひたすら配置されることになってしまう。

こういう条件を加味すると、サイクル毎に先頭のIQインデックスを変えながらランダムにディスパッチするのがよさそうな気がしている。 つまり、あるサイクルはLSU0, LSU1の順番、あるサイクルはLSU1, LSU0の順番などランダムに入れ替える。

というわけで、まずは試行として2つのIQへの命令の割り当ては "0, 2", "1, 3" としてみた。実装は意外と簡単だった。

LSUのパイプラインの負荷はかなり分散されている。しかし性能自体は大きく向上しない... ここがクリティカルではないのか?もう少し解析してみる必要がありそう。