Prediction?

[Harabecw]

How does a CPU "predict" what it should do?
Why does it do it?
what exactly is a "miss"? when the CPU predicts something but ends up needing to do something else?

To make it clear...do both the P4's and AthlonXP's do it?

Thanks for your time

 

[sgtroyer]

I'm not qualified to explain how branch prediction works, but I can tell you why. All modern processors that I know of perform branch prediction, some better than others. The reason is pipelining. Pipelining involves breaking a complicated instruction up into separate chunks so that more than one instruction can be worked on at a time.

A pipeline is like an assembly line. Instead of working on one car at a time, and not starting the second car until the first is completely finished, you work on many cars simultaneously. While the first car is being painted, the second one is being welded, or whatever. The time to finish one car is the same, but the throughput of cars per hour is much higher.

So how does this relate to branch prediction? Suppose you add A + B to get C. Then you branch if C = D. Because of the pipeline, the processor will start the branch instruction before the addition is finished. It doesn't know the answer, but it needs to make a decision. So it guesses. It chooses one alternative, and keeps working on it. When the first instruction is done, it checks to see if it guessed right. If so, everything proceeds as normal. If not, however, the processor must back up and start over again. In modern processors, with very deep pipelines, this can be a serious performance hit. So accurate branch prediction is very important, and a good processor is right most of the time.

I'd recommend any of the Hennessy and Patterson Computer Architecture books for much more extensive information on this. A good starting point is "Computer Organization and Design: The Hardware Software Interface"

 

[wviperw]

/me trys to recall CompOrg class...

A computer predicts pretty much just like we do. It makes predictions based on the facts it has on hand. It can predict "never taken" (ignore a choice with this set of conditions), "always taken" (automatically choose a choice with this set of conditons), predict by opcode, and predict by history (look at frequency tables).

I guess a "miss" would be what you said. Let's say the computer decides to branch from A to B because based on A's history, there is a 90% chance this is what the decision will be. However, if what actually happens is that the decision is C, then A has to branch to C, it is a "miss", and you use precious time.

(I knew I should have listened better in class )

 

[frostgiant]

Not sure how the x86 does it, though I know it is complex.

Some embedded CPUs are much more simple. Their guess is that a branch will not be taken and cache the instruction after the branch. Thus, on a CPU like this, it is in your best interest to program for the most likely case not to branch.

I think I read in some ASM manual that the P4 lets you specify which way a branch is more likely to go... But I am not sure.

 

[Lynx516]

x86 CPUs and most highend CPUs use what is know as a branch table to help in branch prediction. In this table it records whether a branch is either strongly taken,lightly taken,lightly not taken or strongly not taken and then makes disisions based on that.

Less complex CPUs such as the ARM 7 CPU use a technique that says that if the branch links backwards (i.e. a loop) it always takes it while if it links forwards it doesnt.

When it misses all the work it has done is useless and it has to flush all the useless code out of the pipeline which costs alot of cycles.

FrostGiant it is very very unliky if the P4 has something to say if a branch is more likly to be taken because branchprediction was not invented when x86 was introduced and hence if it is not in x86 then it is unliukly the P4 supports it. (SSE is a different thing all together so no comments about it :frown