View Full Document

9 views

Unformatted text preview:

CMU 18 447 S 10 L12 1 2010 J C Hoe J F Mart nez 18 447 Lecture 12 Branch Prediction James C Hoe Dept of ECE CMU February 24 2010 Announcements 1 week to Spring break L b2 due Lab2 d this thi weekk Lab3 starts next week Handouts Control Speculation PC 4 Insth Insti Instj Instk Instl t0 t1 IFPC ID IFPC 4 Insth is a branch t2 t3 t4 CMU 18 447 S 10 L12 2 2010 J C Hoe J F Mart nez t5 ALU MEM ID ALU IFPC 8 ID firstIFopportunity to decode Insth target should we correct now Insth branch condition and target evaluated in ALU When a branch resolves branch target Instk is fetched all instructions fetched since insth so called wrong path instructions must be flushed Performance Impact correct guess no penalty incorrect guess 2 bubbles Assume CMU 18 447 S 10 L12 3 2010 J C Hoe J F Mart nez 86 of the time no data hazards 20 control flow instructions 70 of control flow instructions are taken IPC 1 1 0 20 0 7 2 1 1 0 14 2 1 1 28 0 78 probability of a wrong guess penalty for a wrong guess Can we reduce either of the two penalty terms Making a Better Guess CMU 18 447 S 10 L12 4 2010 J C Hoe J F Mart nez For ALU instructions can t do better than guessing nextPC PC 4 still ill tricky i k since i must guess nextPC PC before b f the h current instruction is fetched For Branch Jump instructions why not always guess in the taken direction since 70 correct again must guess nextPC before the branch instruction is fetched but branch target is encoded in the instruction Must make a guess based only on the current fetch PC Fortunately PC offset branch jump target is static We are allowed to be wrong some of the time CMU 18 447 S 10 L12 5 2010 J C Hoe J F Mart nez Branch Target Buffer Oracle BTB Oracle a giant table indexed by PC returns the guess for nextPC BTB When encountering a PC for the first time store in BTB PC 4 PC offset PC Instruction Memory if ALU LD ST if Branch or Jump if JR Effectively guessing branches are always taken IPC 1 1 0 20 0 3 2 0 89 PC BTB Reality CMU 18 447 S 10 L12 6 2010 J C Hoe J F Mart nez BTB idx unused N bit BTB with 2N entries nPC Hash PC into a 2N entry table On collision BTB returns something meaningless and possibly since 80 of entries all hold PC 4 wrong How big should this table be CMU 18 447 S 10 L12 7 2010 J C Hoe J F Mart nez Tagged BTB tag BTB idx tag table BTB PC 4 1 0 nextPC Only store branch instructions save 80 storage Update tag and BTB for the new branch after each collision Even Better Guess We can get 100 correct on non branch instructions Can we do better than 70 on branch instructions CMU 18 447 S 10 L12 8 2010 J C Hoe J F Mart nez We get 90 right on backward branch dynamic We only get 50 right on forward branch dynamic What pattern can we leverage on forward branches a given static branch instruction is likely to be highly biased in one direction either taken or not taken 80 90 correct if we always guessed the same outcome as the last time the same branch was executed IPC 1 1 0 20 0 15 2 0 94 CMU 18 447 S 10 L12 9 2010 J C Hoe J F Mart nez Branch History Table and Target Buffer tag BTB idx N bit tag table BHT BTB taken PC 4 1 The 1 bit BHT entry is updated with the true outcome after each execution of a branch 0 nextPC Branch Prediction State Machine CMU 18 447 S 10 L12 10 2010 J C Hoe J F Mart nez actually taken actually not taken predict not taken predict taken actually not taken actually taken CMU 18 447 S 10 L12 11 2010 J C Hoe J F Mart nez 2 Bit Saturation Counter actually taken pred taken 11 actually taken pred taken 10 actually taken actually taken pred taken 01 actually taken actually taken pred taken 00 actually taken actually taken 2 Bit Hysteresis Counter actually taken strongly strongly taken actually taken pred taken weakly taken weakly taken pred taken actually taken actually taken CMU 18 447 S 10 L12 12 2010 J C Hoe J F Mart nez actually taken strongly taken taken actually taken pred taken pred taken actually taken Change prediction after 2 consecutive mistakes actually taken State Machine Based Predictors CMU 18 447 S 10 L12 13 2010 J C Hoe J F Mart nez 2 bit predictor can get 90 correct IPC 1 1 0 20 0 10 2 0 96 any reasonable reasonable 2 bit 2 bit predictor does about the same Adding more bits to counters does not help much more Major branch behaviors exploited almost always do the same thing again and again 80 1 bit and 2 bit predictors equally effective occasionally do the opposite once 5 10 2 misprediction with a 1 bit predictor 1 misprediction with a 2 bit predictor miscellaneous 10 some could be captured with more elaborate predictors what does Amdahl s law say about this be careful Path History Branch outcome can be correlated to other branches Equntott SPEC92 if aa 2 aa 0 if bb 2 bb 0 if aa bb B1 B2 B3 If B1 is not taken i e aa 0 B3 and B2 is not taken i e bb 0 B3 then B3 is certainly taken How do you capture this information CMU 18 447 S 10 L12 14 2010 J C Hoe J F Mart nez Gshare Branch Prediction McFarling tag CMU 18 447 S 10 L12 15 2010 J C Hoe J F Mart nez BTB idx N bit N bit xor tag table BHT BTB M bit taken BHSR PC 4 1 0 nextPC Global BHSR Branch History Shift Register tracks the outcomes of the last M branch instructions Return Address Stack The targets of register indirect jumps have little locality history based predictors don t work but a simple stack captures the usage pattern of function call and return very well Return Address Stack RAS the return address is pushed when a link instruction e g JAL is executed when the PC of a return instruction e g JR is encountered predict nPC from the top of the stack and pop What happens when the stack overflows How do you know when to follow RAS vs BTB CMU 18 447 S 10 L12 16 2010 J C Hoe J F Mart nez CMU 18 447 S 10 L12 17 2010 J C Hoe J F Mart nez Alpha 21264 Tournament Predictor Fig 4 Kessler IEEE Micro 1999 Make separate predictions using local history per branch and global …


Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Branch Prediction and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Branch Prediction and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?