NAKAMURA Minoru の日記 (2006年8月)

先月の日記(2006年07月) 今月の日記(2006年08月)
2002 | 10 | 11 | 12
2003 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2004 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2005 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2006 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2007 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2008 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2009 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2010 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2011 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2012 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2013 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2014 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2015 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2016 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2017 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11
ホームページ | 最新のコメント50
インデックス: 食べ歩き | Java | プログラム | UNIX | 画像
最新の日記へのリンク | この日記ページをはてなアンテナに追加 この日記ページをはてなブックマークに追加
はてな ダイアリー アンテナ ブックマーク ブログ
Twitter | mixi | Facebook | Google+
slideshare | github | Qiita



8/31 (木)

[CPU][Prog] IA-64/Linux の sigcontext は gr32 番以降のレジスタが不足している

UNIX 系 OS はシグナルハンドラ中や getcontext で実行コンテキストの保存ができる。 これを使って割り込みが起こった時に、 割り込み元のコンテキストのレジスタを書き換えると言ったプログラムテクニックが可能だ。

しかし IA-64/Linux はちょっと妙だ。 128本ある汎用レジスタのうち回転しない最初の 32 本は sc_gr[] に記録されるのだが、 レジスタスタック分の gr32 〜 gr127 番までのレジスタが sigcontext 中に保存されていない。 このような場合、 レジスタスタックのバッキングストアに格納されていると考えられるのだが、 sc_ar_bsp は gr32 の位置を指していない。

struct sigcontext
{
  unsigned long int sc_flags;   /* see manifest constants below */
  unsigned long int sc_nat;     /* bit i == 1 iff scratch reg gr[i] is a NaT */
  stack_t sc_stack;             /* previously active stack */

  unsigned long int sc_ip;      /* instruction pointer */
  unsigned long int sc_cfm;     /* current frame marker */
  unsigned long int sc_um;      /* user mask bits */
  unsigned long int sc_ar_rsc;  /* register stack configuration register */
  unsigned long int sc_ar_bsp;  /* backing store pointer */
  unsigned long int sc_ar_rnat; /* RSE NaT collection register */
  unsigned long int sc_ar_ccv;  /* compare & exchange compare value register */
  unsigned long int sc_ar_unat; /* ar.unat of interrupted context */
  unsigned long int sc_ar_fpsr; /* floating-point status register */
  unsigned long int sc_ar_pfs;  /* previous function state */
  unsigned long int sc_ar_lc;   /* loop count register */
  unsigned long int sc_pr;      /* predicate registers */
  unsigned long int sc_br[8];   /* branch registers */
  unsigned long int sc_gr[32];  /* general registers (static partition) */
  struct ia64_fpreg sc_fr[128]; /* floating-point registers */
  unsigned long int sc_rbs_base;/* NULL or new base of sighandler's rbs */
  unsigned long int sc_loadrs;  /* see description above */
  unsigned long int sc_ar25;    /* cmp8xchg16 uses this */
  unsigned long int sc_ar26;    /* rsvd for scratch use */
  unsigned long int sc_rsvd[12];/* reserved for future use */

  /* sc_mask is actually an sigset_t but we don't want to
   * include the kernel headers here. */
  unsigned long int sc_mask;    /* signal mask to restore after handler returns */
};

いろいろ調べた結果、 sc_ar_bsp - (入力レジスタ数) × 8 バイトの位置から gr32 が格納されている。 入力レジスタ数は関数の引き数の数で決まるのだが、 呼び出し元関数の構造に関する情報は sigcontext には保存されていない。 どこから情報を持ってくれば足りるのだろうか?

追記:9/1

基本的には sc_ar_bsp から sc_cfm.sof を引いた ポイントが gr32 レジスタの位置になるのでいいようだ。 ただしレジスタスタックを 63 本退避するごとに NaT コレクションレジスタを挟み込むので、 計算がややこしくなる。

libunwind ライブラリを参照すると、 以下のような補正関数を準備する必要があるとある。

unsigned long ia64_rse_slot_num (unsigned long *addr) {
    return (((unsigned long) addr) >> 3) &0x3f;
}

unsigned long* ia64_rse_skip_regs (unsigned long *addr, long num_regs) {
    long delta = ia64_rse_slot_num(addr) + num_regs;
    if (num_regs > 0)
        delta -= 0x3e;
    return addr + num_regs + delta/0x3f;
}

シグナルハンドラの中で、 シグナル発生元関数の gr32 〜 gr34 以降のレジスタを参照したい場合は 以下のように書ける。

unsigned long* bsp;
long sof, gr32, gr33, gr34;

sof = uc->uc_mcontext.sc_cfm & 0x7fUL; 
bsp = ia64_rse_skip_regs (uc->uc_mcontext.sc_ar_bsp, -sof);

flushrs(); 

gr32 = *bsp;
gr33 = *ia64_rse_skip_regs(bsp, 1);
gr34 = *ia64_rse_skip_regs(bsp, 2);

当然ながらシグナルの発生元で gr32 〜 gr34 のレジスタが使えるように alloc 命令を設定する必要がある。 発生元で使用していないレジスタを RSE BS から参照しようとするのは危険だ。


8/28 (月)

[Food] 一六タルト (六時屋)

愛媛と友人から六時屋の「一六タルト」をいただく。

タルトと言っても tarte ではなく taart。 餡をカステラで巻いたオランダ菓子です。 餡子が素晴らしく甘いです。


8/26 (土)

[Bench] SPEC CPU2006 が登場 (CPU2006)

SPEC CPU2004 が延期されて以来幾星霜、 ついに CPU2006 が登場した。 ベンチマーク数は CINT2000が 12 個 (C 言語で書かれたものが×11個と C++ ×1個)、 CFP2000が 14 個 (Fortran77 ×6個と Fortran90 ×4個と C言語×4個) だったのが、 CINT2006が 12個 (C 言語×9個と C++ ×3個)になっている。C++ が増加した。 CFP2006は全部で 17 個のベンチマークで、 Fortran Only が 7 個、C言語 Only が 3 個、 コア部分だけ Fortran で書いて周辺部分は C 言語で書いたものが 3個、 C++ 言語で書かれたものが 4 個になっている。 Fortran95 のコードも登場。

今回の基準マシンは Sun Ultra Enterprise 2 (296MHz UltraSPARC II) になっている。 前回(CPU2000)の基準が Sun Ultra5_10 (300MHz) だったので、 ほとんどベースに差がない。 すでにスコアを登録したマシンを見ると Ultra Enterprise 2 に1桁以上の差をつけているものばかり。

まだ詳しく見ていないが、 CPU2000 と比べてデータセットがぐ〜んと拡大されていると聞いている。 最近のプロセッサはキャッシュが大きくなりすぎて、 ベンチマークのワーキングセットがそのキャッシュ内に収まってしまうこともある。 そのため「実機」の性能測定を公平化するにはデータを大きくしないとダメなんだろう。

一方、 プロセッサ開発を行うアーキテクチャ屋は、 シミュレーションを行う対象として SPEC CPU を長らく使ってきた。 彼等にしてみれば CPU2000 ですら規模が大きすぎて扱い辛くて、 これが膨れ上がるとますます使い辛いものになっていくようだ。 もっともアーキテクチャが収斂した 21 世紀という時代には、 死に絶えつつあるマイクロアーキテクチャ屋の都合なんて どうでもいいのかもしんない。

今のところスコア登録されたのは IA-32/AMD64 系の石と Ultra SPARC だけ。 今後は Itanium2 と POWER 系ぐらいしか参入してこないだろうから、 マイクロアーキテクチャ間で優劣を競うといった醍醐味はもうないだろう。

[Bench] さようなら SPEC CPU2000 (CPU2000)

ついでに最後になるだろう CPU2000 ウォッチ。 前回は 4/13

前回に Opteron 系が SPECint2000 で 2,000 越えをしたと思ったら、 Intel Core2 系はあっさり 3,000 越え。 ついでに SPECfp2000 も POWER5+ には及ばないもの 3,000 台をキープ。

IBM POWER5+ はクロックを 2300MHz まで伸ばして fp2000 が 3,600 台を達成。

新顔の Montecito 系の Itanium2 は微妙にスコアを伸ばすも、 ほとんど成長なし。

今回の分で Intel x86、AMD x86、Itanium、POWER5 がマルチコアになった。 黄色のセルは並列コンパイラを使ったマルチコア最適化の結果で、 4 コア構成で POWER5+(2100MHz) / AIX で 20%、 Opteron (3000MHz) / Solaris で 40% ほど上がっている。

ファミリープロセッサCINT2000CFP2000コメント
x86Intel Core2 Extreme X6800 (2933MHz)3119
(3108)
Win-32
Intel Core2 Extreme X6800 (2933MHz)31093049Win-32
Intel Xeon 516030263056Win-32
x86AMD Opteron 256 (3000MHz)2119 (1942)Win-32
AMD Opteron 256 (3000MHz)2064 (1838)2388 (2182)Linux-64bit
AMD Opteron 256 (3000MHz)1957 (1783)2497 (2260)
Solaris10
AMD Opteron 256 (2933MHz)2057 (1836)2497 (2260)
AMD Opteron 256 (2800MHz)1838 (1713)2505 (2212)
AMD Opteron 856 (3000MHz)3538
(2851)
Solaris10 + Sun Studio 11 + Parallel
POWERIBM POWER5+ (2300MHz)1900
(1820)
3642
(3369)
AIX 5L V5.3 + IBM XL Compilers
IBM POWER5+ (2100MHz)1747
(1670)
3324
(3100)
AIX 5L V5.3 + IBM XL Compilers
IBM POWER5+ (2100MHz)
4051
(3210)
AIX 5L V5.3 + IBM XL Compilers (Parallel)
ItaniumItanium2 9050 (1600MHz)1474
(1474)
3017
(3017)
Linux kernel 2.6.12 + ICC 9.1

しかし、 いろいろ思い返してみると SPEC CPU2000 の歴史は マイクロアーキテクチャの没落の歴史だよな。 失われた CPU に追憶を。


8/25 (金)

研修から帰還

火曜日から三泊四日の会社の研修へ行っていたが、 ようやく帰還。

とりあえず御飯のマトリックスを表示。

8/22 (火) 牛肉のソテー
牛肉のソテー
豚の生姜焼きとポテトサラダとお魚
豚の生姜焼きとポテトサラダと魚
8/23 (水)
かき揚げ丼
かき揚げ丼
鰤の照り焼きと温泉卵のナニカ
鰤の照り焼きと温泉卵のナニカ
8/24 (木)
秋刀魚と冷やしうどん
秋刀魚と冷やしうどん
鶏の唐揚げの餡かけ
鶏の唐揚げの餡かけ
8/25 (金) 朝食
右はジャガイモの冷製スープ
鳥カツ
鳥カツ

8/17 (木)

[Food] 鳥勢@名古屋 (公式)

本日は仕事で名古屋に出張。 ついでに井手さんを名大に表敬訪問してきました。

ウォンバット人形
研究室にはウォンバットの人形が常備されていました。

この後二人で栄の焼き鳥屋さん「鳥勢」へ。 この店は朝絞めた鶏だけを出すお店だそうです。

暖簾
お店の暖簾です
サンシャイン栄
サンシャイン栄の真ん前
キャベツ
前菜のキャベツ
コーチン鳥刺
コーチン鳥刺
冷奴
冷奴
皮
つくね
つくね
せせり
せせり
コーチン(手前) & 軟骨(奥)
コーチン(手前) & 軟骨(奥)
ささみ(手前) & ぼんちり(奥)
ささみ(手前) & ぼんちり(奥)
梅ささみ
梅ささみ
お茶漬け
お茶漬け

名古屋コーチンの焼き鳥はジューシーで柔らかくてうま〜。 玉子をといてタレを掛けて食べるつくねも美味です。

追記:8/20

井手さんからの情報でメニューが判明。

停電

終電間際の「のぞみ」に飛び乗って新横浜経由で帰還。
途中、雷がピカピカと空を照らしていたが、 ようやく帰宅してパソコンの電源を入れたと思ったら、 ピカ〜ゴロゴロと鳴って部屋の電源が一斉に切れる。


8/15 (火)

[MyWeb] nminoru.jp の JP ドメイン管理

nminoru.jp は Domain 21 というレジストラで登録していたのだが、 Domain 21 の運用元の愉快堂出版社が JPRS から JPドメイン名管理指定事業者を解除されたため、 レジストラを移動せねばならなくなった。

ほっといても別のレジストラ (ヒューメイアレジストリに委託)に移るのでいいのだが、 管理が切り替わるまで予備日がない。 ギリギリに発表しよって。

しかし「指定事業者契約を終了する」ではなくて、 「指定事業者を解除する」というのは いった何かやったのだろうか?

[Prog] IA-64/Linux でユーザマスクを弄ると…

IA-64 は Program Status Register (PSR) という 64-bit レジスタが CPU の動作モードを管理している。 このレジスタの特権モードでないとアクセスできないが、 PSR のうち 6 ビット(うち1ビットは予約)は ユーザマスク(UM) と呼ばれ、 非特権モードでも読み書きが可能になっている。

be - ビッグ・エンディアン
このビットが 1 の場合は、 load/store 命令がビッグ・エンディアンで行われる。 0 の場合はリトル・エンディアンになる。
Linux では UM.be = 0 で運用される。
ac - 不正アライメントアクセス制御
UM.ac = 0 の場合には不正アライメントのメモリアクセスを CPU 内でできるだけ解決する。 Itanium2 の場合、8バイトアライメント内に収まる 8 バイト以下のメモリアクセスは、 不正境界であってもを発生させずにメモリアクセスを行う。 UM.ac = 1 の場合にはあらゆる不正アライメントアクセスが Unaligment Data Access 例外になる。 Linux は UM.ac = 1 で運用される。
up - ユーザ・パフォーマンス・モニタ
パフォーマンスモニタ機構が、 非特権側に制御を許している場合には UMA.up ビットでオン・オフできる。
mfl/mfh 浮動小数点レジスタの更新チェック
浮動小数点レジスタに書き込みを行うと sticky に立つビット。

非特権命令でユーザマスクが変更できる以上、 IA-64/Linux でもユーザプロセスでモード変更になっている。 特に変更結果が目に見えて分かるのは UM.{ac,be} で sum/rum 命令でユーザマスクを変更すると、 不正境界アクセスが可能になったり ビッグ・エンディアンでメモリアクセスが可能になったりする。 ただしユーザマスクに関しては ABI で特に規定がないので、 OS 側でコンテキストが保存されるかどうか保証がない。

カーネル 2.6.11 でテストすると、 UM.ac = 0 の方はいったんリセットすると sched_yield(2) でも シグナルハンドラ内でもシグナルハンドラから帰ってきても UM.ac はリセットされるままになっている。 不正アライメントアクセスが頻発するようなプログラムを抱えている場合には朗報だ。

一方、 UM.be = 1 をセットするとエンディアンがリトルからビッグに切り替わるので、 関数呼び出しすらできなくなる。 アセンブラで null pointer exception をわざと出して、 SEGV シグナルハンドラに処理を移すとシグナルハンドラ内では UM.be = 0 に戻っている。

ハンドラからリスタートした時に UM.be = 1 になってくれるのであれば、 専用の ld.so を作りこんでビッグエンディアンのプロセスを導入できそうに思える。 エミュレータを書くときに便利そう。


8/14 (月)

Software Virtualization v.s. Hardware Virtualization (VMware の論文 PDF形式)

VMware 社から面白い論文が発表されている。 論文のタイトルは A Comparision of Software and Hardware Techniques for x86 Virtualization。 1st Author の人は知らないが、 2nd Author の Dr. Ole Agesen は元 Sun Microsystem で Exact VM をやっていた人と同一人物だと思われる。 GC や JIT コンパイラの偉い人なり。 はてなの方にも書いたけど、 論文をショボショボ読んだので日記にも書いてみる。 それにしても HotSpot VM の Cliff Click 氏といい Sun は人材流出が激しいなぁ。

VMware 社は 自分たちの持っているソフトウェアベースの Para-Virtualization (つまり VMware ね)を Intel の x86 用の仮想化技術 VT-i や AMD の Secure Virtual Machine (SVM) アーキテクチャに 実験的に対応させたようだ。 ベンチマークを取ってみると ハードウェアでやってもソフトウェアよりも速くなるとは限らない、 むしろハードウェアの方が遅いことがあると分かったようだ。

VMware のバイナリ変換の概要

3章に(Software-assisted Virtualization の) VMware が行っているバイナリ変換技術の要約が載ってる。 オリジナル x86 命令を基本ブロックの先頭から次の分岐命令までを一塊にして変換を行う。

move %ecx, %edi
move %esi, $2
cmp  %esi, %ecx
jge  label0

分岐命令と特権命令以外はそのままで、 分岐命令は変換する。

move %ecx, %edi      ; そのまま
move %esi, $2        ; そのまま
cmp  %esi, %ecx      ; そのまま
jge  [takenAddr]     ; label0 の飛び先に
jmp  [faullthrAddr]  ; 後続の命令に

こういう基本ブロックをプロシージャ程度の単位で数ブロック分まとめて行い、 基本ブロック同士が繋がっている部分の最適化を行う。

メモリアクセスは x86 のセグメント修飾を活用することで行う。 VMware はアドレススペースの高位に VMM 用のメモリを配置しておく。 ゲスト OS がセグメントレジスタをセットする箇所をトラップして、 高位の VMM 用のメモリ空間を隠した形のセグメントに変換して物理 CPU に設定する。 VMM 用のメモリ空間に触ろうとすると例外が上がるという寸法。

Hardware-assisted Virtualization との比較

Hardware-assisted Virtualization は特権命令等の特殊な命令が実行されるタイミングで トラップが揚がって Hypervisor 側に処理が移る。 このトラップハンドラが Hypervisor の本体になる。 一方、Software-assisted Virtualization ではうまく特権命令をバイナリ変換できれば、 このトラップ処理が不要になる。 このあたりをうまく作るとソフトの方が優位という結果がさえ生まれるそうだ。

論文にはいくつか測定結果が出ているが、 x86-64 / RHEL3 上で SPECint2000、SPECjbb2005 を動かした場合、 ソフトでもハードでも実機の 90〜100% の性能が出ている。

Apache サーバのベンチマークや I/O まで含めたようなベンチマークでは、 いろいろ極端な結果が出ている。 Figure 3. を見ると 同じ Apache ベンチマークでも Linux ではソフトの方が速く、 Windows ではハードの方が速い。 論文中でもはっきりとした分析はされていない。

まぁ、

いろいろ分析はされているけど、 x86 の仮想化が性能面で本領を発揮するのは、 AMD の Nesting Paging や Intel の EPT 待ちだろうね。


8/11 (金)

[Prog] (再々) メモリ・オーダリングについての覚え書き

2002年10月30日2004年10月12日に続いてmemory ordering についての覚え書き。 Total Store Ordering (TSO) と Store Forwarding の関係について。 これが意外にやねこしい状態を産む危険性を持っている。

ストア・バッファにストア命令を貯めて置き、後続のロード命令がストア・バッファ内に自分の書き込む場所と同じアドレスを見つけると、キャッシュまでデータを貰いにいかずにストア・バッファで折り返すことを Store Forwarding と呼ぶ。

今、メモリ [X] と [Y] の初期値が 0 の場合、以下の2つのプログラムの断片を実行したとする。 これを store forwarding のある CPU で並列実行すると、r1 = r3 = 1 で r2 = r4 = 0 という結果が返って来るかもしれない。 これはちょっと困った状態だ。

Program A
1: STORE [X] = 1
2: LOAD  r1 = [X]
3: LOAD  r2 = [Y]
Program B
4: STORE [Y] = 1
5: LOAD  r3  = [Y]
6: LOAD  r4  = [X]
なお X と Y は別々のキャッシュラインに属し、2 つの CPU は X と Y のキャッシュラインを共有(shared)状態で読み込んでいるとする。

プログラム A を実行した CPU では、1 行目のストア命令がストア・バッファに入り、2 行目のロード命令は 1 行目のストア命令からストアフォワーディングされた値を貰ってくる。 3 行目のロード命令はストア・バッファ中に値がないのでキャッシュから値を貰ってくる。 この段階で 1 行目のストア命令はまだキャッシュに反映されていない。 同じことがプログラム B を実行した CPU でも起きると、r1 = r3 = 1 で r2 = r4 = 0 という状態になる。

問題がどこにあるかというと、プログラマーがこの挙動を外側から見ると、r1 = r3 = 1 で r2 = r4 = 0 という状態は2つの CPU のどちらかで後発のロード命令(3,6)が先発のロード命令(2,4) を追い越さないと現れないという点だ。 最近のプロセッサは Total Store Ordering (TSO) やその亜種が多いが、TSO はロードがロードを追い越すことを認めていない。 その TSO でも store forwarding を認めているとこのタイプのロード→ロードの追い抜きは発生する。

難儀な話だ。 こういう状況の解決策は、メモリフェンス命令を余計に入れたりアトミックなメモリアクセスが必要だったりする。 アーキテクチャ毎にやり方が異なるので要注意。

追記:8/20

似たような問題が IA-32 の Speculative Program Ordering (SPO) にも存在する。 SPO は、

  • ロード命令間 (RAR) では追い越して実行可能 (ただし例外が発生する場合は、順序を守ること)。
  • ストア命令間 (WAW) では順序を守る。
  • ストア命令 → ロード命令(RAW) の順で実行された場合、 ロード命令は先行するストア命令を追い越して実行が可能。 ただし同一メモリアドレスに対する RAW では追い越し禁止。
  • ロード命令 → ストア命令 (WAR) の順で実行された場合は順序を守る。 ただし同一メモリアドレスに対する WAR では、 先発のロード命令がプロセッサ内で待機させられている場合、 後発のストア命令の書き込もうとしている値が先発ロード命令にフォワードされる。 これはストア命令によるロード命令の追い越しがあったかのように見える。
    (追記:2006.9.11)
    逆だ。同一アドレスに対する WAR は守り、異なるアドレスに対する WAR は守らない。

P.S.

IA-32 の日本語マニュアル(IA-32 インテル アーキテクチャ・ソフトウェア・デベロッパーズ・マニュアル、下巻: システム・プログラミング・ガイド) の 該当箇所の訳には問題があるように思える。 7-10 節に原文では 6. Data from buffered writes can be forwarded to waiting reads within the processor. とあるが、 これが 6. バッファリングされた書き込みのデータはプロセッサ内部で待機中の読み取りよりも先に実行できる。と訳されている。 誤訳ではないけど、理解し辛い文章だ。

トラックバック   [Trackback URL: http://www.nminoru.jp/cgi-bin/tb.cgi/2006-08-11]
[uDiary] メモ:TSO に関して。 2006-09-19 (Tue) 12:09:40
http://www.nminoru.jp/~nminoru/diary/2006/08.html#2006-08-11 五月雨式に書くのは控えますとかいいつつ、全然控えられていないので、反省中。いままでのやり取りをよくよんで、必要な文献もきちんと調査して、ちゃんと書かないといけないなぁと思う。 いままで、ひとつも嘘は書いていないつもりなのですが。 以下、忘れないように、気付いたことを、気付いた順序で。 [13] [うんの] 2006-09-19 10:08:57 より、 観測されるのは順序であって、各 load/store がそれぞれ global visible になった 瞬間に「あ、いまだ」と観測されるわけではありません。 観測されるべき、global visibility order が確定する瞬間なら存在する。ストアなら、coherence domain の一部であるところの、キャッシュに書かれた瞬間。ロードなら、その後キャンセルされずにコミットするようなロード(微妙な書き方)命令において、ロード値がデスティネーション(たとえばレジスタ)に書かれた瞬間。 こっちを知っていなければわからない順序になっている(ように見える)ところが、誤解の種なんだろうか。 SPARC V8 V9 の参考文献リストをみるに、どうやら、SPARC V8 は 「Sindu 以前」であるらしい。で、実際に SPARC V8 の TSO に関する記述は混乱している可能性が高そうだ。これは、引用された部分からもうかがえる。しまつた。 その点、(そういうのに比べると)P.O.O. は笑えるくらい論理的。直接関係ないけど、Storage Addressing のところを読んだときには、目から鱗が落ちる気持ちだった。
コメントを書き込む
[1] [うんの] 2006-09-11 10:23:29
いつぞや唐突に乱入した、うんのです。(「リアルでは会ったことがある」とか、なんとか)

実用的には、大筋まちがっていないともいえますが、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 のくせに、適切な「フェンス」命令がなくて、アトミック命令で代用せざるを得なかったという噂ですし。
[2] [nminoru] 2006-09-11 14:35:36
うんのさんお久しぶりです。
うんのさんのお話のポイントは、

命令順序 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 命令によって供給されていると、
[3] [うんの] 2006-09-11 15:29:36
こんにちは。覚えていていただけたようで、嬉しいです。

>命令順序 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 の場合)であるべきなのですが、
ロード→ロード追い越しと考えてしまうとこれがわからなくなりますから。

んで、なんでもかんでも「最強」のフェンス命令を置くはめになってしまうと>"余計に入れたり"
[4] [うんの] 2006-09-11 15:45:17
なんか、書き足りないような気がしたので、ちょこまかすみませんが、補足。

自分で、「『実行順序』という呼び方は微妙、というか、危険な感じがしますが。」と書きましたが、ここのポイントはすごく重要だと思います、やはり。

TSO のようなメモリモデルは、
・そのプロセッサ内部において実行される順序と、
・それが外部から観測される順序
を明確に区別したうえで、後者に関する制約を定義したものです。

だから、実行順序と global visible 順序を明確に区別して考えることが、どうしても重要となります。

んで、TSO は、ひとことでいうなら、store forwarding を積極的に推奨しているモデルだといえます。(Store が global visible になる前、つまり store buffer に滞留している間に、後続をどんどん処理してもいいよ、というモデルなので)
[5] [nminoru] 2006-09-13 21:53:08
お返事が遅くなってすいません。

まず言い訳をしておくと、もともとこの考察は 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 の効果が付与されたものが多いようです。
[6] [うんの] 2006-09-14 09:33:04
せっかくお付き合いいただいているので、私ももう少し時間をかけて書かなければならないと思っていますが、まずはすぐにコメント可能な点から。

> これが 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 のメモリモデルは、とても明晰に記述されていると思います。
[7] [うんの] 2006-09-14 01:09:09
いつも2個連続投稿ですみません。
投稿するとすぐに追加で思いつくので。

> 話を戻すと、2. の load が外から直接は観測されないというのは、ご指摘の通りだと思います。

観測されないのは、2. の load の値を使っていない(使うところを議論していない)からですね。

このあたりのことを、これ以上踏み込んで議論するには、
具体的な命令列を考える必要があるように思います。

というわけで、続きは明日投稿させていただきます。
#ご迷惑かもしれませんが、私としても完結させたく。。。
[8] [うんの] 2006-09-14 09:31:19
都合により、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] にはなり得ないことがはっきりするんじゃないかと思います。

#いちおう、五月雨式に書くのは、すこし控えます。
#まとめてからにしたい。
[9] [nminoru] 2006-09-14 19:34:42
まずプログラム例を示した方がよいようですね。

> これについては、命令列を少し変形して、
> 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 間の逆転が起こっているように見えませんか?
[10] [うんの] 2006-09-15 16:15:37
> 1: の STORE の結果は global visiable になっており、2: 4: はまだだと推測されます。
2:,3: はまだでしょうが、4: がまだと推測する根拠がありませんよ。

4: は、2:,3: がいずれも global visible になっていなくても、
それらを追い越して global visible になれて、
実際にそうなっているケースです。

4: のロード値が1であることが引っかかっておられるようですが、3: のストアが外部から観測されるよりも前に 4: のロード値1が確定することこそが、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: を追い越すのだと解釈することになると思います。
[11] [nminoru] 2006-09-15 22:45:10
1つのコメントの表示できる文字数が不足して見えない箇所があったので、表示可能な文字数を 1000 → 2000 に増やしてみました。
あと議論し易いようにコメント番号をつけました。
[12] [nminoru] 2006-09-16 01:36:59
おそらく 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 命令を追い越すと、そのことを他のプロセッサから検出可能なので…
[13] [うんの] 2006-09-19 10:08:57
こんにちわ。連休中は子守りモードにて、すっかりオフラインでした。

> おそらく 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 (こちらは global
visibility に関する)

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 になった
状態の3つがある、と。


> うんのさんは、
> > 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 さんは繰り返し同じ疑問を提示されていて、私も同じようなことを
言い続けているので、すっかり平行線ですね。

なにかきちんと述べられないか、少し考えてみます……。
[14] [うんの] 2006-09-20 23:03:57
いままでの一連のやりとりを読み返してみて、私の「議論」の仕方は常にずいぶんまずかったと思います。申し訳ありません。

述べるべきだったと思われる内容と、間違いの訂正をまとめて、
自分のところにまとめました: http://uhideyuki.sakura.ne.jp/uDiary/?date=20060920

特に、文献を確認しなおさずに、いいかげんな間違いを書いてしまった点については、きわめて不誠実だったと反省しています。すみません。

ボキャブラリが食い違っていることに気づいていながら、ベースとなるべき文献にあたらないというのは、我ながらダメでした。
[15] [nminoru] 2006-09-21 01:12:44
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" されると風になる。
[16] [nminoru] 2006-09-21 01:21:57
うんのさんのコメント[14]を読む前にコメント[15]を出すという、大変失礼なことをしてしまいました。
[14]であげられたページは後日で読ませていただきますが、お返事は少々おまちください m(_ _)m
[17] [うんの] 2006-09-21 09:28:19
おはようございます。
全然論点が絞れていなかったのは、私のせいでした。以後気をつけます。

> 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 を追い越させる効果があると読める、ということのみです。

……よね?(見えざるオーディエンスに尋ねてみる)
[18] [見えざるオーディエンス] 2006-09-21 18:06:35
>IBM System/370 には呪われし storage key という仕組みが

R bit はそもそも設定条件がゆるい上に、R=C=1 のときには
store forwarding の有無による問題はないと思いますよ。
(呪わしき話はそれこそTSO全般に顔を出すけれど)

その文面は storage key とは関係なく単に後方互換性のために外せないということでは。
[19] [うんの] 2006-09-22 11:13:00
コメント [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 の記述が不完全だと考えた
(こう考えているから、どこからともなく規則をもちだしたの
だと理解しています)根拠は何なんでしょうか。

# 語尾が「思います」ばっかりで恥ずかしい……
[20] [nminoru] 2006-09-22 23:04:34
うんのさんのコメント[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 のメモリモデルの本質を変えないもっとよい修正方法があると
# お考えだったからかもしれませんが。
[21] [nminoru] 2006-09-22 23:03:13
コメント[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 則という意味もありますので、簡単には外せないのではないでしょうか?
[22] [nminoru] 2006-09-22 23:01:41
うんのさんのコメント[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] に続けます。
[23] [nminoru] 2006-09-22 22:59:32
# コメント[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 の表現のぶれはあると考えますが) 全体として不完全だと考えていません。
問題は「外側からのプロセッサの観察した場合のメモリ順序」で、この順序の解釈が私とうんのさんで違う理由はコメントの前半部分でご理解いただけませんか?
[24] [うんの] 2006-09-23 22:46:47
うんのです。

どうやら同意には至らないようですが……。

・ うんのは 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."
> の記述(とそれと同様の部分)を削るだけで済むとお考え

[25] [見えざるオーディエンス] 2006-09-25 13:08:44
>>[21]
>その文面というのがコメント[20] の (B) の文のことでしょうか?

そうです。
self consistency を述べるのであればその節の当該段落中に書くのは不適切だということです。むしろ PoO の(他の部分の)書き方からすると、この(B)文では self consistency を述べる気はなく store forwarding を禁止したいだけでしょう。
store forwarding を許すことを親切に書くなら programming note 扱いで (B) 文の否定を書くのだと思います。

# そもそも Self consistency 則は5章の中盤あたりの「Conceptually sequence」ではないですか。
[26] [nminoru] 2006-09-27 03:32:43
ちょっと忙しくてお返事が遅れていますがご容赦を。
うんのさんのコメント[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 節の切り口を変えた要約ではないでしょうか?
[27] [見えざるオーディエンス] 2006-09-27 13:17:12
>メモリモデルが単純なので self consistency を守るということは、同時に外から見た順序を守るということでもあります。

これがおかしい。
[28] [nminoru] 2006-09-28 02:21:41
> メモリモデルが単純なので self consistency を守るということは、
> 同時に外から見た順序を守るということでもあります。

訂正させてください。
コメント[26]で self consisntecy と外から見た順序が同一になると言っているのは、同一のメモリアドレスに関するメモリアクセスのみです。
異なるメモリアドレスのメモリアクセスに関しては、当然 conceptual sequence と sequence observed by other CPUs が異なるのと認識しています。
[29] [nminoru] 2006-09-28 02:46:42
うんのさんのコメント[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. は私の推論ですので、うんのさんが違うとおっしゃられれば謝るほかありません。
[30] [うんの] 2006-09-28 12:42:41
うんのです。

本来話題になるべきは (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 を味方につけたところで、どうなるわけでもない点、
および、そのせいで存分に脱線してしまった点は、私が反省すべきことです。

最後に、盛大に招かれざる客を演じてしまい、すみませんでした。
性懲りも無くまた来るかもしれませんが、よろしくお願いします。

あ、そうだ。元住吉駅が高架化されるのに伴ったできたのは、長い「エスカレータ」
なんではないかと……。あ、いえ、すんません。


8/10 (木)

横置き資料・両面刷り原稿の閉じ方

横置きの原稿や縦置き原稿の2段組を両面印刷する場合、左右閉じと上下閉じのどちらが一般的なんだろう?

大学時代に研究室でミーティングがある時は、2段組・両面刷りの資料は左右閉じがデフォルトだった。 就職して研究所にいた頃は左右閉じと上下閉じが半々だったような気がする。 事業部に移ってからはまわりの人は皆 上下で閉じており自分も最近はそれに習っている。

ミーティングの席で資料を見ている分には左右閉じの方が読みやすいのだが、後でパンチで穴止めしてファイリングすると左右閉じだとページが反転してしまうんだよなぁ。

思い出してみると、大学時代は資料はその場で読み切るもので、ペーパーメディアを保存して参照するということがなかったような気がする。 ○○仕様書とか××資料とかを山と積み上げるのが今の現状。 思えば遠くに来たものだ…

[時事] 鈴置洋孝死す

Z の映画の完成を待っていたようにお亡くなりに。
ご冥福をお祈りします。


8/8 (火)

検索エンジンのロボット

Apache Web サーバのログをみていると 最近 NaverBot からのアクセスが多いなぁと思っていたが、 Naver が日本に帰ってくるそうだ。 うちのサーバー的には Yahoo! Slurp、百度(Baidu) と並び アクセスの多い検索エンジンのトップ3を占めるようになった。 アクセス数だけで言うと、トップ3 はいずれも Goolgebot より 10 倍以上アクセス数が多い。

トップ3と言っても無駄なくクロールが多いで、 実質的な転送内容は Googlebot の 2 〜 3 倍程度と思われる。 とくにアンカー(A)要素の rel="nofollow" (教育は参考資料 2005/01/19)を辿るがどうかが、 無駄ページのクロール数に大きく関係している。 うちのサイトはトラックバックやコメントの書き込みページなどの動的に生成されるページへのリンクは nofollow を指定して、 その先にあるページはクロールしないように宣言している。 しかしこの nofollow 指定に対応しているのは (自分の確認した範囲では) 提唱者の Google ぐらいで、 Yahoo!、Naver、百度はまったく気にせずにアクセスしてくる (教育は参考資料 2005/12/15)

それでも Naver の検索ロボットは Yahoo! Slurp や百度と比べても変な挙動をしている。 Naverbot は同じページへの二度目以降のクロールでも 手持ちのキャッシュと比較しない(If-Modified-Since フィールドを指定した GET リクエストを行わない)し、 robots.txt をコメツキバッタのように毎回取っていくんだよねぇ。


8/7 (月)

[CPU][Prog] 割り算がない

悲しいことに IA-64 には浮動小数点演算に割り算がない。
Intel 様は逆数近似命令と乗算を使ってニュートン・ラプソン法を使えとおっしゃる。

f6 を f7 で割って、結果を f8 に入れる
     frcpa.s0 f8,p6 = f6,f7
     ;;
(p6) fma.s1 f9 = f6,f8,f0
(p6) fnma.s1 f10 = f7,f8,f1
     ;;
(p6) fma.s1 f9 = f10,f9,f9
(p6) fma.s1 f11 = f10,f10,f0
(p6) fma.s1 f8 = f10,f8,f8
     ;;
(p6) fma.s1 f9 = f11,f9,f9
(p6) fma.s1 f10 = f11,f11,f0
(p6) fma.s1 f8 = f11,f8,f8
     ;;
(p6) fma.d.s1 f9 = f10,f9,f9
(p6) fma.s1 f8 = f10,f8,f8
     ;;
(p6) fnma.d.s1 f6 = f7,f9,f6
     ;;
(p6) fma.d.s0 f8 = f6,f8,f9

Intel 様はシフトに展開できない割り算は、 アセンブラの中でこのように書けとおっしゃる orz

とりあえず誤差を考えなければ 除数の逆数近似 frcpa.s0 f8,p6 = f6,f7 と 非除数と逆数の乗算 (p6) fma.s1 f9 = f6,f8,f0 の二つで OK だと思われる。 この誤差をどう評価するかが問題だ。

P.S.

正確に言うと整数掛け算もなくて、 fp ユニットを使う固定小数点演算で代用せにゃならん。 アセンブラを書いているとえらく面倒なんですけど。 どうにかならんかい。

コメントを書き込む
[ぶぅ] 2006-08-09 09:14:32
スクラッチでアセンブラを書いてるんですか?
コンパイラの出力をコピペしたりしてないんですか?
[nminoru] 2006-08-10 00:02:02
そのコンパイラを作る下準備のために、いろいろなコードを考えているところなのです (T_T;

8/5 (土)

[Food] ラージ・マハール@渋谷 (公式Excite楽天グルメ)

渋谷に出たついでにカレーを食べにラージ・マハールにゆく(前回は2004/12/12)。 アルゴビうま〜。

前菜
前菜
ベジタブルセット
ベジタブルのセット
ナン
ナン

本日見つけた懐かしい蛇口

元住吉駅になんか懐かしい蛇口の水道を見つける。


8/4 (金)

[MyWeb] 今度は日記のコメント欄にスパム

掲示板・トラックバックに続き 今度は日記等のコメント欄にスパムがやってきた (前回は7/3)

日記を含めた Web の各ページには「くっつきBBS」を改造したものが仕込んであるが、 ここにスパムコメントを大量に貼り付けてくる輩がいる。

貼り付けられているリンクを見る限り、 掲示板・トラックバックのスパマーとは違う人物らしい。 とにかく徹底的に戦うぞ!!


8/3 (木)

週刊チャンピオンに聖闘士星矢

週刊チャンピオンの 22+23 号に予告されていた通り、 車田正美の聖闘士星矢がチャンピオンに移籍してキター。 袋とじになっているようで立ち見は不能。

八神健、漫☆画太郎、高橋陽一、山根和俊と ジャンプからチャンピオンに移った漫画家は多いけど、 パッとしたヒットを残せずに去っていた。 車田正美もどうなることやら。


8/1 (火)

[Prog][CPU] 不正境界アクセス処理のための命令シミュレータ

x86 などと違って RISC 系だとアライメント境界に沿っていないメモリアクセスは エラーになる。

IA-64 の場合、CPU の Process Status Register (PSR) の中に AC ビットがあり、 これがオンの場合は不正境界アクセスに対して Unaligned Data Reference 例外を生じる。 Linux では PSR.ac=1 で運用しており、 通常は Unaligned Data Reference 例外をトラップして 自前で不正アライメント処理を行っている。

しかし現在実装中のプログラムは、 不正境界アクセスにまで厳密なアトミック性を要求して、 Linux の不正境界アクセス処理が使えない。 自前でトラップ処理を書かねばならぬ。 プロセスに prctl(2) を適用すると、 不正境界アクセスが SIGBUS シグナルになって返って来るので、 これをハンドルして IP アドレスから IA-64 の命令の抽出 → デコード → 擬似実行という 処理を書く。

というわけで、ほげほげと IA-64 の命令デコーダを試作中。 3 命令が 1 バンドル(16バイト)になっているから、 命令がバイト単位では取り出せないのよね。 いろいろ面倒。

追記:9/1

プログラムの中から不正境界アクセスを使用時に SIGBUS シグナルを発生させるようにするには、 以下のように prctl 関数を使用する。

#include <sys/prctl.h>

prctl(PR_SET_UNALIGN, PR_UNALIGN_SIGBUS, 0, 0, 0);

一方、 プロセスの中で 8 バイト境界内に収まる不正境界アクセスを ハードウェアで自動補正するように変更するには、 プログラムの先頭で以下のように実行する。

void reset_usermask_ac() {
  asm volatile ("rum 0x8");
}

先月の日記(2006年07月) 今月の日記(2006年08月)
2002 | 10 | 11 | 12
2003 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2004 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2005 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2006 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2007 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2008 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2009 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2010 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2011 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2012 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2013 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2014 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2015 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2016 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2017 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11
ホームページ | 最新のコメント50
インデックス: 食べ歩き | Java | プログラム | UNIX | 画像
最新の日記へのリンク | この日記ページをはてなアンテナに追加 この日記ページをはてなブックマークに追加
はてな ダイアリー アンテナ ブックマーク ブログ
Twitter | mixi | Facebook | Google+
slideshare | github | Qiita


Written by NAKAMURA Minoru, Email: nminoru atmark nminoru dot jp, Twitter:@nminoru_jp