An Efficient Analysis of Worst Case Flush Timings for Branch Predictors

Computing

Presently with PFU Ltd.">Masahiro Konishi, Takashi Nakada, Tomoaki Tsumura, Hiroshi Nakashima, Hiroaki Takada

Author information

JOURNAL FREE ACCESS

2007 Volume 2 Issue 3 Pages 734-747

DOI https://doi.org/10.11185/imt.2.734

Details

Abstract

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(N²F) 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.

Corresponding author

Register with J-STAGE for free!