A WCET-oriented static branch prediction scheme for real time systems

Branch prediction mechanisms are becoming common-place within current generation processors. Dynamic branch predictors, albeit able to predict branches quite accurately in average, are becoming increasingly com-plex. 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 con-trast, static branch predictors are inherently predictable, to the detriment of a lower prediction accuracy. In this pa-per, 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 mis-prediction rate) but addresses worst-case program perfor-mance 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 improve-ment 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 proces-sors with complex dynamic predictors, for which safe and tight WCET estimate methods do not exist.