プロセッサ一貫性
プロセッサ一貫性（プロセッサいっかんせい、英: processor consistency）またはプロセッサ整合性（プロセッサせいごうせい）とは、分散型共有メモリや分散型トランザクションなど、コンカレント・コンピューティングの領域で使用される一貫性モデル（整合性モデル）の一つである。
システムは、各プロセッサからの書き込みを他のプロセッサが見る順序が、その書き込みが発行された順序と同じであれば、プロセッサ一貫性を示す。このためプロセッサ一貫性は、複数のプロセッサを持つシステムにのみ適用される。すべてのプロセッサからの書き込みを同じ順番で見る必要がないため、因果一貫性モデルよりも弱いが、キャッシュコヒーレンスを必要とするため、PRAM一貫性モデルよりも強い[1]。因果一貫性とプロセッサ一貫性のもう一つの違いは、プロセッサ一貫性では、ロードがストアの完了を待つことや、書き込み不可分性の要件が削除されていることである[1]。プロセッサ一貫性は、同じメモリロケーションへの書き込みだけでなく、プロセッサによるすべての書き込みを順番に見る必要があるため、キャッシュ一貫性よりも強くなっている[1]。
プロセッサ整合性の例
[編集]| P1 | W(x)1 | W(x)3 | ||
|---|---|---|---|---|
| P2 | R(x)1 | R(x)3 | ||
| P3 | W(y)1 | W(y)2 | ||
| P4 | R(y)1 | R(y)2 |
| P1 | W(x)1 | W(x)3 | ||
|---|---|---|---|---|
| P2 | R(x)3 | R(x)1 | ||
| P3 | W(y)1 | W(y)2 | ||
| P4 | R(y)2 | R(y)1 |
右の例1では、単純なシステムはプロセッサ一貫性に従っている。各プロセッサによるすべての書き込みが、他のプロセッサによって発生した順序で観測されるため、トランザクションは首尾一貫している。例2はプロセッサ一貫性ではない。P1とP3による書き込みが、P2とP4によってそれぞれ順番が狂って見えるからである。
以下の例3では、最も強く適用できる一貫性モデルはプロセッサ一貫性である。これは、プロセッサごとに最大でも1つの書き込みしかないため、簡単に判断できる。この例は因果的に一貫していないが、P2のR(x)1がP2のW(x)2を引き起こす可能性があるため、P1のW(x)1がP2のW(x)2に因果的に先行することを立証できる。しかし、P3とP4は、P1とP2による2つの書き込みの順序に同意していない。
例4のシステムは、同じプロセッサによる書き込みが他のプロセッサでは順序が狂って見えることから、プロセッサ一貫性が「ない」と言える。具体的には、1つの場所への書き込みは順番に見られるが、P1によるW(x)2はP2によるW(y)4よりも先に見られることはない。順番に見える書き込みは、同じメモリロケーションへの書き込みだけであることから、この例はキャッシュ一貫性に限定される。
| P1 | W(x)1 | ||||
|---|---|---|---|---|---|
| P2 | R(x)1 | W(x)2 | |||
| P3 | R(x)1 | R(x)2 | |||
| P4 | R(x)2 | R(x)1 |
| P1 | W(x)2 | W(y)4 | W(x)3 | W(y)1 | ||
|---|---|---|---|---|---|---|
| P2 | R(y)4 | R(x)2 | R(y)1 | R(x)3 |
プロセッサ一貫性と逐次一貫性の比較
[編集]プロセッサ一貫性（PC）は逐次一貫性（SC）で強制されている古いストアと若いロードの順序付けを緩和する[2]。これにより、ロードがキャッシュに発行され、古いストアよりも先に完了する可能性がある。つまりロードの推測を実装する必要なく、ストアをライトバッファにキューイングすることができる（ロードは自由に継続できる）[3]。この点、プロセッサ一貫性（PC）は逐次一貫性（SC）よりも性能が高く、失敗した投機の回復技術が必要ないため、パイプラインのフラッシュ回数が少なくて済む[3]。逐次一貫性システムが採用しているプリフェッチによる最適化は、プロセッサ一貫性システムにも適用可能である。プリフェッチとは、ロードやストアの待ち時間を短縮するために、実際に必要となる前に、次のロードやストアのためにデータを事前に取得することである。プロセッサ一貫性では、ロードがストアに対応する前に再発行されることでロードのレイテンシーが短縮されるため、プリフェッチされたデータはロードよりもストアで使用されることになり、プリフェッチの必要性が多少減少する[3]。
プログラマーの直観
[編集]PCシステムがプログラマーの直感にどれだけ従っているかという点では、適切に同期されたシステムでは、プロセッサ一貫性と逐次一貫性の結果は同じであることがわかっている[3]。プログラマーの直感とは、基本的にプログラマーがどのように命令を実行することを期待しているかということで、通常は「プログラムオーダー」と呼ばれている。マルチプロセッサ・システムにおけるプログラムオーダーとは、逐次実行と同じ結果になる命令の実行のことである。プロセッサ一貫性と逐次一貫性がともにこの期待に沿っているのは、プロセッサ一貫性システムでは対応するロードとストアが互いに順序付けられているという事実に直接起因する[3]。例えばロック同期において、プロセッサ一貫性によって動作が完全に定義されていない唯一のオペレーションはロック・アクワイア・ストアであり、後続のロードがクリティカル・セクションにあり、その順序が結果に影響する[3]。しかし、この操作は通常、ストア条件付き命令またはアトミック命令で実装され、操作が失敗した場合には後から繰り返され、すべての若いロードも繰り返されることになる。
プロセッサ一貫性と他の緩和された一貫性モデルとの比較
[編集]プロセッサ整合性は、逐次整合性よりは弱いものの、ほとんどの場合、必要以上に強い整合性モデル(一貫性モデル)である[4]。マルチプロセッサシステム上で実行されるプログラムに固有の同期ポイントの数に起因する。データレースが発生しないことを意味する（データレースとは、少なくとも1つのアクセスが書き込みであるメモリロケーションへの複数の同時アクセスをすることである）。これを考慮すると、同期ポイントを横切る操作がない限り、すべてのメモリ操作の再編成を可能にするモデルが存在することは明らかである。しかし弱い順序は、プロセッサの一貫性と同じいくつかの制限を課している。すなわち、システムは一貫性を維持しなければならず、したがって、同じメモリ位置へのすべての書き込みは、すべてのプロセッサによって同じ順序で見られなければならない。弱い順序と同様に、リリース一貫性モデルは、すべてのメモリ操作の再順序付けを認めているが、さらに具体的になり、同期操作を分解して、再順序付けの緩和を認めている。これらのモデルはいずれも、コードの適切な同期と、場合によってはハードウェアによる同期サポートを前提としているため、プロセッサ一貫性は、そのモデルを使って実行するプログラムの信頼性に不安がある場合に準拠すべき、より安全なモデルと言える。
SPARC V8 TSO、IBM-370、およびx86-TSOメモリモデルとの類似性
[編集]プロセッサの一貫性の主な構成要素の1つは、書き込みの後に読み込みを行うと、プログラムの順番がずれて実行されることがあるというものである。これは本質的に、ロードがストアよりも先に実行されることが許される場合に、書き込みの遅延が隠蔽されるということである。この構造では多くのアプリケーションが正しく機能するため、この種の緩和された順序を実装したシステムは、一般的に順序が一貫しているように見える。この仕様に準拠している他の2つのモデルは、SPARC V8 TSO（Total Store Ordering）とIBM-370である[4]。
IBM-370モデルでは、いくつかの例外を除いて、書き込みの後に読み込みを行うと、プログラムの順番が狂ってしまうという仕様に従っている。1つ目は、2つの操作が同じ場所に対するものであれば、プログラム順でなければならないこと。2つ目は、どちらかの操作が直列化命令の一部であるか、または2つの操作の間に直列化命令がある場合、操作はプログラム順に実行されなければならないというものである。TSOモデルでは、前述の例外の1つが削除されているため、このモデルは、検討されている3つのモデルの中で、おそらく最も厳しいものである。
SPARC V8 TSOモデルは、IBM-370モデルと非常によく似ていますが、重要な違いは、同じ場所への操作がプログラム順に完了しないことを認めていることである。これらのモデルは、プロセッサの一貫性と似ているが、これらのモデルがメモリのコピーを1つしか持たないのに対し、プロセッサの一貫性にはそのような制限がない。これは各プロセッサが独自のメモリを持つシステムを示唆しており、プロセッサの一貫性に「コヒーレンス要件」を強調している。
x86-TSOモデルにはいくつかの異なる定義がある。トータルストアモデルは、その名の通り、SPARC V8と非常によく似ている。もう1つの定義は、ローカルな書き込みバッファに基づいている。x86とSPARCのTSOモデルの違いは、いくつかの命令が省略され、他の命令が含まれている点だが、モデル自体は非常に似ている。書き込みバッファの定義では、様々な状態とロックを利用して、特定の値の読み書きが可能かどうかを判断する。またx86アーキテクチャ用のこのモデルは、以前の（整合性の弱い）モデルの問題に悩まされておらず、プログラマーがより直感的に構築できるベースとなっている。
脚注
[編集]- ^ a b c David Mosberger (1992). Memory Consistency Models. University of Arizona 2015年4月1日閲覧。.
- ^ Kourosh Gharachorloo; Daniel Lenoski; James Laudon; Phillip Gibbons; Anoop Gupta; John Hennessy (1 August 1998) (PDF). Memory Consistency and Event Ordering in Scalable Shared-Memory Multiprocessors. ACM 2015年4月1日閲覧。.
- ^ a b c d e f Solihin, Yan (2009). Fundamentals of parallel computer architecture : multichip and multicore systems. Solihin Pub.. pp. 297–299. ISBN 978-0-9841630-0-7
- ^ a b Kourosh Gharachorloo (1995). Memory Consistency Models for Shared-Memory Multiprocessors. Western Research Laboratory 2015年4月7日閲覧。.