私がいうべきだったのは、その規則は global visibility にとって不要であること、 そして 2: → 1: という追い越しだと解釈すればすべてOKですよということだけ だったと思います。
あと、Store forwarding は、いまだ global visible でない store 値を local にのみ見せて、後続の "local load" を先に visible にする効果がある という解釈は、さほど受け入れがたいものとも思わないのですが。 （こう考えると、すっきり矛盾のないメンタルモデルが出来上がると思っている）
なお、すでにお気づきと思うのですが、「1: → 2: の順序は global からも この順の筈だ」という規則を追加した理解は、TSO と似て異なる、もうひとつの memory model (pseudo-TSO) に相当するものであって、「インプリメントにも メモリモデルにも依存しない global visible order の定義 ([22])」には なっていないんじゃないかとも思います。
(I) > > PoO の一番素直な解釈では「a conceptually subsequent storage-operand > > fetch from the same main-storage location が storage-operand store > > を追い越した状態」とは、self-consistency が壊れた状態ですよ。 > > わたしはこれには同意しません。 > > 私が同意しない理由は、段落の最初、"As observed by other CPUs and > by channel programs" が効いているので、この文を認め、かつ、その CPU 自身 > からみれば conceptually order が見えるという両立が成り立つから。
うんのさんは、(B) の文は conceptual order 則を含んでおらず、もっと前にある 5.13.1 Conceptual Sequence 節などに書かれた原則が適用できるという解釈なのだと思います。
私が元コメント[20]のように書いた理由を述べておきます。 一つ目はコメント[26]で述べている IBM 370 自身の古さや、先行の IBM 360 のメモリモデルの問題です。
(C) The CPU does not fetch operands, ART-table entries, or DAT-table entries from a storage location until all information destined for that location by the CPU has been stored. Prefetched instructions may appear to be updated before the information appears in storage.
System/370 PoO の "Storage-Operand Store References" は、やはり同様の記述を含んでいます。
(C') A CPU does not fetch operands, or dynamic-address-translation table entries, from a main-storage location until all information destined for that real main-storage location by that CPU has been placed in main storage. Prefetrched instructions may appear to be updated prior to the information appearing in storage.
この二つのパラグラフは、ある CPU に立った動作として store が終わるまで fetch を行わないというものですから、CPU の内側からの conceptual order に関する記述と読めます。なおかつ CPU が store を完了し "all information destined for that location" になる時点まで待つので、外側から見た場合の順序も規定することになるでしょう。
Relation between Operand Accesses: (A') Storage-operand fetches associated with one instruction execution precede all storage-operand references for conceptually subsequent instructions. A storage-operand store specified by one instruction precedes all storage-operand stores specified by conceputually subsequent instructions, but it does not necessarily precede storage -operand fetches specified by conceptually subsequent instructions. (B') However, a storage-operand store does precede a conceptually subsequent storage-operand fetch to the same real storage location.
memory model なしでは、「store が globally visible になるまで、その値は 他の CPU からは見えない」以外の仮定は自明ではないので、 globally visible order はほとんど決まらない。 それ以上を望むのであれば、memory model がそうしているように、 globally visible order についてより多くの制約が必要になります。
nminoru さんのやろうとしていたことは、memory model が定める順序が globally visible order だということには同意せず、 memory model 以前に（またはmemory model の外に) あるものとして globally visible order を考えようとなさっているようですね。
(I) "However, a storage-operand store appears to precede a conceptually subsequent storage-operand fetch from the same main-storage location." を否定すると self-consistency が壊れる、には同意しません。
> PoO の一番素直な解釈では「a conceptually subsequent storage-operand > fetch from the same main-storage location が storage-operand store > を追い越した状態」とは、self-consistency が壊れた状態ですよ。
わたしはこれには同意しません。
私が同意しない理由は、段落の最初、"As observed by other CPUs and by channel programs" が効いているので、この文を認め、かつ、その CPU 自身 からみれば conceptually order が見えるという両立が成り立つから。
本 (I) 項は、わたしが最初に書いた↓とそのまま対応します。
> これは、かなり典型的な混乱具合なのですが、Multi processor > システムにおける global visible 順序と、self-consistency > （綴りあってるかな）をごちゃまぜにされています。
(II) 「同じメモリアドレスへ store → load があった場合、 load は store から直接データを貰える(メモリに読みに行かない)が store が完了するまで待つ必要がある」を global visibility に組み入れる という構想がすぐれているとは思いません。
ひとまず、私が考えている global visibility と nminoru さんのものは 別だと認めてしまいます。
その上でも、
「同じメモリアドレスへ store → load があった場合、 load は store から直接データを貰える(メモリに読みに行かない)が store が完了するまで待つ必要がある」
>> 私が指摘したのは、"However, a storage-operand store appears ..." >> の一文が store forwarding の禁止に相当するということ。 >これは認めます。
ですね。
「この一文が store forwarding の禁止に相当する」という主張と、 下の主張には随分隔たりがあるように思います。
> うんのさんは S/370 系 CPU に Store forwarding を導入するとしたら > PoO の "Relation between Operand Accesses" の項の > "However, a storage-operand store appears to precede a conceptually > subsequent storage-operand fetch from the same main-storage location." > の記述(とそれと同様の部分)を削るだけで済むとお考え
・プロセッサが実行した命令列は判明している。 ・プロセッサは以下のルールを守る限り命令を自由に入れ替えて実行する可能性がある。 ただし命令は1命令づつ逐次的に実行され、その度に完了したと考える。 a) レジスタに依存関係がある場合はその順序に従い実行された。 b) 制御に依存関係がある場合はその順序に実行された。 c) ロード・ストア命令は "order" の順序に従い実行された。 ・実行結果(メモリの内容とレジスタの最終値)は、現状と一致すること。
ですが blog に「TSO 等のメモリ・モデルは、global visible order に関する規則です。にも関わらず、例えば、load がいつの時点で global visible になるのか、そもそも、global visible とはなんなのか？という記述なしに、TSO の説明が始まっているように見えます。なぜなら、TSO メモリ・モデル全体が、global visible order を定義するからです。」という言葉があり、うんのさんが global visibility order = memory model と信じられているのは分かりました。 そう疑ってはいたのですが「SPARC の用語定義においては、Memory order と global visiblility order とは別の概念です(コメント[13])」とか「(a),(b) は明らかにあやまってますね(同[13])」とか言ううんのさんの言葉に躓いて、global visibility order = memory model という結論に至れませんでした。
続いてうんのさんは blog の中で「特定のインプリメントに依存しないようにglobal visible order を定義する方法は、これしか無いように思われます。」とおっしゃいます。それならインプリメントにもメモリモデルにも依存しない global visible order の定義があるとすると、その方がスマートだとは思われませんか。
その後、blog の中で例を引きながら以下のような説明をされていますが、
1. Memory model によって決まる memory ordering に従ってメモリ操作の順序付けられる。 2. メモリ操作のうちプロセッサの外部に出て行くメモリ操作は、外部から観測できる。 3. 外部からの観測で global visibility order が決まる。 4. 残ったメモリ操作(ここでは local load)は、memory ordering rule を再適用して順序を決める。
1. と 4. は一致しないかも知れませんが両方とも memory odering rule に従うわけで、幾分トートロジカルです。4. の替わりに「load はその値の供給した store より後」という束縛を加えれば、メモリモデルへ依存せずに global visibility order が定義できます。
ところで以下のような思考実験をした場合、私は memory model による global visibility order の定義に違和感を感じます。
--- TSO に良く似た別のメモリモデル "Pseudo TSO" があるとします。
1. 後続 store は先行 store を追い越せない。 2. アドレスの異なる後続 load は先行 store を追い越せる。 3. load は load を原則追い越せないが、4. のような local load を通常の load が追い越してもよい。 4. 同じメモリアドレスへ store → load があった場合、load は store から直接データを貰える(メモリに読みに行かない)が store が完了するまで待つ必要がある。
> R bit はそもそも設定条件がゆるい上に、R=C=1 のときには > store forwarding の有無による問題はないと思いますよ。
ぶっちゃけるとその通りです。 と言うか PoO 的には 5.13.7 Storage-Key Accesses (http://publib.boulder.ibm.com/cgi-bin/bookmgr/BOOKS/DZ9AR006/5.13.7?DT=19990630131355) には "The record of references provided by the reference bit is not necessarily accurate, and the handling of the reference bit is not subject to the concurrency rules." とありますから、local load 時には R ビットを立てないという実装は考えられます。
(A) As observed by other CPUs and by channel programs, storage-operand fetches associated with one instruction execution appear to precede all storage-operand references for conceptually subsequent instructions. A storage-operand store specified by one instruction appears to precede all storage-operand stores specified by conceptually subsequent instructions, but it does not necessarily precede storage-operand fetches specified by conceptually subsequent instructions. (B) However, a storage-operand store appears to precede a conceptually subsequent storage-operand fetch from the same main-storage location.
同様の箇所は 5.13.8 節などにもあるのですが、だいたい同じことを言っていますので 5.13.10 節で代表できるでしょう。(A) の文は store buffer による「load による store の追い越し」を認める文言です。(B) の文は store forwarding を禁止しています。(B) は (A) の付帯的な禁則条項ですね。
> 私が指摘したのは、"However, a storage-operand store appears ..." > の一文が store forwarding の禁止に相当するということ。 これは認めます。
> つまり、store forwarding は、 > a conceptually subsequent storage-operand fetch from the same main-storage location が storage-operand store を追い越させる効果があると読める、ということのみです。
ここが分からないのです。
PoO の一番素直な解釈では「a conceptually subsequent storage-operand fetch from the same main-storage location が storage-operand store を追い越した状態」とは、self-consistency が壊れた状態ですよ。無論、これは store forwarding ではありません。しかしうんのさんは「a conceptually ... を追い越した状態」に、後続 local load が先行 store を追い抜いた状態を含むのだとお考えです。
うんのさんが (B) の一文だけを PoO の想定しているメモリモデルから切り離して考えているなら別ですが、そうでないなら後続 local load による先行 store の追い抜きという状況が (A) の記述や PoO の他のメモリモデルに関する記述と整合性を保っている必要がありますよね？ そしてコメント[13]で「Store forwarding をした場合、後続の load が先行の store を追い抜くことになるという私と同じ言葉使いを IBM もしてますよ」とおっしゃったからには、その整合性はあると考えられたはずです。 もし store forwarding を実現するために (B) とそれと同内容の箇所以外に修正を加える必要があるのだとしたら、それはうんのさんの言葉使いと (IBM の) PoO のモデルが異なっていることになりませんか？
> うんのさんは S/370 系 CPU に Store forwarding を導入すると > したら PoO の "Relation between Operand Accesses" の項の > "However, a storage-operand store appears to precede a > conceptually subsequent storage-operand fetch from the same > main-storage location." の記述(とそれと同様の部分)を削る > だけで済むとお考えです。
「削るだけで済む」とは主張していないし、ほのめかしてもいません。
単に、この文言が store forwarding の禁止に相当すると言いました。 また、storage-key の問題があるので、この文言が取り除けない のだという点には既に（ゆるやかに）同意しています。
#「あり得ると思い」とぼやかしたのは、この点きちんと考えていな #いので、本当に store forwarding と storage-key がどうやっても #原理的に共存不可なのかについて、態度を保留しているためでした。 #いまここで、この問題に深入りしたくはないなぁ。
私が指摘したのは、"However, a storage-operand store appears ..." の一文が store forwarding の禁止に相当するということ。 つまり、store forwarding は、 a conceptually subsequent storage-operand fetch from the same main-storage location が storage-operand store を追い越させる効果があると読める、ということのみです。
私は上記の SPARC V9 のマニュアルの中から global visibility に関するはっきりした定義は見つけられずにいます。またメモリモデルの文脈で visible という言葉が使われる箇所を順に読むと、store 操作か barrier 操作しか visible と言っていないように読めます。 ＃ その中で Single-Port Memory への値が反映が完了した or Single-Port Memory から値を反映した状態が、 ＃ global visible だと私は漠然と理解しました。
私の知っている範囲で visibility order を一番はっきりした定義しているのは、"A Formal Specification of Intel Itanium Processor Family Memory Ordering" です。 http://developer.intel.com/design/itanium/downloads/251429.htm しかし IA-64 メモリモデルは CPU 毎に独立したメモリを持っていて、load は常にローカルなメモリから読み、store が global visible になった時点で他の CPU のメモリに転送されるというモデル(つまり他の CPU の load は見えないモデル)になります。
私の言い方が悪くて申し訳ない。 IBM PoO はソフト開発者の立場から記述されおり、store buffer や cache のようなプロセッサの内部構造は隠蔽されている点はうんのさんも御存知のはずです。そして「(異なるメモリアドレスに対する)load が store を追い抜く」という記述は、PoO では "as observed by other CPUs" つまり外部の CPU から観測可能な事象として記述されています。
うんのさんは S/370 系 CPU に Store forwarding を導入するとしたら PoO の "Relation between Operand Accesses" の項の "However, a storage-operand store appears to precede a conceptually subsequent storage-operand fetch from the same main-storage location." の記述(とそれと同様の部分)を削るだけで済むとお考えです。しかしそれでは storage-key など PoO の他の部分と整合性が取れなくなると私は思います。もし整合性が取れないのだとすると、それは PoO の "as observed by other CPUs" によって規定されるメモリ規則と、うんのさんが考える SPARC の「global visibility order」には差があるのではないでしょうか？
これは私の考えですが、S/370 系 CPU に store forwarding を導入した場合、PoO には store forwarding という言葉や説明が出てこないと思います。そして PoO の "Relation between Operand Accesses" などの記述が「store-reference 後から serialization までの間に同じメモリに対する fetch-reference があった場合、その fetch-reference が他のプロセッサから観測できるかどうかは unpredictable である」という風に書き改められると考えます。 ＃ つまり 1:store[X] → 2:load [X] → 3:load [Y] は、2: よりも先に 3: が "observed by other CPUs" されると風になる。
いいえ。(a),(b) は明らかにあやまってますね。 Global visibility order というからには、あるプロセッサのメモリ操作を「外部か ら」観測したものです。
ただ、外部から観測されるというのがどういうことなのかという点で大幅に齟齬が ある模様です。
観測されるのは順序であって、各 load/store がそれぞれ global visible になった 瞬間に「あ、いまだ」と観測されるわけではありません。 結果的にプログラムがどう動いたか（だれの、いつの時点の store 値を load が受 け取ったか）を通じて、順序が観測されるのです。
> (a) なら簡単です。 > SPARC の memory ordering の定義を調べてみると (a) が近そうです。 > SPARC V8 Spec. は (Figure 6-1 Model of Memory の図を見ると明らかのように) > Single-Port Memory へのメモリアクセスの順序、つまりメモリトランザクション > の順序が memory ordering だと定義しています。そのため store forwarding を > 受けた load 命令(以下、local load と呼ぶことにします)は memory ordering に > よる順序付けの適用外になります。以下のように記述されています。 > -------- > A load by a processor first checks its Store Buffer to see if it contains > a store to the same location (atomic load-stores do not need to be checked > for because they block the processor). If it does, then the load returns > the value of the most recent such store; otherwise the load goes directly > to memory. SINCE NOT ALL LOADS GO TO MEMORY, LOADS IN GENERAL DO NOT > APPEAR IN THE MEMORY ORDER. A processor is blocked from issuing further > memory operations until the load returns a value. > --------
V8 が手元になかったので（手抜きですみません）、V9 と言葉使いが変わらないもの として。
SPARC の用語定義においては、Memory order と memory model (こちらは global visibility に関する) global visiblility order とは別の概念です。
Memory order の方は、ほぼ dependency order / self-consistency と同じ意味で 定義されています (V9 manual で D.2)
したがって、上記引用のキャピタル強調部分の意味合いは、
「すべての load がメモリに出るわけではないので（つまり、store forwarding が許容されるので）、一般に、load が global visible になる順序は命令順 とは一致しない」
おそらく global visibility order の定義が、私とうんのさんで異なるのだと思います。
パターンとしては (a),(b),(c) でしょうか。
(a) あるプロセッサの立場に立って、そのプロセッサが行った global なメモリ操作(store buffer からデータを bypass された local load を除く)の順序関係。 (b) あるプロセッサの立場に立って、そのプロセッサが行ったロード命令がデータの供給を受ける事象と、store 命令がデータをメモリに書き込む事象の順序関係。 (c) あるプロセッサが行った全てのメモリ操作が「仮想的に」メモリに反映されたと考えた場合、それをその外側のプロセッサが観察していたと考えた場合の順序関係。
うんのさんは (b) の立場で、私は (c) の立場なのだと思います。
(a) なら簡単です。 SPARC の memory ordering の定義を調べてみると (a) が近そうです。 SPARC V8 Spec. は (Figure 6-1 Model of Memory の図を見ると明らかのように) Single-Port Memory へのメモリアクセスの順序、つまりメモリトランザクションの順序が memory ordering だと定義しています。そのため store forwarding を受けた load 命令(以下、local load と呼ぶことにします)は memory ordering による順序付けの適用外になります。以下のように記述されています。 -------- A load by a processor first checks its Store Buffer to see if it contains a store to the same location (atomic load-stores do not need to be checked for because they block the processor). If it does, then the load returns the value of the most recent such store; otherwise the load goes directly to memory. SINCE NOT ALL LOADS GO TO MEMORY, LOADS IN GENERAL DO NOT APPEAR IN THE MEMORY ORDER. A processor is blocked from issuing further memory operations until the load returns a value. --------
うんのです。
本来話題になるべきは (II) だけだったように思われます。
(I), (III) を発生してしまったのは、私の議論のまずさでした。
お恥ずかしい。ずいぶん遠回りしてしまいました。
以下では、便宜的に
1: STORE [X] = 1
2: LOAD r1 = [X]
3: LOAD r2 = [Y]
の番号を用いている個所があります。
・(I) について。
> うんのさんは、(B) の文は conceptual order 則を含んでおらず、
> もっと前にある 5.13.1 Conceptual Sequence 節などに書かれた原則が
> 適用できるという解釈なのだと思います。
その通りです。
・(II) について。
本来この点だけを議論すべきでした。
> 矛盾があるようではダメだと言われるかも知れません。
ええ、ポイントはまさにここだと考えます。そして、この矛盾の原因は
「1: → 2: の順序は global からもこの順の筈だ」という信念からくる暗黙の
規則 (1: → 2:) です。
私がいうべきだったのは、その規則は global visibility にとって不要であること、
そして 2: → 1: という追い越しだと解釈すればすべてOKですよということだけ
だったと思います。
あと、Store forwarding は、いまだ global visible でない store 値を
local にのみ見せて、後続の "local load" を先に visible にする効果がある
という解釈は、さほど受け入れがたいものとも思わないのですが。
（こう考えると、すっきり矛盾のないメンタルモデルが出来上がると思っている）
なお、すでにお気づきと思うのですが、「1: → 2: の順序は global からも
この順の筈だ」という規則を追加した理解は、TSO と似て異なる、もうひとつの
memory model (pseudo-TSO) に相当するものであって、「インプリメントにも
メモリモデルにも依存しない global visible order の定義 ([22])」には
なっていないんじゃないかとも思います。
・(III) について。しかし、poo を持ち出したのは失敗でした。
まず、私がコメント [10] で件の段落を poo から引いてきた動機を白状しておいた
方が話が早い気がします。
動機は純粋に感情的なもので（誉められたものではないです）、
「SPARC V9 Spec. 的には正しいのでしょうが。([5])」に仄めかされるような、
私の理解は SPARC-V9 方言的ローカルな理解だという主張に対する反発でした。
そもそもが感情的なうえに、権威として IBM poo を持ち出すという
二重のチョンボなんですが、いおうとしたのは、次のとおり。
nminoru さん的モデル（もしくは言葉つかい）では、store forwarding の禁止
は「ただし、3: が 2: を追い越すようなこともあってはなりません」という趣旨の
文になる筈。しかしそうはなっておらず、「ただし、2: が 1: を追い越しては
いけません」になってますよね。
こんな風に IBM を味方につけたところで、どうなるわけでもない点、
および、そのせいで存分に脱線してしまった点は、私が反省すべきことです。
最後に、盛大に招かれざる客を演じてしまい、すみませんでした。
性懲りも無くまた来るかもしれませんが、よろしくお願いします。
あ、そうだ。元住吉駅が高架化されるのに伴ったできたのは、長い「エスカレータ」
なんではないかと……。あ、いえ、すんません。
うんのさんのコメント[24]へ：
(I)
> > PoO の一番素直な解釈では「a conceptually subsequent storage-operand
> > fetch from the same main-storage location が storage-operand store
> > を追い越した状態」とは、self-consistency が壊れた状態ですよ。
>
> わたしはこれには同意しません。
>
> 私が同意しない理由は、段落の最初、"As observed by other CPUs and
> by channel programs" が効いているので、この文を認め、かつ、その CPU 自身
> からみれば conceptually order が見えるという両立が成り立つから。
うんのさんは、(B) の文は conceptual order 則を含んでおらず、もっと前にある 5.13.1 Conceptual Sequence 節などに書かれた原則が適用できるという解釈なのだと思います。
私が元コメント[20]のように書いた理由を述べておきます。
一つ目はコメント[26]で述べている IBM 370 自身の古さや、先行の IBM 360 のメモリモデルの問題です。
二つ目は PoO の中に書かれた (B) 以外の記述との整合性です。
私は PoO は重要な規約は繰り返し具体的に述べられていると考えます。メモリ操作をオーバーラップする CPU の中で conceptual sequence を守るためには memory disambiguation が必要です。これに該当する記述は、5.13.10 節の (B) の以外では 5.13.8.2 節 "Storage-Operand Store References" の以下のパラグラフになるはずです。
(C) The CPU does not fetch operands, ART-table entries, or DAT-table entries from a storage location until all information destined for that location by the CPU has been stored. Prefetched instructions may appear to be updated before the information appears in storage.
System/370 PoO の "Storage-Operand Store References" は、やはり同様の記述を含んでいます。
(C') A CPU does not fetch operands, or dynamic-address-translation table entries, from a main-storage location until all information destined for that real main-storage location by that CPU has been placed in main storage. Prefetrched instructions may appear to be updated prior to the information appearing in storage.
この二つのパラグラフは、ある CPU に立った動作として store が終わるまで fetch を行わないというものですから、CPU の内側からの conceptual order に関する記述と読めます。なおかつ CPU が store を完了し "all information destined for that location" になる時点まで待つので、外側から見た場合の順序も規定することになるでしょう。
問題の ESA/390 PoO の 5.13.10 節の (A), (B) の記述は、5.13.8.1 節 "Storage-Operand Fetch References" と 5.13.8.2 節 "Storage-Operand Store References" を合わせたものの要約になっています。(B) の記述は上の (C) のパラグラフを端的に言ったものだと私は考えます。そのため (B) は store forwarding の禁止則であると同時に、self-consistency に関する規則でもあると判断するのです。
＃ 小さな点ですが、コメント[26] で述べた 370 PoO には段落の最初の
＃ "As observed by other CPUs and by channel programs," がありません。
-----
(II)
> 1: STORE [X] = 1
> 2: LOAD r1 = [X]
> 3: if r1 == 1 { LOAD r2 = [Y] }
> のようにしてみては、どうでしょう。
コメント[8]の例ですね。
まずこれは 3: → 1: の追い越しが起こっていると考えていいですね。
この場合、私のやり方で外側からプロセッサを観察をすると、
・メモリのアクセス順序を 3: → 1: → 2: と判断して、3: が制御を越えて先行してしまった矛盾を抱える。
・メモリのアクセス順序を 2: → 3: → 1: と判断して、2: と 3: が逆転してしまった矛盾を抱える。
のどちらかだと思います。
矛盾があるようではダメだと言われるかも知れません。
ただこの矛盾は、元の日記の
1: STORE [X] = 1
2: LOAD r1 = [X]
3: LOAD r2 = [Y]
が 3: → 1: → 2: に見えて、TSO と較べると 2: と 3: の逆転が起きるように見えて困ったねというのと同根だと思います。
＃ 外からブラックボックスとしてプロセッサ見ていると、local load のような in-flight な操作を見切れないと問題
-----
> (III) （横道だとは思いますが、）わたしが、いつ、poo に
> store forwarding を導入しようとした場合の困難について言及しましたか？
> 「この一文が store forwarding の禁止に相当する」という主張と、
> 下の主張には随分隔たりがあるように思います。
うんのさんの主張は「この一文が store forwarding の禁止に相当する」だけではなく、例えばコメント[13]の「Store forwarding をした場合、後続の load が先行の store を追い抜くことになるという私と同じ言葉使いを IBM もしてます」とおっしゃっています。
過去のうんのさんの発言から、私は以下のように推論しています。
1. うんのさんは ESA/390 PoO の 5.13.10 節 の (B) は store forwarding の禁止則であると認めている。
2. うんのさんは IBM S/370 のメモリモデルに store forwarding を導入することを検討された。
3. 2. は PoO の書き換えと同義である。
4. うんのさんは (B) の記述から S/370 のメモリモデルに store forwarding を導入した場合「a conceptually subsequent storage-operand fetch from the same main-storage location が storage-operand store を追い越させる効果がある」(コメント[17])と考えられている。
5. 1.〜 4. より、うんのさんは IBM S/370 メモリモデルに store forwarding を導入しようとし、PoO から (B) を削除あるいは変更し、PoO の中に 4. の同一アドレスの load が store を追い越せるいうルールを加える必要があると判断したと考えられる。
6. コメント[13]などから判断して、うんのさんは、storage-operand fetech reference が store forwarding によって local load のように扱われても構わないと考えていると思われる。その場合には 4. は 5.13.10 節の (A) 則に含まれるので、5. は (B) を削るだけで実現できる。
1.〜4. には合意いただけると思います。
5. は納得いただけませんか？
5. → 6. は私の推論ですので、うんのさんが違うとおっしゃられれば謝るほかありません。
> メモリモデルが単純なので self consistency を守るということは、
> 同時に外から見た順序を守るということでもあります。
訂正させてください。
コメント[26]で self consisntecy と外から見た順序が同一になると言っているのは、同一のメモリアドレスに関するメモリアクセスのみです。
異なるメモリアドレスのメモリアクセスに関しては、当然 conceptual sequence と sequence observed by other CPUs が異なるのと認識しています。
>メモリモデルが単純なので self consistency を守るということは、同時に外から見た順序を守るということでもあります。
これがおかしい。
ちょっと忙しくてお返事が遅れていますがご容赦を。
うんのさんのコメント[24] の (I) にも関係があると思うので、先に見えざるオーディエンスさんのコメント[25]にリプライします。
> self consistency を述べるのであればその節の当該段落中に書くのは不適切だということです。
> むしろ PoO の(他の部分の)書き方からすると、この(B)文では self consistency を述べる気はなく
> store forwarding を禁止したいだけでしょう。
今例としてあげているのは ESA/390 PoO の記述ですが、この中でメモリモデルに関係している部分は "Conceptual Sequence"・"Storage-Operand Fetch References"・"Storage-Operand Store References"・"Relation between Operand Accesses" の節ですよね。
ESA/390 のこれらの記述は、S/370 PoO の記述をほとんどそのまま引き継いでいます。例えば IBM System/370 Principles of Operation GA22-7000-4 (Sep. 1974 の Fourth Edition) を見つけてきたのですが、ESA/390 の 5.13.10 Relation between Operand Accesses (http://publib.boulder.ibm.com/cgi-bin/bookmgr/BOOKS/DZ9AR006/5.13.10?DT=19990630131355) にあたる部分は以下のように書かれています。
Relation between Operand Accesses:
(A') Storage-operand fetches associated with one instruction execution precede all storage-operand references for conceptually subsequent instructions. A storage-operand store specified by one instruction precedes all storage-operand stores specified by conceputually subsequent instructions, but it does not necessarily precede storage -operand fetches specified by conceptually subsequent instructions.
(B') However, a storage-operand store does precede a conceptually subsequent storage-operand fetch to the same real storage location.
(B') は "does" が "appears to" に、"main-storage" が "real storage" になった以外は (B) と同じですね。
1974年当時は store forwarding による local load のような in-flight なメモリ操作はなかった(はず)です。当然 PoO の operand-fetch/store reference もメインメモリに出ていくデータアクセスを想定した定義ですよね。また IBM 370 の前に IBM 360/91 のメモリモデル(同一メモリアドレスに対する store → load は守るけど、load → store は追い抜く可能性あり)があったことを考えると、(B') の記述は self consistency を守るという意味ですよ。メモリモデルが単純なので self consistency を守るということは、同時に外から見た順序を守るということでもあります。
もしそうなら、(B') とほとんど同じ内容の (B) が self consistency を含まないと言うことはないでしょう。
> # そもそも Self consistency 則は5章の中盤あたりの「Conceptually sequence」ではないですか。
PoO は同じ記述を切り口を変えて繰り返すことが多いですから、Self consistency に関することがあそこに書いてあるからここは self consistency のことは書いてないだろう、ということにはならないと思います。
中盤がどこを指すか良く分かりませんが、ESA/390 PoO の 5章の初盤にある 5.13.1 Conceptual sequence の節は self-consistency の概念(と Self-Modifying Code の扱い)について書いているだけなので、5.13.8.1 節と5.13.8.2 節でより詳細な説明がなされていますよね。5.13.10 節の第一パラグラフ((A)+(B))は、5.13.8.1 節と5.13.8.2 節の切り口を変えた要約ではないでしょうか？
>>[21]
>その文面というのがコメント[20] の (B) の文のことでしょうか？
そうです。
self consistency を述べるのであればその節の当該段落中に書くのは不適切だということです。むしろ PoO の(他の部分の)書き方からすると、この(B)文では self consistency を述べる気はなく store forwarding を禁止したいだけでしょう。
store forwarding を許すことを親切に書くなら programming note 扱いで (B) 文の否定を書くのだと思います。
# そもそも Self consistency 則は5章の中盤あたりの「Conceptually sequence」ではないですか。
うんのです。
どうやら同意には至らないようですが……。
・ うんのは memory model で決まるのが globally visible order だと考えていた。
これには同意します。
かつ、私の議論が迷走していたおかげで、このことが確認されるのが遅くなって
しまったことも確かで、このことはお詫びします。
memory model なしでは、「store が globally visible になるまで、その値は
他の CPU からは見えない」以外の仮定は自明ではないので、
globally visible order はほとんど決まらない。
それ以上を望むのであれば、memory model がそうしているように、
globally visible order についてより多くの制約が必要になります。
nminoru さんのやろうとしていたことは、memory model が定める順序が
globally visible order だということには同意せず、
memory model 以前に（またはmemory model の外に) あるものとして
globally visible order を考えようとなさっているようですね。
それならば、それに反対する理由は私には特にありません。
ただし、詳細について、同意できない点がいくつかあるので、列挙します。
個人的に、私はこれらの点に賛成していないことを明示しておきたいというのが
動機です。
(I) "However, a storage-operand store appears to precede
a conceptually subsequent storage-operand fetch
from the same main-storage location." を否定すると self-consistency
が壊れる、には同意しません。
> PoO の一番素直な解釈では「a conceptually subsequent storage-operand
> fetch from the same main-storage location が storage-operand store
> を追い越した状態」とは、self-consistency が壊れた状態ですよ。
わたしはこれには同意しません。
私が同意しない理由は、段落の最初、"As observed by other CPUs and
by channel programs" が効いているので、この文を認め、かつ、その CPU 自身
からみれば conceptually order が見えるという両立が成り立つから。
本 (I) 項は、わたしが最初に書いた↓とそのまま対応します。
> これは、かなり典型的な混乱具合なのですが、Multi processor
> システムにおける global visible 順序と、self-consistency
> （綴りあってるかな）をごちゃまぜにされています。
(II) 「同じメモリアドレスへ store → load があった場合、
load は store から直接データを貰える(メモリに読みに行かない)が
store が完了するまで待つ必要がある」を global visibility に組み入れる
という構想がすぐれているとは思いません。
ひとまず、私が考えている global visibility と nminoru さんのものは
別だと認めてしまいます。
その上でも、
「同じメモリアドレスへ store → load があった場合、
load は store から直接データを貰える(メモリに読みに行かない)が
store が完了するまで待つ必要がある」
が global visibility にとって必要、または、有益だとは考えません。
(I) 項が同意されていない状況で、この議論が可能だとは思えない
のですが、以前私が出した命令列の例（以下）をどう料理するつもり
なのかには、ちょっと興味があります。
> これについては、命令列を少し変形して、
> 1: STORE [X] = 1
> 2: LOAD r1 = [X]
> 3: if r1 == 1 { LOAD r2 = [Y] }
> のようにしてみては、どうでしょう。
# もしかすると、こんな命令列は考えるに値しない？
(III) （横道だとは思いますが、）わたしが、いつ、poo に
store forwarding を導入しようとした場合の困難について言及しましたか？
「うんのさんがそうおっしゃるとは意外です。」とまで言われているので、
まるで私は自分が確かにいったことをしらばっくれているかのような
ムードですが？？？？
>> 私が指摘したのは、"However, a storage-operand store appears ..."
>> の一文が store forwarding の禁止に相当するということ。
>これは認めます。
ですね。
「この一文が store forwarding の禁止に相当する」という主張と、
下の主張には随分隔たりがあるように思います。
> うんのさんは S/370 系 CPU に Store forwarding を導入するとしたら
> PoO の "Relation between Operand Accesses" の項の
> "However, a storage-operand store appears to precede a conceptually
> subsequent storage-operand fetch from the same main-storage location."
> の記述(とそれと同様の部分)を削るだけで済むとお考え
＃ コメント[22]の続き
まず一番最初の日記部分に戻ります。
私は store forwarding を認める TSO(*1) の memory model で 1:store [X] → 2:load[X] → 3:load[Y] を実行した場合、その memory order が 2: → 3: → 1: になることは認めています。また、それが TSO Memory Model の仕様に反しているとは言っていません。
「問題がどこにあるかというと、プログラマーがこの挙動を外側から見ると、… このタイプのロード→ロードの追い抜きは発生する。」の述べているように、TSO に従った動作をするプログラムであっても外側からプロセッサを観察するとロード→ロードの追い抜きが発生しているように見えると言っています (私の書き方が悪くて誤解を生じているかもしれませんが)。
＃ (*1) この表現には問題があることは認めます。コメント[5] で述べているように Store forwarding を認めないと TSO にはなりません。
私の認識：
外側からのプロセッサの観察 ＝ global visibility order ≠ TSO
うんのさんの認識：
外側からのプロセッサの観察 ≠ global visibility order ＝ TSO
なのだと思います。
上で「外側からのプロセッサの観察」と言っているのは、以下のようなモデルを基に "order" がどうなるのかを逆算したものです。表現は面倒ですが以前のコメントで言っていることと同じで、ソフト屋が普通に考えるプロセッサ実行の推論モデルだと思います。
・プロセッサが実行した命令列は判明している。
・プロセッサは以下のルールを守る限り命令を自由に入れ替えて実行する可能性がある。
ただし命令は1命令づつ逐次的に実行され、その度に完了したと考える。
a) レジスタに依存関係がある場合はその順序に従い実行された。
b) 制御に依存関係がある場合はその順序に実行された。
c) ロード・ストア命令は "order" の順序に従い実行された。
・実行結果(メモリの内容とレジスタの最終値)は、現状と一致すること。
おそらくそれでも、うんのさんは「外側からプロセッサを見ても、そのメモリ操作の順序は memory ordering に従うというのが正しい」とおっしゃりたいでしょう。しかし最初の日記部分はもともと似て異なるメモリモデル間のプロセッサの間でメモリ操作の "order" を考えていたわけで、モデル依存しすぎる定義では意味をなさないのです。
> 私が示したような理解は、SPARC-V9 の記述を素直に読めば
> 得られるものだと思います。
> それ以外の解釈（たとえば nminoru さんのような）は、
> SPARC-V9 の記述は不完全なのではないかという偏見なしには
> 得られないものだと思います。
>
> IBM poo と同じく、SPARC-V9 のメモリモデルも、
> ソフトから観測される振る舞いのみに着眼してかかれています。
>
> そうではないと考えた根拠、
> また、SPARC-V9 TSO の記述が不完全だと考えた
> （こう考えているから、どこからともなく規則をもちだしたの
> だと理解しています）根拠は何なんでしょうか。
SPARC V9 TSO のメモリモデルに関しては、(SPARC V9 Architecture Manual の表現のぶれはあると考えますが) 全体として不完全だと考えていません。
問題は「外側からのプロセッサの観察した場合のメモリ順序」で、この順序の解釈が私とうんのさんで違う理由はコメントの前半部分でご理解いただけませんか？
うんのさんのコメント[19]へ：
http://uhideyuki.sakura.ne.jp/uDiary/?date=20060922 のうんのさんのblogを拝見させていただきました。
ただコメント[15]の私のお願い(うんのさんは御自身の global visibility order の定義をスタンダードだと考えられてますが、その出典を明らかにして欲しい)への回答にはなっていないと思います。
ですが blog に「TSO 等のメモリ・モデルは、global visible order に関する規則です。にも関わらず、例えば、load がいつの時点で global visible になるのか、そもそも、global visible とはなんなのか？という記述なしに、TSO の説明が始まっているように見えます。なぜなら、TSO メモリ・モデル全体が、global visible order を定義するからです。」という言葉があり、うんのさんが global visibility order = memory model と信じられているのは分かりました。
そう疑ってはいたのですが「SPARC の用語定義においては、Memory order と global visiblility order とは別の概念です(コメント[13])」とか「(a),(b) は明らかにあやまってますね(同[13])」とか言ううんのさんの言葉に躓いて、global visibility order = memory model という結論に至れませんでした。
続いてうんのさんは blog の中で「特定のインプリメントに依存しないようにglobal visible order を定義する方法は、これしか無いように思われます。」とおっしゃいます。それならインプリメントにもメモリモデルにも依存しない global visible order の定義があるとすると、その方がスマートだとは思われませんか。
その後、blog の中で例を引きながら以下のような説明をされていますが、
1. Memory model によって決まる memory ordering に従ってメモリ操作の順序付けられる。
2. メモリ操作のうちプロセッサの外部に出て行くメモリ操作は、外部から観測できる。
3. 外部からの観測で global visibility order が決まる。
4. 残ったメモリ操作(ここでは local load)は、memory ordering rule を再適用して順序を決める。
1. と 4. は一致しないかも知れませんが両方とも memory odering rule に従うわけで、幾分トートロジカルです。4. の替わりに「load はその値の供給した store より後」という束縛を加えれば、メモリモデルへ依存せずに global visibility order が定義できます。
ところで以下のような思考実験をした場合、私は memory model による global visibility order の定義に違和感を感じます。
---
TSO に良く似た別のメモリモデル "Pseudo TSO" があるとします。
1. 後続 store は先行 store を追い越せない。
2. アドレスの異なる後続 load は先行 store を追い越せる。
3. load は load を原則追い越せないが、4. のような local load を通常の load が追い越してもよい。
4. 同じメモリアドレスへ store → load があった場合、load は store から直接データを貰える(メモリに読みに行かない)が store が完了するまで待つ必要がある。
Pseudo TSO は条件によって load → load の追い越しを認めるのが True TSO と違う所です。ですが、True TSO と Pseudo TSO は両方 self-consisntecy で、他のプロセッサから観測したメモリ操作はまったく同じになります。
では 1:store [X] → 2:load [X] → 3:load[Y] のコードを二つのメモリモデルで実行して、3: → 1: となるような追い抜きが起こった場合はどうでしょう。Memory order として True TSO の場合は 2: → 3: → 1: になり、Pseudo TSO の場合は 3: → 1: → 2: になりますよね。
問題は global visibility order で、うんのさんの解釈では True TSO の場合は 2: → 3: → 1: で Pseudo TSO の場合は 3: → 1: → 2: という異なる結果になります。
この結果にうんのさんが違和感を感じられないのだとしたら、あとは authorized された global visibility order の定義を探す旅に出るか、堂堂巡りの議論を繰り返すだけになると思います。
---
コメントが長大になりすぎるのはスパム対策的にまずいので、次のコメント[23] に続けます。
コメント[18] の見えざるオーディエンスさん：
> R bit はそもそも設定条件がゆるい上に、R=C=1 のときには
> store forwarding の有無による問題はないと思いますよ。
ぶっちゃけるとその通りです。
と言うか PoO 的には 5.13.7 Storage-Key Accesses (http://publib.boulder.ibm.com/cgi-bin/bookmgr/BOOKS/DZ9AR006/5.13.7?DT=19990630131355) には "The record of references provided by the reference bit is not necessarily accurate, and the handling of the reference bit is not subject to the concurrency rules." とありますから、local load 時には R ビットを立てないという実装は考えられます。
> その文面は storage key とは関係なく単に後方互換性のために外せないということでは。
その文面というのがコメント[20] の (B) の文のことでしょうか？
だとすると (B) の文には store forwarding の禁止以外に、self-consistency 則という意味もありますので、簡単には外せないのではないでしょうか？
うんのさんのコメント[17]へ：
> これだけ先にすませてしまいましょう。
(snip)
> 「削るだけで済む」とは主張していないし、ほのめかしてもいません。
うんのさんがそうおっしゃるとは意外です。
我々は "global visibility order" について議論してきたわけで、ESA/390 PoO の中でそれをもっとも端的に定義しているのはコメント[10]の中でうんのさん自身があげられている 5.13.10 Relation between Operand Accesses (http://publib.boulder.ibm.com/cgi-bin/bookmgr/BOOKS/DZ9AR006/5.13.10?DT=19990630131355 ) の節ですよね。
(A) As observed by other CPUs and by channel programs, storage-operand fetches associated with one instruction execution appear to precede all storage-operand references for conceptually subsequent instructions. A storage-operand store specified by one instruction appears to precede all storage-operand stores specified by conceptually subsequent instructions, but it does not necessarily precede storage-operand fetches specified by conceptually subsequent instructions.
(B) However, a storage-operand store appears to precede a conceptually subsequent storage-operand fetch from the same main-storage location.
同様の箇所は 5.13.8 節などにもあるのですが、だいたい同じことを言っていますので 5.13.10 節で代表できるでしょう。(A) の文は store buffer による「load による store の追い越し」を認める文言です。(B) の文は store forwarding を禁止しています。(B) は (A) の付帯的な禁則条項ですね。
> 私が指摘したのは、"However, a storage-operand store appears ..."
> の一文が store forwarding の禁止に相当するということ。
これは認めます。
> つまり、store forwarding は、
> a conceptually subsequent storage-operand fetch from the same main-storage location が storage-operand store を追い越させる効果があると読める、ということのみです。
ここが分からないのです。
PoO の一番素直な解釈では「a conceptually subsequent storage-operand fetch from the same main-storage location が storage-operand store を追い越した状態」とは、self-consistency が壊れた状態ですよ。無論、これは store forwarding ではありません。しかしうんのさんは「a conceptually ... を追い越した状態」に、後続 local load が先行 store を追い抜いた状態を含むのだとお考えです。
うんのさんが (B) の一文だけを PoO の想定しているメモリモデルから切り離して考えているなら別ですが、そうでないなら後続 local load による先行 store の追い抜きという状況が (A) の記述や PoO の他のメモリモデルに関する記述と整合性を保っている必要がありますよね？ そしてコメント[13]で「Store forwarding をした場合、後続の load が先行の store を追い抜くことになるという私と同じ言葉使いを IBM もしてますよ」とおっしゃったからには、その整合性はあると考えられたはずです。
もし store forwarding を実現するために (B) とそれと同内容の箇所以外に修正を加える必要があるのだとしたら、それはうんのさんの言葉使いと (IBM の) PoO のモデルが異なっていることになりませんか？
＃ あるいは『「削るだけで済む」とは主張していないし、ほのめかしてもいません。』という一文は、
＃ (B) を削る以外にも PoO のメモリモデルの本質を変えないもっとよい修正方法があると
＃ お考えだったからかもしれませんが。
コメント [15] の答えになるでしょうか。
ちょっと不安ですが、そのつもりで書きました。
http://uhideyuki.sakura.ne.jp/uDiary/?date=20060922
SPARC-V9 を私はこう読んでいますというのをまとめ。
初めからこう述べなかったのは、nminoru さんとのやり取りと、
それらを反省する過程で、「自分はどう読んでいるのかな」
と考え直してみた結果でてきたものだからでした。
SPARC-V8 にあった Figure 6.1 相当が V9 から取り除かれたのは
なぜかな？と考えたのは、上をまとめるのにいいヒントになった
ように思っています。
Fig 6.1 のようなイメージは、
不必要、不完全かつミスリーディングだからやめたんだと思います。
私が示したような理解は、SPARC-V9 の記述を素直に読めば
得られるものだと思います。
それ以外の解釈（たとえば nminoru さんのような）は、
SPARC-V9 の記述は不完全なのではないかという偏見なしには
得られないものだと思います。
IBM poo と同じく、SPARC-V9 のメモリモデルも、
ソフトから観測される振る舞いのみに着眼してかかれています。
そうではないと考えた根拠、
また、SPARC-V9 TSO の記述が不完全だと考えた
（こう考えているから、どこからともなく規則をもちだしたの
だと理解しています）根拠は何なんでしょうか。
# 語尾が「思います」ばっかりで恥ずかしい……
＞IBM System/370 には呪われし storage key という仕組みが
R bit はそもそも設定条件がゆるい上に、R=C=1 のときには
store forwarding の有無による問題はないと思いますよ。
(呪わしき話はそれこそTSO全般に顔を出すけれど)
その文面は storage key とは関係なく単に後方互換性のために外せないということでは。
おはようございます。
全然論点が絞れていなかったのは、私のせいでした。以後気をつけます。
> P.S.
> 申し訳ないが一点だけ先に。
これだけ先にすませてしまいましょう。
> うんのさんは S/370 系 CPU に Store forwarding を導入すると
> したら PoO の "Relation between Operand Accesses" の項の
> "However, a storage-operand store appears to precede a
> conceptually subsequent storage-operand fetch from the same
> main-storage location." の記述(とそれと同様の部分)を削る
> だけで済むとお考えです。
「削るだけで済む」とは主張していないし、ほのめかしてもいません。
単に、この文言が store forwarding の禁止に相当すると言いました。
また、storage-key の問題があるので、この文言が取り除けない
のだという点には既に（ゆるやかに）同意しています。
>「IBM System/370 には呪われし storage key という仕組みがあるため…」
>以下の説明は、store forwarding を採用できなかった理由の説明としてはあり得ると思います。
#「あり得ると思い」とぼやかしたのは、この点きちんと考えていな
#いので、本当に store forwarding と storage-key がどうやっても
#原理的に共存不可なのかについて、態度を保留しているためでした。
#いまここで、この問題に深入りしたくはないなぁ。
私が指摘したのは、"However, a storage-operand store appears ..."
の一文が store forwarding の禁止に相当するということ。
つまり、store forwarding は、
a conceptually subsequent storage-operand fetch from the same main-storage location が storage-operand store を追い越させる効果があると読める、ということのみです。
……よね？（見えざるオーディエンスに尋ねてみる）
うんのさんのコメント[14]を読む前にコメント[15]を出すという、大変失礼なことをしてしまいました。
[14]であげられたページは後日で読ませていただきますが、お返事は少々おまちください m(_ _)m
Store forwarding を受けた load (local load) の global visibility に関する理解の違いですね…
以下の点についてうんのさんの考えが分かれば、私の疑問も氷解するかもしれません。コメント[13]にお答えする前に、できれば先にお教えください。
私は SPARC の仕様は以下のものを参照しています。
http://www.sparc.com/standards/V8.pdf
http://www.sparc.com/standards/SPARCV9.pdf
私は上記の SPARC V9 のマニュアルの中から global visibility に関するはっきりした定義は見つけられずにいます。またメモリモデルの文脈で visible という言葉が使われる箇所を順に読むと、store 操作か barrier 操作しか visible と言っていないように読めます。
＃ その中で Single-Port Memory への値が反映が完了した or Single-Port Memory から値を反映した状態が、
＃ global visible だと私は漠然と理解しました。
私の知っている範囲で visibility order を一番はっきりした定義しているのは、"A Formal Specification of Intel Itanium Processor Family Memory Ordering" です。
http://developer.intel.com/design/itanium/downloads/251429.htm
しかし IA-64 メモリモデルは CPU 毎に独立したメモリを持っていて、load は常にローカルなメモリから読み、store が global visible になった時点で他の CPU のメモリに転送されるというモデル(つまり他の CPU の load は見えないモデル)になります。
うんのさんの知る "global visible" のスタンダードな定義は、どのドキュメントのどの定義に基づくものなのでしょうか？以降、私もそれを読んでから議論させていただきます。
P.S.
申し訳ないが一点だけ先に。
> 「IBM System/370 には呪われし storage key という仕組みがあるため…」以下の説
> 明は、store forwarding を採用できなかった理由の説明としてはあり得ると思いま
> す。
>
> が、Store forwarding をした場合、後続の load が先行の store を追い抜くことに
> なるという私と同じ言葉使いを IBM もしてますよという私の指摘に対する反論には
> なっていないはずですが。
私の言い方が悪くて申し訳ない。
IBM PoO はソフト開発者の立場から記述されおり、store buffer や cache のようなプロセッサの内部構造は隠蔽されている点はうんのさんも御存知のはずです。そして「(異なるメモリアドレスに対する)load が store を追い抜く」という記述は、PoO では "as observed by other CPUs" つまり外部の CPU から観測可能な事象として記述されています。
うんのさんは S/370 系 CPU に Store forwarding を導入するとしたら PoO の "Relation between Operand Accesses" の項の "However, a storage-operand store appears to precede a conceptually subsequent storage-operand fetch from the same main-storage location." の記述(とそれと同様の部分)を削るだけで済むとお考えです。しかしそれでは storage-key など PoO の他の部分と整合性が取れなくなると私は思います。もし整合性が取れないのだとすると、それは PoO の "as observed by other CPUs" によって規定されるメモリ規則と、うんのさんが考える SPARC の「global visibility order」には差があるのではないでしょうか？
これは私の考えですが、S/370 系 CPU に store forwarding を導入した場合、PoO には store forwarding という言葉や説明が出てこないと思います。そして PoO の "Relation between Operand Accesses" などの記述が「store-reference 後から serialization までの間に同じメモリに対する fetch-reference があった場合、その fetch-reference が他のプロセッサから観測できるかどうかは unpredictable である」という風に書き改められると考えます。
＃ つまり 1:store[X] → 2:load [X] → 3:load [Y] は、2: よりも先に 3: が "observed by other CPUs" されると風になる。
いままでの一連のやりとりを読み返してみて、私の「議論」の仕方は常にずいぶんまずかったと思います。申し訳ありません。
述べるべきだったと思われる内容と、間違いの訂正をまとめて、
自分のところにまとめました： http://uhideyuki.sakura.ne.jp/uDiary/?date=20060920
特に、文献を確認しなおさずに、いいかげんな間違いを書いてしまった点については、きわめて不誠実だったと反省しています。すみません。
ボキャブラリが食い違っていることに気づいていながら、ベースとなるべき文献にあたらないというのは、我ながらダメでした。
こんにちわ。連休中は子守りモードにて、すっかりオフラインでした。
> おそらく global visibility order の定義が、私とうんのさんで異なるのだと思
> います。
そうですね、nminoru さんが、ハードの動作を正しく理解されているのは当初から
明らかなので、言葉遣いの問題になっています。
ただし、私は SPARC V9 に書かれているとおりの言葉で話しているはずですし、
私の確認したところ、それは IBM P.O.O. とも異なっていません。
（具体的な用語は別のものが定義されていたりしますが、用いられている概念は
同じ。）おそらくですが、TSO に関して話す文脈においては、そんなに変な言葉使い
にはなっていないはずです。
日常的な言語感覚とかけはなれているかもしれないのは、なにかをフォーマルに定義
しようとする場合に珍しいことではないでしょう。
> パターンとしては (a),(b),(c) でしょうか。
>
> (a) あるプロセッサの立場に立って、そのプロセッサが行った global なメモリ操
> 作(store buffer からデータを bypass された local load を除く)の順序関係。
> (b) あるプロセッサの立場に立って、そのプロセッサが行ったロード命令がデータ
> の供給を受ける事象と、store 命令がデータをメモリに書き込む事象の順序関係。
> (c) あるプロセッサが行った全てのメモリ操作が「仮想的に」メモリに反映された
> と考えた場合、それをその外側のプロセッサが観察していたと考えた場合の順序関
> 係。
>
> うんのさんは (b) の立場で、私は (c) の立場なのだと思います。
いいえ。(a),(b) は明らかにあやまってますね。
Global visibility order というからには、あるプロセッサのメモリ操作を「外部か
ら」観測したものです。
ただ、外部から観測されるというのがどういうことなのかという点で大幅に齟齬が
ある模様です。
観測されるのは順序であって、各 load/store がそれぞれ global visible になった
瞬間に「あ、いまだ」と観測されるわけではありません。
結果的にプログラムがどう動いたか（だれの、いつの時点の store 値を load が受
け取ったか）を通じて、順序が観測されるのです。
> (a) なら簡単です。
> SPARC の memory ordering の定義を調べてみると (a) が近そうです。
> SPARC V8 Spec. は (Figure 6-1 Model of Memory の図を見ると明らかのように)
> Single-Port Memory へのメモリアクセスの順序、つまりメモリトランザクション
> の順序が memory ordering だと定義しています。そのため store forwarding を
> 受けた load 命令(以下、local load と呼ぶことにします)は memory ordering に
> よる順序付けの適用外になります。以下のように記述されています。
> --------
> A load by a processor first checks its Store Buffer to see if it contains
> a store to the same location (atomic load-stores do not need to be checked
> for because they block the processor). If it does, then the load returns
> the value of the most recent such store; otherwise the load goes directly
> to memory. SINCE NOT ALL LOADS GO TO MEMORY, LOADS IN GENERAL DO NOT
> APPEAR IN THE MEMORY ORDER. A processor is blocked from issuing further
> memory operations until the load returns a value.
> --------
V8 が手元になかったので（手抜きですみません）、V9 と言葉使いが変わらないもの
として。
SPARC の用語定義においては、Memory order と
memory model (こちらは globalvisibility に関する)
global visiblility order とは別の概念です。
Memory order の方は、ほぼ dependency order / self-consistency と同じ意味で
定義されています (V9 manual で D.2)
したがって、上記引用のキャピタル強調部分の意味合いは、
「すべての load がメモリに出るわけではないので（つまり、store forwarding
が許容されるので）、一般に、load が global visible になる順序は命令順
とは一致しない」
という程度のものになります。
nminoru さんのいうところの、「memory ordering による順序付けの適用外になりま
す」がどのような意図のものか不明ですが、「TSO の守備範囲である」という解釈は
不可能です。
> SPARC V9 Spec も memory ordering は memory transaction がメモリに届く順序
> だと規定しています。
そんなことないでしょう。SPARC V9 では、D章にトランザクションは明にでてこない
はず。（8章が description, D 章が形式的定義となっています）
> 私は(ソフト屋ですから) local load 命令が global visible になったと考えるな
> ら、仮想的に local load 命令がメモリから読み込んだと考えます。その場合、コ
> メント[9] のプログラムだと 5: → 1: → 2: → 3: → 4: の順にならざる得ない
> と思うのですよ。4: → 5: → 1: → 2: → 3: ではデータの消費(4:r2=[X] の読
> み込み)がデータの生成(3:[X}=1)に先立つと言う、因果律に反した事態になります。
ソフト屋さんの「生得的な」ボキャブラリと、Memory model 定義に用いられるボキャ
ブラリが異なるであろうことは、私も、おそらく仕様書の執筆者も理解しています。
だから、SPARC V9 マニュアルでは、最初に用語の定義を行っているはずです。
「因果律に反した事態になります。」というあたり、私が最初に指摘したつもり
だったのですが、self-consistency (あるプロセッサの立場にたって、自身のメモリ
操作を見たときに、命令順との矛盾がないこと）と global visibility を区別
していないようにしか見えません。
Processor 1 は、nminoru さんの提示実行例では、
1: → 4: → 5: → 2: → 3: の順で global visible になっています（記憶頼り）。
4: の実行時点において、3: のストアはまだ global visible でなかったというだけ
であって、そのことはストアが未実行であることを示唆しないので、当然ながら、因
果律に反してはいません。まあ、因果律を持ち出す必要はなくて、memory model に
反していません。
Store には、未実行の状態（だれにも store 値は観測され得ない）、実行されたが
global visible でない状態（ローカルからは見える）、global visibe になった
状態の３つがある、と。
> うんのさんは、
> > 4: は、2:,3: がいずれも global visible になっていなくても、
> > それらを追い越して global visible になれて、
> > 実際にそうなっているケースです。
> とおっしゃっておられるので、別の定義を採用されているのだと思いますが…
というわけで、一貫して、スタンダードな定義を採用しているつもりです。
> > ちょっと話題は変わりますが、IBM のアーキが store forwarding を認めていな
> > いというのは、おっしゃるとおりでした。
> (snip)
> > しかし、この文章を store forwarding の禁止であると認めるのであれば（認め
> > るのが正解だと思いますが）、
> > store forwarding した場合には、4: が 3: を追い越すのだと解釈することにな
> > ると思います。
>
> IBM System/370 には呪われし storage key という仕組みがあるためにちょっと特
> 殊なことになると思われます。load 命令が store 命令を追い越すと、そのこと
> を他のプロセッサから検出可能なので…
「IBM System/370 には呪われし storage key という仕組みがあるため…」以下の説
明は、store forwarding を採用できなかった理由の説明としてはあり得ると思いま
す。
が、Store forwarding をした場合、後続の load が先行の store を追い抜くことに
なるという私と同じ言葉使いを IBM もしてますよという私の指摘に対する反論には
なっていないはずですが。
----
ひとまず、受身的に反応してみました。
しかし、nminoru さんは繰り返し同じ疑問を提示されていて、私も同じようなことを
言い続けているので、すっかり平行線ですね。
なにかきちんと述べられないか、少し考えてみます……。
おそらく global visibility order の定義が、私とうんのさんで異なるのだと思います。
パターンとしては (a),(b),(c) でしょうか。
(a) あるプロセッサの立場に立って、そのプロセッサが行った global なメモリ操作(store buffer からデータを bypass された local load を除く)の順序関係。
(b) あるプロセッサの立場に立って、そのプロセッサが行ったロード命令がデータの供給を受ける事象と、store 命令がデータをメモリに書き込む事象の順序関係。
(c) あるプロセッサが行った全てのメモリ操作が「仮想的に」メモリに反映されたと考えた場合、それをその外側のプロセッサが観察していたと考えた場合の順序関係。
うんのさんは (b) の立場で、私は (c) の立場なのだと思います。
(a) なら簡単です。
SPARC の memory ordering の定義を調べてみると (a) が近そうです。
SPARC V8 Spec. は (Figure 6-1 Model of Memory の図を見ると明らかのように) Single-Port Memory へのメモリアクセスの順序、つまりメモリトランザクションの順序が memory ordering だと定義しています。そのため store forwarding を受けた load 命令(以下、local load と呼ぶことにします)は memory ordering による順序付けの適用外になります。以下のように記述されています。
--------
A load by a processor first checks its Store Buffer to see if it contains a store to the same location (atomic load-stores do not need to be checked for because they block the processor). If it does, then the load returns the value of the most recent such store; otherwise the load goes directly to memory. SINCE NOT ALL LOADS GO TO MEMORY, LOADS IN GENERAL DO NOT APPEAR IN THE MEMORY ORDER. A processor is blocked from issuing further memory operations until the load returns a value.
--------
SPARC V9 Spec も memory ordering は memory transaction がメモリに届く順序だと規定しています。8.4 節を見る限り V8 と同様に data pat 上を流れるものです。一方、Appendix D. の memory transaction は 8.4 節と微妙に食い違っていて、store fowarding を受ける load に対しても memory transaction が定義されているようにも見えます。
結局、SPARC Spec. の中では local load 命令は memory ordering の中ではっきり順序付けされていないように読めるし、global visibility のはっきりした定義も与えられていません。
私は(ソフト屋ですから) local load 命令が global visible になったと考えるなら、仮想的に local load 命令がメモリから読み込んだと考えます。その場合、コメント[9] のプログラムだと 5: → 1: → 2: → 3: → 4: の順にならざる得ないと思うのですよ。4: → 5: → 1: → 2: → 3: ではデータの消費(4:r2=[X] の読み込み)がデータの生成(3:[X}=1)に先立つと言う、因果律に反した事態になります。
うんのさんは、
> 4: は、2:,3: がいずれも global visible になっていなくても、
> それらを追い越して global visible になれて、
> 実際にそうなっているケースです。
とおっしゃっておられるので、別の定義を採用されているのだと思いますが…
> ちょっと話題は変わりますが、IBM のアーキが store forwarding を認めていないというのは、おっしゃるとおりでした。
(snip)
> しかし、この文章を store forwarding の禁止であると認めるのであれば（認めるのが正解だと思いますが）、
> store forwarding した場合には、4: が 3: を追い越すのだと解釈することになると思います。
IBM System/370 には呪われし storage key という仕組みがあるためにちょっと特殊なことになると思われます。load 命令が store 命令を追い越すと、そのことを他のプロセッサから検出可能なので…
1つのコメントの表示できる文字数が不足して見えない箇所があったので、表示可能な文字数を 1000 → 2000 に増やしてみました。
あと議論し易いようにコメント番号をつけました。
> 1: の STORE の結果は global visiable になっており、2: 4: はまだだと推測されます。
2:,3: はまだでしょうが、4: がまだと推測する根拠がありませんよ。
4: は、2:,3: がいずれも global visible になっていなくても、
それらを追い越して global visible になれて、
実際にそうなっているケースです。
4: のロード値が１であることが引っかかっておられるようですが、3: のストアが外部から観測されるよりも前に 4: のロード値１が確定することこそが、4: が 3:を追い越した結果なんです。
プログラムを少し改変したほうがいいと提案したのは、
load の結果がもっと直接観測できる例の方がいいと思った
からでした。
この例のままだと、4: が 2:,3: を追い越すという言い方に対する自然言語レベルでの違和感を自然言語レベルで言い合うだけになりかねないと思ったもので。
ちょっと話題は変わりますが、IBM のアーキが store forwarding を認めていないというのは、おっしゃるとおりでした。
http://publib.boulder.ibm.com/cgi-bin/bookmgr/BOOKS/DZ9AR006/5.13.10?DT=19990630131355
However, a storage-operand store
appears to precede a conceptually subsequent storage-operand fetch from
the same main-storage location.
しかし、この文章を store forwarding の禁止であると認めるのであれば（認めるのが正解だと思いますが）、store forwarding した場合には、4: が 3: を追い越すのだと解釈することになると思います。
まずプログラム例を示した方がよいようですね。
> これについては、命令列を少し変形して、
> 1: STORE [X] = 1
> 2: LOAD r1 = [X]
> 3: if r1 == 1 { LOAD r2 = [Y] }
> のようにしてみては、どうでしょう。
> Global visibility order が 3. load [Y] → 1. store [X] → 2. load [X] にはなり得ないことがはっきりするんじゃないかと思います。
制御依存を入れてしまうと、元のプログラムとは別のものになると思います。
少し複雑ですが、下の例を見てください。
[Sync1]、[Sync2]、[X]、[Y] という異なる 4 つのメモリ位置があり、初期状態で全て 0 とします。
Processor1:
1: STORE [Sync1] = 1
2: STORE [Sync2] = 1
3: STORE [X] = 1
4: LOAD r1 = [X]
5: LOAD r2 = [Y]
Processor2:
6: STORE [Y] = 1
7: MEMBAR
8: LOAD r3 = [Sync1]
9: LOAD r4 = [Sync2]
ここで r3 = 1 で r4 = 0 となるにも関わらず、r1 = 1 が r2 = 0 となるパターンが考えられます。
プロセッサ1 で 1:〜3: の store が全て store buffer で待機させられ、4:〜5: の load が追い抜いた場合です。4: は store fowarding を 5: はメモりからデータの供給を受けるとします。
プロセッサ2 からこの状態を観察して、プロセッサ1の中で何が起こっているのかを考えます。
自分が r3 = 1,r4 = 0 というデータを受け取ったとすると、1: の STORE の結果は global visiable になっており、2: 4: はまだだと推測されます。
r2 が 0 ですので、5: load は 6: の store よりも先に visible になったことが確認できます。この結果から 5: が(少なくとも) 2: 3: を追い越したことが分かります。
一方、3: で書き込まれるべき [X]=1 の値は、まだ global visible になっていません (プロセッサ2が 9: で [Sync2] = 0 を確認しているから)。そのため、プロセッサ2から見れば 5: が「実行」されたのは 2: よりも後の事象に見えます。
まとめると r1 = 1, r2 = 0, r3 = 1, r4 = 0 という結果をプロセッサ2 からみると、4: LOAD は 2: よりも後で、5: LOAD は 2: よりも先に実行されたように見えます。4: と 5: の load 間の逆転が起こっているように見えませんか？
都合により、poo とか調べて書くのは、来週になっちゃいそうで。
忘れないうちに、いくつか書いておきたいと思います。
> これが global visibility order かと呼ばれると激しく違和感があります。
これについては、命令列を少し変形して、
1: STORE [X] = 1
2: LOAD r1 = [X]
3: if r1 == 1 { LOAD r2 = [Y] }
のようにしてみては、どうでしょう。
Global visibility order が 3. load [Y] → 1. store [X] → 2. load [X] にはなり得ないことがはっきりするんじゃないかと思います。
＃いちおう、五月雨式に書くのは、すこし控えます。
＃まとめてからにしたい。
いつも２個連続投稿ですみません。
投稿するとすぐに追加で思いつくので。
> 話を戻すと、2. の load が外から直接は観測されないというのは、ご指摘の通りだと思います。
観測されないのは、2. の load の値を使っていない（使うところを議論していない）からですね。
このあたりのことを、これ以上踏み込んで議論するには、
具体的な命令列を考える必要があるように思います。
というわけで、続きは明日投稿させていただきます。
＃ご迷惑かもしれませんが、私としても完結させたく。。。
せっかくお付き合いいただいているので、私ももう少し時間をかけて書かなければならないと思っていますが、まずはすぐにコメント可能な点から。
> これが global visibility order かと呼ばれると激しく違和感があります。
> SPARC V9 Spec. 的には正しいのでしょうが。
うーん、いいたいことがいくつか。
2. load [X] → 3. load [Y] → 1. store [X]は、global visibility order 以外の何者にもなりえないと思います。
プロセッサの内部から見た実行順序、というのが、このプロセッサ上のソフトウエアから見たという意味なのだとすると、
これが 2 → 3 → 1 だったら困ります。
きっと、nminoru さんが実行順序といったときには、program-visible な順序ではなく、ハードインプリに依存した処理順序を想定されているだろうと思いますが……。
また、global visible になる時点というのは、バストランザクションが発行される時点という意味ではありません。
バストランザクションそのものは、ソフトウエアには観測されないので。
これは、SPARC V9 であろうと、なかろうと普遍だと思うのですが。
話を戻すと、2. の load が外から直接は観測されないというのは、ご指摘の通りだと思います。間接的に決まる位置を補った結果、2. load [X] → 3. load [Y] → 1. store [X] に見えることになります（global visible 順序として）。
> ＃ IBM はメモリモデルのことを ``Relation between Operand Accesses''と読んでいます。この定義は Global Visibility だけのものです)。
IBM のメモリモデルと SPARC V9 の TSO は同じはずだなんですけど。
会社にいったら、poo を確認してみます。
SPARC V9 の TSO だって、global visibility だけのものですよね。
> SPARC の MEMBAR 命令は V9 になって詳細な設定ができるようになったのはいいのですが、現場のコーダーからすると混乱して溜まらんです。
TSO だけじゃなくて、PSO,RMO においてもきめ細かく制御できるようになっていますからね。
ただ、私がおもうに、SPARC V9 のメモリモデルは、とても明晰に記述されていると思います。
お返事が遅くなってすいません。
まず言い訳をしておくと、もともとこの考察は IBM/370 「TSO」 と IA-64 の TSO (ld.acq と st.rel だけを使うモデル)の違いを考えることから出発していて、SPARC は念頭にありませんでした。IBM System/370 は store ← load の追い越しを許すが、store forwarding がないメモリモデルです。
＃ IBM はメモリモデルのことを ``Relation between Operand Accesses''と読んでいます。この定義は Global Visibility だけのものです)。
ネット上には IBM/370 メモリモデルも TSO に含める文献があって TSO と store forwarding は独立していると考えていたのですが、Total Store Ordering を考案した P.Sindhu の 1990 年の論文(``Formal Specification of Memory Models'')を読んでみると store forwarding を許さないものはそもそも TSO ではないとありました。
どうもこの私の勘違いが、うんのさんと噛み合わない問題点です。
SPARC プロセッサで、そのプロセッサの内部から見た実行順序が 2. load [X] → 3. load [Y] → 1. store [X] となるのは理解しているのですが、これが global visibility order かと呼ばれると激しく違和感があります。SPARC V9 Spec. 的には正しいのでしょうが。
実際のところ 2. の load はプロセッサの中で折り返してしまうので、メモリバスからは 3. load [Y] → 1. store [X] の 2 つしか見えないでしょう。プロセッサの外側から見える(見えない部分は補足する)メモリ・オーダーとしては 3. load [Y] → 1. store [X] → 2. load [X] の順になると思うのですどうでしょう。
＃ IA-64 は、load に global load と local load があるという形で visibility に折り合いをつけています。
P.S.
SPARC の MEMBAR 命令は V9 になって詳細な設定ができるようになったのはいいのですが、現場のコーダーからすると混乱して溜まらんです。他のアーキテクチャのメモリバリアは MEMBAR の #Lookaside の効果が付与されたものが多いようです。
なんか、書き足りないような気がしたので、ちょこまかすみませんが、補足。
自分で、「『実行順序』という呼び方は微妙、というか、危険な感じがしますが。」と書きましたが、ここのポイントはすごく重要だと思います、やはり。
TSO のようなメモリモデルは、
・そのプロセッサ内部において実行される順序と、
・それが外部から観測される順序
を明確に区別したうえで、後者に関する制約を定義したものです。
だから、実行順序と global visible 順序を明確に区別して考えることが、どうしても重要となります。
んで、TSO は、ひとことでいうなら、store forwarding を積極的に推奨しているモデルだといえます。(Store が global visible になる前、つまり store buffer に滞留している間に、後続をどんどん処理してもいいよ、というモデルなので）
こんにちは。覚えていていただけたようで、嬉しいです。
>命令順序 1. store [X] 2. load [X] 3. load [Y]
>実行順序 2. load [X] 3. load [Y] 1. store [X]
>
>となっているだけで、2. と 3. の順序は変わっていないということでしょうか？
そうです。ただ、「実行順序」という呼び方は微妙、というか、危険な感じがしますが。
Out-of-order マシンは、「実行」順序は次の制約を守っているかぎりどんな風に変えてもよい：
・実行しているプロセッサ自身からみると、実行順序は、命令順序と同じに見えなくてはならず（self-consistency)、
・グローバル（または他プロセッサ）からみると、TSO を守っている必要がある
という考え方の上に成り立っています。
で、グローバルから見たとき load [X] 3. load [Y] 1. store [X] となるのは、TSO 違反でもなんでもありませんよ、というわけです。
実は、最近、身近でもこの件に関して誤解されてしまっているのを目撃したばかりで、個人的にホットな話題だったため、つい反応してしまいました。
なお、「このタイプのロード→ロードの追い抜きは発生する。」という誤解は、実用的にも問題があるかもしれません。
なぜなら、3. load [Y] の直前に「フェンス命令」をおくのであれば、
Membar #StoreLoad （SPARC V9 の場合）であるべきなのですが、
ロード→ロード追い越しと考えてしまうとこれがわからなくなりますから。
んで、なんでもかんでも「最強」のフェンス命令を置くはめになってしまうと＞"余計に入れたり"
うんのさんお久しぶりです。
うんのさんのお話のポイントは、
命令順序 1. store [X] 2. load [X] 3. load [Y]
実行順序 2. load [X] 3. load [Y] 1. store [X]
となっているだけで、2. と 3. の順序は変わっていないということでしょうか？
＃ 2. の値は store forwarding によって1. の store 命令によって供給されていると、
いつぞや唐突に乱入した、うんのです。（「リアルでは会ったことがある」とか、なんとか）
実用的には、大筋まちがっていないともいえますが、TSO の説明には誤りが見られるので、またでしゃばって来ました（すんません…）。急いで書いて、書きかたが失礼な個所があるかもしれません。あらかじめお詫びします（←ちょっとずるい）
>その TSO でも store forwarding を認めていると
> このタイプのロード→ロードの追い抜きは発生する。
これは、かなり典型的な混乱具合なのですが、Multi processor システムにおける global visible 順序と、self-consistency （綴りあってるかな）をごちゃまぜにされています。
Global visible の観点からみると、依存関係のある store と後続の load があった場合に、後続の load は先行の store を追い越すことができます。（文面通り、TSO はこれを禁止していません）
この追い越しを self-consistency を維持したまま実現するのが、store forwarding なのですが。
繰り返すと、1. store , 2. load, 3. load があったときに、
2 の load が 1 の store を追い越しているのです。
だから、「TSO でも store forwarding を認めているとこのタイプのロード→ロードの追い抜きは発生する。」というのは、誤りですね。
> 難儀な話だ。こういう状況の解決策は、メモリフェンス命令を
> 余計に入れたりアトミックなメモリアクセスが必要だったり
> する。アーキテクチャ毎にやり方が異なるので要注意。
だから、「余計に」入れなくても、必要十分なだけ入れとけばいいのです。余計に感じるのは、TSO について少し混乱しているせいでしょう。
難儀な問題があるのは、確かですね。SPARC V8 なんて、TSO のくせに、適切な「フェンス」命令がなくて、アトミック命令で代用せざるを得なかったという噂ですし。