Illustration of the H&P Version of the Scoreboard 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,t=13
Name |
Busy |
Op |
Fi |
Fj |
Fk |
Qj |
Qk |
Rj |
Rk |
Et |
Inst |
|---|---|---|---|---|---|---|---|---|---|---|---|
Mult1 |
|||||||||||
Mult2 |
|||||||||||
Add1 |
yes |
add |
F0 |
F2 |
F4 |
yes |
yes |
S1 |
|||
Add2 |
Register
F0 |
F2 |
||||||||||
add1 |
t=1: Issue S2, S1 reads operands
Name |
Busy |
Op |
Fi |
Fj |
Fk |
Qj |
Qk |
Rj |
Rk |
Et |
Inst |
|---|---|---|---|---|---|---|---|---|---|---|---|
Mult1 |
yes |
mult |
F2 |
F6 |
F8 |
yes |
yes |
S2 |
|||
Mult2 |
|||||||||||
Add1 |
yes |
add |
F0 |
F2 |
F4 |
no |
no |
S1 |
|||
Add2 |
Register
F0 |
F2 |
||||||||||
add1 |
mult1 |
t=2: Issue S3, S2 reads operands, S1 begins execution
Name |
Busy |
Op |
Fi |
Fj |
Fk |
Qj |
Qk |
Rj |
Rk |
Et |
Inst |
mult1 |
yes |
mult |
F2 |
F6 |
F8 |
no |
no |
S2 |
|||
mult2 |
yes |
mult |
F10 |
F0 |
F2 |
add1 |
mult1 |
no |
no |
S3 |
|
add1 |
yes |
add |
F0 |
F2 |
F4 |
no |
no |
1 |
S1 |
||
add2 |
Register
F0 |
F2 |
F10 |
|||||||||
add1 |
mult1 |
mult2 |
t=3:Can't issue S4 as S1 has not written to F0 yet. S3 is waiting, for results of S1 and S2. S2 begins execution. S1 finishes execution.
Name |
Busy |
Op |
Fi |
Fj |
Fk |
Qj |
Qk |
Rj |
Rk |
E Time |
Inst |
|---|---|---|---|---|---|---|---|---|---|---|---|
mult1 |
yes |
mult |
F2 |
F6 |
F8 |
no |
no |
1 |
S2 |
||
mult2 |
yes |
mult |
F10 |
F0 |
F2 |
add1 |
mult1 |
no |
no |
S3 |
|
add1 |
yes |
add |
F0 |
F2 |
F4 |
no |
no |
2 |
S1 |
||
add2 |
Register
F0 |
F2 |
F10 |
|||||||||
add1 |
mult1 |
mult2 |
t=4: Can't issue S4 as S1 has not written to F0 yet. S3 is waiting, for results of S1 and S2. S1 writes back.
Name |
Busy |
Op |
Fi |
Fj |
Fk |
Qj |
Qk |
Rj |
Rk |
E Time |
Inst |
|---|---|---|---|---|---|---|---|---|---|---|---|
mult1 |
yes |
mult |
F2 |
F6 |
F8 |
no |
no |
2 |
S2 |
||
mult2 |
yes |
mult |
F10 |
F0 |
F2 |
add1 |
mult1 |
yes |
no |
S3 |
|
add1 |
no |
||||||||||
add2 |
Register
F0 |
F2 |
F10 |
|||||||||
mult1 |
mult2 |
t=5: S4 issues. S3 is waiting, for results of S2.
Name |
Busy |
Op |
Fi |
Fj |
Fk |
Qj |
Qk |
Rj |
Rk |
E Time |
Inst |
mult1 |
yes |
mult |
F2 |
F6 |
F8 |
no |
no |
3 |
S2 |
||
mult2 |
yes |
mult |
F10 |
F0 |
F2 |
add1 |
mult1 |
yes |
no |
S3 |
|
add1 |
yes |
add |
F0 |
F12 |
F14 |
yes |
yes |
S4 |
|||
add2 |
Register:
F0 |
F2 |
F10 |
|||||||||
add1 |
mult1 |
mult2 |
t=6: S4 reads operands, S3 is waiting for S2. S2 finishes
Name |
Busy |
Op |
Fi |
Fj |
Fk |
Qj |
Qk |
Rj |
Rk |
E Time |
Inst |
|---|---|---|---|---|---|---|---|---|---|---|---|
mult1 |
yes |
mult |
F2 |
F6 |
F8 |
no |
no |
4 |
S2 |
||
mult2 |
yes |
mult |
F10 |
F0 |
F2 |
add1 |
mult1 |
yes |
no |
S3 |
|
add1 |
yes |
add |
F0 |
F12 |
F14 |
no |
no |
S4 |
|||
add2 |
Register
F0 |
F2 |
F10 |
|||||||||
add1 |
mult1 |
mult2 |
t=7:S4 begins to execute,S2 writes back operands, S3 has all needed operands
Name |
Busy |
Op |
Fi |
Fj |
Fk |
Qj |
Qk |
Rj |
Rk |
E Time |
Inst |
|---|---|---|---|---|---|---|---|---|---|---|---|
mult1 |
no |
||||||||||
mult2 |
yes |
mult |
F10 |
F0 |
F2 |
add1 |
mult1 |
yes |
yes |
S3 |
|
add1 |
yes |
add |
F0 |
F12 |
F14 |
no |
no |
1 |
S4 |
||
add2 |
Register
F0 |
F2 |
F10 |
|||||||||
add1 |
mult2 |
t=8: S4 finishes execution,S3 reads operands
Name |
Busy |
Op |
Fi |
Fj |
Fk |
Qj |
Qk |
Rj |
Rk |
E Time |
Inst |
mult1 |
no |
||||||||||
mult2 |
yes |
mult |
F10 |
F0 |
F2 |
add1 |
mult1 |
no |
no |
S3 |
|
add1 |
yes |
add |
F0 |
F12 |
F14 |
no |
no |
2 |
S4 |
||
add2 |
Register
F0 |
F2 |
F10 |
|||||||||
add1 |
mult2 |
t=9: S4 writes back, S3 begins to execute
Name |
Busy |
Op |
Fi |
Fj |
Fk |
Qj |
Qk |
Rj |
Rk |
E Time |
Inst |
mult1 |
no |
||||||||||
mult2 |
yes |
mult |
F10 |
F0 |
F2 |
add1 |
mult1 |
no |
no |
1 |
S3 |
add1 |
no |
||||||||||
add2 |
Register
F0 |
F2 |
F10 |
|||||||||
mult2 |
Name |
Busy |
Op |
Fi |
Fj |
Fk |
Qj |
Qk |
Rj |
Rk |
E Time |
Inst |
mult1 |
no |
||||||||||
mult2 |
yes |
mult |
F10 |
F0 |
F2 |
add1 |
mult1 |
no |
no |
2 |
S3 |
add1 |
no |
||||||||||
add2 |
Register
F0 |
F2 |
F10 |
|||||||||
mult2 |
Name |
Busy |
Op |
Fi |
Fj |
Fk |
Qj |
Qk |
Rj |
Rk |
E Time |
Inst |
mult1 |
no |
||||||||||
mult2 |
yes |
mult |
F10 |
F0 |
F2 |
add1 |
mult1 |
no |
no |
3 |
S3 |
add1 |
no |
||||||||||
add2 |
Register
F0 |
F2 |
F10 |
|||||||||
mult2 |
Name |
Busy |
Op |
Fi |
Fj |
Fk |
Qj |
Qk |
Rj |
Rk |
E Time |
Inst |
mult1 |
no |
||||||||||
mult2 |
yes |
mult |
F10 |
F0 |
F2 |
add1 |
mult1 |
no |
no |
4 |
S3 |
add1 |
no |
||||||||||
add2 |
Register
F0 |
F2 |
F10 |
|||||||||
mult2 |
Name |
Busy |
Op |
Fi |
Fj |
Fk |
Qj |
Qk |
Rj |
Rk |
E Time |
Inst |
mult1 |
no |
||||||||||
mult2 |
no |
||||||||||
add1 |
no |
||||||||||
add2 |
Register
F0 |
F2 |
F10 |
|||||||||