Evaluation of branch-prediction methods on traces from commercial applications

For modern superscalar processors, branch prediction is a must, and there h as been significant progress in this field during recent years. For the IBM System ESA/390(TM) environment, a set of traces exists which represent dif ferent kinds of commercial workloads, and they include operating-system int eractions. We have used four of these traces to evaluate a large variety of branch-prediction algorithms in order to identify possible design tradeoff s. One property of ESA/390 architecture is that for most branches, target a ddress calculation involves the use of values stored in general-purpose reg isters. Therefore, not only branch directions but target addresses must be predicted. When performing prefetch-time prediction, a branch target buffer (BTB) is used to provide/predict the target address. In this paper, all ev aluated prediction methods are combined with such a BTB. The resulting size for the BTB is significantly larger than for designs evaluated with SPECma rk(TM) traces. Algorithms for determining branch direction are examined and compared. These algorithms include local branch history methods as well as global history and path history procedures. Finally, combinations of some of these methods, known as hybrid predictors, are evaluated. The path histo ry algorithm we use is an adaptation of a known algorithm; but including it in the hybrid predictor is new. For all of these methods, design parameter s are varied to find the tradeoff between the hardware needed and the predi ction quality achieved. Results, except for those for the path predictor, a re comparable to SPECmark results, except that for most cases less history must be used. Another property of ESA/390 architecture, the absence of spec ific subroutine call and return instructions, led to the investigation of h ardware for self-detecting call/return pairs. A new approach has been devel oped, and its prediction quality is demonstrated. All of the methods descri bed above use a BTB. A BTB performs well if branches have fixed targets. Ho wever, about 5% of the branches we consider have changing target addresses. Very recently an algorithm was proposed for treating such branches using a modification to the BTB approach. We have implemented an enhancement to th is method, and the prediction correctness achievable using the enhanced met hod is shown in the results presented in this paper. Finally, combining sev eral of the investigated schemes increases branch-prediction correctness in commercial environments. However, it remains to be shown whether the treme ndous increase in hardware required for their implementation can be justifi ed.