Disjoint Eager Execution:
An Optimal Form of Speculative Execution

Augustus K. Uht and Vijay Sindagi
Department of Electrical and Computer Engineering
Kelley Hall
Univ. of Rhode Island
Kingston, RI 02881, USA
email: {uht,vijay}@ele.uri.edu

In Proceedings of the 28th International Symposium on Microarchitecture (MICRO-28). ACM-IEEE, November/December 1995, pages 313-325.


Instruction Level Parallelism (ILP) speedups of an order-of-magnitude or greater may be possible using the techniques described herein. Traditional speculative code execution is the execution of code down one path of a branch (branch prediction) or both paths of a branch (eager execution), before the condition of the branch has been evaluated, thereby executing code ahead of time, and improving performance. A third, optimal, method of speculative execution, Disjoint Eager Execution (DEE), is described herein. A restricted form of DEE, easier to implement than pure DEE, is developed and evaluated. An implementation of both DEE and minimal control dependencies is described. DEE is shown both theoretically and experimentally to yield more parallelism than both branch prediction and eager execution when the same, finite, execution resources are assumed. ILP speedups of factors in the ten's are demonstrated with constrained resources.