Алгоритм Томасуло: Аппаратная реализация динамического планирования инструкций

Computer architecture hardware algorithm
Tomasulo's algorithm is a computer architecture hardware algorithm for dynamic scheduling of instructions that allows out of order execution and enables more efficient use of multiple execution units. It was developed by Robert Tomasulo at IBM in 1967 and was first implemented in the IBM System/360 Model 91’s floating point unit.

The Common Data Bus (CDB) connects reservation stations directly to functional units. According to Tomasulo it "preserves precedence while encouraging concurrency". This has two important effects:
Functional units can access the result of any operation without involving a floating point register, allowing multiple units waiting on a result to proceed without waiting to resolve contention for access to register file read ports. Hazard Detection and control execution are distributed. The reservation stations control when an instruction can execute, rather than a single dedicated hazard unit.

Instructions are issued sequentially so that the effects of a sequence of instructions, such as exceptions raised by these instructions, occur in the same order as they would on an in order processor, regardless of the fact that they are being executed out of order (i. e. non sequentially).

Tomasulo's algorithm uses register renaming to correctly perform out of order execution. All general purpose and reservation station registers hold either a real value or a placeholder value. If a real value is unavailable to a destination register during the issue stage, a placeholder value is initially used. The placeholder value is a tag indicating which reservation station will produce the real value. When the unit finishes and broadcasts the result on the CDB, the placeholder will be replaced with the real value. Each functional unit has a single reservation station. Reservation stations hold information needed to execute a single instruction, including the operation and the operands. The functional unit begins processing when it is free and when all source operands needed for an instruction are real.

Practically speaking, there may be exceptions for which not enough status information about an exception is available, in which case the processor may raise a special exception, called an imprecise exception. Imprecise exceptions cannot occur in in order implementations, as processor state is changed only in program order (see ). Programs that experience precise exceptions, where the specific instruction that took the exception can be determined, can restart or re execute at the point of the exception. However, those that experience imprecise exceptions generally cannot restart or re execute, as the system cannot determine the specific instruction that took the exception.

The three stages listed below are the stages through which each instruction passes from the time it is issued to the time its execution is complete.