近年のほとんどのプロセッサには分岐予測機構が搭載されています。 分岐予測機構は、この命令は分岐命令か否か、分岐命令だとしたらとび先はどこか、条件分岐ならそれが成立するかしないか、などを予測します。 予測が外れていた場合、正しい命令のフェッチからやり直しになり、パイプラインが埋まるまでには時間がかかります。 このパイプラインが埋まるまでにかかる時間を分岐予測ミスペナルティとします。
実験環境
実験1: リターンアドレスを破壊してみる
以下に示した実験コードでは、スタックに保存されているリターンアドレスを勝手に書き替えています。 リターン命令で戻る先を関数コール命令の次ではないところにすることで、分岐予測を外します。
main:
push rax
mov rcx, 1000000000
call f
pop rax
ret
f:
sub rcx, 1
jz L1
sub QWORD PTR[rsp], 5
L1:
ret
これを実行するのにかかった時間は10.8秒ほどでした。 3.1GHzで動いていることから、33G cycleほどかかったことがわかります。 1G回ループを実行していることから、分岐予測ミスペナルティは最大で33 cycle程度ということになります。
実際の分岐予測ミスペナルティは、ループの中にcall, sub, retといったメモリに触る命令があるため解析が難しいです。 メモリアクセスには4cycleかかるとし、メモリを介した依存が正しく予測されているとすれば、callのストアに4cycle、subのロードに4cycle、subの演算に1cycle、subのストアに4cycle、retのロードに4cycle、で分岐予測ミスペナルティ以外に17cycleかかることになります。よって、分岐予測ミスペナルティ自体は16cycleということになります。
実験2: 疑似乱数を用いて方向予測器を外してみる
以下に示した実験コードでは、疑似乱数（64bitのxorshift）の下1bitを使った条件分岐があります。 成立しても成立しなくても結局同じとび先なのですが、正しく予測できなければ分岐予測ミス扱いとなり、ペナルティが発生します。 疑似乱数の下1bitを予測することは難しいので、50%の確率で分岐予測ミスが発生します。
main:
mov rcx, 2000000000
mov rax, 1
L0:
test eax, 1
je L1
L1:
mov rdx, rax
shl rdx, 7
xor rdx, rax
mov rax, rdx
shr rax, 9
xor rax, rdx
sub rcx, 1
jne L0
ret
このコードを実行すると、8.45秒ほどかかりました。 3.1GHzで動いていることから、プログラムの実行に26G cycleかかったことになります。
mov rax, 1の部分をmov rax, 0に変更すると、xorshiftの計算自体は行われるものの常に0が出力され、分岐予測が当たるようになります。
この場合には2.75秒かかりました。
3.1GHzで動いていることから、プログラムの実行に8G cycleかかったことになります。
ループ一周当たりのレイテンシが4cycleであり2G回のループであるため、予想通りの結果です。
これらの差分から、分岐予測ミスペナルティは合計で18G cycle程度であることがわかります。 分岐予測ミスが50%の確率で発生するので、分岐予測ミス回数は1G回です。 よって、分岐予測ミスペナルティは18 cycleということになります。
