School of Computing

Permanent URI for this community

https://dl.comp.nus.edu.sg/handle/1900.100/1

Browse

Browsing School of Computing by Author "Abhik Roychoudhury"

Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    Effects of Branch Prediction on Worst Case Execution Time of Programs
    (2001-11-01T00:00:00Z) Tulika Mitra; Abhik Roychoudhury
    Estimating the Worst Case Execution Time (WCET) of a program on a given hardware platform is useful in the design of embedded real-time systems. These systems communicate with the external environment in a timely fashion, and thus impose constraints on the execution time of programs. Estimating the WCET of a program ensures that these constraints are met. WCET analysis schemes typically model microarchitectural features in modern processors, such as pipeline and caches, to obtain tight estimates. In this paper, we study the effects of speculative execution on WCET analysis. Speculative execution uses branch prediction to predict the outcome of a branch instruction based on past execution history. This allows the program execution to proceed by speculating the control flow. Branch predictions schemes can be local or global. Local schemes predict a branch outcome based exclusively on its own execution history whereas global schemes take into account the outcome of other branches as well. Current WCET analysis schemes have largely ignored the effect of branch prediction. Our technique combines program analysis and microarchitectural modeling to estimate the effects of branch prediction. Starting from the control flow graph of the program, we derive linear inequalities for bounding the number of mispredictions during execution (for all possible inputs). These constraints are then solved by any standard (integer) linear programming solver. Our technique models local as well global branch prediction in a uniform fashion. Although global branch prediction schemes are used in most modern processors, their effect on WCET has not been modeled before. The utility of our method is illustrated through tight WCET estimates obtained for benchmark programs.