Instruction-Level Parallelism and Its Exploitation - Computer Architecture: A Quantitative Approach - page 178

tain maximum performance. Hence, exploiting more parallelism requires that we overcome
the limitation of control dependence.
Overcoming control dependence is done by speculating on the outcome of branches and
executing the program as if our guesses were correct. This mechanism represents a subtle,
but important, extension over branch prediction with dynamic scheduling. In particular, with
speculation, we fetch, issue, and execute instructions, as if our branch predictions were always
correct; dynamic scheduling only fetches and issues such instructions. Of course, we need
mechanisms to handle the situation where the speculation is incorrect. Appendix H discusses
a variety of mechanisms for supporting speculation by the compiler. In this section, we ex-
plore hardware speculation , which extends the ideas of dynamic scheduling.
Hardware-based speculation combines three key ideas: (1) dynamic branch prediction to
choose which instructions to execute, (2) speculation to allow the execution of instructions be-
fore the control dependences are resolved (with the ability to undo the effects of an incorrectly
speculated sequence), and (3) dynamic scheduling to deal with the scheduling of diferent
combinations of basic blocks. (In comparison, dynamic scheduling without speculation only
partially overlaps basic blocks because it requires that a branch be resolved before actually ex-
ecuting any instructions in the successor basic block.)
Hardware-based speculation follows the predicted flow of data values to choose when to
execute instructions. This method of executing programs is essentially a data flow execution :
Operations execute as soon as their operands are available.
To extend Tomasulo's algorithm to support speculation, we must separate the bypassing of
results among instructions, which is needed to execute an instruction speculatively, from the
actual completion of an instruction. By making this separation, we can allow an instruction
to execute and to bypass its results to other instructions, without allowing the instruction to
perform any updates that cannot be undone, until we know that the instruction is no longer
speculative.
Using the bypassed value is like performing a speculative register read, since we do not
know whether the instruction providing the source register value is providing the correct res-
ult until the instruction is no longer speculative. When an instruction is no longer speculative,
we allow it to update the register file or memory; we call this additional step in the instruction
execution sequence instruction commit .
The key idea behind implementing speculation is to allow instructions to execute out of or-
der but to force them to commit in order and to prevent any irrevocable action (such as updat-
ing state or taking an exception) until an instruction commits. Hence, when we add specula-
tion, we need to separate the process of completing execution from instruction commit, since
instructions may finish execution considerably before they are ready to commit. Adding this
commit phase to the instruction execution sequence requires an additional set of hardware
buffers that hold the results of instructions that have finished execution but have not commit-
ted. This hardware buffer, which we call the reorder buffer , is also used to pass results among
instructions that may be speculated.
The reorder buffer (ROB) provides additional registers in the same way as the reservation
stations in Tomasulo's algorithm extend the register set. The ROB holds the result of an in-
struction between the time the operation associated with the instruction completes and the
time the instruction commits. Hence, the ROB is a source of operands for instructions, just as
the reservation stations provide operands in Tomasulo's algorithm. The key difference is that
in Tomasulo's algorithm, once an instruction writes its result, any subsequently issued instruc-
tions will find the result in the register file. With speculation, the register file is not updated
until the instruction commits (and we know definitively that the instruction should execute);