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 not the order but the result: the answers have to be the ones the written order would have produced. So the machine tracks which instruction needs which value, runs whatever is ready, and commits them in order at the end. Committing is the word that matters: the results are not shuffled back into place afterwards, they are held until every earlier instruction has finished, which is also what lets an interrupt land somewhere the program can be restarted from.
What a processor actually does
A processor fetches an instruction, works out what it says, does that one small thing, and moves to the next. Add these two numbers. Put this number there. If that number is zero, carry on somewhere else. That is the job, and it repeats a few billion times a second.
Everything that looks like cleverness is arrangement around that loop: keeping the next instruction ready before it is asked for, keeping recently used numbers close by, letting a slow part and a fast part work at once. The machines here are those arrangements, and most of them exist because one part of the machine is thousands of times slower than another.
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 1964 scoreboard, which overlaps what it can and still waits where a register is one place
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 what each machine waited for: a value that did not exist yet, a register somebody still had to read, a register somebody else was writing. 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 real out-of-order processor has a second half this page does not: 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 the machine could not be interrupted, debugged or recovered, 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.