Out of Order
A processor can run your instructions in an order you did not write, and finish sooner, as long as the answer is the same. Thornton's CDC 6600 did it in 1964 with a scoreboard. Tomasulo's 360/91 did it in 1967 with renaming. They differ over one thing: whether a register name is a place. This page runs one program through both and counts the cycles.
New to instructions running out of order? Start here
The order you wrote and the order the processor runs are two different things. If an instruction is waiting on memory and the next three do not depend on it, running them now costs nothing and saves the wait.
What must be preserved is the result: the answers have to be the ones the written order would have produced. This model tracks which instruction needs which value and which register name still belongs to its result. Renaming removes waits caused only by reusing a name. Modern processors add in-order commitment for precise interrupts and recovery; this model does not implement that stage.
What a processor actually does
A processor fetches an instruction, works out what it says, carries out the operation, and chooses the next instruction. Add these numbers. Read this address. If this value is zero, branch there. Then the cycle repeats.
Caches, pipelines and schedulers arrange work around that cycle. They can change when an operation runs or how long it waits for data. The instruction cycle is the starting point; each machine explains which arrangement it models.
The machine for this idea on its own is Stored Program, if you would rather press it than read about it.
Two answers, three years apart
1 The program, and the three kinds of wait found in it by comparing operands
Four instructions. The last column is what each one has to wait for, found by comparing operands rather than written down beside them.
| # | Instruction | Cycles | Waits on |
|---|
RAW is a real dependency: the value does not exist yet. WAR and WAW are not. They exist only because two instructions were assigned the same register, and a register is one place.
2 Running them in order, which costs the sum of the latencies and overlaps nothing
Pick a machine. Everything below is scheduled from it, cycle by cycle.
3 The machine you picked, cycle by cycle, and what each instruction waited for
DerivedWhat does with them
| # | Instruction | Starts | Finishes | Waited for |
|---|
4 The 1967 renaming, and the waits that stop existing once a register name is not a place
All three, side by side
| Machine | Cycles | For a value | To read | To write |
|---|
The three right-hand columns count the waits each model records against a value or a register: a value that did not exist yet, a register somebody still had to read, a register somebody else was writing. Running in order records none, because every instruction is already waiting for the one in front. The last two are the whole difference. Renaming does not make arithmetic faster; it removes the waits that were never about arithmetic.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| the program contains all three kinds of hazard | yes | 2 RAW, 1 WAR, 1 WAW, found by reading it |
| a scoreboard finishes sooner than running them in order | yes | 22 cycles in order, 20 with the scoreboard |
| and renaming finishes sooner than the scoreboard | yes | 20 with the scoreboard, 14 with renaming |
| renaming removes exactly the stalls that came from sharing a register | yes | the scoreboard took 2 (1 WAR, 1 WAW); renaming takes 0 |
| and never removes a read-after-write stall | yes | 1 on the scoreboard, 2 with renaming: taking away a false dependency can expose a real one, never the other way round |
| all three leave the registers holding the same values | yes | f6 = 35, f8 = 5, f0 = 21 |
| no instruction reads a value before it has been produced | yes | every read-after-write respected in all three |
| running in order costs the sum of the latencies, nothing overlapping | yes | scheduler says 22, the latencies add to 22 |
| and renaming costs the longest chain of real dependencies | yes | scheduler says 14, the longest read-after-write chain costs 14 |
What is real here, and what is not
Neither machine is being emulated
The CDC 6600 had ten functional units, a specific issue restriction and its own timings; the 360/91 had reservation stations, a common data bus and different timings again. Nothing here reproduces either. What is modelled is the one rule they disagree about: whether reusing a register NAME forces an ordering. A scoreboard has to honour both kinds of name dependency, an earlier reader against a later writer and two writers against each other; renaming removes both while leaving every real value dependency alone. An earlier version of this entry described only the two-writers case and the page's own table reported one of each, which an outside review noticed.
The latencies are chosen, and shared, and that is what makes the comparison mean anything
Twelve cycles for a divide and two for an add are plausible and are not measurements. The comparison is valid because every model here uses the SAME numbers, so the difference between the totals is the algorithm and nothing else. This page never says what either real machine would have taken, because it does not know.
There is no speculation, no branch prediction and no memory here
All of those matter enormously on real hardware and none of them changes which stalls renaming removes. A page that added them would be a worse explanation of the one thing this is about.
The renaming model keeps the tag, because without it renaming is simply wrong
Dropping the write-after-write stall on its own lets an earlier instruction's result land last and leave the register holding the wrong value. On a 360/91 it does not, because issuing an instruction tags its destination and a result whose tag no longer matches is discarded. The tag is what makes the removal safe. This was caught by the check that all three models leave the same values, on a version of this page that had removed the stall and not modelled the tag.
Sound: no
Cycles here are a count, not a duration anybody could hear, and the studio's rule is that a sound has to carry the measurement rather than decorate it.
Nothing retires here, so nothing can be precise
Instructions finish in this model when their inputs are ready and a unit is free, and that is where they are done. A modern out-of-order processor has a second half this page does not, and neither 1960s machine had: a reorder buffer that holds every completed result until every earlier instruction has also completed, and commits them in program order. That is what makes an interrupt precise, which is to say what makes it possible to say which instruction the program was on. Without it the speedup counted here is real and precise interruption and recovery are outside the model, and those are most of what the reorder buffer costs transistors for.
Sources
- R. M. Tomasulo, An Efficient Algorithm for Exploiting Multiple Arithmetic Units, IBM Journal of Research and Development 11(1), January 1967 — the common data bus and the register tags.
- J. E. Thornton, Design of a Computer: The Control Data 6600, Scott Foresman, 1970 — the scoreboard and the conditions under which it holds an instruction.
- Logical Art, the studio this belongs to.