具有相關暫存器緩衝區之分支預測

Abstract

對於現今的超純量管線處理器而言，分支指令一直是個執行能力上的瓶頸，因為分支指令會中斷管線中指令流的穩定進行。為了解決這個問題，最近幾年來各種分支預測的機制被提出來，從最簡單的使用2位元計數器紀錄分支預測的結果（bimod predictor），或用兩層式的架構來記錄追蹤鄰近分支指令間的相關性(2-level adaptive predictor)，以及使用較複雜的混合預測機制(combination predictor)，將前兩種不同的預測機制整合在一起並使用一個計數表機制來判斷應該使用哪一種機制的預測結果，這三種是在學產業界最常被使用到的分支預測機制。在分支指令中，相關暫存器的值經常會影響其執行結果，因此如果能利用相關暫存器的資訊來作為分支預測的參考，我們可以更準確的做出預測。 在這篇論文中，我們提出了一個新的分支預測輔助機制來提昇原來分支預測機制的準確度。我們在原來所使用分支預測機制中加入一移位暫存器來記錄三個連續的執行指令以便找出相關的暫存器名稱。並延伸了傳統的分支目的緩衝器架構以記錄每一個分支指令的相關暫存器為何，這項資訊會被用來指出暫存器檔案中哪些暫存器會被參考到。此外我們加入一個歷史緩衝區，在分支預測錯誤時我們將會相關暫存器值和分支指令位址作雜湊運算後當作索引將分支指令結果存入緩衝區，因此下次當同樣的分支指令再執行時，會將相關暫存器的值和分支位址雜湊運算後當作索引存取緩衝區的資料，如果該索引的值存在，表示之前原來分支預測單元曾經預測錯誤，這一次也可能是錯誤的，因此我們便使用該值當作我們的預測結果。 在這篇論文中我們是用SimpleScalar工具來模擬我們的設計。我們將提出的架構與三個基本的分支預測模型在8個SPEC95的標竿程式上面做比較，結果顯示我們提出的預測機制都可以得到很好的效果。使用32K的緩衝區在bimode模型中平均可以提升8% 的效能，在2-level 模型中平均可以提升7.5% 的效能，在combination 模型中平均可以提升3.82% 的效能。

Branch instructions are always the performance bottleneck of pipelined superscalar processors by interrupt the steady flow of instruction stream in the pipeline. To resolve this problem, various branch prediction schemes have been proposed. There are 3 branch prediction schemes are widely used today. The simplest is bimod predictor using 2-bit saturating counts to record the history outcomes of every branch instruction. The 2-level adaptive predictor uses two-level architecture to trace the correlation of nearby branch outcomes. The most complex is the combination predictor, which consists of the bimod and 2-level predictor and use a meta-table to choose which result to be used. To analyze the factors affecting branch instruction outcomes, we find that associated register values take an important role. If we can make reference to the associated register information while making prediction, the accuracy can be improved. In this thesis, we propose a new auxiliary branch prediction mechanism, called as Associate Register Buffer to increase the prediction accuracy of original branch predictors. To implement this mechanism, a 3-entries Instruction Shift Buffer (ISB) is added to find the associated registers of a branch, the BTB entry is extended by adding 4 fields to record the associated register names, and an add-on history buffer to store the correct branch direction. Every time when the original predictor has a wrong prediction, the associated register values and branch address will be hashed to form an index to the history buffer and store the correct outcome. Next time when the branch runs again, the associated register values and branch address will be hashed to index the history buffer and if the entry is valid, the value stored in that entry will be used as our prediction. We simulate our design using the SimpleScalar tools set, and compare with 3 basic predictor models on eight of the SPEC95 benchmarks. The simulation results show that the ARB scheme outperforms all the basic predictor models. Using a 32768 entries of history buffer, the average improvement of accuracy with bimod predictor is 8%. As to 2-level prediction and combination prediction, the average improvements are 7.5% and 3.82% respectively.