Walk-time address adjustment for improving the accuracy of dynamic branch prediction

作     者：Chen, CM King, CT 

作者机构：Natl Tsing Hua Univ Dept Comp Sci Hsinchu 300 Taiwan 

出 版 物：《IEEE TRANSACTIONS ON COMPUTERS》 (IEEE Trans Comput)

年 卷 期：1999年第48卷第5期

页      面：457-469页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：branch prediction address adjustment computer architecture compiler optimization superscalar processor 

摘      要：Dynamic branch prediction has been an effective technique for boosting the performance of modern high performance microprocessors. Since hardware predictors only have a limited number of 2-bit counters but programs often have a large, variable number of branches, two branches in the programs may thus be mapped to the same 2-bit counter. Predictions for these two branches may interfere with each other. This, in turn, reduces the prediction accuracy. In this paper, we discuss how a pre-run-time optimization technique, called address adjustment, can help to reduce branch interference. The technique adjusts the addresses of conditional branches in the given program by inserting NOP instructions at appropriate locations. In this way, the mapping between the conditional branches and the 2-bit counters can be controlled and branch interference can be minimized. Address adjustment can be applied at compile or link time, and the latter makes it a walk-time transformation technique [4]. Three possible address adjustment schemes are investigated: constrained address adjustment, relaxed address adjustment, and branch classification. Experimental results show that address adjustment can reduce branch misprediction ratios on existing hardware predictors. Among the three methods, branch classification has the most improvement.