Out-of-order execution: Foundations — Hardware deep dive

This page assumes you have seen nothing. Before you can read Out-of-order execution, you must own every word and symbol it throws at you. We build them one at a time, each from the one before.

0. What is an "instruction"? (the atom of everything)

The picture: think of a to-do list on paper. Each line is one job.

R1 = R2 + R3    ; line 1: add
R4 = R1 * R5    ; line 2: multiply

Here R1, R2, ... are registers — tiny named storage boxes inside the CPU that hold one number each. R1 = R2 + R3 means "take the number in box R2, add the number in box R3, put the answer in box R1."

Why the topic needs this: everything OoOE does is rearranging these list lines. If you do not picture the list, nothing else lands.

1. Program order — the written sequence

The picture: reading the to-do list straight down, in order.

Why it matters: OoOE deliberately breaks this order while running, then restores the appearance of it. So "program order" is the promise the CPU must keep even while secretly disobeying it.

2. Latency and cycles — why waiting even happens

The picture below: a timeline of ticks (columns) with instructions occupying boxes. A slow instruction is a long box.

Why the topic needs this: if every instruction took the same tiny time, there would be little reason to reorder. It is precisely the huge spread in latencies (1 cycle vs 100+) that makes the CPU want to fill the waiting time with other work. This is the same waiting-problem you first met in 5.1.01-Pipelining.

3. Dependency — when one line truly needs another

This is the heart. An instruction depends on another when it needs a value the other one produces.

Example:

R1 = R2 + R3    ; A: produces R1
R4 = R1 * R5    ; B: reads R1  -> B truly depends on A

The picture: an arrow from A to B meaning "value flows here." You cannot delete this arrow — it is real data flow.

WAW (Write-After-Write): both write the same box.
WAR (Write-After-Read): one writes a box a later-in-order one already read.

R1 = R2 + R3    ; A: writes R1
R1 = R6 - R7    ; C: also writes R1  -> WAW, but A and C share NO real data

The picture: A and C both point into the same box R1, but there is no arrow between A and C. The clash is only over the name of the box, not over any number.

Why the topic needs this distinction: true dependencies are the unbreakable skeleton; false ones are removable clutter. The entire trick of OoOE (5.3.04-Register-renaming) is to erase the false ones so only the true skeleton limits speed.

4. Architectural vs physical registers — the name/box split

The relationship, in symbols: $(physical register count) ≫ (architectural register count)$ Here $≫$ is read "much greater than"— not just bigger, but bigger by a large factor.

The picture: 32 labelled name-tags (architectural) but a big pool of 168 unlabelled boxes (physical). A little map decides which tag currently points to which box.

Why the topic needs this: because there are more real boxes than names, the CPU can give each write its own private box. That is why renaming is even possible. Full mechanics live in 5.3.04-Register-renaming.

5. The Common Data Bus (CDB) and "snooping"

Once instructions run out of order, a finished result must reach everyone still waiting for it, fast.

The picture: one loudspeaker (the bus) announcing "instruction P3's answer is 42!", and a room full of listeners; only those who needed P3 react.

We can write the wake-up rule in plain symbols. Let $I$ be a waiting instruction with an operand tagged as coming from producer $P_{j}$ . When $P_{j}$ broadcasts value $V$ : $if operand of I is tagged P_{j} \Rightarrow operand \leftarrow V, ready \leftarrow true$

Read the symbols:

$\Rightarrow$ means "implies / then"
$\leftarrow$ means "gets set to"
$ready$ is a true/false flag: does this operand have its value yet?

Why broadcast to all at once instead of one-by-one? Because several instructions may wait on the same result. Waking them in parallel avoids a slow chain of one-at-a-time nudges.

6. Logic symbols — reading the ready condition

The parent writes: $Ready (I) = Ready (src_{1}) \land Ready (src_{2})$

Decode every piece:

$Ready (I)$ — a true/false question: "==is instruction $I$ allowed to run?=="
$src_{1}, src_{2}$ — the two input operands (the two values it adds/multiplies).
$\land$ — logical AND: true only when both sides are true.

So in plain words: an instruction is ready exactly when both of its inputs are ready. Simple, but you must own $\land$ and the true/false idea to read it.

7. In-order commit and precise exceptions

Running out of order means finishing out of order too. But the outside world must never see the mess.

The picture: a queue where instructions may compute in any order in the back rooms, but they can only walk out the front door (commit) one at a time, in the original order. If the one at the door faulted, everyone behind it is thrown away, never having really "happened."

Why the topic needs this: it is the promise that lets OoOE stay invisible. It also underpins 5.3.03-Speculative-execution, where the CPU runs guesses that must be discardable.

8. IPC — the scoreboard we are trying to raise

The picture: instructions completed (numerator) divided by ticks elapsed (denominator). Filling idle ticks with useful work raises IPC. Squeezing more instructions per cycle is exactly 7.1.01-Instruction-level-parallelism, and doing several at once needs 5.3.01-Superscalar-architecture.

How the foundations feed the topic

Read top to bottom: raw atoms (instructions, order, latency) create the dependency idea; dependencies motivate renaming (physical boxes + RAT); renaming plus the ready rule and broadcast bus make out-of-order running possible; in-order commit keeps it safe; and the payoff is higher IPC.

Equipment checklist

Test yourself — cover the right side and answer aloud before revealing.

What is an instruction, in one phrase?

A single tiny CPU command (e.g. add, load) — programs are lists of them.

What does "program order" mean?

The exact top-to-bottom order the programmer wrote the instructions.

What is a clock cycle vs latency?

A cycle is one tick of the clock; latency is how many ticks an instruction needs.

Which dependency is real and cannot be removed?

The true (RAW) dependency — B reads what A wrote.

Which dependencies are fake and how are they removed?

WAR and WAW — caused by reusing a register name; removed by giving a fresh physical register (renaming).

Why are there more physical registers than architectural ones?

So each write can get its own private box, killing false name-clash dependencies.

What does the RAT do?

Maps each architectural register name to the physical box it currently means.

Read

Ready (I) = Ready (src_{1}) \land Ready (src_{2})

in words.

An instruction is ready only when BOTH its input operands are ready.

What symbol is "much greater than" and where is it used?

≫

— physical registers

≫

architectural registers.

What does the Common Data Bus do, and what is snooping?

The CDB broadcasts a finished result to all waiting stations at once; snooping is each station listening for the tag it needs.

Why must commit happen in program order?

To keep precise exceptions and make the reordering invisible to the outside world.

What is IPC and why do we care?

Instructions finished per clock cycle — the throughput scoreboard OoOE tries to raise.

Next: with these atoms in hand, return to Out-of-order execution and read the Tomasulo section — every symbol there now has a meaning and a picture.