Illustration of the H&P Version of Tomasulo's Algorithm
Instructions:
S1: addd F0,F2,F4 |
S2: multd F2,F6,F8 |
S3: multd F10,F0,F2 |
S4: addd F0,F12,F14 |
t=0, t=1, t=2, t=3, t=4, t=5, t=6, t=7, t=8, t=9, t=10, t=11, t=12
name |
name |
Op |
Vj |
Vk |
Qj |
Qk |
Etime |
mult1 |
|||||||
mult2 |
|||||||
add1 |
add |
regs[F2] |
regs[F4] |
||||
add2 |
Register
F0 |
|||||||
add1 |
name |
Op |
Vj |
Vk |
Qj |
Qk |
Etime |
Inst |
mult1 |
mult |
regs[F6] |
regs[F8] |
S2 |
|||
mult2 |
|||||||
add1 |
add |
regs[F2] |
regs[F4] |
1 |
S1 |
||
add2 |
Register
F0 |
F2 |
|||||
add1 |
mult1 |
t=2:Issue S3, S2 executes, S1 completes
name |
Op |
Vj |
Vk |
Qj |
Qk |
Etime |
Inst |
mult1 |
mult |
regs[F6] |
regs[F8] |
1 |
S2 |
||
mult2 |
mult |
add1 |
mult1 |
S3 |
|||
add1 |
add |
regs[F2] |
regs[F4] |
2 |
S1 |
||
add2 |
Registers
F0 |
F2 |
F10 |
|||
add1 |
mult1 |
mult2 |
t=3: Issue S4, S3 waits for mult1, S2 executes, S1 writes to CDB
name |
Op |
Vj |
Vk |
Qj |
Qk |
Etime |
Inst |
mult1 |
mult |
regs[F6] |
regs[F8] |
2 |
S2 |
||
mult2 |
mult |
data from add1 |
mult1 |
S3 |
|||
add1 |
|||||||
add2 |
add |
regs[F12] |
regs[F14] |
S4 |
Register
F0 |
F2 |
F10 |
|||
add2 |
mult1 |
mult2 |
t=4: S4 executes, S3 waits for mult1, S2 executes
name |
Op |
Vj |
Vk |
Qj |
Qk |
Etime |
Inst |
mult1 |
mult |
regs[F6] |
regs[F8] |
3 |
S2 |
||
mult2 |
mult |
data from add1 |
mult1 |
S3 |
|||
add1 |
|||||||
add2 |
add |
regs[F12] |
regs[F14] |
1 |
S4 |
Register
F0 |
F2 |
F10 |
|||
add2 |
mult1 |
mult2 |
t=5: S4 completes, S3 waits for mult1, S2 completes
name |
Op |
Vj |
Vk |
Qj |
Qk |
Etime |
Inst |
mult1 |
mult |
regs[F6] |
regs[F8] |
4 |
S2 |
||
mult2 |
mult |
data from add1 |
mult1 |
S3 |
|||
add1 |
|||||||
add2 |
add |
regs[F12] |
regs[F14] |
2 |
S4 |
Register
F0 |
F2 |
F10 |
|||
add2 |
mult1 |
mult2 |
t=6: S4 writes to CDB, S3 waits for mult1, S2 waits for CDB
name |
Op |
Vj |
Vk |
Qj |
Qk |
Etime |
Inst |
mult1 |
mult |
regs[F6] |
regs[F8] |
4 |
S2 |
||
mult2 |
mult |
data from add1 |
mult1 |
S3 |
|||
add1 |
|||||||
add2 |
Register
F0 |
F2 |
F10 |
|||
mult1 |
mult2 |
t=7: S3 waits for mult1, S2 writes to CDB
name |
Op |
Vj |
Vk |
Qj |
Qk |
Etime |
Inst |
mult1 |
|||||||
mult2 |
mult |
data from add1 |
data from mult1 |
mult1 |
S3 |
||
add1 |
|||||||
add2 |
Register
F0 |
F2 |
F10 |
|||
mult2 |
name |
Op |
Vj |
Vk |
Qj |
Qk |
Etime |
Inst |
mult1 |
|||||||
mult2 |
mult |
data from add1 |
data from mult1 |
mult1 |
1 |
S3 |
|
add1 |
|||||||
add2 |
Register
F0 |
F2 |
F10 |
|||
mult2 |
name |
Op |
Vj |
Vk |
Qj |
Qk |
Etime |
Inst |
mult1 |
|||||||
mult2 |
mult |
data from add1 |
data from mult1 |
mult1 |
2 |
S3 |
|
add1 |
|||||||
add2 |
Register
F0 |
F2 |
F10 |
|||
mult2 |
name |
Op |
Vj |
Vk |
Qj |
Qk |
Etime |
Inst |
mult1 |
|||||||
mult2 |
mult |
data from add1 |
data from mult1 |
mult1 |
3 |
S3 |
|
add1 |
|||||||
add2 |
Register
F0 |
F2 |
F10 |
|||
mult2 |
name |
Op |
Vj |
Vk |
Qj |
Qk |
Etime |
Inst |
mult1 |
|||||||
mult2 |
mult |
data from add1 |
data from mult1 |
mult1 |
4 |
S3 |
|
add1 |
|||||||
add2 |
Register:
F0 |
F2 |
F10 |
|||
mult2 |
name |
Op |
Vj |
Vk |
Qj |
Qk |
Etime |
Inst |
mult1 |
|||||||
mult2 |
|||||||
add1 |
|||||||
add2 |
Registers
F0 |
F2 |
F10 |
|||