System and method for target branch prediction using correlation of local target histories

• US 20070239974A1
• Filed: 04/07/2006
• Published: 10/11/2007
• Est. Priority Date: 04/07/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Choi, Jong-Deok, Park, II, Serrano, Mauricio
• Granted Patent: US 7,434,037 B2
• Time in Patent Office: Days
• US Class Current: 712/238
• CPC Class Codes: G06F 9/30061 Multi-way branch instructions, e.g. CASE
• CPC Class Codes: G06F 9/322 for non-sequential address
• CPC Class Codes: G06F 9/323 for indirect branch instructions
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques

Abstract

An information processing system includes a branch target buffer (BTF) comprising the last next address for the instruction and for receiving an indirect instruction address and providing a BTB predicted target; and next branch target table (NBTT) for storing potential branch targets based on a history of the branch and for providing an NBTT when the a BTB predicted target is not successful. In another embodiment a system comprising a plurality of branch prediction resources dynamically predicts the best resource appropriate for a branch. The method includes predicting a target branch for an indirect instruction address using a resource chosen among the plurality of branch prediction resources; and selectively inhibiting updates of the branch prediction resources whose prediction accuracy does not meet a threshold.

Claims

1. An information processing system, comprising:

a branch target buffer (BTB) comprising the last next address for the instruction and for receiving an indirect instruction address and providing a BTB predicted target; and

next branch target table (NBTT) for storing potential branch targets based on a history of the branch and for providing an NBTT-target prediction when the BTB predicted target is not successful.

2. The system of claim 1, wherein the system can be further optimized for space by replacing the target address with an index into a second table branch history table (BHT) storing a local branch history for the past N targets including the oldest target and a series of targets decreasing in age, and wherein the BHT is coupled to the NBTT and is indexed by a branch address, the BHT providing an NTTM target when the BHT does not successfully predict the target.

3. The system of claim 2, wherein the BHT uses a branch history function (BHF) to a branch target address entry to access the NBTT.

4. The system of claim 1, further comprising an exclusion entry predictor (EP) to keep track of prediction accuracy and to inhibit update of inefficient entries.

5. The system of claim 4, wherein the EP is embedded into an existing predictor.

6. The system of claim 1, further comprising an exclusion table predictor for keeping track of the prediction accuracy and for inhibiting the branch target buffer.

7. The system of claim 1, further comprising a hashing function used to index the NBTT.

8. The system of claim 1, wherein the NBTT implements a state machine having a table index that represents the current state of a branch and the content of the table at the index represents the future state of the branch.

9. The system of claim 1, further comprising a thread identification for running several threads simultaneously.

10. A computer-implemented method to predict multiple targets for a single branch comprising steps of:

receiving an indirect branch instruction;

searching a branch target buffer for a target of the indirect branch instruction, the branch target buffer comprising the last next address for the instruction; and

if the target is not found in the indirect branch instruction searching a next branch target storing potential branch targets based on a history of the branch.

11. The method of claim 10 further comprising an exclusion table predictor for keeping track of the prediction accuracy and for inhibiting the branch target buffer.

12. The method of claim 10, further comprising a hashing function used to index the NBTT.

13. The method of claim 10 wherein the NBTT implements a state machine having a table index that represents the current state of a branch and the content of the table at the index represents the future state of the branch.

14. An information processing system, comprising:

a branch target buffer (BTF) comprising the last next address for the instruction and for receiving an indirect instruction address and providing a BTB predicted target; and

a branch history table (BHT) storing a local branch history for the past N targets including the oldest target and a series of targets decreasing in age, and wherein the BHT is coupled to the NBTT and is indexed by a branch address, the BHT providing an NTTM target when the BHT does not successfully predict the target.

15. The system of claim 14 system further comprising a next branch target table (NBTT) for storing potential branch targets based on a history of the branch and for providing an NBTT when the a BTB predicted target is not successful.

16. The system of claim 14, wherein the BHT uses a branch history function (BHF) to a branch target address entry to access the NBTT.

17. The system of claim 14 further comprising The system of claim 2, wherein the BHT uses a branch history function (BHF) to a branch target address entry to access the NBTT.

18. In a system comprising a plurality of branch prediction resources a method for dynamically predicting the best resource appropriate for a branch, a method comprising:

predicting a target branch for a indirect instruction address using a resource chosen among the plurality of branch prediction resources; and

selectively inhibiting updates of the branch prediction resources whose prediction accuracy does not meet a threshold.

19. The method of claim 18 wherein the resources are tables.

20. An exclusion predictor comprising:

a plurality of branch prediction resources for dynamically predicting the best resource appropriate for predicting a target for a branch;

an inhibitor for inhibiting the updating of the branch prediction resources whose prediction accuracy does not meet a threshold.