体系ガイド · 基礎から応用へ

分岐予測と誤予測のコスト

真の割合が等しい三つの入力列を比べ、説明用の費用計算、生成命令の確認、時間とカウンタの区別を身に付けます。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 条件が決まる前に先を読む
  2. 真の割合が同じ三つの列を用意する
  3. 説明用の式へ数を代入する
  4. 測定前に分岐が残っているかを読む
  5. 測る範囲と取得できない数を残す
  6. 分岐を減らす変更にも費用がある
  7. 同じ分岐の入力を揃える意味
  8. 割合と履歴を区別する課題
  9. この記事をロゲイアに質問する理解を確かめる

条件が決まる前に先を読む

CPUが条件分岐へ来たとき、その条件の答えはまだ計算中かもしれません。答えが出るまで命令の取込みを止めると、後ろの実行器まで仕事が届かなくなります。分岐予測は、次に進む側や飛び先を予想して、先の命令を取り込む仕組みです。予想が外れれば、誤った経路の仕事を破棄して正しい場所からやり直します。前提はパイプラインと、実行完了とリタイアの違いです。プログラムから見える計算結果の正しさと、投機の途中で使う回路の動作を分けて考えます。

分岐には、条件が真になるかだけでなく、どこへ飛ぶかという問いもあります。このガイドの主題は、同じ条件分岐を繰り返すときの真偽の並びです。関数呼出しの飛び先や戻り番地にも予測の仕組みがありますが、それらの全てを一つの「当たる割合」へまとめません。CPUの公式資料は、対象の分岐の種類と実行環境を確かめながら読みます。ここで予測器の内部構造を特定せず、観測した履歴から言える範囲を明確にします。

真の割合が同じ三つの列を用意する

値が0か1の配列を用意し、1のときに3、0のときに5を合計へ足す処理を考えます。要素数を1,048,576とし、半分を0、半分を1に揃えます。整列した列では前半を0、後半を1にします。交互の列は0、1を繰り返します。無作為順の列は、同じ個数の0と1を固定seedで並べ替えます。どれも真になる割合は50%で、合計は4,194,304です。入力を揃えず真の割合だけを変えると、分岐の後で実行する仕事の量まで変わる可能性があります。

この三つは、真の割合が等しくても、履歴から次を予想する難しさが同じとは限らない例です。特に交互の列を必ず最悪と決めないでください。複雑な予測器は、直前の一回だけではなく履歴の規則を利用する場合があります。一ビットの説明用予測器なら交互列に弱くても、その結果は現代CPUの保証ではありません。また固定seedは入力を再現するための条件であり、暗号用途の乱数の品質を示すものではありません。

説明用の式へ数を代入する

命令列の基礎費用が1要素あたり2サイクル、対象の分岐を1要素に1回実行し、誤予測1回につき追加12サイクルを払う模型を考えます。誤予測率をpとすると、平均は2+12pサイクルです。p=0.01なら2.12、p=0.5なら8です。要素数を掛ければ、この模型での合計サイクルになります。12という数も、二つの率も説明用に置いた値で、今回の環境の実測値ではありません。分岐の回数を掛け忘れると、分岐の少ない仕事と多い仕事を同じ式で比べてしまいます。

実CPUでは、複数の命令の重なり、条件を計算する長さ、誤った経路で行った読取り、別のボトルネックなどが関係します。全プログラムの時間へ、模型の追加費用をそのまま足せるとは限りません。表は、誤予測率を改善しても基礎費用は残るという判断に使います。50%から1%へ減ったから全体が50倍になる、という読み方は誤りです。観測した時間から逆算してpを実測したと呼ぶこともできません。pを測るなら、対応するイベントのカウンタを別に取得します。

仮定した誤予測率計算模型の費用
1%2+12×0.012.12 cycle/要素
50%2+12×0.58 cycle/要素

測定前に分岐が残っているかを読む

Cでifを書いても、バイナリに同じ条件分岐が残るとは限りません。コンパイラが条件付き移動、算術、SIMDの比較へ変えることがあります。逆アセンブルで対象の関数を開き、データの値を比較した後に、どの命令で別の経路へ進むかを確認します。ループ末尾の繰り返し判定を見つけただけでは、データ依存の分岐を確認したことになりません。関数名の後へ定数伝播などの接尾辞が付く場合もあるので、呼出し先の実際の名前を追います。

付属実験はGCCでif変換とベクトル化を止める設定を使い、分岐を観察する条件を作ります。これは最速の実装を選ぶための推奨設定ではありません。通常の最適化を有効にした版も比較するなら、設定とバイナリを分けて保存してください。ソースが同じという理由で、異なる設定の時間とカウンタを一つの記録へ混ぜないようにします。結果の合計も確かめ、仕事全体が消えていないかを確認します。値をvolatileへ置けば全て解決するわけでもなく、余計なメモリアクセスを測る場合があります。

測る範囲と取得できない数を残す

入力の生成と並べ替えは計測の前に済ませ、配列を読む区間を測ります。整列の時間を含めてしまうと、アプリが既に持つ整列データを使う場合と、わざわざ整列させる場合の比較が混ざります。各列を複数回実行し、初回、繰り返し、全標本、中央値を残します。最速の一回だけを採用すると、割込みや実行待ちを隠してしまいます。並べ替えで結果が変わらないことを先にassertし、測定後にも同じ合計が得られたことを確認します。

PMUへアクセスできる環境なら、対象CPUに対応する分岐・誤予測イベントを調べ、取得区間と多重化の有無も記録します。今回の仮想環境の時間測定では、PMUの値は取得していません。速い列と遅い列があったとしても、その差の全てが誤予測だったとは書けません。命令数やメモリの状態、周波数、ほかの仕事の影響もあります。同じ入力を使った再現可能な時間差と、原因を確定するための追加観測を分けることが、この段階での正確な結論です。

分岐を減らす変更にも費用がある

条件をなくすため両方の計算を実行し、最後に値を選ぶ方法が有利なことがあります。しかし一方が高価な関数なら、毎回両方を実行する費用が増えます。メモリの読取りや例外、外部への出力を伴う処理では、もともと選ばれなかった側まで実行してよいかも確認が必要です。条件分岐の削除だけを目的に、仕様を変えないでください。配列を整列すれば予測しやすくなる場合も、整列費用と元の順序を必要とする処理を含めて判断します。

同じ真の割合でも、複数の分岐が同じ履歴を利用する場合や、条件の答えが遅く届く場合には結果が違います。少数データがキャッシュへ収まる場合と、大きなデータを主記憶から読む場合でも、支配的な待ちは変わります。「分岐があるから遅い」という説明を、どの命令が、どんな入力列で、何を待ったのかへ言い換えましょう。最適化の候補を試すときは、変えた条件を一つに絞り、出力、生成命令、計測区間の三つを比較してから採用します。

同じ分岐の入力を揃える意味

真の個数が同じでも、条件が真の側で外部関数を呼び、偽の側で単純な加算だけを行う処理へ変えると、生成命令と費用の構造が変わります。元の三列の比較と同じ実験として標本を混ぜません。さらに、配列を走査せず真の件数だけから合計を計算できるなら、アプリの最速実装は別のアルゴリズムになるかもしれません。この教材では分岐を観察するため全要素を読む契約を保っています。性能の診断用に機構を分ける実験と、問題全体を最短で解く競争は、入力が同じでも評価する対象が違います。どの問いのために条件を制限したかを結果と一緒に残してください。

どの仮定を変えたかが分かれば、結果の差を次の検査へつなげられます。

割合と履歴を区別する課題

課題は、同じ50%の真を持つ交互列と無作為列について、「誤予測率は必ず同じ」と言えるかを説明することです。解答は言えません。割合は真の個数を表しますが、予測は過去の並びも利用し得ます。一ビット予測器なら、交互列で毎回外れるような模型を作れますが、その模型を使った計算と実CPUの観測は別です。実測の課題では、同じバイナリで両列の合計を確認し、時間と取得可能なイベントを別に記録します。

追加課題として、模型の誤予測率を1%のまま、基礎費用だけを20サイクルへ変えてください。解答は20+12×0.01=20.12です。50%なら26ですから、予測改善の全体への割合は基礎費用2の場合より小さくなります。条件の前後にある仕事も含めて判断する必要があるためです。この二つの課題を説明できたら、分岐データの実験へ進み、実際の比較と条件付きジャンプを探してください。予測器の構造を未測定のまま言い当てることは、この教材の合格条件ではありません。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 7

AI基盤へ進む · STEP 4

学習コースから次を選ぶ