Tomasulo's Algorithm - UCF Computer Science

Tomasulo's Algorithm - UCF Computer Science

Dynamic Scheduling Using Tomasulos Algorithm Lotzi Blni EEL 5708 Acknowledgements All the lecture slides were adopted from the slides of David Patterson (1998, 2001) and David E. Culler (2001), Copyright 1998-2002, University of California Berkeley EEL 5708 Dynamic Scheduling A major limitation of the simple pipelining techniques is in-order execution If an instruction is stalled in the pipeline all the instructions behind it must wait Even if there would be enough hardware resources to execute them Solution: Let the instructions behind the stalled instruction proceed Split the Instruction Decode phase of the pipeline into: Issue: decode instruction and check for structural hazards Read operands: wait until no data hazards, then read operands We will have out-of-order execution and out-of-order completion of the instructions. EEL 5708 Problems with dynamic scheduling Out-of-order execution introduces the possibility of WAR and WAW hazards Handled by register renaming Problems with handling exceptions: We dont care about the internals but we expect that a program would generate exactly the same exceptions as if the program would be executed in order. Imprecise exceptions: the right exceptions are generated, but the state of the processor is not the same as if the program would be executed in order. It makes it difficult to recover from exceptions. Precise exceptions can be achieved by speculation. EEL 5708 Tomasulos Algorithm Designed for the IBM 360/91, by Robert Tomasulo Goal: high performance without special compilers IBM 360 had only 4 FP registers Solution: register renaming Why Study? leads to Alpha 21264, HP 8000, MIPS 10000, Pentium II, PowerPC 604, EEL 5708 Tomasulos Algorithm Control & buffers distributed with Function Units (FU) FU buffers called reservation stations; have pending operands Registers in instructions replaced by values or pointers to reservation stations(RS); called register renaming ; avoids WAR, WAW hazards More reservation stations than registers, so can do optimizations compilers cant Results to FU from RS, not through registers, over Common Data Bus that broadcasts results to all FUs Load and Stores treated as FUs with RSs as well Integer instructions can go past branches, allowing FP ops beyond basic block in FP queue EEL 5708

Tomasulo organization EEL 5708 Reservation Station Components OpOperation to perform in the unit (e.g., + or ) Vj, VkValue of Source operands Store buffers has V field, result to be stored Qj, QkReservation stations producing source registers (value to be written) Qj,Qk=0 => ready Store buffers only have Qi for RS producing result BusyIndicates reservation station or FU is busy Register result statusIndicates which functional unit will write each register, if one exists. Blank when no pending instructions that will write that register. EEL 5708 Three Stages of Tomasulo Algorithm 1. Issueget instruction from FP Op Queue If reservation station free (no structural hazard), control issues instr & sends operands (renames registers). 2. Executionoperate on operands (EX) When both operands ready then execute; if not ready, watch Common Data Bus for result 3. Write resultfinish execution (WB) Write on Common Data Bus to all awaiting units; mark reservation station available Normal data bus: data + destination (go to bus) Common data bus: data + source (come from bus) 64 bits of data + 4 bits of Functional Unit source address Write if matches expected Functional Unit (produces result) Does the broadcast EEL 5708 Tomasulo Example Cycle 0 Instruction status Instruction j k Issue LD F6 34+ R2 LD F2 45+ R3 MULTD F0 F2 F4 SUBD F8 F6 F2 DIVDF10 F0 F6 ADDD F6 F8 F2 Reservation Stations Time Name BusyOp 0 Add1 No 0 Add2 No 0 Add3 No 0 Mult1 No

0 Mult2 No Register result status Execution Write complete Result S1 Vj S2 Vk RS for j Qj RS for k Qk Clock F2 F4 F6 F8 0 F0 Busy Address Load1 No Load2 No Load3 No F10 F12 ... F30 FU EEL 5708 Tomasulo Example Cycle 1 Instruction status Instruction j k Issue LD F6 34+ R2 1 LD F2 45+ R3 MULTD F0 F2 F4 SUBDF8 F6 F2 DIVDF10 F0 F6 ADDD F6 F8 F2 Reservation Stations Time Name BusyOp 0 Add1 No 0 Add2 No Add3 No 0 Mult1 No 0 Mult2 No Register result status Clock 1

Execution Write complete Result S1 Vj F0 F2 FU Busy Address Load1 No 34+R2 Yes Load2 No Load3 No S2 Vk RS for j Qj RS for k Qk F4 F6 F8 F10 F12 ... F30 Load1 EEL 5708 Tomasulo Example Cycle 2 Instruction status Instruction j k Issue LD F6 34+ R2 1 LD F2 45+ R3 2 MULTD F0 F2 F4 SUBD F8 F6 F2 DIVDF10 F0 F6 ADDD F6 F8 F2 Reservation Stations Time Name BusyOp 0 Add1 No 0 Add2 No Add3 No 0 Mult1 No 0 Mult2 No Register result status Execution Write complete Result S1 Vj S2 Vk

RS for j Qj RS for k Qk Clock F2 F4 F6 F8 2 F0 FU Load2 Busy Address Load1 Yes 34+R2 Load2 Yes 45+R3 Load3 No F10 F12 ... F30 Load1 EEL 5708 Tomasulo Example Cycle 3 Instruction status Execution Instruction j k Issue complete LD F6 34+ R2 1 3 LD F2 45+ R3 2 MULTD F0 F2 F4 3 SUBD F8 F6 F2 DIVDF10 F0 F6 ADDD F6 F8 F2 Reservation Stations S1 Time Name BusyOp Vj 0 Add1 No 0 Add2 No Add3 No 0 Mult1 Yes MULTD 0 Mult2 No Register result status Write Result Clock

3 F0 F2 FU Mult1 Load2 Busy Address Load1 Yes 34+R2 Load2 Yes 45+R3 Load3 No S2 Vk RS for j Qj R(F4) Load2 F4 F6 RS for k Qk F8 F10 F12 ... F30 Load1 Note: registers names are removed (renamed) in Reservation Stations EEL 5708 Load1 completing; what is waiting for Load1? Tomasulo Example Cycle 4 Instruction status Execution Write Instruction j k Issue complete Result LD F6 34+ R2 1 3 4 LD F2 45+ R3 2 4 MULTD F0 F2 F4 3 SUBDF8 F6 F2 4 DIVDF10 F0 F6 ADDD F6 F8 F2 Reservation Stations S1 S2 Time Name BusyOp Vj Vk 0 Add1 Yes SUBDM(34+R2)

0 Add2 No Add3 No 0 Mult1 Yes MULTD R(F4) 0 Mult2 No Register result status Clock 4 F0 F2 FU Mult1 Load2 F4 Busy Address Load1 No Load2 Yes 45+R3 Load3 No RS for j Qj RS for k Qk Load2 Load2 F6 F8 F10 F12 ... F30 M(34+R2) Add1 Load2 completing; what is waiting for it? EEL 5708 Tomasulo Example Cycle 5 Instruction status Execution Write Instruction j k Issue complete Result LD F6 34+ R2 1 3 4 LD F2 45+ R3 2 4 5 MULTD F0 F2 F4 3 SUBDF8 F6 F2 4 DIVDF10 F0 F6 5 ADDD F6 F8 F2 Reservation Stations S1 S2 RS for j Time Name BusyOp Vj

Vk Qj 2 Add1 Yes SUBDM(34+R2) M(45+R3) 0 Add2 No Add3 No 10 Mult1 Yes MULTD M(45+R3) R(F4) 0 Mult2 Yes DIVD M(34+R2) Mult1 Register result status Clock 5 F0 F2 FU Mult1 M(45+R3) F4 F6 Busy Address Load1 No Load2 No Load3 No RS for k Qk F8 F10 F12 ... F30 M(34+R2) Add1 Mult2 EEL 5708 Tomasulo Example Cycle 6 Instruction status Execution Write Instruction j k Issue complete Result LD F6 34+ R2 1 3 4 LD F2 45+ R3 2 4 5 MULTD F0 F2 F4 3 SUBDF8 F6 F2 4 DIVDF10 F0 F6 5 ADDD F6 F8 F2 6 Reservation Stations S1 S2 RS for j Time Name BusyOp Vj Vk Qj 1 Add1 Yes SUBDM(34+R2) M(45+R3)

0 Add2 Yes ADDD M(45+R3) Add1 Add3 No 9 Mult1 Yes MULTD M(45+R3) R(F4) 0 Mult2 Yes DIVD M(34+R2) Mult1 Register result status Clock 6 F0 F2 FU Mult1 M(45+R3) F4 Busy Address Load1 No Load2 No Load3 No RS for k Qk F6 F8 F10 F12 ... Add2 Add1 Mult2 F30 EEL 5708 Tomasulo Example Cycle 7 Instruction status Execution Write Instruction j k Issue complete Result LD F6 34+ R2 1 3 4 LD F2 45+ R3 2 4 5 MULTD F0 F2 F4 3 SUBDF8 F6 F2 4 7 DIVDF10 F0 F6 5 ADDD F6 F8 F2 6 Reservation Stations S1 S2 RS for j Time Name BusyOp Vj Vk

Qj 0 Add1 Yes SUBDM(34+R2) M(45+R3) 0 Add2 Yes ADDD M(45+R3) Add1 Add3 No 8 Mult1 Yes MULTD M(45+R3) R(F4) 0 Mult2 Yes DIVD M(34+R2) Mult1 Register result status Clock 7 F0 F2 FU Mult1 M(45+R3) F4 Busy Address Load1 No Load2 No Load3 No RS for k Qk F6 F8 Add2 Add1 Mult2 Add1 completing; what is waiting for it? F10 F12 ... F30 EEL 5708 Tomasulo Example Cycle 8 Instruction status Execution Write Instruction j k Issue complete Result LD F6 34+ R2 1 3 4 LD F2 45+ R3 2 4 5 MULTD F0 F2 F4 3 SUBDF8 F6 F2 4 7 8 DIVDF10 F0 F6 5 ADDDF6 F8 F2 6 Reservation Stations S1 S2

RS for j Time Name BusyOp Vj Vk Qj 0 Add1 No 2 Add2 Yes ADDDM()-M() M(45+R3) 0 Add3 No 7 Mult1 Yes MULTD M(45+R3) R(F4) 0 Mult2 Yes DIVD M(34+R2) Mult1 Register result status Clock 8 F0 F2 FU Mult1 M(45+R3) F4 Busy Address Load1 No Load2 No Load3 No RS for k Qk F6 F8 F10 F12 ... Add2 M()-M()Mult2 F30 EEL 5708 Tomasulo Example Cycle 9 Instruction status Execution Write Instruction j k Issue complete Result LD F6 34+ R2 1 3 4 LD F2 45+ R3 2 4 5 MULTD F0 F2 F4 3 SUBDF8 F6 F2 4 7 8 DIVDF10 F0 F6 5 ADDDF6 F8 F2 6 Reservation Stations S1 S2

RS for j Time Name BusyOp Vj Vk Qj 0 Add1 No 1 Add2 Yes ADDDM()M() M(45+R3) 0 Add3 No 6 Mult1 Yes MULTD M(45+R3) R(F4) 0 Mult2 Yes DIVD M(34+R2) Mult1 Register result status Clock 9 F0 F2 FU Mult1 M(45+R3) F4 Busy Address Load1 No Load2 No Load3 No RS for k Qk F6 F8 F10 F12 ... Add2 M()M()Mult2 F30 EEL 5708 Tomasulo Example Cycle 10 Instruction status Execution Write Instruction j k Issue complete Result LD F6 34+ R2 1 3 4 LD F2 45+ R3 2 4 5 MULTD F0 F2 F4 3 SUBDF8 F6 F2 4 7 8 DIVDF10 F0 F6 5 ADDD F6 F8 F2 6 10 Reservation Stations

S1 S2 RS for j Time Name BusyOp Vj Vk Qj 0 Add1 No 0 Add2 Yes ADDDM()M() M(45+R3) 0 Add3 No 5 Mult1 Yes MULTD M(45+R3) R(F4) 0 Mult2 Yes DIVD M(34+R2) Mult1 Register result status Clock 10 F0 F2 FU Mult1 M(45+R3) F4 Busy Address Load1 No Load2 No Load3 No RS for k Qk F6 F8 Add2 M()M()Mult2 Add2 completing; what is waiting for it? F10 F12 ... F30 EEL 5708 Tomasulo Example Cycle 11 Instruction status Execution Write Instruction j k Issue complete Result LD F6 34+ R2 1 3 4 LD F2 45+ R3 2 4 5 MULTD F0 F2 F4 3 SUBDF8 F6 F2 4 7 8 DIVDF10 F0 F6 5 ADDD

F6 F8 F2 6 10 11 Reservation Stations S1 S2 RS for j Time Name BusyOp Vj Vk Qj 0 Add1 No 0 Add2 No 0 Add3 No 4 Mult1 Yes MULTD M(45+R3) R(F4) 0 Mult2 Yes DIVD M(34+R2) Mult1 Register result status Clock 11 F0 F2 FU Mult1 M(45+R3) F4 F6 Busy Address Load1 No Load2 No Load3 No RS for k Qk F8 F10 F12 ... F30 (M-M)+M()M()M()Mult2 EEL 5708 Tomasulo Example Cycle 12 Instruction status Execution Write Instruction j k Issue complete Result LD F6 34+ R2 1 3 4 LD F2 45+ R3 2 4 5 MULTD F0 F2 F4 3 SUBDF8 F6 F2 4 6 7 DIVDF10 F0 F6

5 ADDD F6 F8 F2 6 10 11 Reservation Stations S1 S2 RS for j Time Name BusyOp Vj Vk Qj 0 Add1 No 0 Add2 No 0 Add3 No 3 Mult1 Yes MULTD M(45+R3) R(F4) 0 Mult2 Yes DIVD M(34+R2) Mult1 Register result status Clock 12 F0 F2 FU Mult1 M(45+R3) F4 F6 Busy Address Load1 No Load2 No Load3 No RS for k Qk F8 F10 F12 ... F30 (M-M)+M()M()M()Mult2 Note: all quick instructions complete already EEL 5708 Tomasulo Example Cycle 13 Instruction status Execution Write Instruction j k Issue complete Result LD F6 34+ R2 1 3 4 LD F2 45+ R3 2 4 5 MULTD F0 F2 F4 3 SUBDF8 F6 F2 4

7 8 DIVDF10 F0 F6 5 ADDDF6 F8 F2 6 10 11 Reservation Stations S1 S2 RS for j Time Name BusyOp Vj Vk Qj 0 Add1 No 0 Add2 No Add3 No 2 Mult1 Yes MULTD M(45+R3) R(F4) 0 Mult2 Yes DIVD M(34+R2) Mult1 Register result status Clock 13 F0 F2 FU Mult1 M(45+R3) F4 F6 Busy Address Load1 No Load2 No Load3 No RS for k Qk F8 F10 F12 ... F30 (MM)+M()M()M()Mult2 EEL 5708 Tomasulo Example Cycle 14 Instruction status Execution Write Instruction j k Issue complete Result LD F6 34+ R2 1 3 4 LD F2 45+ R3 2 4 5 MULTD F0 F2 F4 3 SUBDF8 F6 F2 4 7

8 DIVDF10 F0 F6 5 ADDD F6 F8 F2 6 10 11 Reservation Stations S1 S2 RS for j Time Name BusyOp Vj Vk Qj 0 Add1 No 0 Add2 No 0 Add3 No 1 Mult1 Yes MULTD M(45+R3) R(F4) 0 Mult2 Yes DIVD M(34+R2) Mult1 Register result status Clock 14 F0 F2 FU Mult1 M(45+R3) F4 F6 Busy Address Load1 No Load2 No Load3 No RS for k Qk F8 F10 F12 ... F30 (MM)+M()M()M()Mult2 EEL 5708 Tomasulo Example Cycle 15 Instruction status Execution Write Instruction j k Issue complete Result LD F6 34+ R2 1 3 4 LD F2 45+ R3 2 4 5 MULTD F0 F2 F4 3 15 SUBDF8 F6 F2 4

7 8 DIVDF10 F0 F6 5 ADDD F6 F8 F2 6 10 11 Reservation Stations S1 S2 RS for j Time Name BusyOp Vj Vk Qj 0 Add1 No 0 Add2 No Add3 No 0 Mult1 Yes MULTD M(45+R3) R(F4) 0 Mult2 Yes DIVD M(34+R2) Mult1 Register result status Clock 15 F0 F2 FU Mult1 M(45+R3) F4 F6 Busy Address Load1 No Load2 No Load3 No RS for k Qk F8 F10 F12 ... F30 (MM)+M()M()M()Mult2 Mult1 completing; what is waiting for it? EEL 5708 Tomasulo Example Cycle 16 Instruction status Instruction j k Issue LD F6 34+ R2 1 LD F2 45+ R3 2 MULTD F0 F2 F4 3 SUBD F8 F6 F2 4

DIVDF10 F0 F6 5 ADDD F6 F8 F2 6 Reservation Stations Time Name BusyOp 0 Add1 No 0 Add2 No Add3 No 0 Mult1 No 40 Mult2 Yes DIVD Register result status Execution Write complete Result 3 4 4 5 15 16 7 8 Clock 16 F0 10 Busy Address Load1 No Load2 No Load3 No 11 S1 Vj S2 Vk M*F4 M(34+R2) F2 F4 FU M*F4 M(45+R3) Note: Just waiting for divide RS for j Qj RS for k Qk F6 F8 F10 F12 ... F30 (MM)+M()M()M()Mult2

EEL 5708 Tomasulo Example Cycle 55 Instruction status Instruction j k Issue LD F6 34+ R2 1 LD F2 45+ R3 2 MULTD F0 F2 F4 3 SUBDF8 F6 F2 4 DIVDF10 F0 F6 5 ADDDF6 F8 F2 6 Reservation Stations Time Name BusyOp 0 Add1 No 0 Add2 No Add3 No 0 Mult1 No 1 Mult2 Yes DIVD Register result status Clock 55 Execution Write complete Result 3 4 4 5 15 16 7 8 10 11 S1 Vj S2 Vk M*F4 M(34+R2) F0 F2 FU M*F4 M(45+R3) Busy Address Load1 No Load2 No Load3 No F4 RS for j Qj RS for k Qk

F6 F8 F10 F12 ... F30 (MM)+M()M()M()Mult2 EEL 5708 Tomasulo Example Cycle 56 Instruction status Instruction j k Issue LD F6 34+ R2 1 LD F2 45+ R3 2 MULTD F0 F2 F4 3 SUBDF8 F6 F2 4 DIVDF10 F0 F6 5 ADDDF6 F8 F2 6 Reservation Stations Time Name BusyOp 0 Add1 No 0 Add2 No Add3 No 0 Mult1 No 0 Mult2 Yes DIVD Register result status Clock 56 Execution complete 3 4 15 7 56 10 S1 Vj Write Result 4 5 16 8 M*F4 M(34+R2) F0 F2 FU M*F4 M(45+R3) Busy Address Load1 No Load2 No Load3 No

11 S2 Vk F4 RS for j Qj RS for k Qk F6 F8 F10 F12 ... F30 (MM)+M()M()M()Mult2 Mult 2 completing; what is waiting for it? EEL 5708 Tomasulo Example Cycle 57 Instruction status Instruction j k Issue LD F6 34+ R2 1 LD F2 45+ R3 2 MULTD F0 F2 F4 3 SUBD F8 F6 F2 4 DIVDF10 F0 F6 5 ADDD F6 F8 F2 6 Reservation Stations Time Name BusyOp 0 Add1 No 0 Add2 No Add3 No 0 Mult1 No 0 Mult2 No Register result status Execution complete 3 4 15 7 56 10 S1 Vj Write Result 4 5

16 8 57 11 S2 Vk RS for j Qj RS for k Qk Clock F2 F4 F6 F8 57 F0 FU M*F4 M(45+R3) Busy Address Load1 No Load2 No Load3 No F10 F12 ... F30 (MM)+M()M()M()M*F4/M Again, in-order issue, out-of-order execution, completion EEL 5708 Tomasulo Drawbacks Complexity delays of 360/91, MIPS 10000, IBM 620? Many associative stores (CDB) at high speed Performance limited by Common Data Bus Multiple CDBs => more FU logic for parallel assoc stores EEL 5708 Tomasulo Loop Example Loop: LD MULTD SD F4 SUBI BNEZ F0 F4 0 R1 R1 0 R1 F0 F2 R1 R1

#8 Loop Assume Multiply takes 4 clocks Assume first load takes 8 clocks (cache miss?), second load takes 4 clocks (hit) To be clear, will show clocks for SUBI, BNEZ Reality, integer instructions ahead EEL 5708 Loop Example Cycle 0 Instruction status Instruction j k iteration LD F0 0 R1 1 MULTDF4 F0 F2 1 SD F4 0 R1 1 LD F0 0 R1 2 MULTDF4 F0 F2 2 SD F4 0 R1 2 Reservation Stations Time Name Busy Op 0 Add1 No 0 Add2 No 0 Add3 No 0 Mult1 No 0 Mult2 No Register result status ExecutionWrite Issue completeResult S1 Vj S2 Vk Clock F2 F4 0 R1 80 F0 Busy Address Load1 No Load2 No Load3 No Qi

Store1 No Store2 No Store3 No RS for jRS for k Qj Qk Code: LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 SUBI R1 R1 #8 BNEZ R1 Loop F6 F8 F10 F12... F30 Qi EEL 5708 Loop Example Cycle 1 Instruction status Instruction j k iteration LD F0 0 R1 1 MULTDF4 F0 F2 1 SD F4 0 R1 1 LD F0 0 R1 2 MULTDF4 F0 F2 2 SD F4 0 R1 2 Reservation Stations Time Name Busy Op 0 Add1 No 0 Add2 No 0 Add3 No 0 Mult1 No 0 Mult2 No Register result status ExecutionWrite Issue completeResult Busy Address 1 Load1 Yes 80 Load2 No Load3 No Qi Store1 No

Store2 No Store3 No S1 S2 RS for jRS for k Vj Vk Qj Qk Code: LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 SUBI R1 R1 #8 BNEZ R1 Loop Clock F2 1 R1 80 F0 Qi F4 F6 F8 F10 F12... F30 Load1 EEL 5708 Loop Example Cycle 2 Instruction status Instruction j k iteration LD F0 0 R1 1 MULTDF4 F0 F2 1 SD F4 0 R1 1 LD F0 0 R1 2 MULTDF4 F0 F2 2 SD F4 0 R1 2 Reservation Stations Time Name Busy Op

0 Add1 No 0 Add2 No 0 Add3 No 0 Mult1 Yes MULTD 0 Mult2 No Register result status ExecutionWrite Issue completeResult Busy Address 1 Load1 Yes 80 2 Load2 No Load3 No Qi Store1 No Store2 No Store3 No S1 S2 RS for jRS for k Vj Vk Qj Qk Code: LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 R(F2) Load1 SUBI R1 R1 #8 BNEZ R1 Loop Clock F2 2 R1 80 F0 Qi Load1 F4 F6 F8 F10 F12... F30 Mult1 EEL 5708 Loop Example Cycle 3 Instruction status Instruction j k iteration LD F0

0 R1 1 MULTDF4 F0 F2 1 SD F4 0 R1 1 LD F0 0 R1 2 MULTDF4 F0 F2 2 SD F4 0 R1 2 Reservation Stations Time Name Busy Op 0 Add1 No 0 Add2 No 0 Add3 No 0 Mult1 Yes MULTD 0 Mult2 No Register result status ExecutionWrite Issue completeResult Busy Address 1 Load1 Yes 80 2 Load2 No 3 Load3 No Qi Store1 Yes 80 Mult1 Store2 No Store3 No S1 S2 RS for jRS for k Vj Vk Qj Qk Code: LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 R(F2) Load1 SUBI R1 R1 #8 BNEZ R1 Loop Clock F2 3 R1 80 F0

Qi Load1 F4 F6 F8 F10 F12... F30 Mult1 Note: MULT1 has no registers names in RS EEL 5708 Loop Example Cycle 4 Instruction status Instruction j k iteration LD F0 0 R1 1 MULTDF4 F0 F2 1 SD F4 0 R1 1 LD F0 0 R1 2 MULTDF4 F0 F2 2 SD F4 0 R1 2 Reservation Stations Time Name Busy Op 0 Add1 No 0 Add2 No 0 Add3 No 0 Mult1 Yes MULTD 0 Mult2 No Register result status ExecutionWrite Issue completeResult Busy Address 1 Load1 Yes 80 2 Load2 No 3 Load3 No Qi Store1 Yes 80 Mult1 Store2 No Store3 No S1 S2 RS for jRS for k Vj

Vk Qj Qk Code: LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 R(F2) Load1 SUBI R1 R1 #8 BNEZ R1 Loop Clock F2 4 R1 72 F0 Qi Load1 F4 F6 F8 F10 F12... F30 Mult1 EEL 5708 Loop Example Cycle 5 Instruction status Instruction j k iteration LD F0 0 R1 1 MULTDF4 F0 F2 1 SD F4 0 R1 1 LD F0 0 R1 2 MULTDF4 F0 F2 2 SD F4 0 R1 2 Reservation Stations Time Name Busy Op 0 Add1 No 0 Add2 No

0 Add3 No 0 Mult1 Yes MULTD 0 Mult2 No Register result status ExecutionWrite Issue completeResult Busy Address 1 Load1 Yes 80 2 Load2 No 3 Load3 No Qi Store1 Yes 80 Mult1 Store2 No Store3 No S1 S2 RS for jRS for k Vj Vk Qj Qk Code: LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 R(F2) Load1 SUBI R1 R1 #8 BNEZ R1 Loop Clock F2 5 R1 72 F0 Qi Load1 F4 F6 F8 F10 F12... F30 Mult1 EEL 5708 Loop Example Cycle 6 Instruction status k iteration Instruction j LD F0 0 R1 1

MULTD F4 F0 F2 1 SD F4 0 R1 1 LD F0 0 R1 2 MULTD F4 F0 F2 2 SD F4 0 R1 2 Reservation Stations TimeNameBusyOp 0 Add1 No 0 Add2 No 0 Add3 No 0 Mult1 Yes MULTD 0 Mult2 No Register result status Execution Write Issue complete Result BusyAddress 1 Load1 Yes 80 2 Load2 Yes 72 3 Load3 No Qi 6 Store1 Yes 80 Mult1 Store2 No Store3 No S1 S2 RS forRS j for k Vj Vk Qj Qk Code: LD F0 0 R1 MULTD F4 F0 F2 SD F4 0 R1 R(F2) Load1 SUBIR1 R1 #8 BNEZ R1 Loop Clock F2 6 R1 72 F0 Qi

Load2 F4 F6 F8 F10F12... F30 Mult1 Note: F0 never sees Load1 result EEL 5708 Loop Example Cycle 7 Execution Write Instruction status k iteration Issue complete Result Instruction j BusyAddress LD F0 0 R1 1 1 Load1 Yes 80 MULTD F4 F0 F2 1 2 Load2 Yes 72 SD F4 0 R1 1 3 Load3 No Qi LD F0 0 R1 2 6 Store1 Yes 80 Mult1 MULTD F4 F0 F2 2 7 Store2 No SD F4 0 R1 2 Store3 No S1 S2 RS forRS j for k Reservation Stations TimeNameBusyOp Vj Vk Qj Qk Code: 0 Add1 No LD F0 0 R1 0 Add2 No MULTD F4 F0 F2 0 Add3 No

SD F4 0 R1 0 Mult1 Yes MULTD R(F2) Load1 SUBIR1 R1 #8 0 Mult2 Yes MULTD R(F2) Load2 BNEZR1 Loop Register result status Clock 7 R1 72 Qi F0 Load2 F2 F4 Mult2 F6 F8 F10F12... F30 EEL 5708 Loop Example Cycle 8 Instruction status k iteration Instruction j LD F0 0 R1 1 MULTD F4 F0 F2 1 SD F4 0 R1 1 LD F0 0 R1 2 MULTD F4 F0 F2 2 SD F4 0 R1 2 Reservation Stations TimeNameBusyOp 0 Add1 No 0 Add2 No 0 Add3 No 0 Mult1 Yes MULTD 0 Mult2 Yes MULTD Register result status Execution Write Issue complete Result BusyAddress 1 Load1 Yes 80 2 Load2 Yes 72 3 Load3 No

Qi 6 Store1 Yes 80 Mult1 7 Store2 Yes 72 Mult2 8 Store3 No S1 S2 RS forRS j for k Vj Vk Qj Qk Code: LD F0 0 R1 MULTD F4 F0 F2 SD F4 0 R1 R(F2) Load1 SUBIR1 R1 #8 R(F2) Load2 BNEZ R1 Loop Clock F2 8 R1 72 F0 Qi Load2 F4 F6 F8 F10F12... F30 Mult2 EEL 5708 Loop Example Cycle 9 Instruction status Instruction j k LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 LD F0 0 R1 MULTDF4 F0 F2 SD F4

0 R1 Reservation Stations Time Name Busy 0 Add1 No 0 Add2 No 0 Add3 No 0 Mult1 Yes 0 Mult2 Yes Register result status Clock 9 R1 64 Qi MULTD MULTD ExecutionWrite Issue completeResult Busy Address 1 9 Load1 Yes 80 2 Load2 Yes 72 3 Load3 No Qi 6 Store1 Yes 80 Mult1 7 Store2 Yes 72 Mult2 8 Store3 No S1 S2 RS for jRS for k Vj Vk Qj Qk Code: LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 R(F2) Load1 SUBI R1 R1 #8 R(F2) Load2 BNEZ R1 Loop F0 F2 iteration 1 1 1 2 2

2 Op Load2 F4 F6 F8 F10 F12... F30 Mult2 Load1 completing; what is waiting for it? EEL 5708 Loop Example Cycle 10 Instruction status Instruction j k LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 Reservation Stations Time Name Busy 0 Add1 No 0 Add2 No 0 Add3 No 4 Mult1 Yes 0 Mult2 Yes Register result status Clock 10 R1 64 Qi MULTD MULTD ExecutionWrite Issue completeResult Busy Address 1 9 10 Load1 No 2 Load2 Yes 72 3 Load3 No Qi 6 10

Store1 Yes 80 Mult1 7 Store2 Yes 72 Mult2 8 Store3 No S1 S2 RS for jRS for k Vj Vk Qj Qk Code: LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 M(80) R(F2) SUBI R1 R1 #8 R(F2) Load2 BNEZ R1 Loop F0 F2 iteration 1 1 1 2 2 2 Op Load2 F4 F6 F8 F10 F12... F30 Mult2 Load2 completing; what is waiting for it? EEL 5708 Loop Example Cycle 11 Instruction status Instruction j k LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 LD F0 0 R1 MULTDF4

F0 F2 SD F4 0 R1 Reservation Stations Time Name Busy 0 Add1 No 0 Add2 No 0 Add3 No 3 Mult1 Yes 4 Mult2 Yes Register result status Clock 11 R1 64 Qi MULTD MULTD ExecutionWrite Issue completeResult Busy Address 1 9 10 Load1 No 2 Load2 No 3 Load3 Yes 64 Qi 6 10 11 Store1 Yes 80 Mult1 7 Store2 Yes 72 Mult2 8 Store3 No S1 S2 RS for jRS for k Vj Vk Qj Qk Code: LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 M(80) R(F2) SUBI R1 R1 #8 M(72) R(F2) BNEZ R1 Loop F0 F2 iteration 1 1 1 2 2

2 Op Load3 F4 F6 F8 F10 F12... F30 Mult2 EEL 5708 Loop Example Cycle 12 Instruction status Instruction j k LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 Reservation Stations Time Name Busy 0 Add1 No 0 Add2 No 0 Add3 No 2 Mult1 Yes 3 Mult2 Yes Register result status Clock 12 R1 64 Qi MULTD MULTD ExecutionWrite Issue completeResult Busy Address 1 9 10 Load1 No 2 Load2 No 3 Load3 Yes 64 Qi 6 10 11 Store1 Yes 80 Mult1 7

Store2 Yes 72 Mult2 8 Store3 No S1 S2 RS for jRS for k Vj Vk Qj Qk Code: LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 M(80) R(F2) SUBI R1 R1 #8 M(72) R(F2) BNEZ R1 Loop F0 F2 iteration 1 1 1 2 2 2 Op Load3 F4 F6 F8 F10 F12... F30 Mult2 EEL 5708 Loop Example Cycle 13 Instruction status Instruction j k LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 Reservation Stations Time Name Busy

0 Add1 No 0 Add2 No 0 Add3 No 1 Mult1 Yes 2 Mult2 Yes Register result status Clock 13 R1 64 Qi MULTD MULTD ExecutionWrite Issue completeResult Busy Address 1 9 10 Load1 No 2 Load2 No 3 Load3 Yes 64 Qi 6 10 11 Store1 Yes 80 Mult1 7 Store2 Yes 72 Mult2 8 Store3 No S1 S2 RS for jRS for k Vj Vk Qj Qk Code: LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 M(80) R(F2) SUBI R1 R1 #8 M(72) R(F2) BNEZ R1 Loop F0 F2 iteration 1 1 1 2 2 2 Op Load3 F4

F6 F8 F10 F12... F30 Mult2 EEL 5708 Loop Example Cycle 14 Instruction status Instruction j k LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 Reservation Stations Time Name Busy 0 Add1 No 0 Add2 No 0 Add3 No 0 Mult1 Yes 1 Mult2 Yes Register result status Clock 14 R1 64 Qi MULTD MULTD ExecutionWrite Issue completeResult Busy Address 1 9 10 Load1 No 2 14 Load2 No 3 Load3 Yes 64 Qi 6 10 11 Store1 Yes 80 Mult1 7 Store2 Yes 72 Mult2 8 Store3 No S1

S2 RS for jRS for k Vj Vk Qj Qk Code: LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 M(80) R(F2) SUBI R1 R1 #8 M(72) R(F2) BNEZ R1 Loop F0 F2 iteration 1 1 1 2 2 2 Op Load3 F4 F6 F8 F10 F12... F30 Mult2 Mult1 completing; what is waiting for it? EEL 5708 Loop Example Cycle 15 Instruction status Instruction j k iteration LD F0 0 R1 1 MULTDF4 F0 F2 1 SD F4 0 R1 1 LD F0 0 R1 2 MULTDF4 F0 F2 2 SD F4

0 R1 2 Reservation Stations Time Name Busy Op 0 Add1 No 0 Add2 No 0 Add3 No 0 Mult1 No 0 Mult2 Yes MULTD Register result status ExecutionWrite Issue completeResult Busy Address 1 9 10 Load1 No 2 14 15 Load2 No 3 Load3 Yes 64 Qi 6 10 11 Store1 Yes 80 M(80)*R(F2) 7 15 Store2 Yes 72 Mult2 8 Store3 No S1 S2 RS for jRS for k Vj Vk Qj Qk Code: LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 SUBI R1 R1 #8 M(72) R(F2) BNEZ R1 Loop Clock F2 15 R1 64 F0 Qi Load3 F4 F6 F8 F10 F12... F30

Mult2 Mult2 completing; what is waiting for it? EEL 5708 Loop Example Cycle 16 Instruction status Instruction j k iteration LD F0 0 R1 1 MULTDF4 F0 F2 1 SD F4 0 R1 1 LD F0 0 R1 2 MULTDF4 F0 F2 2 SD F4 0 R1 2 Reservation Stations Time Name Busy Op 0 Add1 No 0 Add2 No 0 Add3 No 0 Mult1 Yes MULTD 0 Mult2 No Register result status ExecutionWrite Issue completeResult Busy Address 1 9 10 Load1 No 2 14 15 Load2 No 3 Load3 Yes 64 Qi 6 10 11 Store1 Yes 80 M(80)*R(F2) 7 15 16 Store2 Yes 72 M(72)*R(72) 8 Store3 No S1 S2 RS for jRS for k Vj Vk Qj Qk Code: LD

F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 R(F2) Load3 SUBI R1 R1 #8 BNEZ R1 Loop Clock F2 16 R1 64 F0 Qi Load3 F4 F6 F8 F10 F12... F30 Mult1 EEL 5708 Loop Example Cycle 17 Instruction status Instruction j k iteration LD F0 0 R1 1 MULTDF4 F0 F2 1 SD F4 0 R1 1 LD F0 0 R1 2 MULTDF4 F0 F2 2 SD F4 0 R1 2 Reservation Stations Time Name Busy Op 0 Add1 No 0 Add2 No 0 Add3 No 0 Mult1 Yes MULTD 0 Mult2 No Register result status

ExecutionWrite Issue completeResult Busy Address 1 9 10 Load1 No 2 14 15 Load2 No 3 Load3 Yes 64 Qi 6 10 11 Store1 Yes 80 M(80)*R(F2) 7 15 16 Store2 Yes 72 M(72)*R(72) 8 Store3 Yes 64 Mult1 S1 S2 RS for jRS for k Vj Vk Qj Qk Code: LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 R(F2) Load3 SUBI R1 R1 #8 BNEZ R1 Loop Clock F2 17 R1 64 F0 Qi Load3 F4 F6 F8 F10 F12... F30 Mult1 EEL 5708 Loop Example Cycle 18 Instruction status Instruction j k

iteration LD F0 0 R1 1 MULTDF4 F0 F2 1 SD F4 0 R1 1 LD F0 0 R1 2 MULTDF4 F0 F2 2 SD F4 0 R1 2 Reservation Stations Time Name Busy Op 0 Add1 No 0 Add2 No 0 Add3 No 0 Mult1 Yes MULTD 0 Mult2 No Register result status ExecutionWrite Issue completeResult Busy Address 1 9 10 Load1 No 2 14 15 Load2 No 3 18 Load3 Yes 64 Qi 6 10 11 Store1 Yes 80 M(80)*R(F2) 7 15 16 Store2 Yes 72 M(72)*R(72) 8 Store3 Yes 64 Mult1 S1 S2 RS for jRS for k Vj Vk Qj Qk Code: LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 R(F2) Load3 SUBI R1 R1 #8

BNEZ R1 Loop Clock F2 18 R1 56 F0 Qi Load3 F4 F6 F8 F10 F12... F30 Mult1 EEL 5708 Loop Example Cycle 19 Instruction status Instruction j k iteration LD F0 0 R1 1 MULTDF4 F0 F2 1 SD F4 0 R1 1 LD F0 0 R1 2 MULTDF4 F0 F2 2 SD F4 0 R1 2 Reservation Stations Time Name Busy Op 0 Add1 No 0 Add2 No 0 Add3 No 0 Mult1 Yes MULTD 0 Mult2 No Register result status ExecutionWrite Issue completeResult Busy Address 1 9 10 Load1 No 2 14 15 Load2 No

3 18 19 Load3 Yes 64 Qi 6 10 11 Store1 No 7 15 16 Store2 Yes 72 M(72)*R(72) 8 Store3 Yes 64 Mult1 S1 S2 RS for jRS for k Vj Vk Qj Qk Code: LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 R(F2) Load3 SUBI R1 R1 #8 BNEZ R1 Loop Clock F2 19 R1 56 F0 Qi Load3 F4 F6 F8 F10 F12... F30 Mult1 EEL 5708 Loop Example Cycle 20 Instruction status Instruction j k iteration LD F0 0 R1 1 MULTDF4 F0 F2 1 SD

F4 0 R1 1 LD F0 0 R1 2 MULTDF4 F0 F2 2 SD F4 0 R1 2 Reservation Stations Time Name Busy Op 0 Add1 No 0 Add2 No 0 Add3 No 0 Mult1 Yes MULTD 0 Mult2 No Register result status ExecutionWrite Issue completeResult Busy Address 1 9 10 Load1 No 2 14 15 Load2 No 3 18 19 Load3 Yes 64 Qi 6 10 11 Store1 No 7 15 16 Store2 Yes 72 M(72)*R(72) 8 20 Store3 Yes 64 Mult1 S1 S2 RS for jRS for k Vj Vk Qj Qk Code: LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 R(F2) Load3 SUBI R1 R1 #8 BNEZ R1 Loop Clock F2 20 R1

56 F0 Qi Load3 F4 F6 F8 F10 F12... F30 Mult1 EEL 5708 Loop Example Cycle 21 Instruction status Instruction j k iteration LD F0 0 R1 1 MULTDF4 F0 F2 1 SD F4 0 R1 1 LD F0 0 R1 2 MULTDF4 F0 F2 2 SD F4 0 R1 2 Reservation Stations Time Name Busy Op 0 Add1 No 0 Add2 No 0 Add3 No 0 Mult1 Yes MULTD 0 Mult2 No Register result status ExecutionWrite Issue completeResult Busy Address 1 9 10 Load1 No 2 14 15 Load2 No 3 18 19 Load3 Yes 64 Qi 6 10 11 Store1 No 7 15

16 Store2 No 8 20 21 Store3 Yes 64 Mult1 S1 S2 RS for jRS for k Vj Vk Qj Qk Code: LD F0 0 R1 MULTDF4 F0 F2 SD F4 0 R1 R(F2) Load3 SUBI R1 R1 #8 BNEZ R1 Loop Clock F2 21 R1 56 F0 Qi Load3 F4 F6 F8 F10 F12... F30 Mult1 EEL 5708 Tomasulo Summary Reservations stations: renaming to larger set of registers + buffering source operands Prevents registers as bottleneck Allows loop unrolling in HW Not limited to basic blocks (integer units gets ahead, beyond branches) Helps cache misses as well Lasting Contributions Dynamic scheduling Register renaming Load/store disambiguation 360/91 descendants are Pentium II; PowerPC 604; MIPS R10000; HP-PA 8000; Alpha 21264 EEL 5708

Recently Viewed Presentations

  • Strategic HRM - 國立中興大學

    Strategic HRM - 國立中興大學

    Strategic HRM Final Notes Our Goal for SHRM: To understand the strategic issues in using Human Resources for sustainable competitive advantage and how to implement the changes necessary to achieve this.
  • Deductive vs Inductive Reasoning

    Deductive vs Inductive Reasoning

    Sets and Set Operations Objectives Determine if a set is well defined. Write all the subsets of a given set and label the subsets as proper or improper. Given a universal set and some subsets, find a complement, intersection or...
  • Week 12 - Professionalism, Hockey and Government Involvement

    Week 12 - Professionalism, Hockey and Government Involvement

    Television 1924 Chamonix, France Toronto Granites First Round: Canada 22 Sweden 0 33 Switz 0 20 Czech 0 1924 Round 2 Canada 19 Britain 2 6 US 1 1928 St. Mortiz Toronto Grads: 3 pools Canada 11 Sweden 0 13...
  • Weathering - WordPress.com

    Weathering - WordPress.com

    Engineering Geology I (GED355) S. Bansah, August 2010 Engineering Geological Maps & Plans
  • Virtual Chess - Computer Science

    Virtual Chess - Computer Science

    Objectives Track individual chess pieces Maintain state of board Graphically represent state changes and state Lab Set-up 1 to 3 cameras Panasonic GP-LM7TA 1 overhead (min) 2 side view PC Matrox imaging board and libraries C++, OpenGL, GLVU Chessboard and...
  • FUNCTIONS of LEGAL SYSTEM - Syracuse University

    FUNCTIONS of LEGAL SYSTEM - Syracuse University

    LEGAL SYSTEMS Common Law : "Anglo-American" Precedent-based (stare decisis) Individual cases source of legal principles Adversarial system, neutral judge Civil Law: European Code-based Cases only application of principles set out in codes Inquisitorial system, judge leads inquiry Socialist Law: Communist...
  • Gas Laws - PC\|MAC

    Gas Laws - PC\|MAC

    Practice. 1.) A mixture of nitrogen and neon gases contains equal moles of each gas and has a total mass of 10.0 g. What is the density of this gas mixture at 500 K and 15.0 atm?
  • Making Custom Cables

    Making Custom Cables

    • Observe the value for in 1 • Turn the dial on the potentiometer and observe how the sensor value on in1 changes This lesson will explain how to hook a standard dial potentiometer into the Vex system to function...