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

Dynamic branch prediction has been an effective technique for boosting the performance of modern high performance microprocessors. Since hardware pred ictors 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 thu s be mapped to the same 2-bit counter. Predictions for these two branches m ay interfere with each other. This, in turn, reduces the prediction accurac y. In this paper, we discuss how a pre-run-time optimization technique, cal led address adjustment, can help to reduce branch interference. The techniq ue adjusts the addresses of conditional branches in the given program by in serting 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 transformatio n technique [4]. Three possible address adjustment schemes are investigated : constrained address adjustment, relaxed address adjustment, and branch cl assification. Experimental results show that address adjustment can reduce branch misprediction ratios on existing hardware predictors. Among the thre e methods, branch classification has the most improvement.