ムーアの法則の終わり、そして最近の分岐予測について
ムーアの法則の終わり、そして最近の分岐予測について
序
僕らx86の大地の上に生きるものは、この10年Intelが告げるTick-Tockの鐘の音にあわせてムーアの法則の恩恵を享受してきた。*1 *2 しかし、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-gcc48 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 naruse@chkbuild008:~/threading$ perf stat ../direct-gcc54 Performance counter stats for '../direct-gcc54': 155.542201 task-clock (msec) # 0.996 CPUs utilized 3 context-switches # 0.019 K/sec 0 cpu-migrations # 0.000 K/sec 113 page-faults # 0.726 K/sec 352,393,558 cycles # 2.266 GHz [82.03%] 141,991,479 stalled-cycles-frontend # 40.29% frontend cycles idle [82.23%] 160,691,365 stalled-cycles-backend # 45.60% backend cycles idle [69.17%] 379,813,966 instructions # 1.08 insns per cycle # 0.42 stalled cycles per insn [84.58%] 160,216,299 branches # 1030.050 M/sec [84.57%] 3,933 branch-misses # 0.00% of all branches [82.03%] 0.156168350 seconds time elapsed
Ivy Bridge
% grep -m1 'model name' /proc/cpuinfo model name : Intel(R) Xeon(R) CPU E5-2650 v2 @ 2.60GHz % perf stat ../direct-gcc48 Performance counter stats for '../direct-gcc48': 238.146900 task-clock (msec) # 0.982 CPUs utilized 37 context-switches # 0.155 K/sec 0 cpu-migrations # 0.000 K/sec 42 page-faults # 0.176 K/sec 689162737 cycles # 2.894 GHz 403352479 stalled-cycles-frontend # 58.53% frontend cycles idle <not supported> stalled-cycles-backend 430913321 instructions # 0.63 insns per cycle # 0.94 stalled cycles per insn 210172241 branches # 882.532 M/sec 14205738 branch-misses # 6.76% of all branches 0.242429416 seconds time elapsed % perf stat ./direct-gcc54 Performance counter stats for './direct-gcc54': 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 % perf stat ../direct-gcc48 Performance counter stats for '../direct-gcc48': 205.179841 task-clock:u (msec) # 0.995 CPUs utilized 0 context-switches:u # 0.000 K/sec 0 cpu-migrations:u # 0.000 K/sec 36 page-faults:u # 0.175 K/sec 448041978 cycles:u # 2.184 GHz 430085324 instructions:u # 0.96 insn per cycle 210015836 branches:u # 1023.570 M/sec 4887 branch-misses:u # 0.00% of all branches 0.206141759 seconds time elapsed % perf stat ../direct-gcc54 Performance counter stats for '../direct': 158.532437 task-clock:u (msec) # 0.995 CPUs utilized 0 context-switches:u # 0.000 K/sec 0 cpu-migrations:u # 0.000 K/sec 35 page-faults:u # 0.221 K/sec 315471369 cycles:u # 1.990 GHz 380085288 instructions:u # 1.20 insn per cycle 160015810 branches:u # 1009.357 M/sec 6829 branch-misses:u # 0.00% of all branches 0.159275797 seconds time elapsed
Skylake
% grep -m1 'model name' /proc/cpuinfo model name : Intel(R) Xeon(R) CPU E3-1245 v5 @ 3.50GHz % 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 % perf stat ../direct-gcc54 Performance counter stats for '../direct': 101.940704 task-clock (msec) # 0.996 CPUs utilized 0 context-switches # 0.000 K/sec 0 cpu-migrations # 0.000 K/sec 37 page-faults # 0.363 K/sec 361064330 cycles # 3.542 GHz 380540900 instructions # 1.05 insn per cycle 160100883 branches # 1570.530 M/sec 18006 branch-misses # 0.01% of all branches 0.102305561 seconds time elapsed
訂正: 初出の記事ではSkylakeの値が-O3にしたものになっていました。-Oだと以上の通りです。
考察
所要時間はCPUの周波数も影響するのでその分は差し引いてみてくださいね。（本当はTurbo Boostオフにするべきなんだけど、手元のマシンじゃないんだゴメンな……）
考察と言ってもそこまで詳しいわけではないので実のあることは言えないのですが、今でもその進化が続いていることは見ればわかるでしょう。また、分岐予測に詳しい人ほど最近のIntel CPUの分岐予測的中率には驚かれるのではないかと思いました。
まとめ
あんまり賢い解説もないまま締めに入りますが、あんまり最近のIntel CPUの分岐予測について言及した記事って英語含めてもないと思うので、これで盛り上がって誰か解説してくれるといいなと思います！
追記
Sandy Bridgeが著しく悪かったのはgcc5.4以降が賢いからっぽい。
gcc (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4 Copyright (C) 2013 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 000000000040052d <main>: 40052d: 48 8b 35 2c 0b 20 00 mov 0x200b2c(%rip),%rsi # 601060 <prog.1723> 400534: 48 89 f2 mov %rsi,%rdx 400537: b9 80 96 98 00 mov $0x989680,%ecx 40053c: b8 68 10 60 00 mov $0x601068,%eax 400541: ff e2 jmpq *%rdx 400543: 48 8b 10 mov (%rax),%rdx 400546: 48 8d 40 08 lea 0x8(%rax),%rax 40054a: eb f5 jmp 400541 <main+0x14> 40054c: 48 8b 10 mov (%rax),%rdx 40054f: 48 8d 40 08 lea 0x8(%rax),%rax 400553: eb ec jmp 400541 <main+0x14> 400555: 48 8b 10 mov (%rax),%rdx 400558: 48 8d 40 08 lea 0x8(%rax),%rax 40055c: eb e3 jmp 400541 <main+0x14> 40055e: 48 8b 10 mov (%rax),%rdx 400561: 48 8d 40 08 lea 0x8(%rax),%rax 400565: eb da jmp 400541 <main+0x14> 400567: 48 8b 10 mov (%rax),%rdx 40056a: 48 8d 40 08 lea 0x8(%rax),%rax 40056e: eb d1 jmp 400541 <main+0x14> 400570: 85 c9 test %ecx,%ecx 400572: 7e 0d jle 400581 <main+0x54> 400574: 83 e9 01 sub $0x1,%ecx 400577: 48 89 f2 mov %rsi,%rdx 40057a: b8 68 10 60 00 mov $0x601068,%eax 40057f: eb c0 jmp 400541 <main+0x14> 400581: 48 83 ec 08 sub $0x8,%rsp 400585: bf 00 00 00 00 mov $0x0,%edi 40058a: e8 a1 fe ff ff callq 400430 <exit@plt> 40058f: 90 nop
% gcc --version gcc (Ubuntu 5.4.0-6ubuntu1~16.04.2) 5.4.0 20160609 Copyright (C) 2015 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 0000000000400526 <main>: [37/1887] 400526: 48 8b 35 33 0b 20 00 mov 0x200b33(%rip),%rsi # 601060 <prog.1832> 40052d: 48 89 f2 mov %rsi,%rdx 400530: b9 80 96 98 00 mov $0x989680,%ecx 400535: b8 68 10 60 00 mov $0x601068,%eax 40053a: eb 07 jmp 400543 <main+0x1d> 40053c: 48 8b 10 mov (%rax),%rdx 40053f: 48 8d 40 08 lea 0x8(%rax),%rax 400543: ff e2 jmpq *%rdx 400545: 48 8b 10 mov (%rax),%rdx 400548: 48 8d 40 08 lea 0x8(%rax),%rax 40054c: eb f5 jmp 400543 <main+0x1d> 40054e: 48 8b 10 mov (%rax),%rdx 400551: 48 8d 40 08 lea 0x8(%rax),%rax 400555: eb ec jmp 400543 <main+0x1d> 400557: 48 8b 10 mov (%rax),%rdx 40055a: 48 8d 40 08 lea 0x8(%rax),%rax 40055e: eb e3 jmp 400543 <main+0x1d> 400560: 48 8b 10 mov (%rax),%rdx 400563: 48 8d 40 08 lea 0x8(%rax),%rax 400567: eb da jmp 400543 <main+0x1d> 400569: 85 c9 test %ecx,%ecx 40056b: 7e 0d jle 40057a <main+0x54> 40056d: 83 e9 01 sub $0x1,%ecx 400570: 48 89 f2 mov %rsi,%rdx 400573: b8 68 10 60 00 mov $0x601068,%eax 400578: eb c9 jmp 400543 <main+0x1d> 40057a: 48 83 ec 08 sub $0x8,%rsp 40057e: bf 00 00 00 00 mov $0x0,%edi 400583: e8 88 fe ff ff callq 400410 <exit@plt> 400588: 0f 1f 84 00 00 00 00 nopl 0x0(%rax,%rax,1) 40058f: 00
追記2
かと思われたが、HaswellだとGCC4.8で作ったバイナリでも分岐予測ミスは0.00%だった。なお、GCC4.8バイナリをIvy Bridgeマシンで実行するとSandyと大差ない結果なので、分岐予測能力はSandyでもそれなりにすごくて、Haswellはもっとすごいってことかな。
追記3
Intel CPUの分岐予測の進化面白いです。 https://t.co/y1t7zEEJn7
— suzaki (@KuniSuzaki) 2016年8月16日
更に求めるとコンパイラによる PGO: Profile Guided Optimization との効果との比較がないものでしょうか。 https://t.co/JWwHZvcvmR
なんか前にやろうとしてできなかった気がしたんだけど、今改めてGCCのマニュアル見たら-fprofile-generateつけて-fprofile-useつけるだけだった。
% perf stat ./direct
Performance counter stats for './direct':
121.760309 task-clock (msec) # 0.993 CPUs utilized
2 context-switches # 0.016 K/sec
0 cpu-migrations # 0.000 K/sec
42 page-faults # 0.345 K/sec
353933863 cycles # 2.907 GHz
167429077 stalled-cycles-frontend # 47.31% frontend cycles idle
<not supported> stalled-cycles-backend
380553084 instructions # 1.08 insns per cycle
# 0.44 stalled cycles per insn
160104472 branches # 1314.915 M/sec
7542 branch-misses # 0.00% of all branches
0.122630111 seconds time elapsed
0000000000400526 <main>:
400526: 48 8b 0d 33 0b 20 00 mov 0x200b33(%rip),%rcx # 601060 <prog.1832>
40052d: 48 89 ca mov %rcx,%rdx
400530: be 80 96 98 00 mov $0x989680,%esi
400535: b8 68 10 60 00 mov $0x601068,%eax
40053a: eb 07 jmp 400543 <main+0x1d>
40053c: 48 8b 10 mov (%rax),%rdx
40053f: 48 8d 40 08 lea 0x8(%rax),%rax
400543: ff e2 jmpq *%rdx
400545: 48 8b 10 mov (%rax),%rdx
400548: 48 8d 40 08 lea 0x8(%rax),%rax
40054c: eb f5 jmp 400543 <main+0x1d>
40054e: 48 8b 10 mov (%rax),%rdx
400551: 48 8d 40 08 lea 0x8(%rax),%rax
400555: eb ec jmp 400543 <main+0x1d>
400557: 48 8b 10 mov (%rax),%rdx
40055a: 48 8d 40 08 lea 0x8(%rax),%rax
40055e: eb e3 jmp 400543 <main+0x1d>
400560: 48 8b 10 mov (%rax),%rdx
400563: 48 8d 40 08 lea 0x8(%rax),%rax
400567: eb da jmp 400543 <main+0x1d>
400569: 85 f6 test %esi,%esi
40056b: 7e 0d jle 40057a <main+0x54>
40056d: 83 ee 01 sub $0x1,%esi
400570: 48 89 ca mov %rcx,%rdx
400573: b8 68 10 60 00 mov $0x601068,%eax
400578: eb c9 jmp 400543 <main+0x1d>
40057a: 48 83 ec 08 sub $0x8,%rsp
40057e: bf 00 00 00 00 mov $0x0,%edi
400583: e8 88 fe ff ff callq 400410 <exit@plt>
400588: 0f 1f 84 00 00 00 00 nopl 0x0(%rax,%rax,1)
40058f: 00
あんまかわりませんね。
ちなみに-O3だと以下のような調子なので、最適化レベルを上げると意味がある模様。
% gcc -O3 -fomit-frame-pointer direct.c -o direct
direct.c:4:1: warning: return type defaults to 'int' [-Wimplicit-int]
main()
^
direct.c: In function 'main':
direct.c:32:3: warning: implicit declaration of function 'exit' [-Wimplicit-function-declaration]
exit(0);
^
direct.c:32:3: warning: incompatible implicit declaration of built-in function 'exit'
direct.c:32:3: note: include '<stdlib.h>' or provide a declaration of 'exit'
# 1471360659 0:17:39 naruse@tk2-243-31075:~/threading
% perf stat ./direct
Performance counter stats for './direct':
46.157782 task-clock (msec) # 0.980 CPUs utilized
0 context-switches # 0.000 K/sec
0 cpu-migrations # 0.000 K/sec
41 page-faults # 0.888 K/sec
135493298 cycles # 2.935 GHz
49319786 stalled-cycles-frontend # 36.40% frontend cycles idle
<not supported> stalled-cycles-backend
320446132 instructions # 2.37 insns per cycle
# 0.15 stalled cycles per insn
110085385 branches # 2384.980 M/sec
6551 branch-misses # 0.01% of all branches
0.047097047 seconds time elapsed
0000000000400430 <main>:
400430: 48 8b 35 29 0c 20 00 mov 0x200c29(%rip),%rsi # 601060 <prog.1832>
400437: b9 80 96 98 00 mov $0x989680,%ecx
40043c: b8 68 10 60 00 mov $0x601068,%eax
400441: ff e6 jmpq *%rsi
400443: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)
400448: 85 c9 test %ecx,%ecx
40044a: 7e 64 jle 4004b0 <main+0x80>
40044c: 83 e9 01 sub $0x1,%ecx
40044f: b8 68 10 60 00 mov $0x601068,%eax
400454: ff e6 jmpq *%rsi
400456: 66 2e 0f 1f 84 00 00 nopw %cs:0x0(%rax,%rax,1)
40045d: 00 00 00
400460: 48 8b 10 mov (%rax),%rdx
400463: 48 83 c0 08 add $0x8,%rax
400467: ff e2 jmpq *%rdx
400469: 0f 1f 80 00 00 00 00 nopl 0x0(%rax)
400470: 48 8b 10 mov (%rax),%rdx
400473: 48 83 c0 08 add $0x8,%rax
400477: ff e2 jmpq *%rdx
400479: 0f 1f 80 00 00 00 00 nopl 0x0(%rax)
400480: 48 8b 10 mov (%rax),%rdx
400483: 48 83 c0 08 add $0x8,%rax
400487: ff e2 jmpq *%rdx
400489: 0f 1f 80 00 00 00 00 nopl 0x0(%rax)
400490: 48 8b 10 mov (%rax),%rdx
400493: 48 83 c0 08 add $0x8,%rax
400497: ff e2 jmpq *%rdx
400499: 0f 1f 80 00 00 00 00 nopl 0x0(%rax)
4004a0: 48 8b 10 mov (%rax),%rdx
4004a3: 48 83 c0 08 add $0x8,%rax
4004a7: ff e2 jmpq *%rdx
4004a9: 0f 1f 80 00 00 00 00 nopl 0x0(%rax)
4004b0: 48 83 ec 08 sub $0x8,%rsp
4004b4: 31 ff xor %edi,%edi
4004b6: e8 55 ff ff ff callq 400410 <exit@plt>
4004bb: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)
% gcc -O3 -fprofile-use -fomit-frame-pointer direct.c -o direct
direct.c:4:1: warning: return type defaults to 'int' [-Wimplicit-int]
main()
^
direct.c: In function 'main':
direct.c:32:3: warning: implicit declaration of function 'exit' [-Wimplicit-function-declaration]
exit(0);
^
direct.c:32:3: warning: incompatible implicit declaration of built-in function 'exit'
direct.c:32:3: note: include '<stdlib.h>' or provide a declaration of 'exit'
# 1471360636 0:17:16 naruse@tk2-243-31075:~/threading
% perf stat ./direct
Performance counter stats for './direct':
46.108716 task-clock (msec) # 0.981 CPUs utilized
0 context-switches # 0.000 K/sec
0 cpu-migrations # 0.000 K/sec
41 page-faults # 0.889 K/sec
123812228 cycles # 2.685 GHz
39859092 stalled-cycles-frontend # 32.19% frontend cycles idle
<not supported> stalled-cycles-backend
320466395 instructions # 2.59 insns per cycle
# 0.12 stalled cycles per insn
110090077 branches # 2387.620 M/sec
6079 branch-misses # 0.01% of all branches
0.046992565 seconds time elapsed
0000000000400430 <main>:
400430: 48 8b 0d 29 0c 20 00 mov 0x200c29(%rip),%rcx # 601060 <prog.1832>
400437: be 80 96 98 00 mov $0x989680,%esi
40043c: b8 68 10 60 00 mov $0x601068,%eax
400441: ff e1 jmpq *%rcx
400443: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)
400448: 48 8b 10 mov (%rax),%rdx
40044b: 48 83 c0 08 add $0x8,%rax
40044f: ff e2 jmpq *%rdx
400451: 0f 1f 80 00 00 00 00 nopl 0x0(%rax)
400458: 4c 8b 18 mov (%rax),%r11
40045b: 48 83 c0 08 add $0x8,%rax
40045f: 41 ff e3 jmpq *%r11
400462: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1)
400468: 85 f6 test %esi,%esi
40046a: 7e 3e jle 4004aa <main+0x7a>
40046c: 83 ee 01 sub $0x1,%esi
40046f: b8 68 10 60 00 mov $0x601068,%eax
400474: ff e1 jmpq *%rcx
400476: 66 2e 0f 1f 84 00 00 nopw %cs:0x0(%rax,%rax,1)
40047d: 00 00 00
400480: 4c 8b 00 mov (%rax),%r8
400483: 48 83 c0 08 add $0x8,%rax
400487: 41 ff e0 jmpq *%r8
40048a: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1)
400490: 4c 8b 08 mov (%rax),%r9
400493: 48 83 c0 08 add $0x8,%rax
400497: 41 ff e1 jmpq *%r9
40049a: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1)
4004a0: 4c 8b 10 mov (%rax),%r10
4004a3: 48 83 c0 08 add $0x8,%rax
4004a7: 41 ff e2 jmpq *%r10
4004aa: 50 push %rax
4004ab: 31 ff xor %edi,%edi
4004ad: e8 5e ff ff ff callq 400410 <exit@plt>
4004b2: 66 2e 0f 1f 84 00 00 nopw %cs:0x0(%rax,%rax,1)
4004b9: 00 00 00
4004bc: 0f 1f 40 00 nopl 0x0(%rax)
