Speculation
It is the technique to keep the instruction execution rate high using
prediction based on program structure and profile. There are two types
of speculated execution of instructions:
Compiler speculation
Hardware based speculation
Compiler Speculation
1. It tries to make instructions control independent,meaning they are
harmless as far as the control statement outcome is concerned
2. It would move such speculated instructions before the execuation of
the control instructions (branches)
3. It ensures that the exception behaviour is not changed
4. It ensures that dynamic data dependence remains the same
5. It can rename the registers so that the speculated code will not
distroy data values when they are needed
Since exception behaviour is one of the limiting factors , many techniqes
have been investigated to ensure correct program execution. For example:
1. The hardware and the operating system cooperatively ignore exceptions
for speculative instructions
2. A set of status bits, called poison bits, are attached to the result
registers written by the speculated instructions when the instructions cause
exceptions.The poison bits cause a fault when a normal instruction
attempts to use the register.
3. A mechanism is provided to indicate that an instruction is speculative
and the hardware buffers the instruction result until it is certain that
the instruction is no longer speculative.
Hardware Based Speculation (HBS)
HBS is based on three key concepts:
Dynamic Branch prediction to choose which instruction to execute
Speculation to allow the execution of instructions before the control
dependences are resolved
Dynamic scheduling to deal with the scheduling of different combinations
os basic blocks
The Hardware that implements Tomasulo's algo can be extended to support
speculation.The important thing about program execution using speculation
is that, instructions can use results of other speculated instructions
but cannot write back to the registers until the speculated instructions
are in harmony with the outcome of the control instruction and have already
been commited to the registers, and if the outcome of the control instruction
is against the speculated instructions then all speculated instructions
as well as the dependent instructions must be abandoned(flushed out)
So the key idea is to allow the execution out of order but to commit results
in order to prevent any irrevocable action. In order to keep the results
of the completed but incommited instructions, a hardware buffer named REORDER
BUFFER is provided.This reorder buffer provides additional virtual registers
in the same way as the reservation stations in Tomasulo's algo extend
the register set.It is a source of operands for instructions untill the
instruction is committed back.
The entry in a reorder buffer contains following information:
Instruction type: whether the instruction is a branch, store or ALU op
Destination Field: Register no. or the memory address where this result should go
Value Field: Result of that instruction which is to sent to Reg/Memory
Steps of Execution
1.Issue
Instruction is passed to the available reservation station from the
instruction queue, and entry is made in the Reorder Buffer to ensure
proper commition of results.
2.Execute
As soon as the operands are available, the FU's start execution.
3.Write Result
Results are written to the Reorder Buffer as soon as the CDB is available
and also to the Reservation stations which are awaiting this result.The
reservation station is freed.
4.Commit
As the instruction reaches the head of the Reorder Buffer, it written
back to the Registers if the outcome of the control instruction is not
against the speculated instructions.