Lecture
Speculative execution is an optimization technique in which a computer system performs some task that may turn out to be unnecessary. The work is done before it is known whether it is actually needed, in order to prevent the delay that could occur if the work were done after it becomes known that it is needed. If it turns out that the work is ultimately not needed, most of the changes made by the work are rolled back, and the results are ignored.
The goal is to provide more parallelism when additional resources are available . This approach is used in many areas, including branch prediction in pipelined processors, value prediction to take advantage of value locality, memory and file prefetching, and optimistic concurrency control in database systems
Speculative multithreading is a special case of speculative execution.
Modern pipelined microprocessors use speculative execution to reduce the cost of conditional branch instructions by using circuits that predict a program's execution path based on the history of branch outcomes . To improve performance and the use of computer resources, instructions can be scheduled at a time when it has not yet been determined that they should be executed before the branch .
One of the main features of the sixth generation of IA32-architecture microprocessors is dynamic (speculative) execution. This term refers to the following set of capabilities:
Deep branch prediction (with a probability of >90%, the next 10-15 branches can be predicted).
Data flow analysis (looking 20-30 steps ahead in the program to determine dependencies between instructions based on data or resources).
Speculative instruction execution (the P6 microprocessor can execute instructions in an order different from their order in the program).
The internal organization of the P6 microprocessor follows the RISC architecture, so the instruction fetch unit, having read a stream of IA-32 instructions from the L1 instruction cache, decodes them into a series of micro-operations. The stream of micro-operations enters the reorder buffer (instruction pool). It contains both micro-operations that have not yet been executed and ones that have already been executed but have not yet affected the state of the processor. Three parallel decoders are used to decode instructions: two for simple instructions and one for complex instructions. Each IA-32 instruction is decoded into 1-4 micro-operations. Micro-operations are executed by five parallel execution units: two for integer arithmetic, two for floating-point arithmetic, and a memory interface unit. Thus, up to five micro-operations can be executed per clock cycle.
The execution unit block is able to select instructions from the pool in any order. In doing so, thanks to the branch prediction unit, it is possible to execute instructions that follow conditional branches. The reservation unit continuously monitors the instruction pool for those micro-operations that are ready for execution (their source data does not depend on the result of other unexecuted instructions) and dispatches them to a free execution unit of the corresponding type. One of the integer execution units additionally handles verifying the correctness of branch predictions. When an incorrectly predicted branch is detected, all micro-operations following the branch are removed from the pool, and the instruction pipeline is refilled with instructions from the new address.
The mutual dependency of instructions on the values of IA-32 architecture registers may require waiting for registers to be freed. To solve this problem, 40 internal general-purpose registers are provided, used in actual computations.
The retirement unit tracks the result of speculatively executed micro-operations. If a micro-operation no longer depends on other micro-operations, its result is committed to the processor state, and it is removed from the reorder buffer. The retirement unit commits the execution of instructions (up to three micro-operations per clock cycle) in the order they appear in the program, taking into account interrupts, exceptions, breakpoints, and branch prediction misses.
The scheme described is shown in Fig. 5.2.
Fig. 5.2.Block diagram of the Pentium Pro microprocessor
Speculative computing was related to an earlier concept .
Eager execution is a form of speculative execution in which both sides of a conditional branch are executed; however, the results are committed only if the predicate is true. With unlimited resources, eager execution (also known as oracle execution) would theoretically provide the same performance as ideal branch prediction. With limited resources, eager execution should be used with caution, since the amount of resources required grows exponentially with each level of a branch executed eagerly .
Predicated execution is a form of speculative execution in which some result is predicted, and execution continues along the predicted path until the actual result becomes known. If the prediction is correct, the predicated execution is allowed to be committed; however, if there is a misprediction, the execution must be rolled back and redone. Common forms of this include the branch predictor and memory dependence prediction. The generalized form is sometimes called cost prediction .
Lazy execution is the opposite of eager execution and does not involve speculation. Incorporating speculative execution into implementations of the Haskell programming language, a lazy language, is a current research topic. Eager Haskell, a variant of the language, is based on the idea of speculative execution. In a 2003 doctoral dissertation, GHC was given support for a kind of speculative execution with a rollback mechanism for the case of an unsuccessful choice, called optimistic execution . This was considered too complex[10].
Since 2017, a number of security vulnerabilities have been discovered in speculative execution implementations on common processor architectures, which allowed privilege escalation.
These include:
Comments