An Efficient Analysis of Worst Case Flush Timings for Branch Predictors

Masahiro Konishi; Takashi Nakada; Tomoaki Tsumura; Hiroshi Nakashima; Hiroaki Takada

doi:10.2197/ipsjdc.3.255

Masahiro Konishi, Takashi Nakada, Tomoaki Tsumura, Hiroshi Nakashima, Hiroaki Takada

Author information

JOURNAL FREE ACCESS

2007 Volume 3 Pages 255-268

DOI https://doi.org/10.2197/ipsjdc.3.255

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!