Tomasulo's Algorithm
An Efficient Algorithm for Exploiting Multiple Arithmetic Units, R. M. Tomasulo, IBM Journal, January 1967
instructions and it’s execution plan would be like this.
div Rg, Rb, Rc
add Rh, Rg, Rd (data hazard)
mul Rg, Re, Rf
add Ra, Rh, Rg (data hazard)
then, we should maintain RS(Reservation Station) for 2nd and 4th instructions because those instruction need to wait for previous result. and, RS may look like this. source operands of the 1st instruction are ready and the result would be tagged T1 for register Rg and then put this tag T1 and mark busy bit into register till the result comes out. but the first operand of 2nd instruction is not ready when this instruction decode. it need to wait for Rg which is tagged for T1 by previous instruction. by looking up the register, we can figure out. if busy bit is set, the register is not available. so, we should wait for this tagged result.
| Ready | Tag | Contents | Ready | Tag | Contents | Register |
| Y | Rb | Y | Rc | T1 | ||
| N | T1 | Y | Rd | T2 | ||
| Y | Re | Y | Rf | T3 | ||
| N | T2 | N | T3 | T4 |
RS and register will watch the result bus to get tagged result. for this example, we will get T1 first then 2nd instruction will be ready to go. when we got 2nd tagged result(T3), left operand of 4th instruction will be ready and the busy bit of the register Rg will be marked free(N).
| busy | Tab | register |
| Y | T4 | Ra |
| Y | T2 | Rh |
| N | T3 | Rg |