Out-of-order execution: Tomasulo, the reorder buffer and speculation

An in-order pipeline stalls when an instruction waits for data, and with it all the following ones, even independent ones. An out-of-order processor lets ready instructions go ahead, and reorders the results at the end. This is the idea of Tomasulo’s algorithm (IBM 360/91, 1967), which with the addition of the reorder buffer is the heart of every high-performance processor today. In this lesson we look at reservation stations, the common data bus, the reorder buffer with the proof that it guarantees precise exceptions, speculative execution and memory disambiguation.

The idea

A load that misses the cache can cost hundreds of cycles. In an in-order pipeline the processor stays idle all that time. Yet behind the load there are often tens of instructions that have nothing to do with the awaited data. Out-of-order execution separates three moments that coincide in the simple pipeline:

1. issue, in order: the instruction is decoded, its registers renamed, and it is put on hold;
2. execution, out of order: it starts as soon as its operands are available;
3. commit, again in order: the result becomes final, visible to the architecture.

Reservation stations and the common data bus

Each functional unit has a group of reservation stations in front of it: registers holding a waiting instruction, with its operands. For each operand the station contains the value, if already available, or the tag of the instruction that will produce it. The tags are in practice the physical registers of the previous lesson: renaming happens here, and WAR and WAW dependences disappear.

When a unit finishes, it puts the result and its tag on the common data bus (CDB). All the stations waiting for that tag capture it in the same cycle; an instruction with all operands ready is sent to its unit at the first opportunity, regardless of program order. True dependences are respected by construction, because no instruction starts without its operands.

The reorder buffer

In the original algorithm results wrote directly into the registers out of order. This creates a problem: if an instruction causes an exception (a division by zero, a page fault), some later instructions might already have modified the state, and the operating system would not know where to restart. The solution is the reorder buffer (ROB): a circular queue in which every instruction takes a slot, in program order, at issue. Results are written into the ROB; an instruction commits, i.e. writes to the architectural registers or to memory, only when it is at the head of the queue and has finished.

Theorem. With in-order commit from the ROB, exceptions are precise: when the exception of instruction is handled, the architectural state contains the results of all instructions preceding and of none following it.

Proof. The architectural state (registers and memory) changes only at commit, and instructions commit in program order, one after another from the head of the ROB. The exception of is recorded in its ROB slot and handled when reaches the head: at that moment all the preceding instructions have committed, because they were ahead in the queue, and none of the following ones has, because they are behind. The processor discards the contents of the ROB from onwards and jumps to the handler. ∎

Speculative execution

The same mechanism allows instructions to be executed before knowing whether they should be executed. When a conditional branch is met, the processor predicts its direction (lesson on prediction) and keeps issuing instructions along that path. If the prediction was right, those instructions commit normally; if it was wrong, when the branch reaches the head of the ROB all the following instructions are discarded and execution restarts from the correct address. Nothing done by mistake has touched the architectural state.

The micro-architectural state, however, has been touched: instructions executed by mistake may have loaded data into the caches. This is the principle of the Spectre attacks (2018), which deduce secret data by measuring cache access times after speculative execution. The countermeasures (barriers, isolation, compiler changes) cost a few per cent of performance.

Memory

Dependences through memory are the trickiest: a load may read the address that an earlier store is about to write, but the address is known only after it has been computed. Stores wait for commit in a store queue; a load compares its address with those in the queue and, if it finds a write to the same address, takes the value directly from it (store-to-load forwarding). Modern processors dare more: they execute the load even before the addresses of earlier writes are known, predicting that there is no conflict, and if they are wrong they squash and re-execute.

Sizes

A 2025 high-performance processor has a ROB of 500-600 entries, a few hundred physical registers, about ten functional units and can have hundreds of instructions “in flight”. The large window serves above all to hide memory latency: while a load waits for DRAM, the processor finds useful work many instructions ahead.