Method and Apparatus for Branch Prediction

A branch prediction unit for prediction of a next taken branch instruction in a processing unit comprising the branch prediction unit, the branch prediction unit is:

• a pattern history memory comprising a number of branch source addresses and a number of branch indicators, wherein the branch indicator is configured to indicate at least one predicted taken branch instruction for a branch source address;
• a branch target buffer comprising a number of branch targets;
• and
• branch prediction logical circuit connected to the pattern history memory and to the branch target buffer, wherein the branch prediction logical circuit is configured to:
• receive a program counter corresponding to a start address of an instruction memory word;
• determine a search program counter based on the received program counter;
• by means of the search program counter, find in the pattern history memory at least one branch indicator, wherein the at least one branch indicator is configured to indicate at least one predicted taken branch instruction that is comprised in an execution path;
• select a first found branch indicator as an indication of a first predicted taken branch instruction in the execution path;
• by means of the first found branch indicator retrieve from the pattern history memory, a branch source address of the first predicted taken branch instruction;
• when the retrieved branch source address is the nearest branch source address to the search program counter,
• index the branch target buffer by means of the retrieved branch source address;
• output a retrieved branch target from the branch target buffer as a next program counter;
• and
• stop prediction of a next taken branch instruction.