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.
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.
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.
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.
