The idea: more than one instruction per cycle

The five-stage pipeline finishes at best one instruction per cycle: its IPC (instructions per cycle) is at most 1. Advanced processors go further in two ways. A superscalar processor has several copies of the datapath and issues several instructions in the same cycle. An out-of-order processor looks ahead in the program and runs instructions as soon as their inputs are ready, not in the order they were written.

The page runs one short MIPS program, the one from Harris & Harris Figures 7.69–7.71, on three 2-wide machines, one per tab. Step through it one clock cycle at a time. The table at the bottom fills in cycle by cycle, and the box on the right gives the cycle count and IPC of the same program on all three machines.

lw  $t0, 40($s0)
add $t1, $t0, $s1
sub $t0, $s2, $s3
and $t2, $s4, $t0
or  $t3, $s5, $s6
sw  $s7, 80($t3)

All three machines issue at most 2 instructions per cycle, at most one of them a lw or sw (there is one data memory port). An ALU instruction's result can be used by an instruction issued in the next cycle (forwarding). A lw takes 2 cycles, so an instruction that needs its value must wait one extra cycle.

The in-order superscalar

The first tab issues instructions in program order, two at a time when it can. When an instruction cannot issue, everything behind it waits too, even instructions that are ready. In the program above, add needs the value lw loads, so it waits until cycle 3, and so do sub, and, or and sw behind it (Demo 2: in-order):

CycleIssuedWhy the others wait
1lwadd needs $t0 from lw; the rest are behind it
2–lw takes 2 cycles
3add, suband is the third instruction (only 2 per cycle)
4and, orsw is the third
5sw

Six instructions in 5 cycles: IPC 1.2. With a program whose instructions do not depend on each other (H&H Figure 7.68, Demo 3: independent), the same machine issues two every cycle: 6 instructions in 3 cycles, IPC 2. How much a wider machine gains depends on the program, not on the hardware alone.

RAW, WAR and WAW

Two instructions depend on each other when they use the same register and at least one of them writes it. Demo 1: dependences finds all five in the program:

KindMeaningIn the programRemoved by renaming?
RAW, read after writea true dependence: a value flows from the writer to the readerlw→add ($t0), sub→and ($t0), or→sw ($t3)no
WAR, write after readthe younger instruction must not overwrite a register an older one still has to readadd reads $t0, then sub writes ityes
WAW, write after writethe younger write must be the one that stayslw and sub both write $t0yes

WAR and WAW are name dependences: no value passes between the two instructions. sub just reuses the name $t0 for a new, unrelated value. In program order they cause no trouble; they only matter once instructions are allowed to run out of order.

The six instructions with their dependences: RAW arrows lw to add on $t0, sub to and on $t0, or to sw on $t3; a WAR arrow add to sub on $t0 and a WAW arrow lw to sub on $t0
Three true dependences (RAW) pass a value; the WAR and WAW only reuse the name $t0, which renaming removes.

Out-of-order issue with a scoreboard

The second tab keeps several instructions in an issue queue (the window) and, each cycle, issues the oldest ones whose operands are ready, wherever they are in the queue. A scoreboard tracks which register is waiting for which instruction. Because there is still only one register per name, it must also respect the name dependences: an instruction may not write a register an older, unissued instruction still has to read (WAR), nor one an older instruction has not written yet (WAW).

In Demo 4: WAR stall, or issues in cycle 1 next to lw, and sw in cycle 2, both ahead of add. But sub is held back until cycle 3: it is ready, but it would overwrite $t0 before add has read the loaded value. and, which needs sub's $t0, follows in cycle 4. Six instructions in 4 cycles: IPC 1.5. The "Not issued this cycle, and why" list on the canvas names the reason for every instruction that waits.

Register renaming

The MIPS program can only name 32 registers, but the hardware can have many more physical registers. Register renaming gives every result a fresh one. The rename table says which physical register currently holds each architectural register; the free list holds the unused ones. When an instruction enters the window, its sources are looked up in the rename table and its destination gets the next free register, which then becomes the table's entry for that name.

The program before and after renaming: lw writes p7, add reads p7 and writes p8, sub writes p9 instead of $t0, and reads p9, or writes p11, sw reads p11
After renaming, the loaded $t0 lives in p7 and sub's new $t0 in p9, so sub no longer has to wait for add.

Here $t0–$t6 start in p0–p6 and p7–p15 are free. lw writes p7, add reads p7, and sub writes p9 instead of overwriting the loaded value; and reads p9. The WAR and the WAW are gone; only the three RAW dependences remain (Demo 6: renaming):

CycleScoreboard (tab 2)Renaming (tab 3)
1lw, orlw, sub
2swand, or
3add, subadd, sw
4and

Six instructions in 3 cycles: IPC 2, the most a 2-wide machine can do.

Two issue slots per cycle for each machine: in order needs 5 cycles with empty slots while add waits for lw; the scoreboard fills more slots in 4 cycles; with renaming every slot is filled and the program issues in 3 cycles
The same six instructions need 5 cycles in order, 4 with a scoreboard and 3 with renaming, when every issue slot is filled.

The reorder buffer and in-order commit

If instructions finish in any order, what is "the state of the machine" when an exception or a mispredicted branch happens? The reorder buffer (ROB) answers that. Instructions enter it in program order. They execute and finish out of order, writing their results only to physical registers. Then they commit from the head of the ROB, in program order, up to 2 per cycle: only then is the result part of the architectural state, and only then does a sw write memory. A finished instruction behind an unfinished one waits ("done" in the table).

Committing an instruction also frees a physical register: not its own, but the one that held the previous value of its destination, which no instruction can read any more. That is why each ROB entry remembers the old physical register (the "old" column). In Demo 6, lw commits in cycle 3 and returns p0, the old $t0, to the free list. The last commit is in cycle 6, three cycles after the last result.

Hiding a cache miss

When a lw misses in the cache it takes much longer, here 6 cycles. An in-order machine stops at the first instruction that needs the value; an out-of-order machine keeps issuing the independent instructions behind it (Demo 5: load miss):

Load-miss programCyclesIPC
(a) in order100.8
(b) out of order, 8-entry window81.0
(c) out of order + renaming, 8-entry ROB81.0
(c) with a 4-entry ROB90.89

The machine can only run ahead as far as its window reaches. In Demo 7: full ROB the 4-entry ROB fills with lw, add, sub and and in cycle 1; sub and and finish early, but nothing commits while the lw at the head is still waiting for memory, so or cannot even enter until cycle 7. Real processors have ROBs of 200 or more entries for this reason.

Speculation and squashing

The front end does not wait for a branch to resolve: a branch predictor guesses, and fetching continues on the guessed path. The renaming machine also executes those instructions speculatively, because nothing they do is final until they commit. In the branch program, lw loads 0, so beq $t0, $zero, L is taken. With the prediction not taken (Demo 8: mispredict), add, sub, and and or from the fall-through path run in cycles 1–3. In cycle 3 the branch resolves taken: every ROB entry younger than the branch is squashed. Walking the ROB from the youngest entry back to the branch undoes each rename ($t0 goes back to p7, the loaded value, and so on) and returns p8–p11 to the free list. Fetch restarts at L in cycle 4.

A wrong guess costs the same 5 cycles as not speculating at all. A right guess (set prediction: taken) lets and and or run under the lw: 3 cycles instead of 5. The first two tabs never speculate; nothing behind an unresolved branch issues there.

All programs on all machines

Program(a) in order(b) scoreboard(c) renaming + ROB
H&H 7.69, with dependences5 cycles, IPC 1.24 cycles, IPC 1.53 cycles, IPC 2 (last commit: cycle 6)
H&H 7.68, independent3, IPC 23, IPC 23, IPC 2
Load miss (8-entry window)10, IPC 0.88, IPC 1.08, IPC 1.0
Branch, mispredicted5, IPC 0.85, IPC 0.85, IPC 0.8 (4 squashed)
Branch, predicted right5, IPC 0.85, IPC 0.83, IPC 1.33

Cycles are counted as in the book, from the first issue to the last result. IPC counts only correct-path instructions.

What the page leaves out

  • The front end is idealised: the whole program (or as much as fits in the window) is fetched and decoded at once, with no fetch width, no instruction cache and no decode or rename pipeline stages.
  • No memory dependences: no load reads an address an older store writes, so loads and stores never need to be ordered. Real machines have a load/store queue for that.
  • Only the $t registers are drawn in the rename table; $s registers are only read and stay where they are.
  • The squash walks the ROB; many real processors instead keep a checkpoint of the rename table at each branch and restore it in one cycle. There is no branch predictor table, only a fixed guess.
  • No reservation stations or result buses (Tomasulo's algorithm), no issue-queue size separate from the ROB, no limit on register-file ports, no exceptions.
  • Multithreading and multiprocessors (H&H 7.7.7–7.7.8) are not shown.

The same program on simpler machines: single-cycle, multicycle and pipelined MIPS.