Static Branch Prediction (II).Program-based (or, program analysis based)Idea: Use heuristics based on program analysis to determinestatically-predicteddirection- Opcode heuristic: Predict BLEZ as NT (negative integers used aserrorvaluesin manyprograms)Loop heuristic: Predict a branch guarding a loop execution as taken(i.e.,executetheloop)-PointerandFPcomparisons:Predictnotequal+ Does not require profiling-- Heuristics might be not representative or good-- Requires compiler analysis and ISA supportBallandLarus,"Branchpredictionforfree,”PLDI1993- 20% misprediction rateComputerArchitecture11
Computer Architecture Static Branch Prediction (III) • Program-based (or, program analysis based) – Idea: Use heuristics based on program analysis to determine statically-predicted direction – Opcode heuristic: Predict BLEZ as NT (negative integers used as error values in many programs) – Loop heuristic: Predict a branch guarding a loop execution as taken (i.e., execute the loop) – Pointer and FP comparisons: Predict not equal + Does not require profiling - Heuristics might be not representative or good - Requires compiler analysis and ISA support • Ball and Larus, ”Branch prediction for free, ” PLDI 1993. – 20% misprediction rate 11
Static Branch Prediction (III)Programmer-based-Idea:Programmerprovidesthestatically-predicted directionViapragmasintheprogramminglanguagethatqualifyabranchaslikely-takenversuslikely-not-taken+Does not requireprofiling or program analysis+Programmermayknowsomebranchesand theirprogrambetterthanotheranalysistechniques-- Requires programming language, compiler, ISA support-- Burdens the programmer?ComputerArchitecture12
Computer Architecture Static Branch Prediction (III) • Programmer-based – Idea: Programmer provides the statically-predicted direction – Via pragmas in the programming language that qualify a branch as likely-taken versus likely-not-taken + Does not require profiling or program analysis + Programmer may know some branches and their program better than other analysis techniques - Requires programming language, compiler, ISA support - Burdens the programmer? 12
Aside: PragmasIdea: Keywords that enable a programmer to convey hintsto lower levels of the transformation hierarchy.if (likely(x)) { ... }.if (unlikely(error)) ( ... )Manyotherhintsandoptimizationscanbeenabledwithpragmas-E.g.,whethera loop can be parallelized-#pragmaompparallel-Description.The omp parallel directive explicitlyinstructs the compilertoparallelizethechosensegmentofcode.ComputerArchitecture13
Computer Architecture Aside: Pragmas • Idea: Keywords that enable a programmer to convey hints to lower levels of the transformaLon hierarchy • if (likely(x)) { . } • if (unlikely(error)) { . } • Many other hints and opLmizaLons can be enabled with pragmas – E.g., whether a loop can be parallelized – #pragma omp parallel – Descrip1on • The omp parallel direcLve explicitly instructs the compiler to parallelize the chosen segment of code. 13
Static Branch Prediction: All previous techniques can be combined- Profile based- Program based- Programmer based: How would you do that? What are common disadvantages of all threetechniques?- Cannot adapt to dynamic changes in branch behaviorThiscanbemitigatedbyadynamiccompiler,butnotatafinegranularity (and a dynamic compiler has its overheads...)ComputerArchitecture14
Computer Architecture Static Branch Prediction • All previous techniques can be combined – Profile based – Program based – Programmer based • How would you do that? • What are common disadvantages of all three techniques? – Cannot adapt to dynamic changes in branch behavior • This can be mitigated by a dynamic compiler, but not at a fine granularity (and a dynamic compiler has its overheads.) 14
Dvnamic Branch Prediction: Idea: Predict branches based on dynamicinformation (collected at run-time)·Advantages+ Prediction based on history of the execution of branches+ It can adapt to dynamic changes in branch behavior+ No need for static profiling: input set representativenessproblem goes awayDisadvantages-- More complex (requires additional hardware)ComputerArchitecture15
Computer Architecture Dynamic Branch Prediction • Idea: Predict branches based on dynamic information (collected at run-time) • Advantages + Prediction based on history of the execution of branches + It can adapt to dynamic changes in branch behavior + No need for static profiling: input set representativeness problem goes away • Disadvantages - More complex (requires additional hardware) 15