Talk:Branch predictor

From Wikipedia, the free encyclopedia

It's not true that all pipelined processors have to do branch prediction -- the processor could just wait on the results of the conditional statement before resuming execution. I know of at least one modern microcontroller that does this. The second paragraph should be changed to say that branch prediction is just the best way to handle conditionals --Ryan Stone 18:08, 17 Nov 2004 (UTC)

Which microcontroller? Iain McClatchie 18:43, 17 Nov 2004 (UTC)

Contents 1 all kinds of branches, or just conditional branches ? 2 some comments 3 question 4 Comments in relation to modern high performance MPUs

[edit] all kinds of branches, or just conditional branches ?

My understanding is that MIPS has a branch delay slot for *every* branch, even unconditional branches.

Yes, that's true. That's because irrespective of whether the branch is conditional or not, fetching the instruction at the target address takes some time. Another way the problem could be solved is to watch out for unconditional jump instructions right at the IF (instrn. fetch) stage instead of waiting for the ID (decode) stage & start fetching at the target address, but this increases the time taken by the IF stage & thus increases the time taken per instruction.

Are these "93.5%" numbers *just* for conditional branches, or do they also include unconditional branches ?

For unconditional branches, there's no use of predicting whether the branch is taken or not. They're always taken! Hence as far as the branch prediction logic goes, these should be treated as normal instructions.

A minor point about "unconditional branch" in MIPS. The `B <target>' "pseudo"-instruction is actually converted by the assembler to `BEQ $0, $0, <target>'. Since register 0 is equal to register 0, the branch is "unconditional". A MIPS processor could just naïvely treat it as a conditional branch and do branch prediction, or it could decode the instruction specially & avoid branch prediction. Note that the "unconditional jump" instruction `J <target>' is a real unconditional instruction and not assembler-synthesised. BTW the difference between B and J is that for B (used for nearby branches) the target is specified as a relative offset from the current PC whereas for J (used for "long" jumps) the absolute address of the target is specified. -- Paddu 07:42, 20 Feb 2005 (UTC)

For unconditional branches, at least on x86 systems, the target still must be predicted. Things like a "switch" statement in a high level language always branch, but it is not clear to where.:

In what way does the third paragraph of the article not address this point? Iain McClatchie 03:48, 15 October 2005 (UTC)

The article addresses it fine, but the "these should be treated as normal instructions" comment above is wrong. Branch prediction doesn't have to be done after the instruction is decoded, it can be done on the address alone, in which case you must predict the taken despite the fact it is unconditional.

[edit] some comments

I think it isn't made clear early enough in the section that the counters are indexed by the PC.

It might be good to move the local/global/combined predictor sections into a subsection of their own for 2-level predictors.

Good references on 2-level branch predictors: A Comparison of Dynamic Branch Predictors that use Two Levels of Branch History, by Yeh and Patt, 1993 (I've found it online as p257-yeh.pdf) Alternative Implementations of Two-Level Adaptive Branch Prediction, by Yeh and Patt, 1992 (p451-yeh.pdf)

A good (the original?) reference on global-history predictors: Improving the Accuracy of Dynamic Branch Prediction Using Branch Correlation, by Pan, So, and Rahmeh, 1992 (p76-pan.pdf)

A (the?) reference on gskew: Trading Conflict and Capacity Aliasing in Conditional Branch Predictors, by Michaud, Seznec and Uhlig, 1992 (p292-michaud.pdf)

I think a little too much importance is given to the comparison of the "speed" of the various predictor types (the article already mentions the need for overriding predictors, which arise because all interesting predictors are too slow).

It might be worth explaining more why branch prediction is so important. --CTho 02:20, 23 December 2005 (UTC)

Do we need to mention a little bit about perceptron predictors?

[edit] question

the article is not clear. "They allow processors to fetch and execute instructions without waiting for a branch to be resolved." Does the processor then discard the executed instructions if the branch is not taken? is this because logic is a lot slower than execution?

[edit] Comments in relation to modern high performance MPUs

Great article, it's quite comprehensive. One area that receives less attention than it should is specialized branch predictors. For instance, many of the advances in Intel's newer microarchitectures are adding more and more prediction mechanisms targeted at particular situations:

Indirect branch predictor - also to be added in AMD's new Barcelona core, mechanism to predict the target address of indirect branches. i.e. it picks from the BHT the most likely target address for a given branch Loop detector - mechanism to predict when a loop will be exited

Dkanter 19:38, 13 December 2006 (UTC)