Out-of-Order Execution and Register Renaming

An out-of-order processor does not wait for a stalled instruction: it looks further ahead in the program and runs whatever is ready, then puts the results back in order before anyone can notice. This single idea, together with register renaming, is the main reason large processors run so fast. It is also the most complex thing inside them. This article explains why in-order issue gets stuck, how renaming removes false dependences, how the issue queue and reorder buffer work, and how much all this gains on real programs.

12 min read | Intermediate

What You'll Learn

• Explain why out-of-order execution finds more parallelism
• Distinguish true dependences from name dependences
• Trace register renaming through a short code sequence
• Describe the roles of the issue queue and the reorder buffer

The Problem With Going in Order

Superscalar Issue showed that a wide in-order core is limited by the instruction at the front. If a load misses the cache, every instruction behind it waits, even those with all their inputs ready. On a large core, a cache miss to memory can take hundreds of cycles, enough time to run a thousand instructions.

Look at this sequence:

lw   t0,0(a0)      # misses the cache: 100 cycles
add  t1,t0,a1      # needs t0, must wait
addi a2,a2,1       # independent
sub  a3,a4,a5      # independent
xor  a6,a2,a3      # needs only the two above

An in-order core stops at the add, and the last three instructions wait for no good reason. If the processor could run them now, the program would lose nothing. That is out-of-order execution: an instruction runs when its inputs are ready, not when its turn comes. The dependences between instructions, the data flow, decide the order, rather than the sequence in which they were written.

This creates two problems. Registers are reused by compilers, so instructions that have nothing in common can appear to depend on each other. And the program must still appear to run in order, in case an exception occurs or a branch was wrong. Renaming solves the first, and the reorder buffer the second.

True and False Dependences

Three kinds of register dependence exist, as Data Hazards and Forwarding introduced:

add a0,a1,a2
sub a3,a0,a4       # read after write: needs the value. A true dependence.

add a0,a1,a2
sub a1,a4,a5       # write after read: must not overwrite a1 too early.

add a0,a1,a2
sub a0,a4,a5       # write after write: must end with the second value.

Only the first carries a value from one instruction to the next. The other two exist because there are only 31 usable register names, so they get reused. These are name dependences, or false dependences. Had the compiler had a different name to use, they would disappear.

Register Renaming

Hardware fixes this by having more registers than the instruction set names. A large core may have a few hundred physical registers. The names in instructions, x0 to x31, are architectural registers. As each instruction enters the out-of-order part, a rename table maps its source names to the physical registers holding the newest values, and gives its destination a fresh physical register from a free list.

Take this code. Names on the left are what the program says. On the right is what the hardware runs, with p for physical:

program                 after renaming
add a0,a1,a2            add p10,p1,p2        (a0 now maps to p10)
sub a1,a0,a4            sub p11,p10,p4       (a1 now maps to p11)
add a0,a4,a5            add p12,p4,p5        (a0 now maps to p12)
xor a3,a0,a1            xor p13,p12,p11

Look at what happened. The two writes to a0 go to different physical registers, so they can happen in any order. The third instruction no longer depends on the first in any way, and it can run first. Yet the fourth still gets exactly the right inputs: p12 and p11. Real dependences are kept and false ones are gone.

The old physical register of a name can be freed only when the new write is certain, because a misprediction might need it back. Why Branches Hurt explains recovery. Rename happens in the front end, in program order, for several instructions per cycle, each checking the others in its group. That makes it one of the hardest pieces of timing in the design.

The Parts of the Core

An out-of-order core is an in-order front end, an out-of-order middle, and an in-order back end.

The front end fetches and decodes on the predicted path, renames, and places each instruction in both the issue queue and the reorder buffer.

The issue queue, sometimes called the scheduler or reservation stations, holds instructions waiting for their inputs. When an instruction finishes, it broadcasts its destination register number, and every waiting instruction compares that with its sources. This is wakeup. Then select logic picks, from the ready ones, as many as there are free units. Wakeup and select must complete in one cycle, so that dependent instructions can run in consecutive cycles. Since this needs a comparison in every entry, the queue is one of the hottest parts of the chip.

The idea is older than you might guess. Robert Tomasulo designed a version of it in 1967 for the floating-point unit of the IBM System/360 Model 91. It became general in microprocessors in the 1990s.

The reorder buffer (ROB) is a queue of every instruction in flight, in program order. Instructions are added at the tail at rename. A finished instruction marks its entry as done. At the head, finished instructions commit, or retire, in order: their result becomes official, their old physical register is freed, and a store may go on to memory. Load/Store Queues and Memory Disambiguation explains how that works.

The ROB gives two guarantees. Exceptions are precise: if an instruction faults, this is only acted on when it reaches the head, and everything older has already finished, as Traps and Precise Exceptions describes. And a misprediction is recoverable: instructions younger than the wrong branch are simply dropped from the tail, and the rename table is restored from a saved copy. Nothing in the architecture was touched.

The Window

The number of instructions the core can hold at once, the size of the ROB, is its instruction window. A larger window sees further ahead. If one instruction waits for memory for 100 cycles, the ROB head blocks there, but the rest of the window can keep going until it fills. A core that fetches 4 instructions per cycle and has a 100-cycle miss would need a window of 400 to keep busy throughout. Modern large cores have ROBs of several hundred entries.

Many structures must grow with the window: the ROB, the physical registers, the issue queue, and the load and store queues. Larger queues are slower and use more power, which limits how far this goes.

What It Gains

A model on the same six programs gives an upper limit. It assumes perfect branch prediction, and enough execution units:

Out-of-order execution helps most programs a good deal, at the same width: at 4 wide, the IPC of the sort rises from about 1.9 to about 3.3. With 8 wide and a 256-entry window, the matrix program passes 7. The checksum, though, is stuck at about 1.8 whatever the design, because its instructions form a single chain of true dependences. Renaming cannot break a true dependence.

The ideal limit, with an infinite window and infinite width, varied hugely: about 2 for the checksum and over 50 for the matrix program. The gap between that and a practical design shows that parallelism exists, but often far apart in the program, out of reach of any real window. Also, all of this assumes perfect prediction. A real core gets far less, and on real programs, typical sustained IPC is around 1 to 3. On workloads with heavy memory misses, it is less than 1.

Memory Is the Hard Part

Registers are easy to reorder, because their names are visible at decode, and renaming removes the clashes. Memory is harder. Whether a load depends on an earlier store is not known until both addresses have been computed, which may be long after they entered the window. And unlike a register, a store cannot be undone, so it must not reach memory until commit. Large cores deal with this using separate queues for loads and stores, and they even guess when it is safe for a load to pass an earlier store. Much of the performance of a modern core depends on these guesses being right.

Another limit is simple bookkeeping. Every structure in the window fills up: if the physical registers, issue queue entries or load queue entries run out, the front end has to stop, even if the ROB has room. A balanced design sizes each of them so that none of them is regularly the one that stalls the others.

What It Costs

A large out-of-order core can be several times the area of a dual-issue in-order core, for perhaps twice the performance, at much higher power per instruction. It also adds a lot of design and verification work: bugs involving rare orderings can hide for a long time. Speculation has its risks too, as the Spectre attacks showed. Even so, single-thread speed still matters, and this is still the best known way to get it.

Common Mistakes