ムーアの法則の終わり、そして最近の分岐予測について
序
僕らx86の大地の上に生きるものは、この10年Intelが告げるTick-Tockの鐘の音にあわせてムーアの法則の恩恵を享受してきた。^1 しかし、Kaby Lakeの14nmプロセス採用つまり、2年おきのプロセスルール刷新を諦めたことを持って、ムーアの法則は終焉を迎えたとされる。が、この認識は本当に正しいのだろうか。
ムーアの1965年の論文では、後のムーアの法則を”The complexity for minimum component costs has increased at a rate of roughly a factor of two per year"と表現している。人々はこの”complexity"は単位面積あたりのトランジスタ数のことだとこの50年間理解してきた。もっと言えばこの10年はプロセス・ルールのことだったかもしれない。だが、CPUがその内に集積してきたものはトランジスタだけだったのだろうか。
前述の論文のタイトルは"Cramming more components onto integrated circuits”という。Intelは様々なものをCPUという集積回路に詰め込んできた。しかし、このタイトルとムーアの法則の記述をあわせれば、真にCPUが集積したものが何かは明らかだろう。それは「複雑さ」だ。多数のSIMD命令も、AVXの奇怪なVEXエンコーディングも、すべてこの世界の複雑さを小さな魔法の石に封じ込めた結果なのだ。
分岐予測の進化
さて、高度なCPUにはブラックボックスが多数含まれますが、分岐予測はその中の最たるものの一つでしょう。CPUの最適化情報豊富なIntel® 64 and IA-32 Architectures Optimization Reference Manualを見ても毎度"Improved branch predictor."としか書かれていません。
とはいえ、手元にCPUはあるわけで、実際に動かしてその実力を測ることは出来るので測ってみましょう。
計測に使ったのはSpeed of various interpreter dispatch techniques V2のthreading.tar.gzの./directです。現代においてこれが適切なベンチマークだとは思わないのですが、間接分岐については多少参考にはなるんじゃないかな……。
SandyBridge
naruse@chkbuild008:~/threading$ grep -m1 'model name' /proc/cpuinfo model name : Intel(R) Xeon(R) CPU E5-2630L 0 @ 2.00GHz naruse@chkbuild008:~/threading$ perf stat ./direct Performance counter stats for './direct': 277.440861 task-clock (msec) # 0.998 CPUs utilized 5 context-switches # 0.018 K/sec 0 cpu-migrations # 0.000 K/sec 112 page-faults # 0.404 K/sec 650,780,115 cycles # 2.346 GHz [82.74%] 365,836,274 stalled-cycles-frontend # 56.22% frontend cycles idle [82.72%] 377,885,001 stalled-cycles-backend # 58.07% backend cycles idle [67.70%] 423,892,636 instructions # 0.65 insns per cycle # 0.89 stalled cycles per insn [84.15%] 208,884,768 branches # 752.898 M/sec [84.14%] 12,251,769 branch-misses # 5.87% of all branches [82.71%] 0.278114864 seconds time elapsed
Ivy Bridge
% grep -m1 'model name' /proc/cpuinfo model name : Intel(R) Xeon(R) CPU E5-2650 v2 @ 2.60GHz # 1470829786 20:49:46 naruse@tk2-243-31075:~/threading % perf stat ./direct Performance counter stats for './direct': 120.812507 task-clock (msec) # 0.996 CPUs utilized 0 context-switches # 0.000 K/sec 0 cpu-migrations # 0.000 K/sec 41 page-faults # 0.339 K/sec 355605784 cycles # 2.943 GHz 170213145 stalled-cycles-frontend # 47.87% frontend cycles idle <not supported> stalled-cycles-backend 380562594 instructions # 1.07 insns per cycle # 0.45 stalled cycles per insn 160106383 branches # 1325.247 M/sec 9808 branch-misses # 0.01% of all branches 0.121333298 seconds time elapsed
Haswell
% grep -m1 'model name' /proc/cpuinfo model name : Intel(R) Xeon(R) CPU E5-2660 v3 @ 2.60GHz % perf stat ./direct Performance counter stats for './direct': 159.226456 task-clock:u (msec) # 0.996 CPUs utilized 0 context-switches:u # 0.000 K/sec 0 cpu-migrations:u # 0.000 K/sec 35 page-faults:u # 0.220 K/sec 321780650 cycles:u # 2.021 GHz 380085245 instructions:u # 1.18 insn per cycle 160015808 branches:u # 1004.957 M/sec 5206 branch-misses:u # 0.00% of all branches 0.159844405 seconds time elapsed
Skylake
% grep -m1 'model name' /proc/cpuinfo model name : Intel(R) Xeon(R) CPU E3-1245 v5 @ 3.50GHz # 1470829624 13:47:04 naruse@sd-98161:~/threading % perf stat ./direct Performance counter stats for './direct': 84.458565 task-clock (msec) # 0.996 CPUs utilized 0 context-switches # 0.000 K/sec 0 cpu-migrations # 0.000 K/sec 38 page-faults # 0.450 K/sec 300759565 cycles # 3.561 GHz 380503237 instructions # 1.27 insn per cycle 160093203 branches # 1895.524 M/sec 9349 branch-misses # 0.01% of all branches 0.084794713 seconds time elapsed
訂正: 初出の記事ではSkylakeの値が-O3にしたものになっていました。-Oだと以上の通りです。
考察
所要時間はCPUの周波数も影響するのでその分は差し引いてみてくださいね。（本当はTurbo Boostオフにするべきなんだけど、手元のマシンじゃないんだゴメンな……）
考察と言ってもそこまで詳しいわけではないので実のあることは言えないのですが、今でもその進化が続いていることは見ればわかるでしょう。また、分岐予測に詳しい人ほど最近のIntel CPUの分岐予測的中率には驚かれるのではないかと思いました。
まとめ
あんまり賢い解説もないまま締めに入りますが、あんまり最近のIntel CPUの分岐予測について言及した記事って英語含めてもないと思うので、これで盛り上がって誰か解説してくれるといいなと思います！