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.
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
What 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.
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.