Prev (Scoreboard) Next (Modern processors)
MULTD F4,F2,F2 ADDD F2,F0,F6contains an anti-dependence since the first instruction reads from F2 and the second instruction writes to F2 (a WAR hazard). However, there is no data dependence, as is shown by the code below (assumin F8 is unused):
MULTD F4,F2,F2 ADDD F8,F0,F6The anti-dependence is removed without changing the semantics of the code simply by changing the F2 to an F8. However, we don't have to use F8, we can use any available register. In fact, suppose there were some physical registers in the chip that the instruction set was not aware of, i.e. there were some extra registers. We can use those extra registers and leave the rest for the compiler to play with. This is what register renaming is; it allows the hardware to detect a name dependence and eliminate it by storing the result of an instruction somewhere else. Thus, with register renaming,
MULTD F4,F2,F2 ADDD F2,F0,F6the add can execute and finish before the multiply starts even though looking at the code suggests that would result in an erroneous answer.
Tomasulo's algorithm implements register renaming through the use of what are called reservation stations. Reservation stations are buffers which fetch and store instruction operands as soon as they're available. Source operands point to either the register file or to other reservation stations. Each reservation station corresponds to one instruction. Once all source operands are available, the instruction is sent for execution, provided a functional unit is also available. Once execution is complete, the result is buffered at the reservation station. Thus, unlike in scoreboarding where the functional unit would stall during a WAR hazard, the functional unit is free to execute another instruction. The reservation station then sends the result to the register file and any other reservation station which is waiting on that result. WAW hazards are handled since only the last instruction (in program order) actually writes to the registers. The other results are buffered in other reservation stations and are eventually sent to any instructions waiting for those results. WAR hazards are handled since reservation stations can get source operands from either the register file or other reservation stations (in other words, from another instruction). In Tomasulo's algorithm, the control logic is distributed among the reservation stations, whereas in scoreboarding, the scoreboard keeps track of everything.
Prev (Scoreboard) Next (Modern processors)