Branch Prediction Overview Branch Prediction 2 bit saturating counter state machine Correlated Branch Prediction Global history Index table of state machines by loworder bits of the PC Many variations and approaches Alex Nizhner Yang Gu 2003 10 1 Papers Cliff Young Nicolas Gloy and Michael D Smith A Comparative Analysis of Schemes for Correlated Branch Prediction Timothy Heil Zak Smith and James E Smith Improving Branch Predictors by Correlating on Data Values Joel Emer and Nikolas Gloy A Language for Describing Predictors and its Application to Automatic Synthesis 2003 10 1 2 A Comparative Analysis of Schemes for Correlated Branch Prediction Cliff Young Nicolas Gloy and Michael D Smith 3 1 A Framework for Brach Prediction Questions branch execution e b d e 0 1 identifier b and direction var iable d 0 1 Why does branch prediction scheme A perform better than B How well does a branch prediction scheme work Execution Stream a sequence of branch executions Predictor a simple mechanism that predicts the next direction of a stream Prediction scheme a comprehensive mechanism that takes a program execution stream divides it into substreams and directs each substream to a unique predictor 2003 10 1 5 2003 10 1 The Keys Existing divider mechanisms and their prediction schemes The Identity selections of the right divider The selections of the good predictor 6 function Per branch substream ei bi d i bi 2003 10 1 7 2003 10 1 8 2 Existing divider mechanisms and their prediction schemes cont Per branch The benefit of path history global pattern streams e g GA gshare Per branch branch pattern streams Per branch global path streams 2003 10 1 9 10 Where can we improve Paths versus Patterns Why Static Correlated Prediction Works 2003 10 1 2003 10 1 11 2003 10 1 12 3 Where can we improve Aliasing Where can we improve Cross Procedure Correlation Aliasing in a 4096 counter table for awk a White squares represent unused counters black squares represent counters with seven or more aliased streams Gray scale indicates the degree of aliasing 2003 10 1 13 Conclusion Path history is slightly better than pattern history in exploiting branch correlation Correlated dynamic branch prediction schemes utilize more 2 bit counters in their tables but simultaneously increase the amount of aliasing Cross procedure correlation limits the accuracy of static branch prediction schemes 2003 10 1 2003 10 1 14 A Language for Describing Predictors and its Application to Automatic Synthesis Joel Emer DEC Nikolas Gloy Harvard 15 4 Predictor Notation Difference Previous work High level construct from existing blocks Manually specify the predictor Examples Onebit d PC T Here P 1 d PC T Where Start from Low level primitives Provide automatic help in the process of specification of the predictor PC current program counter T branch resolution 0 Not Taken 1 Taken Counter n d I T 17 2003 10 1 Branch Prediction BP Language The parser understands 2003 10 1 P n d I if T then P 1 else P 1 18 Genetic Programming Search Represent expressions and describes predictors in BP language Parse algebraic expressions into treelike structure Adapt genetic operations on tree node individuals Replication Predictor primitives Composition of predictors Logic expressions XOR IF Functions SATURATE MASK HI Translation and Simulation Can link to a trace reader Crossover Mutation 2003 10 1 19 2003 10 1 Encapsulation20 5 Adaptation Process Example Crossover Operation Randomly choose crossover nodes exchange the subtree Create initial population of randomly generated individuals 2 Rank fitness of individuals in the population by simulation 3 Apply genetic operations to create new generation 4 Repeat steps 2 and 3 1 21 2003 10 1 Example Mutation Operation Predictor Node 2003 10 1 22 Results of Branch Predictors Predictor Node Width Height Width Height If it is a predictor node we change the width and or height XOR IF If it is a function node we replace it with a different function 2003 10 1 23 2003 10 1 24 6 Questions Conclusion gshare Present still works better Results very deep tree structures probably not directly implementable 2003 10 1 a new language for describing predictors BP language allows for automatic manipulation including generating simulators and automated synthesis Use GP to search the design space for branch prediction 25 2003 10 1 26 Why Are Branches Mispredicted Improving Branch Predictors by Correlating on Data Values History register not wide enough Can t see the outcome for the last iteration of a loop of even moderate length Timothy H Heil Zak Smith J E Smith Is branch history a good heuristic Programs structured to manipulate DATA 2003 10 1 28 7 Value History Example Data values of registers used to compute a branch condition code Typically use ra rb gcc front end Giant switch statement branch history useless Aside how would this be done on Alpha Correlate on data history the same way previous schemes correlate on branch history E g accurately predict the last branch of a loop counter should approach 0 2003 10 1 29 Condition setting instructions 2003 10 1 30 The Branch Difference Predictor e g cmple ra rb rc followed by a beq Maintain a table indexed by branch PC containing the values used for condition code computation valid bit set by a subset of instructions 2003 10 1 31 2003 10 1 32 8 The Branch Difference Predictor Results 1 history depth Backing Predictor Conventional global branch history predictor often does well enough Fails in exceptional cases Use Rare Event Predictor for all branches previously mispredicted by BP Rare Event Predictor REP Cache of difficult to predict branches Separate prediction logic e g 2 bit counters Value history table Per branch difference history one entry typically enough Used for validating REP entries Diminishing 2003 10 1 33 Results 2 Performance returns on increasing history buffer depth 2003 10 1 34 Discussion Conclusion Clearly outperforms branch historycorrelated schemes Improvements Branch register values natural choice What other program state can be captured to aid with BP 2003 10 1 35 2003 10 1 36 9
View Full Document
Unlocking...