- ブラウザURL入力
- DNS名前→IP
- ルータ経路選択
- ロードバランサ振り分け
- Nginx受け口
- アプリ処理今ここ
- DB保存
前回、パイプラインの流れを妨げる事情のひとつが「分岐で次の行き先が分からない」制御ハザードでした。今回はそれにどう対処しているかを見ます。
まず結論
if文に出会ったCPUは、条件の計算が終わるのを待たずに「たぶんこっち」と予測して先へ進みます。過去の傾向を記録しているので、当たる確率はかなり高くなります。
外したときは、先走って進めた分をすべて捨てて詰め直します。その損失はおよそ15〜20サイクル程度です。よく「数十サイクル」と書かれますが、実測値はそこまで大きくありません。
CPUが分岐予測を外したとき、間違って実行してしまった計算の結果はどうなるでしょうか。
当てることが目的ではありません。外した予測ほど記憶に残るので、直感で選んでください。
if文はパイプラインにとって困りもの
前回、パイプラインは命令を流れ作業で重ねると学びました。ところがここに困った命令があります。分岐命令、つまりif文やループです。
問題はこうです。if (x > 0) という命令をフェッチした時点では、xがいくつなのかまだ分かりません。xの比較は「実行」段で行われるので、それまで数サイクルかかります。しかしパイプラインは、その間にも次の命令を取ってこなければ流れが止まります。
ではどの命令を取ってくればいいのでしょうか。条件が成立したときの飛び先か、成立しなかったときの次の行か。分からないのです。
正直に待つという手もありますが、それではパイプラインが数サイクル空になります。分岐命令はプログラム全体の15〜30%を占めるので、毎回止まっていては話になりません。
そこで、先回りする
現代のCPUが採る戦略は単純です。とりあえず予測して、進んでしまう。
- ・投機実行の結果は確定するまで反映されないので、外れても計算結果は狂わない
- ・だから分岐予測は「正しさ」ではなく「速度」だけの問題
ここで最も大事な点を押さえてください。外れたときに失われるのは時間だけです。先走って計算した結果は、確定するまでどこにも書き込まれません。外れが判明した時点で、なかったことにして捨てます。
つまり分岐予測は、間違えてもプログラムの結果は正しいのです。
分岐予測が外れると、プログラムの計算結果はどうなりますか。
どうやって「たぶんこっち」を決めるのか
予測といっても、当てずっぽうではありません。過去にその分岐がどちらへ進んだかを記録して、そのパターンから判断します。
たとえば1000回まわるループを考えてください。ループの終わりにある「まだ続けるか?」という分岐は、**999回は「続ける」で、最後の1回だけ「抜ける」**です。履歴を見ていれば、ほぼ確実に当てられます。
現代のCPUはもっと凝った仕組みを使っています。TAGEと呼ばれる方式が代表的で、長さの違う複数の履歴を同時に記録し、最も一致する記録を選びます。「直前の3回」だけでなく「直前の数十回のパターン」まで見ることで、複雑な規則性も捉えます。
外したときの損失は、実は思ったほど大きくない
ここが本レッスンで一番伝えたい数字です。
CPU世代 予測ミスの損失Intel Skylake 以降 15〜20 サイクルAMD Zen 1〜3 約18 サイクル(平均)AMD Zen 4 15〜18 サイクルAMD Zen 5 15〜25 サイクルIntel Atom系 11〜13 サイクル─────────────────────────────────────────────(参考) Pentium 4 100サイクルを超えることも
おおむね15〜20サイクルです。ところが世の中の解説では「数十サイクル」という表現をよく見かけます。「数十」は20〜90程度を意味するので、実測値より大きく、上限側では4倍を超えて見積もった表現です。
なぜこの誇張が広まったのか。おそらくPentium 4時代の数字が引きずられています。Agner Fogによれば、Pentium 4では予測ミスからの回復に24サイクルを下回ることはまれで、時間のかかる命令が詰まっていると100サイクル以上になることもありました。その時代の印象が、世代が変わった後も残っているのでしょう。
「分岐予測を外すと数百サイクル失われます」という説明を見ました。どう判断すべきですか。
この章のまとめ
- 分岐命令は「次にどこへ行くか」が確定する前にフェッチされるので、パイプラインが困る。
- CPUは過去の履歴から予測して先へ進む(投機実行)。現代はTAGE系の予測器で長短の履歴パターンを併用する。
- 外れても計算結果は正しい。投機実行の結果は確定まで反映されず、破棄されるだけ。失うのは時間。
- 損失は15〜20サイクル程度。「数十サイクル」は実測より大きく見積もった表現で、Pentium 4時代の数字の引きずりと思われる。
- キャッシュミス(200〜400サイクル)とは桁が違う。混同すると性能問題の診断を誤る。
自分の現場で確かめる
読んだだけでは身につきません。手元の環境で実際に見てみてください。
理解度チェック
読んだ直後は「分かった」と感じやすいものです。実際に解いて確かめてください。
現代のCPUで分岐予測を外したときの損失は、おおよそどのくらいですか。
用語集(5語)
- 分岐命令
- 条件によって次に実行する場所を変える命令。if文・ループ・関数呼び出しなどが機械語ではこれになる。
- 分岐予測
- 条件の計算が終わる前に、過去の履歴から「たぶんこちらへ進む」と予測してパイプラインを進める仕組み。
- 投機実行
- 予測に基づいて先へ進めること。結果は確定するまで反映されず、予測が外れれば破棄される。
- パイプラインフラッシュ
- 予測が外れたとき、先走って進めた処理をすべて捨ててパイプラインを詰め直すこと。これが15〜20サイクルの損失になる。
- MPKI
- 1000命令あたりの予測ミス数。分岐予測器の性能を測る指標。研究では「正解率%」ではなくこちらが使われる。