HackMD
Design of a High Performance Branch Predictor Based on Global History Considering Hardware Cost
Abstract
- 分支預測(Branch prediction)是提高效能的關鍵技術
- CPU 執行時，分支佔所有指令的 20~30%
- 基於 global history 的動態分支預測結構簡單，占用的內存少，但有 index aliasing 的問題
- 本文對分支預測改進，將預測生成的 index 和指令 PC 位址最後 8-bits 做 XOR，緩解 index aliasing 的問題
- 使用 simplescalar 3.0 模擬
- 實驗表明，GHR 為 12 時，改進的分支預測器效果最好，平均比原本的高出 1.93%
Introduction
- 以一般 MIPS 架構的 five-level pipeline 為例，如果沒有分支預測，在遇到分支指令時可能導致 pipeline 中所有指令都被清除
- 分支預測分為靜態和動態
- 靜態的通常預測率較低
- 基於全局歷史寄存器（GHR）的動態分支預測器使用移位的分支歷史寄存器記錄第一級最近 n 條指令的執行情況，並使用具有四個狀態值的模式歷史表（PHT）來預測分支的跳轉方向二級指令
- 因為 GHR 寬度有限，不同指令可能有相同的 GHR，導致預測率下降
- 本文目標是改進 Gselect 類型的分支預測器
Shortages of Several Classical Dynamic Branch Predictors
Branch Predictor Based on 1-bit Saturation Counter
- 用 1-bit 來紀錄上次有沒有跳轉
- 如果一直預測成功就永遠不會改變狀態
- 如果預測結果頻繁改變效果就會很差，實務上沒有過這種作法
Branch Predictor Based on 2-bit Saturation Counter
- 用 2-bits 紀錄前兩次有沒有跳轉
- 變成四種狀態的狀態機，概念和上面的基本一樣
One-Level Branch Predictor
- 用一部分的 PC 值當作 index 去找 PHT
- 第一個問題是不同 PC 會有同樣的 index
- 第二個問題是某些狀況之下預測率會很低
Two-level branch predictor
- 有三個 PHT
- 用 Choice-PHT 決定要用哪張 PHT
- 只改變 Choice-PHT
- 硬體成本高
- 看不太懂= =
Hybird and Neural Network Predictor
- 結合多個預測器
- 延遲高，需要時間訓練
- 硬體成本也高
New Scheme Proposal
- Gselect 分支預測器使用 PC 高位和 GHR 低位當作 PHT 的 index，而沒使用 PC 低位
- 因為沒辦法準確區分沒使用到的 PC，導致 Gselect 預測率下降
- 為了充分使用 PC，本文將 Gselect 分支預測器生成的 index 和 PC 低位 8-bits XOR
- 假設 PC 和 GHR 為 16-bits，Gselect 將 PC 的高 8 位和 GHR 的低 8 位合併得到 index；然後我們再將 PC 的低 8 位和結果做 XOR
- 只影響結果的低 8 位
- 一個 Gselect 會重複 index 但 XOR 不會的例子
| Index Name | Value | Gselect | XOR-Gselect |
|---|---|---|---|
| PC1 | 1010001111001111 | 1010001110101010 | 1010001101100101 |
| GHR1 | 0011110010101010 | ||
| PC2 | 1010001100000001 | 1010001110101010 | 1010001110101011 |
| GHR2 | 1010111110101010 |
- 無法證明 XOR 有更好的表現，因此使用 simplescalar 執行一堆指令來判斷效能
Experimental Environment and Results
Experimental Environment
- 使用 SimpleScalar 3.0 sim-bpred 模擬，並使用 Gselect, Bimode 比較
Experimental Results
- GHR 的長度會影響預測的成功率，因此這會是我們需要研究的因素之一
- 長度為 12 的時候飽和
- PC 低位使用的數量也會影響結果(for XOR)
- 根據上面的結果，GHR 長度使用 12，並和 Bimode, Gselect 比較的結果
- 平均比 Gselect 好 1.93%，但比 Bimode 差
- Bimode 的硬體成本高，因此輸了很正常
Conclusion
- 使用 XOR-Gselect 改善 index aliasing 的問題
- 實驗表明 GHR 長度為 12 時效果最好，並且 XOR 能改善 Gselect 的預測率
