トップ «前の日記(2007-09-15) 最新 次の日記(2007-09-19)» 編集

U-memo

2006|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|08|
2009|08|10|
2010|02|03|
2011|11|12|
2012|04|
2016|02|
All= / Today= / Yesterday=

2007-09-17

_ [プロセッサ] 順不同に見せない努力

記事内容の言わんとするところにケチを付ける気は無いのだけれど、

並列に実行しちゃうことをOut of Order (OOO)実行とか言っちゃうのだけど、(厳密に言えばOOOは並列に実行することを含意していない。実行順が機械語の順番と違うことを言っているだけ)、それによって、ある命令列によって引き起こされる効果を、他の人が観察すると機械語と違う順序で観察されるのである。

それ違うし。 まず「並列に実行すること」は業界的には「スーパースカラ」と言っておいた方が良いと思うけれどさておいて。

OoOE でも、あくまでもプロセッサはプログラムオーダを保証しているので、少なくとも観測できる形式としては順序を「保証」しています。 と既にOut of Order (アウトオブオーダー)実行って・・・ で突っ込まれてますな。

OoOE で行っていることは、

  • 順序を引っくり返したところで結果に影響が無い

ときに順不同に(Out-of-order)実行する(Execution)わけです。 演算器の個数が限られているので、演算器の利用効率をあげて性能向上を図っているわけなのですが。そういうわけなので、

このとき、いつキャッシュミスが発生し(それはμOPの実行を数百命令浪費する)、いつキャッシュヒットするかはプロセッサの状態によるので、後ろの命令が先の命令を追い越して先に実行するというのは通常に発生している。上の命令列のどれが最初に終了するかは、誰もわからないのである。(すげーな、これは)

これは前半は正しいが後ろは嘘。 引っくり返して「実行」しているかもしれないけれど、「終了」は順番通りに行われる。IntelやAMDの用語にあわせれば、retire は順番通りになる。 AMD は retire すら順不同にしていた時期はあるけれど(今もかも)、それを観測出来る術は無いはず。(観測できる範囲内では順番通り)

例えば、あるアドレス(X) にAレジスタの値を代入し、次のアドレス(X+1)にBレジスタの値を代入するなんていう命令列では、Aレジスタの値が代入されてからBレジスタの値が代入されるなどという順序は、プロセッサは保証していないのである。(ああああ〜)

これは順序がきちんと保証されている。 Intel x86 でも(一部の命令に例外があるが)。

形式的に

store %a -> [X]
store %b -> [X+1]

という順序で命令が書かれていてこれらを実行したとき、 お隣のプロセッサで X+1 の中身が %b になっていて X の中身が まだ %a になっていないように処理されている、 と観測できてしまうとすれば、 これは一般的な SMP システムにおけるメモリオーダリング (Total Store Ordering などと呼ばれるもの) に違反している。

なお、問題をややこしくするのはこの順序を「観測する」手段であって、 Intel がプロセッサオーダリングと呼んでいるメモリオーダリング規則では、load の順は「推論」によって順不同に動く可能性があるのが話をややこしくする。参考: IA-32 インテル召アーキテクチャー・ソフトウェア・デベロッパーズ・マニュアル、下巻: システム・プログラミング・ガイド の7章。

ちゃんと知っていないと。ストアの順序を観測しようとおもって組んだプログラムが 意図通りに動いてくれない罠に陥る。 こういったメモリオーダリングは、 別に最新の OoOE でもスーパースカラでもない昔のパイプライン実行の CPU であっても、マルチプロセッサシステムになれば回避して通れない難しい話です。 とりあえず、Binary Hacks の Hack#94 でも読むと良いんだけれど、 余計混乱すること請け合い。

そういうわけなので、

こーゆー実行の挙動は外部から、観測するしかないのである。

そういう CPU の頑張っている様は、性能の変化という間接的な手段以外での直接的な観測はできないのだー。全ては ISA (Instruction Set Architecture) という壁に阻まれるのです。