A Contribution to Branch Prediction Modeling in WCET Analysis

The wider and wider use of high-performance proces-sors as part of real-time systems makes it more and more difficult to guarantee that programs will respect their strict deadlines. While the computation of Worst-Case Execution Times relies on static analysis of the code, the challenge is to model with enough safety and accuracy the behaviour of intrisically dynamic components. In this paper, we fo-cus on the dynamic branch predictor. Several models to bound the number of branch mispredictions have been pre-viously published. Some of them exhibit a high complexity while other ones have shown that taking into account se-mantic information from the source code makes things more tractable. We extend this work to more general nested loop structures. We also give some simulation results that show that the way branch mispredictions are usually taken into account cannot be both safe and accurate in the case of high-performance pipelines. We propose a more realistic approach to be used as part of WCET computation. 1