Out-of-order execution: renaming, reservation stations and the reorder buffer

An in-order processor stops whenever the next instruction cannot proceed. If a load misses in the cache and takes twelve cycles, every instruction behind it waits, even those that have nothing to do with the loaded value. An out-of-order processor keeps a window of upcoming instructions, starts each one as soon as its operands are ready, and lets independent work flow around the blocked instruction. It still appears to the program to execute instructions one at a time in order, because it commits results in program order. Dynamic scheduling of this kind is the core technique of every high-performance general-purpose processor in phones, laptops and servers.

The NS-5 will not use an out-of-order core: Maren's power budget rules it out. But Dana's servers do, and Jonah's profiling of the nightly aggregation jobs shows that their speed depends heavily on how well those cores hide memory latency. Understanding the mechanism explains both why the servers tolerate cache misses so well and why such cores cost so much power.

The idea of dynamic scheduling

Dynamic scheduling separates the issue of an instruction into two steps. In the first, instructions are decoded in program order and placed into a waiting area, with their register dependences recorded. In the second, any instruction in the waiting area whose operands are available is dispatched to a functional unit, regardless of its position in the program. Results are broadcast to waiting instructions as they complete, waking up those that needed them. The order of execution is thus determined by the flow of data, not by the order of the program text, which is why such machines are also described as dataflow engines with a sequential interface.

Executing out of order creates two problems that in-order pipelines avoid. Name dependences, the antidependences and output dependences of lesson 5, now matter: if a later instruction writes a register before an earlier instruction has read the old value, the earlier instruction gets the wrong value. And exceptions and mispredictions become hard to handle, because later instructions may already have finished when an earlier one faults. Register renaming solves the first problem and the reorder buffer the second.

Tomasulo's algorithm

The classic scheme, devised in the 1960s for the floating-point unit of a large mainframe, introduced the key structures still used today in modified form. Each functional unit has a set of reservation stations, small buffers that hold instructions waiting to execute. When an instruction issues, it is placed in a free reservation station. For each source operand, the station records either the value, if it is already available, or a tag naming the reservation station that will produce it. The register file is likewise annotated: each register records either that its value is current or the tag of the station that will write it next.

When a functional unit finishes, it broadcasts its result and tag on a common data bus. Every reservation station waiting for that tag captures the value, and the register file updates any register whose recorded tag matches. An instruction executes as soon as all its operands have arrived. Because sources are renamed to station tags at issue, later writes to a register cannot disturb an earlier instruction that is waiting for the old value: that instruction is waiting for a tag, not for the register. Renaming has removed the name dependences without the compiler's help.

Register renaming with a physical register file

Most modern cores implement renaming with a large physical register file and a rename table. The instruction set names 32 architectural registers, but the core has, say, 128 or more physical registers. When an instruction that writes a register is renamed, it is given a free physical register as its destination, and the rename table is updated so that later readers of that architectural register are directed to the new physical one. Earlier readers keep pointing at the old physical register, which is freed only when the instruction that overwrote it commits and no reader can still need it. Every write gets a fresh name, so anti and output dependences vanish; only true dependences remain. The number of physical registers bounds how many instructions can be in flight.

The reorder buffer and precise exceptions

The reorder buffer is a circular queue holding every in-flight instruction in program order. Instructions enter at the tail when they are renamed. They may execute and finish in any order, but they leave from the head, an operation called commit or retirement, only when they have finished and every older instruction has committed. Committing makes an instruction's effects architectural: its destination becomes the official value of its register and, for a store, its data may be written to memory.

Committing in order makes exceptions precise even though execution is not in order. If an instruction faults, the fault is recorded in its reorder buffer entry and acted on only when the entry reaches the head. At that moment every older instruction has committed and no younger one has changed architectural state, so the processor discards all younger entries, restores the rename table to the committed mapping, and jumps to the handler. Branch mispredictions are handled the same way, though usually without waiting for the head: when a branch resolves wrong, the core squashes all younger entries and restores a rename-table snapshot taken at the branch. The reorder buffer is thus also the mechanism that makes the speculation of lesson 4 safe.

Memory disambiguation and the load-store queue

Registers are easy to rename because their names are known at decode. Memory addresses are not known until they are computed, so the core cannot tell at first whether a load reads a location that an earlier, still-pending store will write. A conservative core makes every load wait until all earlier store addresses are known. An aggressive core lets loads run early and checks later. A load-store queue holds pending memory operations in program order. When a load executes, it searches the queue for older stores to the same address; if one exists with its data ready, the store's value is forwarded directly to the load, avoiding a trip to the cache. If a store's address turns out to match a load that has already executed using stale data, the load and everything after it are squashed and replayed. Memory dependence predictors learn which loads tend to conflict with stores and make just those loads wait.

Stores themselves are never written to the cache speculatively: a store's data waits in the queue until the store commits, because a store, once visible to other cores or devices, cannot be undone. This rule ties memory consistency, discussed in lesson 10, to the commit mechanism.

A dataflow timing example

Jonah compares in-order and out-of-order execution on a fragment of the aggregation code in which the first load misses in the cache. Both machines can start two instructions per cycle. The out-of-order machine starts each instruction as soon as its operands are ready; the in-order machine also cannot start an instruction before any older one. Both commit in program order, up to two per cycle.

# Dataflow timing: in-order issue versus out-of-order issue with in-order commit
LAT = {"lw": 2, "miss": 12, "mul": 3, "add": 1, "sub": 1}
prog = [("lw   t0, 0(a0)", "miss", "t0", []),      # this load misses in the cache
        ("add  t1, t0, s1", "add", "t1", ["t0"]),
        ("lw   t2, 4(a0)", "lw",   "t2", []),
        ("mul  t3, t2, s2", "mul", "t3", ["t2"]),
        ("lw   t4, 8(a0)", "lw",   "t4", []),
        ("sub  t5, t4, s3", "sub", "t5", ["t4"]),
        ("add  t6, t3, t5", "add", "t6", ["t3", "t5"]),
        ("add  a1, t1, t6", "add", "a1", ["t1", "t6"])]

def schedule(out_of_order, width=2):
    done, start, cycle_use = {}, [], {}
    last = 0
    for i, (_, op, rd, srcs) in enumerate(prog):
        earliest = max([i // width + 1] + [done[r] for r in srcs if r in done])
        if not out_of_order:
            earliest = max(earliest, last)            # cannot start before an older instruction
        c = earliest
        while cycle_use.get(c, 0) >= width:           # at most `width` starts per cycle
            c += 1
        cycle_use[c] = cycle_use.get(c, 0) + 1
        start.append(c); last = c
        done[rd] = c + LAT[op]
    finish = [start[i] + LAT[op] for i, (_, op, _, _) in enumerate(prog)]
    commit, t, n = [], 0, 0
    for f in finish:                                   # reorder buffer retires in order, 2 per cycle
        c = max(t, f + 1)                              # retire the cycle after the result is ready
        n = n + 1 if c == t else 1
        if n > width: c, n = c + 1, 1
        t = c; commit.append(c)
    return start, finish, commit

for ooo in (False, True):
    s, f, c = schedule(ooo)
    print("out-of-order" if ooo else "in-order", f"(all committed by cycle {c[-1]})")
    for (text, *_), a, b, d in zip(prog, s, f, c):
        print(f"  {text:17s} start {a:2d}  result {b:2d}  commit {d:2d}")

in-order (all committed by cycle 21)
  lw   t0, 0(a0)    start  1  result 13  commit 14
  add  t1, t0, s1   start 13  result 14  commit 15
  lw   t2, 4(a0)    start 13  result 15  commit 16
  mul  t3, t2, s2   start 15  result 18  commit 19
  lw   t4, 8(a0)    start 15  result 17  commit 19
  sub  t5, t4, s3   start 17  result 18  commit 20
  add  t6, t3, t5   start 18  result 19  commit 20
  add  a1, t1, t6   start 19  result 20  commit 21
out-of-order (all committed by cycle 18)
  lw   t0, 0(a0)    start  1  result 13  commit 14
  add  t1, t0, s1   start 13  result 14  commit 15
  lw   t2, 4(a0)    start  2  result  4  commit 15
  mul  t3, t2, s2   start  4  result  7  commit 16
  lw   t4, 8(a0)    start  3  result  5  commit 16
  sub  t5, t4, s3   start  5  result  6  commit 17
  add  t6, t3, t5   start  7  result  8  commit 17
  add  a1, t1, t6   start 14  result 15  commit 18

On the in-order machine everything behind the missing load waits until cycle 13, and the fragment commits in cycle 21. The out-of-order machine runs the second and third loads, the multiply, the subtraction and one of the adds while the miss is outstanding, so that only the add that truly needs the missing value, and the final add that depends on it, wait. It commits everything by cycle 18. The out-of-order core does not commit any earlier than the miss allows: the independent instructions finish early but commit only after the load at the head, preserving the sequential appearance.

The cost of out-of-order execution

The benefits come with substantial cost. Renaming tables, wakeup and select logic for the reservation stations, the reorder buffer, the load-store queue and the wide bypass network take large areas, and much of that logic is active every cycle. The wakeup and select loop, which must broadcast a result and choose the next ready instruction in one cycle, is a critical timing path that limits how large the scheduling window can grow. Out-of-order cores also waste energy on mispredicted work and on the bookkeeping itself. In phones and laptops, designers pair large out-of-order cores with small in-order cores and move work between them according to demand, so that light tasks run on the efficient cores. For a device on a solar budget, the small in-order core is the only option.