A contribution to branch prediction modeling in WCET analysis

The wider and wider use of high-performance processors 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 (WCET) relies on static analysis of the code, the challenge is to model, with enough safety and accuracy, the behaviour of intrinsically dynamic components. We focus on the dynamic branch predictor. Several models to bound the number of branch mispredictions have previously been published. Some of them exhibit a high complexity while others have shown that taking into account semantic 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.