リリース一貫性
リリース一貫性（リリースいっかんせい、英: release consistency）は分散型共有メモリや分散型トランザクションなど、並行プログラミングで使用される同期ベースの一貫性モデルの1つである。
概要
[編集]現代の並列コンピューティングシステムでは、望ましくない結果を避けるために、メモリの一貫性を維持する必要がある。逐次一貫性のような厳密な整合性モデルは、直観的に構成されているが、逐次プログラミングで広く適用されている命令レベルの並列処理を無効にしてしまうため、性能の面ではかなり制限される。より良い性能を得るために、いくつかの緩和されたモデルが検討されており、リリース一貫性は積極的な緩和の試みの一つである[1]。
リリース一貫性と逐次一貫性の比較
[編集]ハードウェアの構造とプログラムレベルの努力
[編集]逐次整合性はハードウェアの実装だけで実現できるが、リリース一貫性は多くの並列プログラムが適切に同期されているという観察に基づいている。プログラミングレベルでは、あるスレッドのメモリアクセスが他のスレッドの後に発生するように明確にスケジュールするために同期を適用する。同期変数がアクセスされるとハードウェアは、あるプロセッサのローカルな書き込みがすべて他のプロセッサに伝わり、他のプロセッサからの書き込みがすべて見られ、集められていることを確認する。リリース一貫性モデルでは、クリティカルセクションへの出入りの動作をアクイジション(取得)とリリース(解放)に分類し、いずれの場合も、これらの動作を行うタイミングを示す明示的なコードをプログラムに記述する。
逐次一貫性がとれる条件
[編集]一般に分散共有メモリが以下のルールに従う場合、リリース一貫性があるとされている。
- 共有変数へのアクセスを行う前に、そのプロセッサが以前に行ったすべての取得が完了していなければならない。
- リリースを実行する前に、このプロセスによる以前のすべての読み取りと書き込みが完了していなければならない。
- アクイジションとリリースのアクセスは、プロセッサの一貫性がなければならない。
上記の条件が満たされ、プログラムが適切に同期されていれば（すなわち、プロセッサがアクワイアとリリースを適切に実装していれば）、どのような実行結果であっても、逐次整合性に従って実行された場合と全く同じになる。共有変数へのアクセスは、アクワイア（取得）とリリース（解放）によってアトミックな操作ブロックに分割され、ブロック間の競合やインターリーブを防ぐことができる。
導入事例
[編集]ロックリリース
[編集]
ロックリリースはリリース同期の一種と考えられる。右図のようなコードでループ処理が行われているとする。2つのスレッドがクリティカルセクションに入り、aの最新の値を読み込んだ後、クリティカルセクションを抜ける予定である。このコードでは、まずスレッド0がロックを取得してクリティカルセクションに入る。正しく実行するためには、P0が書き込んだaの最新値をP1が読み込まなければならない。その際、一度に1つのスレッドしかクリティカルセクションに入ることができない。したがって、P0がロックを解放した後にP1のロック獲得が成功するように、同期自体が保証されている。また、P0がaの新しい値をP1に伝達しなければならないため、S2→S3の順序が保証されなければならない。同じ理由で、S5はS4の後に発生しなければならない[2]。
ロック解除問題の後にロック解除完了前にメモリ・アクセスを行っても、ロック獲得後にロック問題の前にメモリ・アクセスを行っても、正しさに影響はない。ただし，ロック取得が完了する前にクリティカルセクションのコードを発行すると、相互排除が保証されない可能性があるため発行できない。
ポストウェイト
[編集]
ポストウェイト同期はリリース一貫性のもう一つの実装形態となる。右のコードに示されているように、ポスト操作はすべてのメモリアクセス（特に'a'へのストア）が完了した後にのみ行われれば、正しさが保証される。また読み取り操作は、待機操作が完了するまで実行してはいけない。S2はリリース同期、S3はアクイジション同期として動作する。したがって、S2は前の実行が後に発生しないようにする必要があり、S3は後の実行が前に発生しないようにする必要がある。S2は自分より後の実行を防ぐ必要はなく、同様にS3も自分より後の実行を防ぐ必要はない。
遅延リリース一貫性
[編集]
遅延リリース一貫性はリリース一貫性をさらに最適化したものです。アクイジション・アクセスを実行するスレッドは、アクイジション・アクセスが完了するまで、他のスレッドが書き込んだ値を必要としないと仮定している。したがって、コヒーレンスのすべての動作を遅延させたり、書き込みの伝播のタイミングを調整することができる[3]。
例
[編集]右の画像のようなシナリオを考えてみる。このケースはリリース一貫性モデルに基づいたキャッシュコヒーレントシステムで、書き込み伝搬が行われる場合を示している。datumIsReadyの伝搬の前に、変数datumは完全に伝搬されている。しかしdatumの値はP1の同期アクセスを獲得するまで必要ないため、datumIsReadyとともに伝播させても、プログラムの結果に悪影響を与えることはない。
2つ目の図は、遅延解放整合性が適用された場合の例です。このシナリオでは、リリース同期の前に書き込まれたすべての値が遅延され、リリース・アクセス自体の伝搬とともに伝搬される。したがって、datumとdatumIsReadyはリリースポイントで一緒に伝搬される。
遅延リリース一貫性を実際に適用した例として「TreadMarks」[4]がある。
リリース一貫性の性能向上
[編集]遅延リリース一貫性は、場合によってはリリース一貫性を上回る性能を発揮する。プロセッサ間のバンド幅が小さいシステムや、小さなデータブロックを頻繁に伝搬するのと大きなデータブロックを頻繁に伝搬しないのとでは、オーバーヘッドが大きくなってしまうため、遅延リリース一貫性（LRC）はパフォーマンスを大きく向上させることができる。
実際のハードウェア実装ではなく、ソフトウェアレベルで共有メモリを抽象化したシステムを考えてみる。このシステムでは、書き込みの伝搬はページ単位で実行されるため、ページ内の1つのブロックだけが変更された場合、ページ全体を伝搬させるのは非常にコストがかかる。そのため、書き込み伝搬はリリース同期ポイントに到達するまで遅延され、この時にページ全体が変更され、ページ全体が伝搬されることになる。
欠点
[編集]遅延リリース一貫性（LRC）では、リリース同期点で一括して書き込み伝搬を行う必要がある。このような大量の書き込みを一括して伝搬させると、リリースアクセスとそれに続くアクイジションアクセスが遅くなる。そのため、ハードウェアキャッシュコヒーレンスシステムの性能を向上させることはできない。
リリース一貫性と他の緩和された一貫性モデルとの比較
[編集]弱い順序 (弱い一貫性)
[編集]リリース一貫性は、弱い順序（ウィークオーダリング）と比較して、プログラマーに多くのことを要求する。同期アクセスを単に同期アクセスとしてではなく、アクイジションまたはリリースとしてラベル付けしなければならない。弱い順序付けと同様に、リリース一貫性では、ロードとストアを自由に並べ替えることができるが、アクワイア同期を越えて上方に移動することはできず、リリース同期を越えて下方に移動することもできない。しかし、リリース一貫性の柔軟性と性能上の利点は、同期アクセスを適切に識別し、アクワイアとリリースを識別する必要性を犠牲にしている。弱い順序の場合とは異なり、同期アクセスは命令のオペコードだけでは簡単に識別できない。したがってアクワイアとリリースの同期アクセスを適切に識別することは、プログラマーの肩にかかる負担となる。
プロセッサ一貫性
[編集]プロセッサ一貫性のために、すべてのプロセスは、各プロセッサからの書き込みを開始された順に見る。異なるプロセッサからの書き込みは、同じ順序で見られるとは限らない。ただし、同じ場所への書き込みは、どこでも同じ順序で見られる。プロセッサ一貫性と比較して、リリース一貫性は、プロセッサ一貫性で発生するストア間の順序付けを強制しないため、より緩和されている。コンパイラの最適化に対する制限が比較的少ないため、プログラマの直感には従う必要がない。
脚注
[編集]- ^ Memory Consistency and Event Ordering in Scalable Shared-Memory Multiprocessors by Kourosh Gharachorloo, Daniel Lenoski, James Laudon, Phillip Gibbons, Anoop Gupta, and John Hennessy published in ISCA '90 Proceedings of the 17th annual international symposium on Computer Architecture
- ^ Solihin, Yan (2015). Fundamentals of Parallel Multicore Architecture. Chapman & Hall/CRC Computational Science. pp. 315–320. ISBN 9781482211184
- ^ Lazy release consistency for software distributed shared memory by Pete Keleher, Alan L. Cox, and Willy Zwaenepoel published in Proceeding ISCA '92 Proceedings of the 19th annual international symposium on Computer architecture
- ^ TreadMarks: distributed shared memory on standard workstations and operating systems by Pete Keleher, Alan L. Cox, Sandhya Dwarkadas and Willy Zwaenepoel published in WTEC'94 Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference