Disjoint Eager Execution Tutorial

In order to more fully exploit the Instruction Level Parallelism inherent in typical code the ill effects of branches must be reduced. This is commonly done by executing instructions speculatively, i.e., before it is known that their results are definitely to be used.

As shown in the following figure, there are 3 forms of speculative code execution potentially usable in modern and future computers. Each form assigns execution resources, such as functional units, to instructions in the window of the processor in a different fashion. A unit of executable code is a branch path: the dynamic code between two branches.

  1. Single Path (SP): This is simple branch prediction. When a processor comes to a branch, the branch is predicted, and execution proceeds down the predicted path. Succeeding branches encountered on the predicted path are similarly predicted. Cost is linear in the overall depth of prediction (l), but the cumulative probability of using the code after a branch falls to zero rapidly with deeper predictions, as shown in the figure by the uncircled numbers. SP is commonly used in today's superscalar processors.
  2. Eager Execution (EE): When a branch is encountered, execution proceeds down both paths of the branch (no prediction is made). Cost is exponential in l (2l), although performance can be good for very large values of l. Due to the excessive cost, EE is not used extensively.
  3. Disjoint Eager Execution (DEE): The key idea of DEE is to assign resources to the most likely code to be executed over all unexecuted code. This results in an ordering of resource assignment which often assigns resources to prior not-predicted paths in the processor's window, as shown by the circled order numbers in the figure. Branches are predicted, and often eagerly executed as well. The cost is similar to that of SP, with performance exceeding that of both SP and EE. DEE is an optimal form of speculative execution; resources are assigned optimally.
Also see:

May 23, 1997 | Gus Uht | uht@ele.uri.edu