speculation combines three key ideas: dynamic branch prediction to choose which
instructions to execute, speculation to allow the execution of instructions
before the control dependences are resolved and dynamic scheduling to deal with
the scheduling of different combinations of basic blocks.
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.
The approach is implemented in a number of processors (PowerPC 603/604/G3/G4, MIPS R10000/R12000, Intel Pentium II/III/ 4, Alpha 21264, and AMD K5/K6/Athlon), is to implement speculative execution based on Tomasulo’s algorithm.
idea behind implementing speculation is to allow instructions to execute out of
order but to force them to commit in order and to prevent any irrevocable
action until an instruction commits.
simple single-issue five-stage pipeline we could ensure that instructions
committed in order, and only after any exceptions for that instruction had been
detected, simply by moving writes to the end of the pipeline.
the four steps involved in instruction execution:
1. Issue—Get an instruction from the
instruction queue. Issue the instruction if there is an empty reservation station and an empty slot
in the ROB, send the operands to the reservation station if they available in
either the registers or the ROB for execution. If either all reservations are
full or the ROB is full, then instruction issue is stalled until both have
available entries. This stage is sometimes called dispatch in a dynamically
2. Execute—If one or more of the operands
is not yet available, monitor the CDB (common data bus) while waiting for the register to be computed. When both
operands are available at a reservation station, execute the operation.
3. Write result—When the result is available,
write it on the CDB and from the CDB into the ROB, as well as to any reservation stations waiting for this
result. If the value to be stored is not available yet, the CDB must be
monitored until that value is broadcast, at which time the Value field of the
ROB entry of the store is updated.
4. Commit—There are three different
sequences of actions at commit depending on whether the committing instruction is: a branch with an incorrect prediction,
a store, or any other instruction (normal commit). The normal commit case
occurs when an instruction reaches the head of the ROB and its result is
present in the buffer; at this point, the processor updates the register with
the result and removes the instruction from the ROB.
a store is similar except that memory is updated rather than a result register.
When a branch with incorrect prediction reaches the head of the ROB, it
indicates that the speculation was wrong. The ROB is flushed and execution is
restarted at the correct successor of the branch. If the branch was correctly
predicted, the branch is finished. Some machines call this commit phase
completion or graduation.