Effects of Branch Prediction on Worst Case Execution Time of Programs
No Thumbnail Available
Date
2001-11-01T00:00:00Z
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.