CS152 Computer Architecture and Engineering Lecture 19 Speculation ILP Con t Locality and Memory Technology April 14 2003 John Kubiatowicz www cs berkeley edu kubitron lecture slides http inst eecs berkeley edu cs152 4 14 03 UCB Spring 2003 CS152 Kubiatowicz Review Tomasulo With Reorder buffer Done FP Op Queue Reorder val2 val2 F0 F0 val2 val2 F4 F4 M 10 M 10 Buffer F2 F2 F10 F10 F0 F0 ST ST 0 R3 F0 0 R3 F0 ADDD ADDD F0 F4 F6 F0 F4 F6 LD LD F4 0 R3 F4 0 R3 BNE BNE F2 F2 DIVD DIVD F2 F10 F6 F2 F10 F6 ADDD ADDD F10 F4 F0 F10 F4 F0 LD LD F0 10 R2 F0 10 R2 Registers Dest 22 ADDD ADDD R F4 ROB1 R F4 ROB1 To Memory Dest 33 DIVD DIVD ROB2 R F6 ROB2 R F6 Reservation Stations FP FP FPadders adders FPmultipliers multipliers 4 14 03 YY ROB7 Newest Ex Ex ROB6 YY ROB5 NN ROB5 NN ROB3 NN ROB2 Oldest NN ROB1 UCB Spring 2003 from Memory Dest 11 10 R2 10 R2 CS152 Kubiatowicz Review Independent Fetch unit Stream of Instructions To Execute Out Of Order Execution Unit Instruction Fetch with Branch Prediction Correctness Feedback On Branch Results Instruction fetch decoupled from execution Often issue logic rename included with Fetch 4 14 03 UCB Spring 2003 CS152 Kubiatowicz Review Branch Target Buffer BTB 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 PC of instruction FETCH Branch PC Predicted PC 4 14 03 Predict taken or untaken UCB Spring 2003 CS152 Kubiatowicz Review Branch History Table Predictor 0 Predictor 1 T Branch PC Predictor 7 NT NT T NT T NT BHT is a table of Predictors 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 CS152 Kubiatowicz Review Explicit Register Renaming Make use of a physical register file that is larger than number of registers specified by ISA Key insight Allocate a new physical destination register for every instruction that writes Very similar to a compiler transformation called Static Single Assignment SSA form but in hardware Removes all chance of WAR or WAW hazards Like Tomasulo good for allowing full out of order completion Like hardware based dynamic compilation 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 UCB Spring 2003 CS152 Kubiatowicz 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 Execution operate on operands The functional unit begins execution upon receiving operands When the result is ready it notifies the scoreboard Write result finish execution Note No checks for WAR or WAW hazards 4 14 03 UCB Spring 2003 CS152 Kubiatowicz Renamed Scoreboard 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 Functional unit status Time Name Int1 Int2 Mult1 Add Divide 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 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 Each instruction allocates free register 4 14 03 Similar to single assignment compiler CS152 Kubiatowicz UCB Spring 2003 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 Read Exec Write Issue Oper Comp Result 1 2 2 Functional unit status Time Name Int1 Int2 Mult1 Add Divide Busy Op dest Fi Yes Yes No No No Load Load P32 P34 Register Rename and Result F0 F2 Clock 2 4 14 03 FU P0 P34 S1 Fj S2 Fk FU Qj FU Qk Fj Rj R2 R3 F4 F6 P4 P32 UCB Spring 2003 Yes Yes F8 F10 F12 P8 Fk Rk P10 P12 F30 P30 CS152 Kubiatowicz Renamed Scoreboard 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 Read Exec Write Issue Oper Comp Result 1 2 3 2 3 3 Functional unit status Time Name Int1 Int2 Mult1 Add Divide Busy Op dest Fi Yes Yes Yes No No Load Load Multd P32 P34 P36 P34 F4 F6 P4 P32 Register Rename and Result F0 F2 Clock 3 4 14 03 FU P36 P34 S1 Fj S2 Fk R2 R3 P4 UCB Spring 2003 Fj Rj Fk Rk Int2 No Yes Yes Yes F8 F10 F12 F30 P8 FU Qj P10 FU Qk P12 P30 CS152 Kubiatowicz 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 Read Exec Write Issue Oper Comp Result 1 2 3 4 2 3 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 F4 F6 F8 F10 F12 P4 P32 P38 Functional unit status Time Name Int1 Int2 Mult1 Add Divide Register Rename and Result F0 F2 Clock 4 4 14 03 FU P36 P34 UCB Spring 2003 FU Qj FU Qk Int2 Int2 P10 P12 Fj Rj Fk Rk No Yes Yes Yes No F30 P30 CS152 Kubiatowicz Renamed Scoreboard 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 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 P4 Functional unit status Time Name Int1 Int2 Mult1 Add Divide Register Rename and Result F0 F2 Clock 5 4 14 03 FU P36 P34 Fj Rj Fk Rk Mult1 Yes Yes No …
View Full Document
Unlocking...