branch prediction

(redirected from Branch predictor)
Also found in: Wikipedia.

branch prediction

[′branch prə‚dik·shən]
(computer science)
A method whereby a processor guesses the outcome of a branch instruction so that it can prepare in advance to carry out the instructions that follow the predicted outcome.

branch prediction

(processor, algorithm)
A technique used in some processors with instruction prefetch to guess whether a conditional branch will be taken or not and prefetch code from the appropriate location.

When a branch instruction is executed, its address and that of the next instruction executed (the chosen destination of the branch) are stored in the Branch Target Buffer. This information is used to predict which way the instruction will branch the next time it is executed so that instruction prefetch can continue. When the prediction is correct (and it is over 90% of the time), executing a branch does not cause a pipeline break.

Some later CPUs simply prefetch both paths instead of trying to predict which way the branch will go.

An extension of the idea of branch prediction is speculative execution.

branch prediction

In CPU instruction execution, predicting the outcome of a branch so that those instructions may be executed in parallel with the current instructions. If the CPU guesses the wrong branch, it will take extra machine cycles to go back and execute the correct one; however, on average, if the prediction algorithms are good, overall performance is increased. See predication and branch.
References in periodicals archive ?
It has to do with "training" the branch predictor hardware to
Keywords: branch predictor, bimodal, finite state machine, SDFSM, SPEC2000, saturated counter, SimpleScalar
This method of state swapping dynamically records unique branch patterns, thus specializing the branch predictor to the needs of an application.
The novelty of this proposal is the inclusion of data values to assign confidence to branch predictions, attempting to use different information from that employed by the branch predictor (usually branch history and branch PC).
The second proposal generalizes the BPRU, improving its functionality with a twofold objective: first, that it could be used as an independent confidence estimator, and second, continuing with the application to branch inversion, that it could be used in conjunction with any correlating branch predictor in a hybrid scheme as an effective approach to increasing the original branch prediction accuracy.
With imperfect branch prediction, uncommon paths, like error conditions, may be executed (but not committed) if the branch predictor points that way.
Parameter Value Branch Predictor Combined, Bimodal 4K table, 2-Level 1K table, 10-bit history 4K chooser BTB 2048-entry, 2-way Return-address stack 32-entry Mispredict penalty 2 cycles
The chip is an out-of-order design capable of decoding four instructions per cycle and with a perceptron-based branch predictor.
Finally, the conditional branch predictor combines a 1K-entry local history table indexing a 1K-entry local prediction table with a 4K-entry global history table, using a 4K-entry selection table.
They said Spectre "miss-trains branch predictors in modern processors in order to trick applications into accessing arbitrary locations in their memory.
The core also includes a 128-entry, fully set associative TLB (Translation Lookaside Buffer) and advanced branch predictors to optimize flow through the pipeline.