A simple pipeline is a queue with rigid manners: instructions execute in exactly the order the compiler wrote them, and if one instruction stalls — waiting on a slow multiply, or a value still travelling back from memory — everybody behind it waits too, even the ones that have nothing to do with the stall. That is the tragedy of in-order execution: a single traffic jam freezes a whole road of cars that could happily have taken the next exit.
Dynamic scheduling is the hardware's answer. The processor is allowed to look a little way down the instruction stream, notice which instructions are ready — their inputs are available and a functional unit is free — and run those now, letting them slip past a stalled instruction ahead of them. The program still means the same thing; it just isn't executed in textbook order. This is the seed of every high-performance CPU built since, and it was born in 1964 in Seymour Cray's CDC 6600 and its scoreboard.
Consider four instructions, where
The
The scoreboard is a central bookkeeper. Instructions are issued in order from the queue, but once issued each one lives at its own functional unit and proceeds independently. The scoreboard watches every register and every unit, and answers one question over and over: is it safe to let this instruction take its next step yet? Because the divide and the subtract live at different units, they run in parallel and finish in whatever order their latencies dictate.
Scoreboarding replaces the single "execute" step with four bookkept stages. An instruction may not advance to the next stage until the scoreboard clears it:
| Stage | What happens | The scoreboard blocks it until… |
|---|---|---|
| 1. Issue | decode; allocate a functional unit | the needed unit is free and no other active instruction targets the same destination register (avoids a WAW hazard) |
| 2. Read operands | read source registers | both sources are available (no pending write to them) — this resolves RAW |
| 3. Execute | the functional unit computes | — (runs freely; may take many cycles) |
| 4. Write result | write the destination register | no earlier instruction still needs to read the old value of that register (avoids a WAR hazard) |
Notice what has appeared. On a plain in-order pipeline the only data hazard that mattered was RAW (a true dependence). The moment we let instructions execute and finish out of order, two new hazards crawl out of the woodwork — and the scoreboard's stall conditions in stages 1 and 4 exist precisely to police them.
Every pair of instructions that touch the same register can conflict in one of three ways. Only one is a real dependence; the other two are accidents of reusing register names.
WAR and WAW are false dependences: they exist only because the two instructions happened
to be assigned the same architectural register name, not because any value truly flows between them. The
scoreboard copes by stalling — a blunt but correct tool. The next lesson,
Run the little model below. It walks our four instructions through an in-order machine and then a dynamically-scheduled one, counting the cycles wasted waiting behind the slow divide.
The saving is real, but so is the cost: the scoreboard is a chunk of hardware that must track the status of every instruction, every register, and every functional unit, and check a web of conditions every cycle. Seymour Cray spent that silicon in 1964 and made the fastest computer in the world. The idea never left.
The 6600's scoreboard resolved a RAW hazard by making the consumer wait until the producer had written the register file, then read it in stage 2. There was no forwarding path to hand the result directly from one unit to the next. So even a ready result sat one extra beat in the register file before its consumer could grab it. Worse, the scoreboard's stall conditions for WAR and WAW meant instructions could block at issue or block at write-back purely over reused register names — throughput lost to bookkeeping, not to real work. Tomasulo's design a few years later fixed both: results are broadcast directly to waiting instructions, and renaming makes the WAR/WAW stalls disappear. Scoreboarding was the brilliant first draft.
A scoreboard issues in order but lets instructions execute and write back out of order.
Students often conclude the program's meaning can change — it cannot. The hardware only reorders
instructions it has proven independent; every true (RAW) dependence is still honoured to the
letter, and WAR/WAW are policed by stalls. The visible result is exactly what in-order execution
would produce, just sooner. Reordering is an optimisation you are never supposed to be able to observe —
until, decades later, speculation makes tiny timing leaks observable, which is a story for the
Scoreboarding gives us the core bargain of instruction-level parallelism: issue in order, execute out of order, and let independent work overlap a stall. Its weaknesses — no result forwarding, and stalls on false (WAR/WAW) dependences — are exactly what the next generation of designs attacks. Tomasulo's algorithm adds a common data bus that broadcasts results the instant they are ready, and register renaming that abolishes false dependences altogether. Everything modern — superscalar issue, the reorder buffer, speculation — is built on the foundation you have just seen.