Editing Branch predictor (section)

{{Short description|Digital circuit}}
{{Distinguish|Predication (computer architecture)}}
In [[computer architecture]], a '''branch predictor'''<ref name="dbp-class-report">{{cite web |url=http://web.engr.oregonstate.edu/~benl/Projects/branch_pred/ |title=Dynamic Branch Prediction |author-first1=Alexey |author-last1=Malishevsky |author-first2=Douglas |author-last2=Beck |author-first3=Andreas |author-last3=Schmid |author-first4=Eric |author-last4=Landry |access-date=2017-03-22 |archive-date=2019-07-17 |archive-url=https://web.archive.org/web/20190717130447/http://web.engr.oregonstate.edu/~benl/Projects/branch_pred/ |url-status=dead}}</ref><ref name="schemes-and-performances">{{cite web |url=http://bwrcs.eecs.berkeley.edu/Classes/CS252/Projects/Reports/terry_chen.pdf |title=The Schemes and Performances of Dynamic Branch predictors |author-first=Chih-Cheng |author-last=Cheng}}</ref><ref>{{cite web |url=http://www.cse.iitd.ernet.in/~srsarangi/col_718_2017/papers/branchpred/branch-pred-many.pdf |title=Branch Prediction Techniques and Optimizations |author-first=Raj |author-last=Parihar |access-date=2017-04-02 |archive-url=https://web.archive.org/web/20170516211522/http://www.cse.iitd.ernet.in/~srsarangi/col_718_2017/papers/branchpred/branch-pred-many.pdf |archive-date=2017-05-16 |url-status=dead}}</ref><ref>{{cite web |url=https://www.ece.cmu.edu/~ece447/s13/lib/exe/fetch.php?media=onur-447-spring13-lecture11-branch-prediction-afterlecture.pdf |title=18-447 Computer Architecture Lecture 11: Branch Prediction |author-first=Onur |author-last=Mutlu |date=2013-02-11 |archive-url=https://web.archive.org/web/20150325083615/https://www.ece.cmu.edu/~ece447/s13/lib/exe/fetch.php?media=onur-447-spring13-lecture11-branch-prediction-afterlecture.pdf |archive-date=2015-03-25 |url-status=dead}}</ref><ref>{{cite thesis |title=Skewed branch predictors |website=HAL |url=https://hal.science/inria-00073720/en/ |author-first1=Pierre |author-last1=Michaud |author-first2=André |author-last2=Seznec |author-first3=Richard |author-last3=Uhlig |s2cid=3712157 |date=September 1996|type=report }}</ref> is a [[digital electronics|digital circuit]] that tries to guess which way a [[branch (computer science)|branch]] (e.g., an [[conditional (programming)|if–then–else structure]]) will go before this is known definitively. The purpose of the branch predictor is to improve the flow in the [[instruction pipeline]]. Branch predictors play a critical role in achieving high [[computer performance|performance]] in many modern [[Instruction pipelining|pipelined]] [[microprocessor]] architectures.

[[File:Pipeline, 4 stage.svg|thumb|upright=1.2|Figure 1: Example of 4-stage pipeline. The colored boxes represent instructions independent of each other.]]

Two-way branching is usually implemented with a [[branch (computer science)|conditional jump]] instruction. A conditional jump can either be "taken" and jump to a different place in program memory, or it can be "not taken" and continue execution immediately after the conditional jump.  It is not known for certain whether a conditional jump will be taken or not taken until the condition has been calculated and the conditional jump has passed the execution stage in the instruction pipeline (see fig. 1).

Without branch prediction, the processor would have to wait until the conditional jump instruction has passed the execute stage before the next instruction can enter the fetch stage in the pipeline. The branch predictor attempts to avoid this waste of time by trying to guess whether the conditional jump is most likely to be taken or not taken. The branch that is guessed to be the most likely is then fetched and [[speculative execution|speculatively executed]]. If it is later detected that the guess was wrong, then the speculatively executed or partially executed instructions are discarded and the pipeline starts over with the correct branch, incurring a delay.

The time that is wasted in case of a '''branch misprediction''' is equal to the number of stages in the pipeline from the fetch stage to the execute stage. Modern microprocessors tend to have quite long pipelines so that the misprediction delay is between 10 and 20 [[clock cycle]]s. As a result, making a pipeline longer increases the need for a more advanced branch predictor.<ref>{{Cite conference|last1=Eyerman|first1=S.|last2=Smith|first2=J.E.|last3=Eeckhout|first3=L.|title=Characterizing the branch misprediction penalty|conference=2006 IEEE International Symposium on Performance Analysis of Systems and Software|year=2006|pages=48–58|publisher=IEEE|doi=10.1109/ispass.2006.1620789|isbn=1-4244-0186-0|s2cid=72217}}</ref>

The first time a conditional jump instruction is encountered, there is not much information to base a prediction on. However, the branch predictor keeps records of whether or not branches are taken, so when it encounters a conditional jump that has been seen several times before, it can base the prediction on the recorded history. The branch predictor may, for example, recognize that the conditional jump is taken more often than not, or that it is taken every second time.

Branch prediction is not the same as [[branch target predictor|branch target prediction]]. Branch prediction attempts to guess whether a conditional jump will be taken or not. Branch target prediction attempts to guess the target of a taken conditional or unconditional jump before it is computed by decoding and executing the instruction itself. Branch prediction and branch target prediction are often combined into the same circuitry.