ロードリンク/ストア条件

コンピュータサイエンスにおいて、ロードリンク/ストア条件付き^[1] ( LL/SC ) は、ロード予約/ストア条件付き^[2] ( LR/SC )とも呼ばれ、マルチスレッドで同期を実現するために使用される命令のペアです。ロードリンクはメモリ位置の現在の値を返しますが、同じメモリ位置への後続のストア条件付きでは、ロードリンク以降にその位置に更新が発生していない場合にのみ新しい値を格納します。これらを組み合わせることで、ロックフリーでアトミックな読み取り、変更、書き込み操作が実装されます。

「ロードリンク」は、ロードリンク、^[3]、 ロードリザーブ、^[2]、ロードロックとも呼ばれます。^[要出典]

LL/SCはもともと、ローレンス・リバモア国立研究所のS-1 AAPマルチプロセッサ^[1]向けにJensen、Hagensen、Broughtonによって提案された^[4]。

LL/SCと比較スワップの比較

更新が行われた場合、ロードリンクによって読み取られた値が復元されたとしても、ストア条件は必ず失敗します。そのため、LL/SC ペアは、古い値が復元された場合に更新を検出しない比較スワップ(CAS) が続く読み取りよりも強力です ( ABA 問題を参照)。

LL/SC の実際の実装は、問題のメモリ位置への同時更新がない場合でも、必ずしも成功するとは限りません。コンテキストスイッチ、別のロードリンク、または (多くのプラットフォームでは) 別のロードまたはストア操作など、2 つの操作間の例外的なイベントにより、ストア条件が誤って失敗します。古い実装では、メモリバスを介してブロードキャストされた更新があると失敗します。これは、多くの理論的な LL/SC アルゴリズムに支障をきたすため、研究者によって弱い LL/SC と呼ばれています。 [ 5 ^]弱さは相対的であり、一部の弱い実装は一部のアルゴリズムに使用できます。

LL/SCはCASよりもエミュレートが困難です。さらに、コードをシングルステップで実行する場合など、ペアになったLL/SC命令間で実行中のコードを停止すると、前進が妨げられ、デバッグが難しくなります。^[6]

それにもかかわらず、LL/SCは、どちらかのプリミティブを他方のプリミティブに基づいてO(1)で待機なしで実装できるという意味でCASと同等である。^[7]

実装

LL/SC 命令は以下でサポートされています。

アルファ：ldl_l ^[8] /stl_c ^[9]およびldq_l ^[8] /stq_c ^[9]
PowerPC / Power ISA : lwarx/stwcx および ldarx/stdcx ^[10]^[11]
MIPS：ll/sc ^[12]およびlld/scd ^[13]
ARM : ldrex/strex (ARMv6、^[14] v7およびv8-M ^[15] )、およびldxr/stxr (ARMv8-A ^[16] )
RISC-V : lr/sc ^[2]
ARC : LLOCK/SCOND

一部の CPU ^{[どれですか? ] では、}排他的にアクセスされるアドレスをライトスルーモードで構成する必要があります。

通常、CPU はキャッシュラインまたはその他の粒度でロードリンクアドレスを追跡するため、キャッシュラインのどの部分に対しても (別のコアのストア条件によるか、単に通常のストアによるかに関係なく) 変更を行うと、ストア条件が失敗する可能性があります。

これらのプラットフォームはすべて、弱い^{[明確化が必要]} LL/SC を提供します。PowerPC 実装では、LL/SC ペアがロードをラップし、他のキャッシュラインにストアすることもできます(ただし、このアプローチは誤ったキャッシュライン共有に対して脆弱です)。これにより、たとえば、任意のカウンター再利用によるオブジェクトグラフの変更に直面しても、ロックフリーの参照カウントを実装できます (そうでない場合は、二重の比較とスワップ(DCAS) が必要です)。RISC-V は、長さが制限された LL/SC シーケンスの最終的な進行をアーキテクチャ的に保証します。

一部の ARM 実装では、8 バイトから 2048 バイトの範囲のプラットフォーム依存ブロックが定義されており、同じブロック内で LL と SC の間に通常のメモリアクセスがある場合、特定のブロックでの LL/SC の試行は失敗します。その他の ARM 実装では、アドレス空間全体のどこかに変更があると失敗します。前者の実装の方が強力で、最も実用的です。

ロードストアアーキテクチャを設計する場合、 LL/SC には CAS に比べて 2 つの利点があります。設計哲学 (およびパイプラインアーキテクチャ) で要求されているように、読み取りと書き込みは別々の命令です。また、両方の命令は 2 つのレジスタ(アドレスと値)のみを使用して実行できるため、一般的な2 オペランド ISAに自然に適合します。一方、CAS では 3 つのレジスタ (アドレス、古い値、新しい値) と、読み取られた値と書き込まれた値の間の依存関係が必要です。CISCアーキテクチャであるx86にはこの制約はありませんが、最新のチップでは CAS 命令を内部で別々の LL/SCマイクロ操作に変換する可能性があります。

拡張機能

ハードウェア LL/SC 実装では通常、LL/SC ペアのネストは許可されません。^[17]ネスト LL/SC メカニズムを使用すると、MCAS プリミティブ (単語を分散できるマルチワード CAS) を提供できます。^[18] 2013 年に、Trevor Brown、Faith Ellen、Eric Ruppert は、自動コード生成に依存するマルチアドレス LL/SC 拡張 (LLX/SCX と呼ぶ) をソフトウェアで実装しました。^{[19]彼らはこれを使用して、}JDK CAS ベースのスキップリスト実装をわずかに上回る、最もパフォーマンスの高い並行バイナリ検索ツリー(実際にはクロマティックツリー)の 1 つを実装しました。^[20]

参照

参考文献

^ ab 「S-1プロジェクト」。スタンフォードコンピュータサイエンスwiki。2018-11-30。
^ abc Andrew Waterman; Krste Asanović編 (2017-05-07). 「7.2 Load-Reserved/Store-Conditional 命令」。RISC-V 命令セットマニュアル、第 1 巻: ユーザーレベル ISA、バージョン 2.2 (PDF)。
^ US20030217115A1、Rowlands、Joseph、「CC-NUMA システムにおけるロードリンク/ストア条件付きメカニズム」、2003 年 11 月 20 日発行
^ Herlihy, Maurice (1993-11-01). 「高度に並行なデータオブジェクトを実装するための方法論」. ACM Transactions on Programming Languages and Systems . 15 (5): 745–770. doi :10.1145/161468.161469. ISSN 0164-0925.
^ Beckmann, Nathan. 「同期」（PDF）。15-740 ：コンピュータアーキテクチャ、2018年秋。カーネギーメロン大学。 2021年4月23日閲覧。
^ Keno Fischer (2020-05-02). 「Julia 1.5 機能プレビュー: タイムトラベル (Linux) バグ報告」2020-05-14閲覧。
^ James H. Anderson、Mark Moir (1995)。「マルチオブジェクト操作のユニバーサル構築」。PODC '95 分散コンピューティングの原理に関する第 14 回 ACM シンポジウム議事録。ACM。pp. 184–193。doi : 10.1145 / 224964.224985。ISBN 0-89791-710-3. S2CID 8204331。特に表 1、図 1 と 2、セクション 2 を参照してください。
^ ab 「Alpha Architecture Reference Manual」（PDF） pp. 4–9~4–12 。 2024年1月26日閲覧。
^ ab 「Alpha Architecture Reference Manual」（PDF） pp. 4–13~4–15 。 2024年1月26日閲覧。
^ May, Cathy; Silha, Ed; Simpson, Eick; Warren, Hank (1993). PowerPC アーキテクチャ: 新しい RISC プロセッサファミリの仕様。Morgan Kaufmann PUblishers, Inc. pp. 336–338, 465. ISBN 1-55860-316-6。
^ Kacmarcik, Cary (1995). PowerPC コードの最適化. Addison-Wesley Publishing Company. pp. 71–72. ISBN 0-201-40839-2。
^ 「アプリケーションノート MIPS R4000 同期プリミティブ」(PDF) . p. 9 . 2023-12-27に閲覧。
^ 「アプリケーションノート MIPS R4000 同期プリミティブ」(PDF) . p. 5 . 2023 年 12 月 27 日閲覧。
^ 「ARM11 MPCore™ プロセッサリビジョン: r2p0 テクニカルリファレンスマニュアル」。p. 301-302(8-7,8-8) 。2023 年 12 月 14 日閲覧。
^ 「Arm®v8-Mアーキテクチャリファレンスマニュアル」p. 278 。 2023年12月14日閲覧。
^ 「ARMv8-A 同期プリミティブ」。p. 6 。2023年12月14日閲覧。
^ James R. Larus、Ravi Rajwar (2007)。トランザクショナルメモリ。Morgan & Claypool。p. 55。ISBN 978-1-59829-124-7。
^ Keir Fraser (2004 年 2 月). 実用的なロックフリーダム(PDF) (技術レポート). ケンブリッジ大学コンピュータ研究所. p. 20. UCAM-CL-TR-579.
^ Brown, Trevor; Ellen, Faith; Ruppert, Eric (2013). 「非ブロッキングデータ構造の実用的なプリミティブ」(PDF) . PODC '13 Proceedings of the 2013 ACM symposium on Principles of Distributed Computing . ACM. pp. 13–22. arXiv : 1712.06688 . doi :10.1145/2484239.2484273. ISBN 978-1-4503-2065-8. S2CID 6537417。スライドも参照
^ Trevor Brown、Faith Ellen、Eric Ruppert (2014)。「非ブロッキングツリーの一般的な手法」( PDF)。PPoPP '14 ACM SIGPLAN 並列プログラミングの原理と実践に関するシンポジウム。ACM。pp. 329–342。arXiv : 1712.06687。doi : 10.1145 / 2555243.2555267。ISBN 978-1-4503-2656-8. S2CID 9442380。

Jensen, Eric H.; Hagensen, Gary W.; Broughton, Jeffrey M. (1987 年 11 月)。共有メモリマルチプロセッサにおける排他的データアクセスの新しいアプローチ(PDF) (技術レポート)。ローレンスリバモア国立研究所。UCRL-97663。2017年 2 月 2 日のオリジナル(PDF)からアーカイブ。2012年 2 月 22 日に取得。
Bruner, John D.; Hagensen, Gary W.; Jensen, Eric H.; Pattin, Jay C.; Broughton, Jeffrey M. (1987 年 11 月 11 日). S-1 AAP のキャッシュコヒーレンス(PDF) (技術レポート). ローレンスリバモア国立研究所. UCRL-97646. 2017 年 2 月 2 日時点のオリジナル(PDF)からアーカイブ。2013年11 月 10 日閲覧。
Detlefs, D.; Martin, P.; Moir, M.; Steele, Jr., Guy L. (2001). 「ロックフリー参照カウント」。PODC '01 Proceedings of the twentieth annual ACM symposium on Principles of Distributed Computing . ACM. pp. 190–9. CiteSeerX 10.1.1.92.8221 . doi :10.1145/383962.384016. ISBN 1-58113-383-9。
Reinholtz, Kirk (2004 年 12 月)。「アトミック参照カウントポインター」。C /C++ ユーザージャーナル。
Sites, RL (1993 年 2 月). 「Alpha AXP アーキテクチャ」. Comm. ACM . 36 (2): 33–44. doi : 10.1145/151220.151226 . S2CID 5473184.

[S-1-1] 「S-1プロジェクト」。スタンフォードコンピュータサイエンスwiki。2018-11-30。

[RISCV-2] Andrew Waterman; Krste Asanović編 (2017-05-07). 「7.2 Load-Reserved/Store-Conditional 命令」。RISC-V 命令セットマニュアル、第 1 巻: ユーザーレベル ISA、バージョン 2.2 (PDF)。

[3] US20030217115A1、Rowlands、Joseph、「CC-NUMA システムにおけるロードリンク/ストア条件付きメカニズム」、2003 年 11 月 20 日発行

[4] Herlihy, Maurice (1993-11-01). 「高度に並行なデータオブジェクトを実装するための方法論」. ACM Transactions on Programming Languages and Systems . 15 (5): 745–770. doi :10.1145/161468.161469. ISSN 0164-0925.

[5] Beckmann, Nathan. 「同期」（PDF）。15-740 ：コンピュータアーキテクチャ、2018年秋。カーネギーメロン大学。 2021年4月23日閲覧。

[Fischer2020-6] Keno Fischer (2020-05-02). 「Julia 1.5 機能プレビュー: タイムトラベル (Linux) バグ報告」2020-05-14閲覧。

[Anderson1995-7] James H. Anderson、Mark Moir (1995)。「マルチオブジェクト操作のユニバーサル構築」。PODC '95 分散コンピューティングの原理に関する第 14 回 ACM シンポジウム議事録。ACM。pp. 184–193。doi : 10.1145 / 224964.224985。ISBN 0-89791-710-3. S2CID 8204331。特に表 1、図 1 と 2、セクション 2 を参照してください。

[alpha-ll-8] 「Alpha Architecture Reference Manual」（PDF） pp. 4–9~4–12 。 2024年1月26日閲覧。

[alpha-sc-9] 「Alpha Architecture Reference Manual」（PDF） pp. 4–13~4–15 。 2024年1月26日閲覧。

[10] May, Cathy; Silha, Ed; Simpson, Eick; Warren, Hank (1993). PowerPC アーキテクチャ: 新しい RISC プロセッサファミリの仕様。Morgan Kaufmann PUblishers, Inc. pp. 336–338, 465. ISBN 1-55860-316-6。

[11] Kacmarcik, Cary (1995). PowerPC コードの最適化. Addison-Wesley Publishing Company. pp. 71–72. ISBN 0-201-40839-2。

[12] 「アプリケーションノート MIPS R4000 同期プリミティブ」(PDF) . p. 9 . 2023-12-27に閲覧。

[13] 「アプリケーションノート MIPS R4000 同期プリミティブ」(PDF) . p. 5 . 2023 年 12 月 27 日閲覧。

[14] 「ARM11 MPCore™ プロセッサリビジョン: r2p0 テクニカルリファレンスマニュアル」。p. 301-302(8-7,8-8) 。2023 年 12 月 14 日閲覧。

[15] 「Arm®v8-Mアーキテクチャリファレンスマニュアル」p. 278 。 2023年12月14日閲覧。

[16] 「ARMv8-A 同期プリミティブ」。p. 6 。2023年12月14日閲覧。

[LarusRajwar2007-17] James R. Larus、Ravi Rajwar (2007)。トランザクショナルメモリ。Morgan & Claypool。p. 55。ISBN 978-1-59829-124-7。

[Fraser2004-18] Keir Fraser (2004 年 2 月). 実用的なロックフリーダム(PDF) (技術レポート). ケンブリッジ大学コンピュータ研究所. p. 20. UCAM-CL-TR-579.

[Brown2013-19] Brown, Trevor; Ellen, Faith; Ruppert, Eric (2013). 「非ブロッキングデータ構造の実用的なプリミティブ」(PDF) . PODC '13 Proceedings of the 2013 ACM symposium on Principles of Distributed Computing . ACM. pp. 13–22. arXiv : 1712.06688 . doi :10.1145/2484239.2484273. ISBN 978-1-4503-2065-8. S2CID 6537417。スライドも参照

[Brown2014-20] Trevor Brown、Faith Ellen、Eric Ruppert (2014)。「非ブロッキングツリーの一般的な手法」( PDF)。PPoPP '14 ACM SIGPLAN 並列プログラミングの原理と実践に関するシンポジウム。ACM。pp. 329–342。arXiv : 1712.06687。doi : 10.1145 / 2555243.2555267。ISBN 978-1-4503-2656-8. S2CID 9442380。