分岐予測を予測する

いろいろな手法を使って分岐を減らすことを試みていましたが実際にはどの程度"効く"のか試してみました.

#タイトルは`推測'の方が適切でしょうが語呂がいいので...

No. 001
サンプルプログラムはint型配列のデータの絶対値を取るルーチンで中身はtest1Aとtest2Aです.
test1Aが条件分岐するタイプ, test2Aがしないタイプです.

1024回ループしたときにかかったクロック数
-		jmpしない比率(r)
CPU	ルーチン	0.000	0.380	0.495	0.876	1.000
K6-III	test1A	3104	4324	7254	6949	4175
K6-III	test2A	5741	5730	5730	5745	5728
Athlon	test1A	5195	6839	9842	9850	3145
Athlon	test2A	4142	4143	4143	4142	4146
Coppermine	test1A	5208	6662	10182	9089	3133
Coppermine	test2A	5181	5182	5185	5181	5184

当たり前ですが, 入力データによらないタイプのtest2Aはクロックは一定です.
ただAthlonは他のCPUよりも1ループあたり1clock速いです.
9命令を4clockで実行するのですから流石です.
test1Aは分岐予測が殆んど当たらないと思われる r = 0.5 でどれもクロックが一番かかっています.

分岐でかかる時間は次の4つのタイプとそれらの比率で決定されるはずです.

A. 分岐すると予測して当たり

B. 分岐すると予測してはずれ

C. 分岐しないと予測して当たり

D. 分岐しないと予測しはずれ
#"予測出来ない場合は分岐予測しない"なんてパターンもあるのかな?

これらの数値を求めたいのですが, それは可能なのか, もしそうならその値は?
ではまた次回

No. 002
まずA, Cは簡単ですね.
r= 0 または 1 のときに分岐予測が外れるとは考えられないので次の様になります.

分岐予測成立時の1loop当たりのクロック
CPU	A (jmpする)	C (jmpしない)
K6-III	3	4
Athlon	5	3
Coppermine	5	3

パイプラインが深いCPU(Athlon, Coppermine)では分岐すると時間がかかることがわかります.
これらのCPUではループを延ばすことは最適化につながると判断できます.
逆にK6-IIIではコンパクトを目指せば良いようですね. (これは私の乏しい経験にも合致します)

次に問題のB, Dですが, これがどうもよく分かりません(^^;.
CPUの分岐予測の精度がどの程度かが分からないからです.
仕方がないので r = 0.495 の時の値だけから推測してみます.
このときは完全にランダムなので分岐予測が当るか外れるかは半々と見てよいでしょう.
従って ( A + B + C + D ) * 0.25 = test1Aのクロックとなります.
これから計算すると次のようになります.

分岐予測非成立時の1loop当たりのクロック
CPU	B + D
K6-III	21
Athlon	30
Coppermine	32

現時点ではB, Dそれぞれの値を求めることは出来ませんが, BとCの値は殆んど違わないだろうと考えると上の表の値の約半分, つまり K6-IIIで10clk, Athlon, Coppermineで15clk となります.
この数値があってるのか分かりませんが, かなり大きい値ですね.

No. 003
ところでAthlon, Coppermineの r = 0.876 のときのクロックの大きさが気になります.
データは結構偏っていると思うのですがあんまり分岐予測が当っているとは思えない数値です.
というわけで次はこんな実験をしてみました.
まず最初に全て jmp する場合( ALL_JMP ) と全く jmp しない場合 ( NON_JMP ) のクロックを測定しています.
それから分岐パターンを
-------------- ( -;非分岐 +;分岐)
-+-+-+-+-+-+-+
-**-**-**-**-*
-***-***--***-
-****-****-***
...
の様に規則正しく変化させながら, その場合のクロックを計測します.
Expは ALL_JMP と NON_JMP の単純比例配分, real が計測値です.
この2つ値が近いなら分岐予測が当たっていると推測できます.
プログラムと結果
一部抜粋
K6-III

 all jmp=3061.971680 non jmp=4062.577148
1.000000(1000)  Exp 4062.577148 real 4086.478000 
0.500000( 500)  Exp 3562.274414 real 3554.477600 
0.334000( 334)  Exp 3396.173906 real 3388.902400 
0.250000( 250)  Exp 3312.123047 real 3320.248000 
0.200000( 200)  Exp 3262.092773 real 3271.769200 
0.167000( 167)  Exp 3229.072793 real 5423.620000 over
0.143000( 143)  Exp 3205.058262 real 5219.144800 over
0.125000( 125)  Exp 3187.047363 real 4064.984000

Athlon

 all jmp=5074.309082 non jmp=5067.795898
1.000000(1000)  Exp 5067.795898 real 4257.562400 
0.500000( 500)  Exp 5071.052490 real 5090.226800 
0.334000( 334)  Exp 5072.133679 real 5063.602400 
0.250000( 250)  Exp 5072.680786 real 5091.344000 
0.200000( 200)  Exp 5073.006445 real 5094.566400 
0.167000( 167)  Exp 5073.221380 real 5070.599600 
0.143000( 143)  Exp 5073.377697 real 5072.131200 
0.125000( 125)  Exp 5073.494934 real 5092.923600 
0.112000( 112)  Exp 5073.579605 real 5068.163200 
0.100000( 100)  Exp 5073.657764 real 6180.954800 over
0.091000(  91)  Exp 5073.716382 real 6081.521200 over
0.084000(  84)  Exp 5073.761975 real 5985.178000

Coppermine

 all jmp=5084.919434 non jmp=3062.996338
1.000000(1000)  Exp 3062.996338 real 3059.267600 
0.500000( 500)  Exp 4073.957886 real 4062.639200 
0.334000( 334)  Exp 4409.597120 real 4440.931200 
0.250000( 250)  Exp 4579.438660 real 4600.040400 
0.200000( 200)  Exp 4680.534814 real 7478.774400 over
0.167000( 167)  Exp 4747.258277 real 6897.462400 over
0.143000( 143)  Exp 4795.784431 real 6775.444800 over
0.125000( 125)  Exp 4832.179047 real 6433.467600 over

No. 004
同じサブルーチンなのにAthlonのnon jmpの値がさっきの計測値と異なるのが謎です.
まあ, それはさて置き各CPUについてみるとパターンの周期がPIIIが5, K6IIIが6, K7IIIが10になった時点でrealがExpを大幅に上回っています.
この時点で分岐予測が外れ出したと考えてよいでしょう.
逆にAthlonの分岐予測はかなりの履歴を見ているようです.
Coppermineの推測の幅は小さいようです. 履歴用レジスタが2bitしか無い???
それから r = 0.2のとき7500clk, r = 0.8のとき3500clkと全然値が違います.
もしかして No.002 で B = D としたのは誤りなのでしょうか.
それとも分岐予測の非対称性なのでしょうか.
Normal Pentiumには分岐予測に関するバグ(あるいはバグに近い仕様)がありましたけど.
また次回

No. 05
dskさんが分岐予測が外れるはずのパターンを教えてくださいました.
PII, PIIIでは動的分岐予測では最新の4回の分岐パターンを元に分岐予測を行います.
それで10111001 10101100 01010010 00001111というパターン(0, 1は分岐する/しない)を与えると常に予測がはずれるだろうという考えです.
何故かというと先頭から順番に4つづす取り出してみます.

1 0 1 1 1 0 0 1
1 0 1 1(1)
  0 1 1 1(0)
    1 1 1 0(0)...

まず最初は1011というパターンの後1が来ているのでCPUは次回このパターンが来た時は次に1がくると予測します.
同様に0111が来た時は0と予測します.
ところが上の長い列を眺めると次に1011があるところ

10111001 10101100 01010010 00001111
           ^^^^*

では0が来ているので分岐予測がはずれます.
他全ての16パターンについてその次の数字は0と1が交互に現れるため必ず分岐予測が外れるというわけです.
#面白い！
実際にこのパターンをPIIIに与えてみると1万クロック以上掛かっていました.
やはり分岐予測が外れた時は10クロック以上のペナルティがあると見てよいと思います.

No. 06
掲示板にも書きましたが, 同じパターンを与えてもAthlonは5クロックしかかかっていません.
予測がほぼ完璧と思える数値です. 凄いですね.
それからPIIIでの疑問の続きです.
上のCoppermineでの0.2000ときの実測値が7478クロックとなっています.
この場合は000010000100001...という数列なので(周期5)

0 0 0 0 1 0 0 0 0 1 0 0 0 ..
0 0 0 0(1)
  0 0 0 1(0)
    0 0 1 0(0)
      0 1 0 0(0)
        1 0 0 0(0)
          0 0 0 0(1)

だから現れるパターンは0000, 0001, 0010, 0100, 1000でそれぞれその後の状態は一定なので常に分岐予測が当たるはずですのでこの値は大き過ぎます. この理由がよく分かりません. もっと調べないといけませんね.
周期6の時は

0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 ...
0 0 0 0(0)
  0 0 0 0(1)
    0 0 0 1(0)
      0 0 1 0(0)
        0 1 0 0(0)
          1 0 0 0(0)
            0 0 0 0(0)
              0 0 0 0(1)
                0 0 0 1(0)

ですから0000のパターンの後は0と1が交互に現れます. その他の0001, 0010, 0100, 1000の場合は常に0ですから全体で6回のうち2回だけ分岐予測が外れると推測されます.
おおざっぱに予測成功のときを4000クロック, 失敗の時を10000クロックとすると 4000*4/6+10000*2/6=6000ですから大体実測値に近いです.

No. 07
関数呼び出しプログラムはとあるMLで少し話題になったことを試みたものです. 適当に作ったプログラムなので何をやっているのか分かりにくいですが,

int test1(int a){return a+a;}

などのごく簡単なプログラムをいくつか用意してそれらを

static int (*funcTbl[])() = {
    test0, test1, test2, test3, test4, test5, test6, test7,
    test0, test1, test2, test3, test4, test5, test6, test7,
};

というテーブルに用意し,

a = funcTbl[a](a);
a = a & 15;

という形で何度も呼び出したときにパラメータによって所要時間は変わるのか, ということを調べてるつもりです.結果は以下の通り.

所要クロック/10000loop
-	CPU
呼び出し方法	PIII	Athlon
つねに同じテーブル	8.2	12
交互呼び出し	23.4	20

1回切りのテストなので数値はほとんど信用できませんが間接呼び出しは意外と速いこと, けれども前回と異なる場所を呼び出すとかなり遅くなることが分かりました.
レジスタを使った相対分岐でもそれなりに分岐先の情報を記録してるんですね.
#私は条件分岐以外は何もしてないと思っていたのでちょっとびっくり.

[Back]

御意見は光成滋生<herumi@nifty.com>までお願いします