適用於高效能處理器的分支預測方法之研究

Abstract

分支預測是新一代中央處理器一項重要的機制, 它是一種有效解決控 制權危障的方法,其功能是在擷取指令的同時預測正被擷取的指令是否會 導致控制權轉移. 有了它可使指令的擷取率維持在所需的水準, 管線中的 指令流也較平順, 因此能使執行效能提高. 而且現在許多中央處理器為了 更提昇效能, 具備某程度推測性執行的能力, 這也需要高正確性的分支預 測機制作其依據. 本論文對許多典型的分支預測法做特性探討, 並針 對目前動分支預測法的熱機懲罰提出改進分支預測正確率的分法, 可以提 昇處理器的效能. 我們提出一種稱為自調適混合演算法的構想, 它結合一 個高準確率的分支預測法及另一個具有短暫啟動時間的預測法, 在頻繁的 工作切換下仍維持高預測正確率. 另外我們還提出一種有彈性的分支歷史 表的設計,可以將部份分支歷史表所佔空間移到處理器晶粒外, 同時提昇 分支資訊的擊中率. 我們的實驗結果證實了我們方法的可行性. Branch Prediction is an important mechanism of the new generation of CPU. It is an effective method for resolving control hazard. Its function is pre-dicting whether the instruction being fetched will cause the control transferof processor. Using this mechanism can achieve the instruction fetch rate meets the requirement, and keep the instruction stream in the pipeline smoo-thly. Hence branch prediction can enhance the execution performance. Moreover,for further enhancing the processor performance many CPUs equip some level ofspeculative execution that also need a high accurate branch prediction mecha-nism. In this thesis, we evaluate many typical branch prediction schemes, andpropose a new mechanism to enhance the prediction accuracy based on the warm-up penalty of dynamic predictors. We propose one method called Self- AdaptiveCombination algorithm that combines a highly accurate predictor with anotherpredictor which has shortest warm-up time. This scheme will retain high pre-diction accuracy under the environment with frequent context switching. Fur-ther we suggest an flexible design of branch history table that can enhancethe hit rate and reduce the area occupied by the branch history table in theCPU die. Our simulation results verify the feasibility of these mechanismsmentioned above.