Nios II - Branch Prediction

I am not sure how it is for Nios II, but in general.

For static branch prediction, the CPU makes a fixed prediction when it encounters a conditional branch in the instruction stream. For example if the CPU encounters a jump on zero flag set, a static branch predictor will assume that the CPU will take the branch. It does not use the history of the instruction to determine if it will branch or not. This I believe has pretty good results.

A dynamic branch predictor works on the history of the instruction stream to determine if a jump will take place. For example if the CPU encounters the same aforementioned instruction, it will look into internals to determine the history of the instruction and make a prediction based on that. The function to keep track of this varies widely. A good example to look at would be the original Intel Pentium's BTB (Branch Target Buffer). Or looking at the way the P2 or P3 do it. The methods these chips use are ingenious and have very good prediction rates, but by the looks of it, they do require some complicated hardware.

Obviously the dynamic predictor will have better prediction records than the static, but the static is FAR easier to implement.

Here is a link:

I was reading this article sometime ago and was very impressed with the method Intel used. Perhaps somebody could post a link to a better method than this, than I will faint :).

-Isaac

Hi Udo,

Your chances of getting a reply from an expert are much better if you post Nios questions on

- Subroto Datta Altera Corp.

Hi Isaac,

There are far fancier ones than this. The DEC Alpha 21264 had a snazzy scheme where they had two different branch predictors, and picked the better of the two dynamically. A global predictor used the results (taken/not taken) of the last 12 branches to predict what the next branch would do. A local predictor tracked for a set of branches whether they were taken or not taken for the past few times the branch was evaluated, and predicts accordingly.

The 21264 would then store on a per-branch basis which predictor was doing a better job. Some branches (say, the end of a for loop with a lot of iterations) are well predicted by a local predictor. Some branches (for example, a for loop that iterates exactly 4 times, resulting in taken-taken-taken-not_taken pattern) are better predicted by a global predictor. So it woudl get the best of both worlds.

I did a school project on 21264 branch prediction, but can no longer find the source material on the web. However, I did come across this fairly good presentation that describes branch prediction methods and which processors use what.

Enjoy,

Paul Leventis Altera Corp.