Review Tomasulo With Reorder buffer CS152 Computer Architecture and Engineering Lecture 19 3 2S 4XHXH 5HRUGHU XIIHU Speculation ILP Con t Locality and Memory Technology John Kubiatowicz www cs berkeley edu kubitron HVW 22 ADDD ADDD R F4 ROB1 R F4 ROB1 lecture slides http inst eecs berkeley edu cs152 3 DGGHUV 3 DGGHUV CS152 Kubiatowicz Lec19 1 UCB Spring 2003 1HZHVW 2OGHVW 7R 0HPRU HVW 33 DIVD DIVD ROB2 R F6 ROB2 R F6 5HVHUYDWLRQ 6WDWLRQV 4 14 03 IURP 0HPRU HVW 11 10 R2 10 R2 3 PXOWLSOLHUV 3 PXOWLSOLHUV CS152 Kubiatowicz Lec19 2 UCB Spring 2003 Review Branch Target Buffer BTB Review Independent Fetch unit Stream of Instructions To Execute Out Of Order Execution Unit Instruction Fetch with Branch Prediction RQH ST 0 R3 F0 YY 52 ST 0 R3 F0 ADDD ADDD F0 F4 F6 F0 F4 F6 Ex Ex 52 LD YY 52 LD F4 0 R3 F4 0 R3 BNE NN 52 BNE F2 F2 DIVD F2 F10 F6 DIVD F2 F10 F6 NN 52 ADDD ADDD F10 F4 F0 F10 F4 F0 NN 52 LD NN 52 LD F0 10 R2 F0 10 R2 5HJLVWHUV April 14 2003 4 14 03 val2 val2 F0 F0 val2 val2 F4 M 10 F4 M 10 F2 F2 F10 F10 F0 F0 Address of branch index to get prediction AND branch address if taken Must check for branch match now since can t use wrong branch address Grab predicted PC from table since may take several cycles to compute UDQFK 3 3UHGLFWHG 3 3 RI LQVWUXFWLRQ 7 Correctness Feedback On Branch Results Instruction fetch decoupled from execution 3UHGLFW WDNHQ RU XQWDNHQ Often issue logic rename included with Fetch 4 14 03 UCB Spring 2003 CS152 Kubiatowicz Lec19 3 4 14 03 UCB Spring 2003 CS152 Kubiatowicz Lec19 4 Review Branch History Table Review Explicit Register Renaming Predictor 0 Predictor 1 Make use of a physical register file that is larger than number of registers specified by ISA T NT Key insight Allocate a new physical destination register for every instruction that writes Branch PC Predictor 7 NT T NT T NT BHT is a table of Predictors Like Tomasulo good for allowing full out of order completion Like hardware based dynamic compilation Usually 2 bit saturating counters Indexed by PC address of Branch without tags Combine Branch Target Buffer and History Tables Branch Target Buffer BTB identify branches and hold taken addresses Trick identify branch before fetching instruction Must be careful not to misidentify branches or destinations Branch History Table makes prediction Can be complex prediction mechanisms with long history No address check Can be good can be bad aliasing 4 14 03 UCB Spring 2003 Very similar to a compiler transformation called Static Single Assignment SSA form but in hardware Removes all chance of WAR or WAW hazards CS152 Kubiatowicz Lec19 5 Review Stages of Scoreboard With Explicit Renaming Issue decode instructions check for structural hazards allocate new physical register for result Instructions issued in program order for hazard checking Don t issue if no free physical registers Don t issue if structural hazard Read operands wait until no hazards read operands All real dependencies RAW hazards resolved in this stage since we wait for instructions to write back data Mechanism Keep a translation table ISA register physical register mapping When register written replace entry with new register from freelist Physical register becomes free when not used by any active instructions 4 14 03 Renamed Scoreboard 1 Instruction status Instruction LD F6 LD F2 MULTD F0 SUBD F8 DIVD F10 ADDD F6 Write result finish execution Read Exec Write Issue Oper Comp Result 1 Busy Op dest Fi Yes No No No No Load P32 Register Rename and Result F0 F2 Clock 1 UCB Spring 2003 k R2 R3 F4 F2 F6 F2 Time Name Int1 Int2 Mult1 Add Divide The functional unit begins execution upon receiving operands When the result is ready it notifies the scoreboard 4 14 03 j 34 45 F2 F6 F0 F8 Functional unit status Execution operate on operands Note No checks for WAR or WAW hazards CS152 Kubiatowicz Lec19 7 CS152 Kubiatowicz Lec19 6 UCB Spring 2003 FU P0 P2 S1 Fj S2 Fk FU Qj FU Qk Fj Rj R2 F4 F6 P4 P32 Yes F8 F10 F12 P8 Fk Rk P10 P12 F30 P30 DFK LQVWUXFWLRQ DOORFDWHV IUHH UHJLVWHU 6LPLODU WR VLQJOH DVVLJQPHQW FRPSLOHU WUDQVIRUPDWLRQ CS152 Kubiatowicz 4 14 03 UCB Spring 2003 Lec19 8 Renamed Scoreboard 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 1 2 2 Busy Op dest Fi Yes Yes No No No Load Load P32 P34 Register Rename and Result F0 F2 Clock FU 2 Instruction status Read Exec Write Issue Oper Comp Result Functional unit status Time Name Int1 Int2 Mult1 Add Divide Renamed Scoreboard 3 P0 P34 4 14 03 S1 Fj Instruction LD F6 LD F2 MULTD F0 SUBD F8 DIVD F10 ADDD F6 S2 Fk FU Qj FU Qk Fj Rj R2 R3 F4 F6 P4 P32 P10 P12 F30 Renamed Scoreboard 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 Time Name Int1 Int2 Mult1 Add Divide 4 4 14 03 FU 3 4 4 Busy Op dest Fi S1 Fj S2 Fk No Yes Yes Yes No Load Multd Sub P34 P36 P38 P34 P32 R3 P4 P34 P34 FU 3 2 3 Busy Op dest Fi Yes Yes Yes No No Load Load Multd P36 3 P34 4 14 03 S1 Fj S2 Fk P32 P34 P36 P34 R2 R3 P4 F4 F6 P4 P32 FU Qj FU Qk Int2 F8 F10 F12 P8 P10 Fj Rj Fk Rk No Yes Yes Yes F30 P12 P30 CS152 Kubiatowicz Lec19 10 UCB Spring 2003 Instruction LD F6 LD F2 MULTD F0 SUBD F8 DIVD F10 ADDD F6 2 3 P36 1 2 3 Register Rename and Result F0 F2 Clock Instruction status 1 2 3 4 Register Rename and Result F0 F2 Clock Read Exec Write Issue Oper Comp Result Renamed Scoreboard 5 Read Exec Write Issue Oper Comp Result Functional unit status Time Name Int1 Int2 Mult1 Add Divide P30 CS152 Kubiatowicz Lec19 9 UCB Spring 2003 k R2 R3 F4 F2 F6 F2 Functional unit status Yes Yes F8 F10 F12 P8 Fk Rk j 34 45 F2 F6 F0 F8 FU Qj FU Qk Int2 Int2 F4 F6 F8 F10 F12 P4 P32 P38 UCB Spring 2003 P10 P12 Fj Rj Fk Rk No Yes Yes Yes No F30 k R2 R3 F4 F2 F6 F2 Read Exec Write Issue Oper Comp Result 1 2 3 4 5 2 3 3 4 4 5 Busy Op dest Fi S1 Fj S2 Fk No No Yes Yes Yes Multd Sub Divd P36 P38 P40 P34 P32 P36 P4 P34 P32 F4 F6 F8 F10 F12 P4 P32 P38 Functional unit status Time Name Int1 Int2 Mult1 Add Divide Register Rename and …
View Full Document
Unlocking...