概要
POSTDの分岐予測の簡単な歴史 – Part 1を読んで、CPUの分岐予測について学習しています。
見出し「予測は成立」配下には、以下のように記載されています。
全ての分岐が成立すると予測した場合、恐らく70％前後の精度が得られることになります。その場合、分岐の30％に対しては、誤予測のコストが必要になり、平均1命令あたり
(0.8 + 0.7 * 0.2) * 1 + 0.3 * 0.2 * 20 = 0.94 + 1.2. = 2.14のコストを支払わなければなりません。
最初読んだとき、平均1命令あたりのコストの計算式が理解できませんでした。各数値はそれぞれ何を表しているのか分からなかったのです。
1個ずつ数値が何かを考えることで、式の意味をようやく理解することができました。その覚え書きをQiitaに残します。
平均1命令あたりのコストの計算式
(0.8 + 0.7 * 0.2) * 1 + 0.3 * 0.2 * 20
まずは左項と右項で分けて考えます。
左項
(0.8 + 0.7 * 0.2) * 1
= (0.8 * 1) + (0.7 * 0.2 * 1)
-
0.8：一般的なベンチマークから算出した分岐以外の処理の確率80% -
0.7：正しく分岐が予測される確率70% -
1：正しく予測された分岐に必要なサイクル数
右項
0.3 * 0.2 * 20
-
0.3：誤予測の確率30% -
0.2：一般的なベンチマークから算出した分岐処理の確率20% -
20：予測しない、または予測を誤った分岐に必要なサイクル数
まとめ
以下の計算式は3つの項で成り立っていると考えれば、理解できました。
(0.8 + 0.7 * 0.2) * 1 + 0.3 * 0.2 * 20
= 0.8 * 1 + 0.2 * (0.7 * 1 + 0.3 * 20)
= 0.8 * 1 + 0.2 * 0.7 * 1 + 0.2 * 0.3 * 20
- 分岐以外の処理に必要なサイクル数:
0.8 * 1 - 正しく予測された分岐に必要なサイクル数:
0.2 * 0.7 * 1 - 予測を誤った分岐に必要なサイクル数:
0.2 * 0.3 * 1