CS152 Computer Architecture and Engineering Lecture 17 Dynamic Scheduling Cont Speculation April 7 2003 John Kubiatowicz www cs berkeley edu kubitron lecture slides http inst eecs berkeley edu cs152 4 07 03 UCB Spring 2003 CS152 Kubiatowicz The Big Picture Where are We Now The Five Classic Components of a Computer Processor Input Control Memory Datapath Output Today s Topics Recap last lecture Hardware loop unrolling with Tomasulo algorithm Administrivia Speculation branch prediction Reorder buffers 4 07 03 UCB Spring 2003 CS152 Kubiatowicz Registers FP FPMult Mult FP FPMult Mult FP FPDivide Divide FP FPAdd Add Integer Integer SCOREBOARD SCOREBOARD 4 07 03 UCB Spring 2003 Functional Units Review Scoreboard Architecture CDC 6600 Memory CS152 Kubiatowicz Review Four Stages of Scoreboard Control Issue decode instructions check for structural hazards Instructions issued in program order for hazard checking Don t issue if structural hazard Don t issue if instruction is output dependent on any previously issued but uncompleted instruction no WAW hazards Read operands wait until no data hazards then read operands All real dependencies RAW hazards resolved in this stage No forwarding of data in this model Execution operate on operands EX The functional unit begins execution upon receiving operands When the result is ready it notifies the scoreboard that it has completed execution Write result finish execution WB Stall until no WAR hazards with previous instructions Example DIVD ADDD SUBD F0 F2 F4 F10 F0 F8 F8 F8 F14 CDC 6600 scoreboard would stall SUBD until ADDD reads operands 4 07 03 UCB Spring 2003 CS152 Kubiatowicz Review Tomasulo Organization FP Registers From Mem FP Op Queue Load Buffers Load1 Load2 Load3 Load4 Load5 Load6 Store Buffers Add1 Add2 Add3 Mult1 Mult2 Reservation Stations FP FP FPadders adders FPmultipliers multipliers Common Data Bus CDB 4 07 03 UCB Spring 2003 To Mem CS152 Kubiatowicz Recall Reservation Station Components Op Operation to perform in the unit e g or Vj Vk Value of Source operands Store buffers has V field result to be stored Qj Qk Reservation stations producing source registers value to be written Note No ready flags as in Scoreboard Qj Qk 0 ready Store buffers only have Qi for RS producing result Busy Indicates reservation station or FU is busy Register result status Or Rename Table Mapping from user visible registers to reservation stations or value 4 07 03 UCB Spring 2003 CS152 Kubiatowicz Recall Three Stages of Tomasulo Algorithm 1 Issue get instruction from FP Op Queue If reservation station free no structural hazard control issues instr sends operands renames registers 2 Execution operate on operands EX When both operands ready then execute if not ready watch Common Data Bus for result 3 Write result finish 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 4 07 03 UCB Spring 2003 CS152 Kubiatowicz Recall Tomasulo Example Cycle 1 Instruction status Instruction LD F6 LD F2 MULTD F0 SUBD F8 DIVD F10 ADDD F6 j 34 45 F2 F6 F0 F8 k R2 R3 F4 F2 F6 F2 Exec Write Issue Comp Result 1 Reservation Stations Time Name Busy Add1 No Add2 No Add3 No Mult1 No Mult2 No Register result status Clock 1 4 07 03 FU Busy Address Load1 Load2 Load3 Op S1 Vj S2 Vk RS Qj RS Qk F0 F2 F4 F6 F8 Yes No No 34 R2 F10 F12 F30 Load1 UCB Spring 2003 CS152 Kubiatowicz Recall Tomasulo Example Cycle 2 Instruction status Instruction LD F6 LD F2 MULTD F0 SUBD F8 DIVD F10 ADDD F6 j 34 45 F2 F6 F0 F8 k R2 R3 F4 F2 F6 F2 Exec Write Issue Comp Result 1 2 Reservation Stations Time Name Busy Add1 No Add2 No Add3 No Mult1 No Mult2 No Register result status Clock 2 FU Busy Address Load1 Load2 Load3 Op S1 Vj S2 Vk RS Qj RS Qk F0 F2 F4 F6 F8 Load2 Yes Yes No 34 R2 45 R3 F10 F12 F30 Load1 Note Unlike 6600 can have multiple loads outstanding 4 07 03 UCB Spring 2003 CS152 Kubiatowicz Recall Tomasulo Example Cycle 3 Instruction status Instruction LD F6 LD F2 MULTD F0 SUBD F8 DIVD F10 ADDD F6 j 34 45 F2 F6 F0 F8 k R2 R3 F4 F2 F6 F2 Exec Write Issue Comp Result 1 2 3 Reservation Stations Time Name Busy Op Add1 No Add2 No Add3 No Mult1 Yes MULTD Mult2 No Register result status Clock 3 FU F0 Busy Address 3 S1 Vj Load1 Load2 Load3 S2 Vk RS Qj Yes Yes No 34 R2 45 R3 F10 F12 RS Qk R F4 Load2 F2 Mult1 Load2 F4 F6 F8 F30 Load1 Note registers names are removed renamed in Reservation Stations MULT CS152 Kubiatowicz issued vs scoreboard 4 07 03 UCB Spring 2003 Recall Tomasulo Example Cycle 4 Instruction status Instruction LD F6 LD F2 MULTD F0 SUBD F8 DIVD F10 ADDD F6 j 34 45 F2 F6 F0 F8 k R2 R3 F4 F2 F6 F2 Exec Write Issue Comp Result 1 2 3 4 Reservation Stations Busy Address 3 4 4 Load1 Load2 Load3 S1 Vj S2 Vk RS Qj RS Qk F2 F4 F6 F8 No Yes No 45 R3 F10 F12 Time Name Busy Op Add1 Yes SUBD M A1 Load2 Add2 No Add3 No Mult1 Yes MULTD R F4 Load2 Mult2 No Register result status Clock 4 FU F0 Mult1 Load2 F30 M A1 Add1 Load2 completing what is waiting for Load1 4 07 03 UCB Spring 2003 CS152 Kubiatowicz Recall Tomasulo Example Cycle 5 Instruction status Instruction LD F6 LD F2 MULTD F0 SUBD F8 DIVD F10 ADDD F6 j 34 45 F2 F6 F0 F8 k R2 R3 F4 F2 F6 F2 Exec Write Issue Comp Result 1 2 3 4 5 Reservation Stations Busy Address 3 4 4 5 Load1 Load2 Load3 S1 Vj S2 Vk RS Qj RS Qk F2 F4 F6 F8 Time Name Busy Op 2 Add1 Yes SUBD M A1 M A2 Add2 No Add3 No 10 Mult1 Yes MULTD M A2 R F4 Mult2 Yes DIVD M A1 Mult1 Register result status Clock 5 4 07 03 FU F0 Mult1 M A2 No No No F10 F12 F30 M A1 Add1 Mult2 UCB Spring 2003 CS152 Kubiatowicz Recall Tomasulo Example Cycle 6 Instruction status Instruction LD F6 LD F2 MULTD F0 SUBD F8 DIVD F10 ADDD F6 j 34 45 F2 F6 F0 F8 k R2 R3 F4 F2 F6 F2 Exec Write Issue Comp Result 1 2 3 4 5 6 Reservation Stations Busy Address 3 4 4 5 Load1 Load2 Load3 S1 Vj S2 Vk RS Qj RS Qk F2 F4 F6 F8 Time Name Busy Op 1 Add1 Yes SUBD M A1 M A2 Add2 Yes ADDD M A2 Add1 Add3 No 9 Mult1 Yes MULTD M A2 R F4 Mult2 Yes DIVD M A1 Mult1 Register result status Clock 6 FU F0 Mult1 M A2 Add2 No No …
View Full Document
Unlocking...