NAKAMURA Minoru の日記 (2009年1月)

キーボードの打鍵数

昨年の1月27日から職場の Windows マシンンに 「打鍵のtomo」をインストールして、 毎日のキーボード打鍵数を計測していた (2008年2月9日の日記)のだが、 ちょうど1年が経過した。 その間の打鍵数データをまとめると、

• 1年の総打鍵数が1682万9027回
• (出勤した日の)1日平均は約5万回
• 1日の自己最高は 2008年の11月30日で 12,0697 回

になる。 打鍵数を万回単位でカウントすると以下の表のようになる。

叩いた回数以上に、 職場のパソコンを叩いた合計日数が344日というのが悲しい。
昨年一年で20日は休んだと思っていたのだが orz。

P.S.

いや、いいんだ。
1年は365日だから 365 - 344 で 21 日休んでいる計算になる。
一瞬、1年は356日と思ってしまったよ。

[CPU] IA-64 の Long VHPT のハッシュアルゴリズム

IA-64 の仮想記憶方式は TLB に仮想ページが載っていない場合は、 フォルトを発生させ TLB 挿入命令を使うというのが基本になっている。 ただこれだけだと TLB ミスフォルトが多発するので、 Virtual Hash Page Table (VHPT) と呼ばれる支援機構を持っていて、 TLB ミスが起こったらまず VHPT をハード的に検索するという機構になっている。

VHPT はショート形式とロング形式の 2 つを持っている。
ショート形式の方は virtual Hash page table といいつつ リニアマップになっている。 2⁶⁴ の空間を 8 つに分けた 2⁶¹ 毎に VHPT を配置して、 以下の検索式でエントリにアクセスする (ショート形式の VHPT のエントリサイズは 8 バイト)。

VHPT_base + (address) / page-size * VHPT-short-entry-size

VHPT のサイズはページサイズで決まるのだが、 VHPT 自身も仮想記憶上に配置できるので実際に使用する仮想ページに対応した部分だけを 構成すればよい。

一方、 ロング形式は本当にハッシュテーブルになっている。 ただハッシュ方式は連想度1のダイレクトマップなので、 仮想アドレス毎にハッシュエントリが決まり、 そこにエントリがない場合はフォルトが発生する。 複数の仮想アドレスが同一のエントリを巡って衝突することもある。 というかどうも Long VHPT はこの衝突がすごい頻度で発生するんですけど…

ロング形式の VHPT エントリ数は、 VHPT全体で VHPT サイズ / エントリサイズ(32) で決まる。 ショート形式と異なりロング形式の VHPT はテーブルサイズを制御レジスタで指定するので サイズを拡大すると衝突は減少する。 ただハッシュ関数がすごい単純なようで、 調査の範囲では同じ RID のアドレスは、 単にモジュロをとっているだけみたい。

((address) / page-size) % (VHPT-size / 32)

プログラムの性質によっては、 というか今書いているプログラムは、 この周期にクリーンヒットを受けて VHPT ミスしまくりなんだけど、 どうにかならんものかしら？

成人式

今日は成人式らしい。 会社の隣にある横浜アリーナも成人式の会場になっているようで、 プリンスペペの前を新成人がぞろぞろと歩いているよ。 シールドを抱えた警察官もぞろぞろ。

[CPU] x86-64 のページテーブルエントリにある available-to-software bits

AMD64 というか Intel64 というか x86-64 の仕様書を読み読みしながら、 アレをどうやってアレしようか考える。

32 ビットの x86 のページングはセグメントテーブルとページテーブルの 2 段を使っていたが、 64 ビットの x86-64 はこれを無理矢理 4 段に拡張している。 しかも x86 は各テーブルのエントリが 4 バイトだったのに対して、x86-64 は 8 バイトに倍増。 結果として x86 が 1 ページ(4KB) のページングのために 4 バイト×2段で 8 バイトの情報を使っていたのに対して、 x86-64 は同じ 1 ページ(4KB) のアドレス変換のために 8 バイト×4段で 32 バイトの情報が必要になる。

その分、各テーブルのエントリの中のビットはすかすかで Intel64 and IA-32 Architectures Software Developer's Manual の Volume 3A: System Programming Guide, Part1 によると 各エントリの [62:52] ビットと [11:9] ビットはソフトウェアが自由に使用してよい領域として残されているようだ。

ソフトが自由に使って良い余白ビットは本来は OSの実装者のために用意された領域だが、 x86-64/Linux のカーネルは (P ビットが 0 の場合を除くと) avail ビットフィールドは使用していないようだ。 このビットフィールドを使ってアレを高速化したいのだが、なんかうまい方法はないものかしら？

自分に勝つより自分に克て

前から気になっていたんだけど 「自分に勝つ」という表現は日本語としてどうかと思う。 刃牙のリアルシャドーじゃないんだから。

Google 様にお伺いを立てると…

もう駄目なのかしれない。

[CPU] 最近の Intel x86 CPU の最適化方法をぼちぼち考える

最近 x86-64 の調査をボチボチしているのだが、 ここ数年 Itanium2 に浸りっぱなしだったので メインストリームである x86 CPU の事情にすっかり疎くなっているに気づく。 反省。

今後 x86 で開発を進めるとなると分岐ミスペナルティの影響を再考し直す必要がありそう。 Itanium2 はパイプライン段数が6段しかなかったが、x86 の Core duo だと14段になる。

IF 変換

IA-64 はほとんど全ての命令がプレディケートの対象だったけど、 x86 は CMOV と SETCC ぐらいしかないよ ヽ(;´Д｀)ノ
修飾可能なロード・ストア命令がないと困るんだけど、、、 ってないよなぁ、、、 みんなどうやってプログラム書いているんだ。

レジスタ間接分岐

Itanium2 の場合、 レジスタ間接分岐のターゲットアドレスは分岐レジスタと呼ばれる8本の専用レジスタを使って行われていた。 命令フェッチのフェーズで間接分岐命令が出現すると分岐レジスタの値を呼んで、 その値をターゲットアドレスみなして投機実行を続ける。 分岐レジスタへの書き込みはレジスタ間接分岐命令に先行するが、 パイプライン動作しているために間接分岐命令をフェッチした段階で分岐レジスタの値が確定していないことがあるが、 Itanium2 はパイプライン段数が6段なので適当な間隔が空くように最適化できれば 分岐ミスなしで動作させることが可能だった。

mov b6 = ....

(ここを空ける)

br.call  b0 = b6

一方、x86 は NetBurst と Core duo マイクロアーキテクチャは 分岐予測器が間接分岐の命令アドレスと最後に分岐したターゲットアドレスを記録しおいて、 次回も同じ方向に分岐するだろうという予測の元に投機実行を行う。 つまり間接分岐命令毎に1方向しか分岐予測できない。

Pentium M の間接分岐の予測はもう少し複雑なのだが焼け石に水。 結局インタプリータのディスパッチャーは毎回分岐予測が外れるってことだね (T_T;

追記：2009/6/12

よく考えれば修飾可能なロードは CMOVcc 命令を使えば可能だよね。 修飾可能なストアは SETcc 命令を使えば 1 バイト領域に 1 を書き込むだけなら可能…

謹賀新年

明けましておめでとうございます。
今年もよろしくお願いします。

昨年は leap second が入った

昨年はうるう秒が挿入されたのですが、 今朝起きて Linux マシンのカーネルログを見てみるとちゃんと うるう秒が挿入されていました。 偉いですね。

Clock: inserting leap second 23:59:60 UTC

[CPU][Compiler] Intel C++ Compiler で IA-64 の probe 命令を出す方法が分かった!!

Intel C++ Compiler は しかし組み込み関数で生成できない命令もあって、 その一つが probe 命令だった。 lfetch 命令は生成可能なのだが…

しかし、 何気なく HP-UX のアセンブラマニュアル を眺めていると、 _Asm_probe_rw_fault というインラインアセンブラ構文が載っている。 そういえば /opt/intel/cc/*/bin/mcpcom を strings した出力の中に _Asm_probe_rw_fault ってあったよなぁ〜と思いながらサンプルコードを書いて見ると ビンゴ!!

#include <ia64intrin.h>

void probe_fault_test(void * p)
{
    _Asm_probe_rw_fault(p, 3);
}

0000000000000000 <probe_fault_test>:
   0:   01 00 0c 40 31 04       [MII]       probe.rw.fault r32,3
   6:   00 00 00 02 00 00                   nop.i 0x0
   c:   00 00 04 00                         nop.i 0x0;;
  10:   09 10 04 02 80 05       [MMI]       alloc r2=ar.pfs,1,1,0
  16:   00 00 00 02 00 00                   nop.m 0x0
  1c:   00 00 04 00                         nop.i 0x0;;
  20:   11 00 00 00 01 00       [MIB]       nop.m 0x0
  26:   00 00 00 02 00 80                   nop.i 0x0
  2c:   08 00 84 00                         br.ret.sptk.many b0;;

他のインラインアセンブラも試してみたのだが、 どうも IA-64/Linux 用の icc は HP C/aC++ のインラインアセンブラの記法を受け付けるみたいだ。 Undocumented だけど。

ただ生成されたコードに若干疑問が残る。 alloc 命令よりも probe 命令の方が上に行ってしまうのが謎だ。 ただ icc のマニュアルに書いてある他の組み込み関数(__fcとか)でも同様のことは起きるので気にしない。 最もマニュアルに書いてあってもバグ持ちで使えないということはあるわけだが (2007年5月9日の日記)…