摘要：This paper proposes an efficient algorithm to find the worst case flush timings for a given program with respect to the number of branch mispredictions. We first give a basic algorithm based on dynamic programming which takes O ( N2F ) computation time for a program with Nconditional branches and F flush timings. We then show it can be improved to achieve a computation time of approximately O ( NF ) for practical programs with its proof obtained through an evaluation with SPEC CPU95 benchmarks.
