Nios II - Branch Predication

[Altera_Forum]

Hello, 

 does somebody know more details about the Nios II-branch predication? I know only that two types are supported - static and dynamic. Any more details?  Thanks and greetings!

[Altera_Forum]

Hi niostester, 

 > does somebody know more details about the Nios II-branch predication?  What details are you looking for?  > Any more details?  You should read the Nios II Processor Reference Handbook -- you can find more information scattered about its pages.  Regards, --Scott

[Altera_Forum]

Branch prediction is to help the processor avoid pipeline stalls when it jumps. The processor is constantly looking ahead to the next instruction but jumps will prevent this sequential flow. Typically after a jump the pipeline needs to be flushed because the CPU went ahead and loaded the next instruction(s). 

 Branch prediction will help avoid the stall by giving the CPU a hint that it shouldn't load the next instruction but some other instruction (wherever your jump location is). The difference between static and dynamic is fairly straight forward. Static means that the table can't adapt to new jumps as the code runs. Dynamic means as your code runs the "branch prediction table" will update during runtime which gives you even few stalls because your branch prediction adapts to the state your processor happens to be in.  For more information take a look at the document smcnutt stated or google search "Branch prediction" since it's used in other processors as well.

[Altera_Forum]

Nios II dynamic branch prediction uses the classic gShare algorithm. 

Check out this paper http://www.cs.ucsb.edu/~arch/cs254/papers/combining.pdf (http://www.cs.ucsb.edu/~arch/cs254/papers/combining.pdf) for more details on gShare.   The branch history table is 256 entries (of 2 bits each). When the CPU feches a branch, it indexes into this table using the 8 LSB of the instruction address XORed with the 8 global branch history bits. This 2 bit entry specifies one of four states: strongly taken, weakly taken, weakly not taken, and strongly not taken. If the branch is either weakly or strongly predicted taken, the CPU predicts that the branch will be taken and fetches the target of the branch. If the prediciton is wrong, it takes four cycles to recover.  Static prediction just assumes all backwards branches are taken and all forward branches are not taken. This takes advantage of the branches at the end of loops which tend to be taken and tend to be backwards.