藉由全動態斷定執行減少難以預測的分支指令對於效能的影響

Abstract

分支預測器從很久以前就遭遇了難以猜測的分支指令造成系統效能降低的問題。斷定執行在之前就已經被使用來解決這個問題。一開始出現的是靜態的斷定執行，這種方式無法改變去配合分支指令在 run time 的行為。接著出現的是動態的斷定執行，他可以在 run time 的環境下，根據分支指令的行為去改變自己執行的時機。可是這是需要編譯器的幫助，由編譯器預先產生額外的資訊，因此會造成執行程式變大的問題。 在這篇論文中，我們提出了一種方法叫做全動態的斷定執行。我們希望這個設計可以動態的偵測出有機會做斷定執行的分支指令，並且動態的產生可以斷定執行的指令，最後我們使用斷定執行的方式來執行這些指令。假如我們可以做到這些，我們就不需要藉助編譯器的幫助，執行程式也可以維持原本的大小。另外我們也會動態的去選擇合適的分支指令，這樣可以根據分支指令的行為替換掉可以做斷定執行的難以預測的分支指令。根據實驗的結果，在 instruction windows 大小為128時，平均的改善為 1.854%，最好時為6.217%，最差的改善為0.005%。若我們將 benchmarks依照有效性來分組的話，效果最好的組別(vpr, twolf)的平均改善是5.655%，最好的情況是6.217%，最差的改善是5.093%。

The branch predictor suffers from hard-to-predict branch for a long time. Predicated execution has been used to resolve this problem. The static predicated execution cannot adapt to branches’ run-time behavior. The dynamic predicated execution assisted by the compiler can adapt to branches’ run-time behavior, but the code size will increase. In this thesis, we propose a method called fully dynamic predicated execution. We hope our design can dynamically detect the possible predicate region and dynamically generate the predicated instructions. Finally, the processor executes them in the way of predicated execution. If we can do so, the code size will not increase. We also select the proper branches dynamically so the design can adapt to branches’ run-time behavior. As the results of an experiment, when instruction window size is 128, the average improvement is 1.854%, the best case is 6.217% and the worst case is 0.005%. If we group the benchmarks by effectiveness (vpr, twolf), the average improvement is 5.655%, the best case is 6.217% and the worst case is 5.093%.