Out-of-order execution — Tomasulo algorithm (conceptual): Foundations

Before you can read the parent note on Tomasulo's algorithm, you need a small pile of vocabulary. The parent note throws around words like register, tag, hazard, broadcast, and functional unit as if you already own them. This page builds every one of them from nothing, in an order where each idea rests strictly on the one before it — no word is used before it is defined.

1. What is an instruction, really?

Throughout the parent note you see lines like:

I1: ADD.D F2, F4, F6    ; F2 = F4 + F6

Let us read this out loud, piece by piece, so no symbol sneaks past:

I1 — a label we invented meaning "instruction number 1". Purely for talking about it.
ADD.D — the operation (the "op"). .D means "double-precision floating-point" — a way of storing real numbers (like 3.5 or -0.0072) in 64 bits of binary, not decimal digits. The .D just tells you the size and format of the numbers; it does not change how Tomasulo schedules anything. The parent calls this field Op.
F2 — the destination: where the answer is stored.
F4, F6 — the sources: the two inputs that get added.
Everything after ; is a human comment.

So I1 means: take whatever is in F4, add whatever is in F6, put the result in F2.

The names F0, F2, F4, ... are registers — our next brick.

2. Registers — the CPU's tiny hand-labelled boxes

Figure — Out-of-order execution — Tomasulo algorithm (conceptual)

Look at the figure: a row of five labelled cups sits on the counter, each with its painted name (F0, F2, F4, F6, F8) on top and a value inside — except F2, drawn with a ? because nothing has been poured into it yet. Notice the orange arrow: it points into a cup, showing the only allowed move — pour a new number in. There is no arrow that creates a cup, because the label is painted on and the set of cups is fixed. F0 is always cup F0; you cannot manufacture a sixth cup.

3. Memory, "load", and "store" — the slow warehouse

The parent links this idea to Cache Misses & Memory Latency — that page explains why memory is slow.

4. A cycle — the CPU's heartbeat

Time in this whole topic is counted in ticks. When later sections say "only one result per cycle", they mean one result per tick.

5. Functional units — the specialist cooks

In the figure, three separate boxes — a blue Adder, an orange Multiplier, a green Load unit — each show a little job label inside them. Notice they are drawn side by side, and the grey double-headed arrow labelled "parallel" spans all three: that spacing is the whole point. Because each cook has their own station, all three boxes can be lit up in the same cycle. This is why out-of-order execution is even possible: if two independent instructions need different units, they can genuinely run at the same time. If everything needed the one adder, reordering would gain nothing.

This is the seed of Superscalar Execution — having many units so many instructions finish per cycle, easing exactly these structural conflicts.

6. Dependency — when one instruction NEEDS another

Let's build all three from pictures, because the parent's whole trick rests on telling the real one from the fakes.

Definition RAW — Read After Write (the REAL one)

B reads a register that A wrote. B genuinely needs A's produced value.

I1: F2 = F4 + F6      ; writes F2
I2: F0 = F2 * F8      ; READS F2  ← needs I1's actual result

This is real data flow. No trick removes it — you must wait.

Definition WAR — Write After Read (a FAKE one)

A later instruction writes a register that an earlier one still needs to read. If the later write happens first, the earlier read gets the wrong (new) value.

I2: ... = F0 + F8     ; still needs to READ F8
I3: F8 = ...          ; WRITES F8  ← must not overwrite before I2 reads

Notice: there's no data flowing from I2 to I3. They just share the cup named F8.

Definition WAW — Write After Write (a FAKE one)

Two instructions write the same register. The final value in the cup must be the later instruction's, not whichever finishes last by luck.

I2: F6 = ...          ; writes F6
I4: F6 = ...          ; writes F6 too  ← the cup must end up holding I4's value

Study the figure side by side. On the left, a solid green arrow runs from I1 down to I2: it is labelled "real data (juice flows)" because I2 literally consumes the number I1 produced — that is RAW. On the right, a dashed red arrow connects I2 and I3: the caption stresses "same cup F8 only — no juice". Nothing is produced and consumed; the two instructions merely fight over the name F8. The green header reads "TRUE dependency"; the red header reads "FAKE — a rename kills it". That visual contrast — solid = real data, dashed = mere name clash — is the single most important thing to carry forward.

7. Tags — private names invented on the fly

8. Reservation station — a waiting room with a memo pad

The parent lists the memo fields: Busy (is this slot occupied?), Op (which operation), Vj/Vk (the two operand values, if ready), Qj/Qk (the two operand tags, if still waiting), and A (a memory address, for the load/store buffers of Section 3).

Definition The sentinel "0" in Qj/Qk, and how a value gets INTO Vj/Vk

Qj and Qk are tag slots. We reserve the special value 0 (sometimes drawn as blank/null) to mean "no tag — I am NOT waiting on anyone; my value in Vj/Vk is real and ready." Any non-zero entry names an actual producer (e.g. Qj = Add1) still owed. How does a real value land in Vj/Vk? Two ways:

At operand capture (issue time): when the operand's register is already ready (its status says "no pending producer" — see Section 9), the hardware reads the register file right then and copies that number straight into Vj (or Vk), setting the matching Qj/Qk = 0. The value is grabbed once, at issue.
Later, by snooping: if the operand was NOT ready at issue, Qj held a producer's tag; when that producer finishes and announces its result (Section 9), this RS copies the announced value into Vj and flips Qj to 0.

The letters j and k are just "operand 1" and "operand 2" — arbitrary labels, like calling two things "left" and "right". Nothing mysterious.

9. Register status table (Qi) and the Common Data Bus (CDB)

Now for the wire that carries finished results back to everyone waiting:

10. In-order Issue, out-of-order Execute, then Write Result

Everything above was the vocabulary. Here is the machine that uses it. There are three stages every instruction passes through — the parent's mnemonic "I E W".

Definition The three stages

Issue — admit the instruction (strictly in program order), claim a free reservation station of the right type (a tag is borrowed from the pool here), capture each ready operand into Vj/Vk and record each not-ready operand's producer tag into Qj/Qk (this is operand capture from Section 8), and set Qi[dest] = thisRS (the sticky note). If no RS of the needed type is free, the instruction stalls — this is exactly the structural hazard of Section 5 on the issue side.
Execute — compute the result, but only once Qj == 0 && Qk == 0 (both operands present). Done in any order. If several RS entries are ready but the functional unit can serve only one this cycle, the hardware arbitrates (e.g. oldest first) — the structural hazard on the execute side.
Write Result (write-back) — the moment the functional unit finishes, put the answer on the CDB as (thisRS_tag, result). Every waiting RS with a matching Qj/Qk snoops it into Vj/Vk and clears that tag to 0; every register with matching Qi stores it and clears Qi to 0; then the RS is freed and its tag returns to the pool (Section 7).

Intuition Why Write must come LAST, and why Issue stays in order

Write cannot precede Execute for a blunt reason: you have nothing to broadcast until the computation has actually produced a value. Write-back is the delivery step — it is how a private result inside one functional unit becomes a value the register file and every dependent instruction can finally see. Skip it, and the answer would be trapped inside the unit forever, and every RS waiting on that tag would wait forever. So the order is forced: you must compute before you can announce, hence Execute strictly precedes Write. Issue stays in order so the sticky notes (Qi) get overwritten in program sequence, guaranteeing the register file reflects the last writer — the WAW guarantee. Reordering is allowed for doing the work (Execute), never for deciding who owns each cup (Issue).

This connects forward to Pipelining and Hazards (where hazards first appear), Scoreboarding (an older, simpler out-of-order scheme), and Reorder Buffer (ROB) (added later to make exceptions precise).

11. Branches — the "which way?" problem Tomasulo can't ignore

The prerequisite map

Read it bottom-up: instructions and registers give you the raw material; slow loads/stores give you the motive; dependencies give you the obstacle; tags and reservation stations give you the tool; the CDB and the I-E-W flow give you the machine; branches show where it must guess.

Equipment checklist

Test yourself — say the answer out loud before revealing.

An instruction's destination and sources

Destination = the register that receives the answer; sources = the registers whose values are the inputs.

What .D denotes on ADD.D

Double-precision floating-point — 64-bit binary real numbers; it sets the data format, not the scheduling.

What a register is, and why there are so few

A tiny fast named storage box inside the CPU; there are few, so programs are forced to reuse names.

The difference between a load and a store

Load copies memory → register (pickup); store copies register → memory (drop-off), and a store must also wait for its data value.

Why a load/store needs to wait before acting

It must first know its address A (often computed from a register), and a store must also have its data value.

Why a load can be slow

It fetches from far-away memory; on a cache miss it can take 100+ cycles.

What a clock cycle measures

One tick of the CPU clock — the unit of time everything is counted in.

What a functional unit is

Hardware that does one kind of operation (adder, multiplier, load unit); several run in parallel.

What a structural hazard is and where Tomasulo meets it

Two ready instructions needing the same unit (or the single CDB) at once; at Issue a missing RS stalls, at Execute the hardware arbitrates and the rest wait.

The three hazard types and which is real

RAW (real data need), WAR and WAW (fake — only shared register names). Only RAW is a true dependency.

What register renaming does

Gives each result a fresh private name (tag) so WAR and WAW collisions disappear.

What a tag is

A temporary name for "the value that a specific reservation station will produce".

Where tags come from and when they are reclaimed

From a finite pool (the RS slots themselves); borrowed at Issue, returned to the pool at Write Result when the RS is freed.

What a reservation station is and what RS abbreviates

RS = reservation station — a waiting slot in front of a functional unit holding an instruction plus its operands (as values or tags).

The two things an RS operand field can hold

Either the actual value (in Vj/Vk) or the tag of the producer it still waits for (in Qj/Qk).

What Qj == 0 means

The sentinel 0 = "no tag, not waiting on anyone" — the operand's value is already sitting in Vj.

How a value first gets into Vj/Vk

At issue, if the register is ready (Qi=0) its value is read from the register file and copied in; otherwise it arrives later via a CDB broadcast the RS snoops.

What the Qi table records and its initial state

For each register, the tag of the RS that will write it next; every Qi starts at 0 (ready) before any instruction runs.

What the CDB is and its limit

Common Data Bus — one shared wire broadcasting (tag, value) to everyone at once; only one broadcast per cycle.

What the three stages I-E-W are

Issue (in order, rename/capture operands), Execute (when both operands ready), Write Result (broadcast on the CDB, free the RS).

Why Write Result must come last

There is nothing to broadcast until Execute has produced a value; Write is the delivery step that lets everyone waiting finally see the result.

Why Issue is in order but Execute is not

In-order Issue keeps "last writer wins" correct (WAW); out-of-order Execute lets ready instructions run without waiting on position.

What a branch/control hazard is and Tomasulo's response

The next instructions are unknown until a branch resolves; the engine predicts, issues speculatively, and squashes those RS entries on a misprediction (ROB added for clean recovery).