Dynamic schemes for speculative execution of code

Speculative execution of code is becoming a key technique for enhancing the performance of pipeline processors. In this work we study schemes that predict the execution path of a program based on the history of branch executions. Building on previous work, we present a model for analyzing the effective speedup from pipelining, when speculative execution is employed. We follow this with stochastic analyses of several schemes for speculative execution. A main result of our study is that if we can predict branch resolution with high probability (as in the Pentium Pro processor, e.g.) the Single Path scheme commonly used on modem processors is within factor of 2 from the optimal. We conclude with simulations covering several of the settings that we study. (C) 2002 Elsevier Science B.V. All rights reserved.