March 11, 2010 CS152, Spring 2010 CS 152 Computer Architecture and Engineering Lecture 14 - Advanced Superscalars Krste Asanovic Electrical Engineering and Computer Sciences University of California at Berkeley http://www.eecs.berkeley.edu/~krste!http://inst.eecs.berkeley.edu/~cs152!March 11, 2010 CS152, Spring 2010 2 Last time in Lecture 13 • Register renaming removes WAR, WAW hazards • Instruction execution divided into four major stages: – Instruction Fetch, Decode/Rename, Execute/Complete, Commit • Control hazards are serious impediment to superscalar performance • Dynamic branch predictors can be quite accurate (>95%) and avoid most control hazards • Branch History Tables (BHTs) just predict direction (later in pipeline) – Just need a few bits per entry (2 bits gives hysteresis) – Need to decode instruction bits to determine whether this is a branch and what the target address isMarch 11, 2010 CS152, Spring 2010 3 Limitations of BHTs Only predicts branch direction. Therefore, cannot redirect fetch stream until after branch target is determined. UltraSPARC-III fetch pipeline Correctly predicted taken branch penalty Jump Register penalty A PC Generation/Mux P Instruction Fetch Stage 1 F Instruction Fetch Stage 2 B Branch Address Calc/Begin Decode I Complete Decode J Steer Instructions to Functional units R Register File Read E Integer Execute Remainder of execute pipeline (+ another 6 stages)March 11, 2010 CS152, Spring 2010 4 Branch Target Buffer BP bits are stored with the predicted target address. IF stage: If (BP=taken) then nPC=target else nPC=PC+4 later: check prediction, if wrong then kill the instruction and update BTB & BPb else update BPb IMEM PC Branch Target Buffer (2k entries) k BPb predicted target BP targetMarch 11, 2010 CS152, Spring 2010 5 Address Collisions What will be fetched after the instruction at 1028? BTB prediction = Correct target = !⇒ Assume a 128-entry BTB BPb target take 236 1028 Add ..... 132 Jump 100 Instruction Memory 236 1032 kill PC=236 and fetch PC=1032 Is this a common occurrence? Can we avoid these bubbles?March 11, 2010 CS152, Spring 2010 6 BTB is only for Control Instructions BTB contains useful information for branch and jump instructions only !⇒ Do not update it for other instructions For all other instructions the next PC is PC+4 ! How to achieve this effect without decoding the instruction?March 11, 2010 CS152, Spring 2010 7 Branch Target Buffer (BTB) • Keep both the branch PC and target PC in the BTB • PC+4 is fetched if match fails • Only taken branches and jumps held in BTB • Next PC determined before branch fetched and decoded 2k-entry direct-mapped BTB (can also be associative) I-Cache PC k Valid valid Entry PC = match predicted target target PCMarch 11, 2010 CS152, Spring 2010 8 Combining BTB and BHT • BTB entries are considerably more expensive than BHT, but can redirect fetches at earlier stage in pipeline and can accelerate indirect branches (JR) • BHT can hold many more entries and is more accurate A PC Generation/Mux P Instruction Fetch Stage 1 F Instruction Fetch Stage 2 B Branch Address Calc/Begin Decode I Complete Decode J Steer Instructions to Functional units R Register File Read E Integer Execute BTB BHT BHT in later pipeline stage corrects when BTB misses a predicted taken branch BTB/BHT only updated after branch resolves in E stageMarch 11, 2010 CS152, Spring 2010 9 Uses of Jump Register (JR) • Switch statements (jump to address of matching case) • Dynamic function call (jump to run-time function address) • Subroutine returns (jump to return address) How well does BTB work for each of these cases? BTB works well if same case used repeatedly BTB works well if same function usually called, (e.g., in C++ programming, when objects have same type in virtual function call) BTB works well if usually return to the same place ⇒ Often one function called from many distinct call sites!March 11, 2010 CS152, Spring 2010 10 Subroutine Return Stack Small structure to accelerate JR for subroutine returns, typically much more accurate than BTBs. &fb() &fc() Push call address when function call executed Pop return address when subroutine return decoded fa() { fb(); } fb() { fc(); } fc() { fd(); } &fd() k entries (typically k=8-16)March 11, 2010 CS152, Spring 2010 11 Mispredict Recovery In-order execution machines: – Assume no instruction issued after branch can write-back before branch resolves – Kill all instructions in pipeline behind mispredicted branch – Multiple instructions following branch in program order can complete before branch resolves Out-of-order execution?March 11, 2010 CS152, Spring 2010 12 In-Order Commit for Precise Exceptions • Instructions fetched and decoded into instruction reorder buffer in-order • Execution is out-of-order ( ⇒ out-of-order completion) • Commit (write-back to architectural state, i.e., regfile & memory, is in-order Temporary storage needed in ROB to hold results before commit Fetch Decode Execute Commit Reorder Buffer In-order In-order Out-of-order Kill Kill Kill Exception? Inject handler PCMarch 11, 2010 CS152, Spring 2010 13 Branch Misprediction in Pipeline Fetch Decode Execute Commit Reorder Buffer Kill Kill Kill Branch Resolution Inject correct PC • Can have multiple unresolved branches in ROB • Can resolve branches out-of-order by killing all the instructions in ROB that follow a mispredicted branch Branch Prediction PC CompleteMarch 11, 2010 CS152, Spring 2010 14 t v t v t v Recovering ROB/Renaming Table Register File Reorder buffer Load Unit FU FU FU Store Unit < t, result > t1 t2 . . tn Ins# use exec op p1 src1 p2 src2 pd dest data Commit Rename Table r1 t v r2 Take snapshot of register rename table at each predicted branch, recover earlier snapshot if branch mispredicted Rename Snapshots Ptr2 next to commit Ptr1 next available rollback next availableMarch 11, 2010 CS152, Spring 2010 15 Speculating Both Directions • resource requirement is proportional to the number of concurrent speculative executions An alternative to branch prediction is to execute both directions of a branch speculatively • branch prediction takes less resources than speculative execution of both paths • only half the resources
View Full Document
Unlocking...