二重比較スワップ

ダブル比較スワップ( DCASまたはCAS2 ) は、特定の並行プログラミング手法をサポートするために提案されたアトミックプリミティブです。DCAS は、必ずしも連続していない 2 つのメモリ位置を取得し、事前に指定された「期待」値と一致する場合にのみ、そこに新しい値を書き込みます。そのため、これは、より一般的な比較スワップ(CAS) 操作の拡張です。

DCAS は、x86 CMPXCHG16B などの命令によって実装される倍幅比較スワップ ( DWCAS ) と混同されることがあります。ここで説明する DCAS は、通常はポインタサイズの 2 つの不連続なメモリ位置を処理しますが、DWCAS は 2 つの隣接するポインタサイズのメモリ位置を処理します。

マイケル・グリーンウォルドは博士論文で、DCAS を現代のハードウェアに追加することを推奨し、簡単に適用でき、かつ効率的なソフトウェアトランザクションメモリ(STM) の作成に使用できることを示しました。グリーンウォルドは、CAS に対する DCAS の利点として、高次 (複数項目) CAS n はDCAS では O( n )で実装できますが、単項 CAS ではO( n log p ) の時間が必要であることを指摘しています ( pは競合プロセスの数)。^[1]

DCASの利点の1つは、アトミックデック（二重リンクリスト）を比較的簡単に実装できることです。^[2] しかし最近では、CASのみを使用して同等の特性を持つSTMを実装できることが示されています^{[説明が必要]}。^[3]ただし、一般的にDCASは万能薬ではありません。ロックフリーおよび待機フリーのアルゴリズムをDCASを使用して実装することは、通常、CASと同じくらい複雑でエラーが発生しやすいです。^[4]

モトローラはかつて68kシリーズの命令セットにDCASを組み込んでいたが^[5]、他のプリミティブに比べてDCASが遅いため（キャッシュ処理の問題が原因と思われる）、実用的なコンテキストではDCASの使用は避けられている。^[6] 2015年現在^{[アップデート]}、DCASは広く生産されているCPUではネイティブにサポートされていない。

DCAS を 2 つ以上のアドレスに一般化したもの MCAS (マルチワード CAS) と呼ばれることがあります。MCAS はネスト可能なLL/SCで実装できますが、そのようなプリミティブはハードウェアで直接利用できません。^[3] MCAS は、さまざまな方法で DCAS の観点からソフトウェアで実装できます。^[7] 2013 年に、Trevor Brown、Faith Ellen、および Eric Ruppert は、マルチアドレス LL/SC 拡張 (彼らはこれを LLX/SCX と呼んでいます) をソフトウェアで実装しました。これは MCAS よりも制限が厳しいものですが^{[8]、自動コード生成を介して、}JDK CAS ベースのスキップリスト実装をわずかに上回る、最もパフォーマンスの高い並行二分探索木(実際には彩色木)の 1 つを実装できました。^[9]

一般的に、DCASはより表現力豊かなハードウェアトランザクショナルメモリによって提供できます。^[10] IBM POWER8とIntel Intel TSXはトランザクショナルメモリの実用的な実装を提供しています。SunのキャンセルされたRockプロセッサもこれをサポートしていたはずです。

参考文献

^ M. Greenwald. 「非ブロッキング同期とシステム設計」スタンフォード大学技術レポート STAN-CS-TR-99-1624 [1] (特に 10 ページ)
^ Ole Agesen、David L. Detlefs、Christine H. Flood、Alexander T. Garthwaite、Paul A. Martin、Mark Moir、Nir N. Shavit、および Guy L. Steele Jr. 「DCAS ベースの同時実行 Deques」。Theory of Computing Systems 35、第 3 号 (2002): 349-386。
^ ab Keir Fraser (2004)、「実用的なロックフリーダム」UCAM-CL-TR-579.pdf
^ Simon Doherty 他、「DCAS は非ブロッキングアルゴリズム設計の万能薬ではない」。アルゴリズムとアーキテクチャにおける並列処理に関する第 16 回 ACM シンポジウム、2004 年、216 ～ 224 ページ [2]。
^ CAS2
^ Greenwald, Michael、および David Cheriton。「非ブロッキング同期とオペレーティングシステム構造の相乗効果」OSDI '96 Proceedings of the second USENIX symposium on Operating systems design and implementation (1996): 123-136。(特にセクション 7.1「実験的実装」)
^ Harris, Timothy L.; Fraser, Keir; Pratt, Ian A. (2002). 「実用的なマルチワード比較スワップ操作」 Proc. Int'l Symp. 分散コンピューティング。CiteSeerX 10.1.1.13.7938。
^ Trevor Brown、Faith Ellen、Eric Ruppert。「非ブロッキングデータ構造の実用的なプリミティブ」。2013 ACM シンポジウム「分散コンピューティングの原理」の議事録、pp. 13-22。ACM、2013 年。
^ Trevor Brown、Faith Ellen、Eric Ruppert。「非ブロッキングツリーの一般的な手法」並列プログラミングの原理と実践に関する第 19 回 ACM SIGPLAN シンポジウムの議事録、329-342 ページ。ACM、2014 年。
^ Dave Dice、Yossi Lev、Mark Moir、Dan Nussbaum、Marek Olszewski (2009)「商用ハードウェアトランザクションメモリ実装の初期経験」Sun Microsystems 技術レポート (60 ページ) SMLI TR-2009-180。短縮版は ASPLOS'09 に掲載されました。doi : 10.1145/1508244.1508263。完全版レポートのセクション 5 では、HTM を使用して DCAS を実装する方法について説明しています。

外部リンク

米国特許 4584640 比較スワップ命令のための方法および装置

[1] M. Greenwald. 「非ブロッキング同期とシステム設計」スタンフォード大学技術レポート STAN-CS-TR-99-1624 [1] (特に 10 ページ)

[2] Ole Agesen、David L. Detlefs、Christine H. Flood、Alexander T. Garthwaite、Paul A. Martin、Mark Moir、Nir N. Shavit、および Guy L. Steele Jr. 「DCAS ベースの同時実行 Deques」。Theory of Computing Systems 35、第 3 号 (2002): 349-386。

[Fraser2004-3] Keir Fraser (2004)、「実用的なロックフリーダム」UCAM-CL-TR-579.pdf

[4] Simon Doherty 他、「DCAS は非ブロッキングアルゴリズム設計の万能薬ではない」。アルゴリズムとアーキテクチャにおける並列処理に関する第 16 回 ACM シンポジウム、2004 年、216 ～ 224 ページ [2]。

[5] CAS2

[6] Greenwald, Michael、および David Cheriton。「非ブロッキング同期とオペレーティングシステム構造の相乗効果」OSDI '96 Proceedings of the second USENIX symposium on Operating systems design and implementation (1996): 123-136。(特にセクション 7.1「実験的実装」)

[7] Harris, Timothy L.; Fraser, Keir; Pratt, Ian A. (2002). 「実用的なマルチワード比較スワップ操作」 Proc. Int'l Symp. 分散コンピューティング。CiteSeerX 10.1.1.13.7938。

[8] Trevor Brown、Faith Ellen、Eric Ruppert。「非ブロッキングデータ構造の実用的なプリミティブ」。2013 ACM シンポジウム「分散コンピューティングの原理」の議事録、pp. 13-22。ACM、2013 年。

[9] Trevor Brown、Faith Ellen、Eric Ruppert。「非ブロッキングツリーの一般的な手法」並列プログラミングの原理と実践に関する第 19 回 ACM SIGPLAN シンポジウムの議事録、329-342 ページ。ACM、2014 年。

[10] Dave Dice、Yossi Lev、Mark Moir、Dan Nussbaum、Marek Olszewski (2009)「商用ハードウェアトランザクションメモリ実装の初期経験」Sun Microsystems 技術レポート (60 ページ) SMLI TR-2009-180。短縮版は ASPLOS'09 に掲載されました。doi : 10.1145/1508244.1508263。完全版レポートのセクション 5 では、HTM を使用して DCAS を実装する方法について説明しています。