A WCET-Oriented Static Branch Prediction Scheme for Real Time Systems

Branch prediction mechanisms are becoming commonplace within current generation processors. Dynamic branch predictors, albeit able to predict branches quite accurately in average, are becoming increasingly complex. Thus, determining their worst-case behavior, which is highly recommended for real-time applications, is getting increasingly difficult and error-prone, and may even be soon impossible for the most complex branch predictors. In contrast, static branch predictors are inherently predictable, to the detriment of a lower prediction accuracy. In this paper, we propose a WCET-oriented static branch prediction scheme. Unlike related work on compiler-directed static branch prediction, our scheme does not address program average-case performance (i.e. average-case branch misprediction rate) but addresses worst-case program performance instead (i.e. branch mispredictions which impact programs WCET estimates). Experimental results on a PowerPC 7451 architecture show that the estimated WCET can be decreased by up to 21 % (with an average improvement of 15%) as compared with the method where all branches are conservatively considered mispredicted. Our scheme, although applicable to any processor with support for static branch prediction, is specially suited to processors with complex dynamic predictors, for which safe and tight WCET estimate methods do not exist.