Disjoint Eager Execution: An Optimal Form of Speculative Execution

Augustus K. Uht, Vijay Sindagi

Abstract

Research towards the realization of Instruction Level Parallelism (ILP) speedups of an order-of-magnitude or greater is reported. Traditional speculative code execution is the execution of code down one (branch prediction) or both (eager execution) paths of a branch, 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 reduced 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 in the ten's are demonstrated, with constrained resources.

Keywords

control flow, instruction level parallelism, branch prediction, disjoint eager execution, minimal control dependencies.

Talk Overheads (341584 bytes)