具投票預測器之分支方向預測

Abstract

由於現今的微處理器擁有較長的管線，並且具有每個時脈能夠發出多道指令的能力，所以分支預測的準確率就變的格外重要。到目前為止有各種不同的分支預測的機制已經被提出，其中有兩種至今仍被常常使用。第一種稱為「bimod branch predictor」，使用2位元的計數器來計錄分支預測的結果。由於他只使用簡單的2位元計數器，所以對一般偏向於跳或不跳的分支指令都能準確的預測。第二種是「2-level branch predictor」，它使用兩層式的架構記錄追蹤鄰近指令之間的相關性，如果某分支指令與臨近之間的分支指令存在著相關性，那麼2-level branch predictor能夠準確的作預測。可當我們使用不同的預測機制作實驗時，我們發現，沒有一種預測機制能同時滿足所有的benchmark。 因為上述的原因，我們提出一種稱為「vote predictor」的分支預測機制，它能夠達到更準確的預測。在vote predictor中我們使用三種不同的預測機制來同時作預測，並且使用vote circuit來選擇最後的輸出。當一道分支指令抓取之後，此三個不同的預測機制會同時進行預測，如果有兩個以上的預測機制產生相同的輸出，那麼vote circuit就會把它當做最後的輸出。所以vote circuit只是做簡單多數決的動作而已。 為了找出具有最佳性能的組合，我們選擇了四種著名的預測機制「bimod predictor、gshare、PAg、path-base branch predictor」，並且任意選擇三種來進行組合。我們使用SimpleScalar工具來模擬我們的設計。我們將提出的架構與所有構成它的基本機制在8個SPEC95的標竿程式上面來做比較，結果顯示我們所提出的機制可以獲得最好的效果。在4K的PHT entry下，我們提出的機制在分支方向的預測上，可以比其中性能最佳者增進1%到2%的性能。最後我們也把我們的機制跟著名的combining branch predictor做了比較，結果顯示當PHT entry加大到8K時，我們的機制優於combining branch predictor。

As modern microprocessors employ deeper pipelines and issue multiple instructions per cycle, they are becoming increasingly dependent on accurate branch prediction. Up to now, various branch prediction strategies have been proposed. There are two branch predictors are widely used today. The first is bimod predictor, using 2-bit saturation counters to record the history outcomes of every branch instruction. So bimod predictor is good to predict those branches which are bias taken or non-taken. The second is two-level adaptive branch predictor, which using two-level architecture to trace the correlation of nearby branch outcomes. So if one branch have correlation with nearby branches, the two-level branch predictor can make the correct predictor. These two branch predictors can gain benefits on their way individually. However, we find that there is no one branch predictor is good for all benchmarks. With the factor above, we propose a branch prediction machine, called “vote predictor”, to make the more accurate prediction. In the vote predictor, we combine three different branch predictors to make prediction and use a vote circuit to select the final output. Every time when one branch is encountered, three branch predictors make prediction concurrently. If two or more branch predictors make the same output (taken or non-taken), the vote circuit will select it as the final output. So the vote circuit just work like the majority rule. In order to find the best combination, we select four well-known branch predictors, which are bimod, gshare, PAg and path-based branch predictor, and combine three of them arbitrarily. We simulate our design by using the SimpleScalar tools set, and compare with its component predictor models on eight of the SPEC95 benchmarks. From the simulation results, it shows that the vote predictor outperforms its component predictors that make prediction alone. With 4K entries of pattern history table, the vote predictor increases the prediction accuracy with one of its most accurate component predictor from 1% to 2%. Finally, we also compare our vote predictor with the famous combining predictor, and the result shows that our vote predictor is slight better than the combining predictor as the PHT entry is increased to 8K.