|
|
分岐予測
|
|
|
========
|
|
|
|
|
|
分岐予測とは、「(1)分岐命令であるか」「(2)分岐命令であれば、その飛び先」「(3)条件分岐であるか」「(4)条件分岐命令であれば、そもそも条件が成立するか」の四つを予測するものです((3)は必須ではありません[^1])。
|
|
|
|
|
|
この中では(1)(2)が重要な部分です。
|
|
|
(4)のみを分岐予測器と呼ぶことが多いですが、それよりも(1)(2)の方がはるかに重要です。
|
|
|
以下では区別するために(4)を「分岐方向予測器」と呼ぶことにします。
|
|
|
遅延分岐を使うことで(1)(2)を不要とできますが、遅延分岐は過去の遺物です。忘れましょう。
|
|
|
|
|
|
(1)(2)(3)の予測を行うためには、分岐先バッファ(branch target buffer, BTB)というハードウェアが用いられます。
|
|
|
分岐先バッファは、ある種のキャッシュ[^2]です。
|
|
|
キャッシュにアクセスする際のアドレスは分岐命令のPC、キャッシュの内容は分岐命令の飛び先と条件分岐かを示すビットです。
|
|
|
分岐先バッファには、分岐命令を初めてデコードしたときや実行したとき[^3]に情報を書き込んでおきます。
|
|
|
こうすることで、次回以降同じPCに出会ったときに予測を行うことができます。
|
|
|
|
|
|
### なぜ分岐先バッファが必要なのか
|
|
|
|
|
|
普通の五段パイプラインで考えてみます。
|
|
|
分岐先バッファがなければ、フェッチしてデコードするまで分岐命令であることが分かりません。
|
|
|
したがって、分岐命令をデコードしているサイクルでフェッチされた命令は破棄しなければいけません。
|
|
|
つまり最低1 cycleのペナルティが生じます。
|
|
|
分岐先バッファがあれば、フェッチと並行して分岐であることが分かるため、その次のサイクルのフェッチは分岐先の命令をフェッチすることができます。
|
|
|
|
|
|
### 予測方法
|
|
|
|
|
|
分岐先バッファを用いた予測は、以下のように行います。
|
|
|
|
|
|
1. フェッチしようとしているPCをアドレスとして、分岐先バッファにアクセスする。
|
|
|
1. キャッシュヒットすれば、その命令は分岐命令であることがほぼ確実である[^4]。
|
|
|
* 読み出された「条件分岐か否か」ビットを見て以下の判断を行う。
|
|
|
* 条件分岐でない(無条件分岐である)なら、読み出された飛び先(前回の飛び先)に、今回も飛ぶと予測する。
|
|
|
* 間接分岐(`RET`、`JR`、`JALR`)であれば本当にそうとは限らないが、他に情報がないのでそう予測するしかない(「次のPCはPC+4」と予測するよりはまし)[^5]。
|
|
|
* 条件分岐であるなら、分岐方向予測器に問い合わせる[^6]。
|
|
|
* 分岐方向予測器に問い合わせて、「条件成立」と予測されたのなら、読み出された飛び先(前回の飛び先)に、今回も飛ぶと予測する。
|
|
|
* 分岐方向予測器に問い合わせて、「条件不成立」と予測されたのなら、「次のPCはPC+4」と予測する。
|
|
|
1. キャッシュヒットしなければ、以下のパターンのいずれかである。
|
|
|
* いずれにせよ情報がないので、「次のPCはPC+4」と予測する以外ない。
|
|
|
* そもそも分岐命令ではない。
|
|
|
* 初見の分岐命令である。
|
|
|
* すごく昔に見たことがある分岐命令であるが、キャッシュから追い出されてしまった。
|
|
|
|
|
|
### 分岐方向予測器
|
|
|
|
|
|
有名どころの分岐方向予測器と、ググる時のキーワードを羅列しておきます。
|
|
|
|
|
|
* 静的予測
|
|
|
* 常に分岐しないと予測:正答率は30%くらい[1]
|
|
|
* 常に分岐すると予測:正答率は70%くらい[1]
|
|
|
* Forward not-taken, backward taken (FNBT)分岐予測:後方分岐の正答率は85%くらい
|
|
|
* 動的予測
|
|
|
* 2ビット飽和カウンタ(2-bit saturating counter)分岐予測器(Bimodal分岐予測器)
|
|
|
* ローカル履歴(local history)二レベル適応型(two-level adaptive branch prediction)分岐予測器
|
|
|
* Pattern history table (PHT) と branch history table (BHT)
|
|
|
* GAsと呼ばれる構成が最適[2]
|
|
|
* グローバル履歴(global history)二レベル適応型分岐予測器
|
|
|
* PAsと呼ばれる構成が最適[2]
|
|
|
* gshareと比較する意味でgselectと呼ばれることも
|
|
|
* gshare分岐予測器
|
|
|
* その他の高度な分岐予測器
|
|
|
* agree分岐予測器
|
|
|
* bi-mode分岐予測器
|
|
|
* gskew分岐予測器
|
|
|
* YAGS分岐予測器
|
|
|
* perceptron分岐予測器
|
|
|
* TAGE分岐予測器
|
|
|
|
|
|
### 参考文献
|
|
|
|
|
|
* [1] 「命令レベル並列処理-プロセッサアーキテクチャとコンパイラ」安藤秀樹著 コロナ社 2005年出版
|
|
|
* [2] "A Comparison of Dynamic Branch Predictions that use Two Levels of Branch History", Tse-Yu yehand Yale N. Patt, ACM SIGARCH Computer Architecture News, Volume 21 Issue 2, pp.257-266, 1993. http://www.eecs.harvard.edu/cs146-246/p257-yeh.pdf
|
|
|
|
|
|
---
|
|
|
[^1]: 無条件分岐についての情報を分岐方向予測器に学習させるのはやや無駄が多い。
|
|
|
[^2]: キャッシュメモリとの混同に注意。キャッシュとは、データのコピーを持つことで局所性を利用して高速化する技術一般のことである。キャッシュメモリと同様、高速小容量、タグがある、置換が行われる、局所性を利用している、などの特徴を持つ。しかし、何か具体的な「元データ」のようなものがあってそれのコピーを保存しているとは限らない。計算結果を再利用に備えて保存しておくというタイプのキャッシュも存在する。分岐先バッファもそのタイプで、デコード・実行した結果をメモしてあるだけである。
|
|
|
[^3]: 近年の商用プロセッサでは、条件分岐の場合は条件が成立したときのみ分岐先バッファに書き込むらしい(論文:https://ieeexplore.ieee.org/document/9408197 )。絶対に成立しない分岐命令 (例えば配列外アクセスであるかを検査する分岐命令など。never-taken branch)のために分岐先バッファの容量が使われることがなるという利益がある。
|
|
|
[^4]: 分岐先バッファはキャッシュだが、タグを全部は持たないというハードウェア容量ケチり最適化がある。その最適化をした場合、分岐先バッファは嘘を言うことがある。予測を間違えてもどうせ分岐予測失敗対策のハードウェアが存在するので問題ないという思想である。そもそも、プログラムが変化すれば「このPCの命令は以前分岐命令だったから、今回もそのはず」というのは成り立たないから、分岐先バッファを全面的に信用することはできない。
|
|
|
[^5]: 商用プロセッサではという飛び先が動的に変化する分岐命令専用の分岐予測器(間接分岐予測器)が使われることもある。またリターン命令はコール命令がフェッチされたのを見張っておけば十分予測可能である(リターンアドレススタックと呼ばれる技術。その場合、分岐先バッファに「コール命令か」「リターン命令か」フラグも入れたほうが良い)。
|
|
|
[^6]: 特に直列化する理由はないので、分岐先バッファに問い合わせるのと並列に分岐方向予測器にも問い合わせておけば遅延が減る。分岐先バッファに問い合わせた結果条件分岐でないと判明した場合は、分岐方向予測器の答えを単に捨てればよい。 |
|
|
\ No newline at end of file |