Scribd
Upload
3 views21 pages

Tomasulo Example

The document provides a detailed example of the Tomasulo algorithm, illustrating the execution of various instructions over multiple cycles. It includes a dependency graph, operation latencies, and the status of instructions, reservation stations, and register results throughout the execution process. The document highlights the handling of true dependencies, antidependence, and output dependence in a pipeline architecture.

Uploaded by

ahsanrazasha
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views21 pages

Tomasulo Example

The document provides a detailed example of the Tomasulo algorithm, illustrating the execution of various instructions over multiple cycles. It includes a dependency graph, operation latencies, and the status of instructions, reservation stations, and register results throughout the execution process. The document highlights the handling of true dependencies, antidependence, and output dependence in a pipeline architecture.

Uploaded by

ahsanrazasha
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Tomasulo Example Dependency graph

LD F6,34(R2) LD1 LD2


LD F2,45(R3)
MULTI F0,F2,F4
SUBD F8,F6,F2
DIVD F10,F0,F6 SUBD MULT
ADDD F6,F8,F2

ADDD DIVD

True dependency
Antidependence
Output dependence

• Operation latencies: load/store 2 cycles,


• Add/sub 2 cycles, Mult 10 cycles, divide 40 cycle

1
Adapted from David A. Patterson Spring 98
Tomasulo Example Cycle 0
Instruction status Execution Write
Instruction j k Issue complete Result Busy Address
LD F6 34+ R2 Load1 No
LD F2 45+ R3 Load2 No
MULT F0 F2 F4 Load3 No
SUBD F8 F6 F2
DIVD F10 F0 F6
ADDD F6 F8 F2
Reservation Stations S1 S2 RS for j RS for k
Name Busy Op Vj Vk Qj Qk
Add1 No
Add2 No
Add3 No
Mult1 No
Mult2 No
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
0 FU

• RS entries for loads shown separately


• Qj labelled as RS for j meaning the RS entry where j will come
from
• S1 and S2 are labels for values/results corresponding to Vj and
Vk
2
Adapted from David A. Patterson Spring 98
Tomasulo Example Cycle 1

Instruction status Execution Write


Instruction j k Issue complete Result Busy Address
LD F6 34+ R2 1 Load1 No
Yes 34+R2
LD F2 45+ R3 Load2 No
MULT F0 F2 F4 Load3 No
SUBD F8 F6 F2
DIVD F10 F0 F6
ADDD F6 F8 F2
Reservation Stations S1 S2 RS for j RS for k
Name Busy Op Vj Vk Qj Qk
Add1 No
Add2 No
Add3 No
Mult1 No
Mult2 No
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
1 FU Load1

3
Adapted from David A. Patterson Spring 98
Tomasulo Example Cycle 2

Instruction status Execution Write


Instruction j k Issue complete Result Busy Address
LD F6 34+ R2 1 Load1 Yes 34+R2
LD F2 45+ R3 2 Load2 Yes 45+R3
MULT F0 F2 F4 Load3 No
SUBD F8 F6 F2
DIVD F10 F0 F6
ADDD F6 F8 F2
Reservation Stations S1 S2 RS for j RS for k
Name Busy Op Vj Vk Qj Qk
Add1 No
Add2 No
Add3 No
Mult1 No
Mult2 No
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
2 FU Load2 Load1

4
Adapted from David A. Patterson Spring 98
Tomasulo Example Cycle 3
Instruction status Execution Write
Instruction j k Issue complete Result Busy Address
LD F6 34+ R2 1 3 Load1 Yes 34+R2
LD F2 45+ R3 2 Load2 Yes 45+R3
MULT F0 F2 F4 3 Load3 No
SUBD F8 F6 F2
DIVD F10 F0 F6
ADDD F6 F8 F2
Reservation Stations S1 S2 RS for j RS for k
Name Busy Op Vj Vk Qj Qk
Add1 No
Add2 No
Add3 No
Mult1 Yes MULTD R(F4) Load2
Mult2 No
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
3 FU Mult1 Load2 Load1

• Note: registers names are removed (“renamed”) in Reservation


Stations
• R(F4) means that value from F4 is provided to the RS through
operand bus
• Load1 completing, which instruction is waiting for Load1?
5
Adapted from David A. Patterson Spring 98
Tomasulo Example Cycle 4
Instruction status Execution Write
Instruction j k Issue complete Result Busy Address
LD F6 34+ R2 1 3 4 Load1 No
LD F2 45+ R3 2 4 Load2 Yes 45+R3
MULT F0 F2 F4 3 Load3 No
SUBD F8 F6 F2 4
DIVD F10 F0 F6
ADDD F6 F8 F2
Reservation Stations S1 S2 RS for j RS for k
Name Busy Op Vj Vk Qj Qk
Add1 Yes SUBD M(34+R2) Load2
Add2 No
Add3 No
Mult1 Yes MULTD R(F4) Load2
Mult2 No
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
4 FU Mult1 Load2 M(34+R2) Add1

• Load2 completing; SUBD and MULTD waiting for it


• M(34+R2) means value red from memory address (34+R2)
• Note: Add1 gets value for j directly from CDB, WAR hazard eliminated!
6
Adapted from David A. Patterson Spring 98
Tomasulo Example Cycle 5

Instruction status Execution Write


Instruction j k Issue complete Result Busy Address
LD F6 34+ R2 1 3 4 Load1 No
LD F2 45+ R3 2 4 5 Load2 No
MULT F0 F2 F4 3 Load3 No
SUBD F8 F6 F2 4
DIVD F10 F0 F6 5
ADDD F6 F8 F2
Reservation Stations S1 S2 RS for j RS for k
Name Busy Op Vj Vk Qj Qk
Add1 Yes SUBD M(34+R2) M(45+R3)
Add2 No
Add3 No
Mult1 Yes MULTD M(45+R3) R(F4)
Mult2 Yes DIVD M(34+R2) Mult1
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
5 FU Mult1 M(45+R3) M(34+R2) Add1 Mult2

Similarly, MULT2 gets its value k directly from CDB, WAR hazard eliminated!

7
Adapted from David A. Patterson Spring 98
Tomasulo Example Cycle 6

Instruction status Execution Write


Instruction j k Issue complete Result Busy Address
LD F6 34+ R2 1 3 4 Load1 No
LD F2 45+ R3 2 4 5 Load2 No
MULT F0 F2 F4 3 Load3 No
SUBD F8 F6 F2 4
DIVD F10 F0 F6 5
ADDD F6 F8 F2 6
Reservation Stations S1 S2 RS for j RS for k
Name Busy Op Vj Vk Qj Qk
Add1 Yes SUBD M(34+R2) M(45+R3)
Add2 Yes ADDD M(45+R3) Add1
Add3 No
Mult1 Yes MULTD M(45+R3) R(F4)
Mult2 Yes DIVD M(34+R2) Mult1
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
6 FU Mult1 M(45+R3) Add2 Add1 Mult2

Register status for F6 updated by Add2; WAW hazard eliminated!

8
Adapted from David A. Patterson Spring 98
Tomasulo Example Cycle 7

Instruction status Execution Write


Instruction j k Issue complete Result Busy Address
LD F6 34+ R2 1 3 4 Load1 No
LD F2 45+ R3 2 4 5 Load2 No
MULT F0 F2 F4 3 Load3 No
SUBD F8 F6 F2 4 7
DIVD F10 F0 F6 5
ADDD F6 F8 F2 6
Reservation Stations S1 S2 RS for j RS for k
Name Busy Op Vj Vk Qj Qk
Add1 Yes SUBD M(34+R2) M(45+R3)
Add2 Yes ADDD M(45+R3) Add1
Add3 No
Mult1 Yes MULTD M(45+R3) R(F4)
Mult2 Yes DIVD M(34+R2) Mult1
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
7 FU Mult1 M(45+R3) Add2 Add1 Mult2

• Add1 completing; Add2 is waiting for it!


9
Adapted from David A. Patterson Spring 98
Tomasulo Example Cycle 8
Instruction status Execution Write
Instruction j k Issue complete Result Busy Address
LD F6 34+ R2 1 3 4 Load1 No
LD F2 45+ R3 2 4 5 Load2 No
MULT F0 F2 F4 3 Load3 No
SUBD F8 F6 F2 4 7 8
DIVD F10 F0 F6 5
ADDD F6 F8 F2 6
Reservation Stations S1 S2 RS for j RS for k
Name Busy Op Vj Vk Qj Qk
Add1 No
Add2 Yes ADDD M()-M() M(45+R3)
Add3 No
Mult1 Yes MULTD M(45+R3) R(F4)
Mult2 Yes DIVD M(34+R2) Mult1
Register result statu
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
8 FU Mult1 M(45+R3) Add2 M()-M() Mult2

• M()-M() means result of memory location M(45+R3) subtracted from


M(34+R32)

10
Adapted from David A. Patterson Spring 98
Tomasulo Example Cycle 9

Instruction status Execution Write


Instruction j k Issue complete Result Busy Address
LD F6 34+ R2 1 3 4 Load1 No
LD F2 45+ R3 2 4 5 Load2 No
MULT F0 F2 F4 3 Load3 No
SUBD F8 F6 F2 4 7 8
DIVD F10 F0 F6 5
ADDD F6 F8 F2 6
Reservation Stations S1 S2 RS for j RS for k
Name Busy Op Vj Vk Qj Qk
Add1 No
Add2 Yes ADDD M()–M() M(45+R3)
Add3 No
Mult1 Yes MULTD M(45+R3) R(F4)
Mult2 Yes DIVD M(34+R2) Mult1
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
9 FU Mult1 M(45+R3) Add2 M()–M() Mult2

11
Adapted from David A. Patterson Spring 98
Tomasulo Example Cycle 10

Instruction status Execution Write


Instruction j k Issue complete Result Busy Address
LD F6 34+ R2 1 3 4 Load1 No
LD F2 45+ R3 2 4 5 Load2 No
MULT F0 F2 F4 3 Load3 No
SUBD F8 F6 F2 4 7 8
DIVD F10 F0 F6 5
ADDD F6 F8 F2 6 10
Reservation Stations S1 S2 RS for j RS for k
Name Busy Op Vj Vk Qj Qk
Add1 No
Add2 Yes ADDD M()–M() M(45+R3)
Add3 No
Mult1 Yes MULTD M(45+R3) R(F4)
Mult2 Yes DIVD M(34+R2) Mult1
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
10 FU Mult1 M(45+R3) Add2 M()–M() Mult2

• Add2 completing; what is waiting for it? Nothing!


12
Adapted from David A. Patterson Spring 98
Tomasulo Example Cycle 11

Instruction status Execution Write


Instruction j k Issue complete Result Busy Address
LD F6 34+ R2 1 3 4 Load1 No
LD F2 45+ R3 2 4 5 Load2 No
MULT F0 F2 F4 3 Load3 No
SUBD F8 F6 F2 4 7 8
DIVD F10 F0 F6 5
ADDD F6 F8 F2 6 10 11
Reservation Stations S1 S2 RS for j RS for k
Name Busy Op Vj Vk Qj Qk
Add1 No
Add2 No
Add3 No
Mult1 Yes MULTD M(45+R3) R(F4)
Mult2 Yes DIVD M(34+R2) Mult1
Register result statu
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
11 FU Mult1 M(45+R3) (M-M)+M() M()-M() Mult2

• Write result of ADDD is result of SUBD (itself sum of two memory


locations) plus memory location (45+R3)
13
Adapted from David A. Patterson Spring 98
Tomasulo Example Cycle 12

I n s t r u c t i o n s t a tu s Execution Write
I ns t ru c t io n j k Issue complete Result Busy Address
LD F6 34+ R2 1 3 4 Load1 No
LD F2 45+ R3 2 4 5 Load2 No
M U L F0 F2 F4 3 Load3 No
SU B F8 F6 F2 4 7 8
DIVD F10 F0 F6 5
ADD F6 F8 F2 6 10 11
R e s e r v a t i o n St a t io n s S1 S2 R S for j R S for k
Nam Bus Op Vj Vk Qj Qk
e
Add1 N o
Add2 No
Add3 No
M u l t 1 Ye s M U L T M( 45 +R3) R(F4)
M u l t 2 Ye s DIVD M ( 3 4 + R 2 ) Mult1
R e g i s t e r r e s u lt s ta t us
Clock F0 F2 F4 F6 F8 F 1 0 F 1 2 ... F30
12 FU Mult1 M( 4 5 + R3 ) (M-M)+M() M()–M Mult2

14
Adapted from David A. Patterson Spring 98
Tomasulo Example Cycle 13

Instruction status Execution Write


Instruction j k Issue complete Result Busy Address
LD F6 34+ R2 1 3 4 Load1 No
LD F2 45+ R3 2 4 5 Load2 No
MULT F0 F2 F4 3 Load3 No
SUBD F8 F6 F2 4 7 8
DIVD F10 F0 F6 5
ADDD F6 F8 F2 6 10 11
Reservation Stations S1 S2 RS for j RS for k
Name Busy Op Vj Vk Qj Qk
Add1 No
Add2 No
Add3 No
Mult1 Yes MULTD M(45+R3) R(F4)
Mult2 Yes DIVD M(34+R2) Mult1
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
13 FU Mult1 M(45+R3) (M–M)+M() M()–M() Mult2

15
Adapted from David A. Patterson Spring 98
Tomasulo Example Cycle 14

Instruction status Execution Write


Instruction j k Issue complete Result Busy Address
LD F6 34+ R2 1 3 4 Load1 No
LD F2 45+ R3 2 4 5 Load2 No
MULT F0 F2 F4 3 Load3 No
SUBD F8 F6 F2 4 7 8
DIVD F10 F0 F6 5
ADDD F6 F8 F2 6 10 11
Reservation Stations S1 S2 RS for j RS for k
Name Busy Op Vj Vk Qj Qk
Add1 No
Add2 No
Add3 No
Mult1 Yes MULTD M(45+R3) R(F4)
Mult2 Yes DIVD M(34+R2) Mult1
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
14 FU Mult1 M(45+R3) (M–M)+M() M()–M() Mult2

16
Adapted from David A. Patterson Spring 98
Tomasulo Example Cycle 15

Instruction status Execution Write


Instruction j k Issue complete Result Busy Address
LD F6 34+ R2 1 3 4 Load1 No
LD F2 45+ R3 2 4 5 Load2 No
MULT F0 F2 F4 3 15 Load3 No
SUBD F8 F6 F2 4 7 8
DIVD F10 F0 F6 5
ADDD F6 F8 F2 6 10 11
Reservation Stations S1 S2 RS for j RS for k
Name Busy Op Vj Vk Qj Qk
Add1 No
Add2 No
Add3 No
Mult1 Yes MULTD M(45+R3) R(F4)
Mult2 Yes DIVD M(34+R2) Mult1
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
15 FU Mult1 M(45+R3) (M–M)+M() M()–M() Mult2

• Mult1 completing; Mult2 is waiting for it!

17
Adapted from David A. Patterson Spring 98
Tomasulo Example Cycle 16

Instruction status Execution Write


Instruction j k Issue complete Result Busy Address
LD F6 34+ R2 1 3 4 Load1 No
LD F2 45+ R3 2 4 5 Load2 No
MULT F0 F2 F4 3 15 16 Load3 No
SUBD F8 F6 F2 4 7 8
DIVD F10 F0 F6 5
ADDD F6 F8 F2 6 10 11
Reservation Stations S1 S2 RS for j RS for k
Name Busy Op Vj Vk Qj Qk
Add1 No
Add2 No
Add3 No
Mult1 No
Mult2 Yes DIVD M*F4 M(34+R2)
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
16 FU M*F4 M(45+R3) (M–M)+M() M()–M() Mult2

• Just waiting for divide

18
Adapted from David A. Patterson Spring 98
Tomasulo Example Cycle 55

Instruction status Execution Write


Instruction j k Issue complete Result Busy Address
LD F6 34+ R2 1 3 4 Load1 No
LD F2 45+ R3 2 4 5 Load2 No
MULT F0 F2 F4 3 15 16 Load3 No
SUBD F8 F6 F2 4 7 8
DIVD F10 F0 F6 5
ADDD F6 F8 F2 6 10 11
Reservation Stations S1 S2 RS for j RS for k
Name Busy Op Vj Vk Qj Qk
Add1 No
Add2 No
Add3 No
Mult1 No
Mult2 Yes DIVD M*F4 M(34+R2)
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
55 FU M*F4 M(45+R3) (M–M)+M() M()–M() Mult2

19
Adapted from David A. Patterson Spring 98
Tomasulo Example Cycle 56

Instruction status Execution Write


Instruction j k Issue complete Result Busy Address
LD F6 34+ R2 1 3 4 Load1 No
LD F2 45+ R3 2 4 5 Load2 No
MULT F0 F2 F4 3 15 16 Load3 No
SUBD F8 F6 F2 4 7 8
DIVD F10 F0 F6 5 56
ADDD F6 F8 F2 6 10 11
Reservation Stations S1 S2 RS for j RS for k
Name Busy Op Vj Vk Qj Qk
Add1 No
Add2 No
Add3 No
Mult1 No
Mult2 Yes DIVD M*F4 M(34+R2)
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
56 FU M*F4 M(45+R3) (M–M)+M() M()–M() Mult2

• Mult 2 completing; what is waiting for it?


20
Adapted from David A. Patterson Spring 98
Tomasulo Example Cycle 57

Instruction status Execution Write


Instruction j k Issue complete Result Busy Address
LD F6 34+ R2 1 3 4 Load1 No
LD F2 45+ R3 2 4 5 Load2 No
MULT F0 F2 F4 3 15 16 Load3 No
SUBD F8 F6 F2 4 7 8
DIVD F10 F0 F6 5 56 57
ADDD F6 F8 F2 6 10 11
Reservation Stations S1 S2 RS for j RS for k
Name Busy Op Vj Vk Qj Qk
Add1 No
Add2 No
Add3 No
Mult1 No
Mult2 No
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
57 FU M*F4 M(45+R3) (M–M)+M() M()–M() M*F4/M

• In-order issue, out-of-order execution, completion

21
Adapted from David A. Patterson Spring 98

You might also like