Why superscalar processors use dynamic branch prediction

Question

I'm studying for an exam on Advanced Computer Architecture and in an exam question the question above is asked.

I know that branch prediction is crucial in superscalar processors in order to exploit ILP as much as possible, but I was wondering what could be the precise reason why superscalar processors use dynamic branch prediction instead of static one.

Update:

Hi again, as the two comments below suggested, I tried to think about it and thought that in case of a misprediction a processor using branch predictor has to flush the pipeline from the incorrect instructions issued because of the prediction.

So, for a superscalar processor issuing multiple instructions at the same time, the penalty would be much higher, but I'm still not sure this is the real point...

Any other help?

Answer 1

What you want from a branch predictor: Low implementation cost, prediction speed (you don't want to wait for branch prediction), and high accuracy (high percentage of correctly predicted branches).

So compare static and dynamic branch prediction: Dynamic branch prediction is more expensive, after all it needs to store the history of branches. Dynamic branch history is as fast as static prediction, but its accuracy is enormously higher.

The logical consequence is that when you build a chip that is going to be expensive and high performance anyway, you are not going to scrimp on the cost of branch prediction and use the more accurate method.

And look at Pseudonym's comment: Look at what a static branch predictor does, and see why it will be often less good than dynamic prediction. (Not always. Any dynamic branch prediction can be tricked into always predicting wrong).

Answer 2

About the cost of mispredictions: I have a newish superscalar processor, and timing can be “interesting”. It can issue three floating-point instructions per cycle, but they usually have four cycles latency. So you might have a loop with 20 instructions that take 80 cycles to finish using only one 12th of the available capacity. Now you do 1000 iterations and the calculations from 12 iterations can overlap if they are independent. So suddenly you have 240 operations in flight simultaneously, using all the available hardware.

And then you get a branch misprediction. That misprediction might be detected at the very end of an iteration after 80 cycles. With 200 instructions incorrectly executed. That really costs.

And dynamic prediction tends to mispredict rarely, while static misprediction may mispredict most of the time.

Answer 3

Something else happens in compilers that try to do static prediction. On many processors branches taken take longer than branches not taken. Now take a statement “if (x == 0) ++z;”. Typically you will have a conditional branch around the ++z. Now assume the compiler thinks that x is almost never zero. So the branch is always taken. The compiler can put the code for the ++z somewhere else, have a conditional branch that almost never branches to the ++z but 99.9% falls through to the next statement-which is faster. So you can use static prediction in the compiler to rearrange your code to have fewer branches taken.