Branch prediction utilizing both a branch target buffer and a multiple target table

• US 7,082,520 B2
• Filed: 05/09/2002
• Issued: 07/25/2006
• Est. Priority Date: 05/09/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Prasky, Brian R., Bonanno, James J.
• Primary Examiner(s): Tsai, Henry W. H.
• Assistant Examiner(s): DOLLINGER, TONIA LYNN MEONSKE
• Application Number:
  US10/143,621
• Publication Number:
  US 20030212882A1
• Time in Patent Office: 1,538 Days
• Field of Search: 712/236, 712/237, 712/238, 712/239, 712/240
• US Class Current: 712/236
• CPC Class Codes: G06F 9/322 for non-sequential address
• 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

Improved Branch prediction utilizes both a Branch Target Buffer (BTB) and a Multiple Target Table (MTT) for providing the capability to predict multiple targets for a single branch. A MTT when used in conjunction with a BTB allows for branches which have changing targets to be able to selectively choose the target of choice based on the execution path that was taken that lead to the given branch. The method predicts traget addresses, and between the static and dynamic target address, and upon finding a hit, the target is sent to the instruction cache such that a fetch can begin for the current target address and the target address is sent back to the Branch Target Buffer (BTB) to begin the search for the next branch given the current target predicted address. Upon resolving a branch the dynamic target is placed in MTT for future use.

Claims

1. A method of processing branch targets in a computer systems for a local microprocessor having branch prediction and an instruction cache using a Branch Target Buffer (BTB) comprising of:

(a) predicting an address corresponding to a next branch;

(b) predicting a static target address of a predicted branch; and

(c) predicting a dynamic target address of a predicted branch; and

then

(d) selecting between the static and dynamic target address wherein;

upon finding a hit during selecting between the static and dynamic target addresses, the target is sent to the local microprocessor'"'"'s instruction cache such that a fetch can begin for the current target address and the target address is sent back to the Branch Target Buffer (BTB) and a global history register (GHR) is speculatively updated immediately following and based upon a prediction of a dynamic target address of said next branch a speculative GHR is used to access a Multiple Target Table (MTT) in searching for a predicted target address for said next branch, and

wherein the step of selecting between the static and dynamic target address includes selecting between two predicted target addresses based on entry information supplied from said branch target buffer (BTB) and said Multiple Target Table (MTT) and upon resolving a branch the dynamic target is placed in said Multiple Target Table (MTT) for future use when the resolved dynamic taken branch of said branch target buffer (BTB) initially resolves with a different target address computation than employed when predicted via said branch target buffer (BTB).

2. The method as defined in claim 1 wherein predicting includes predicting an address of the location of the next branch in a given address space given a starting address point.

3. The method of claim 2, further comprising a step of updating the branch target buffer (BTB) with a new branch address entry upon resolution when a branch entry is currently not in the BTB.

4. The method as defined in claim 1 wherein predicting the static target address includes predicting a branch target address of a given branch based on the associated target of a last occurrence of the branch at the given address.

5. The method of claim 4, further comprising a step of updating the branch target buffer (BTB) with a new branch target entry upon resolution when a branch entry is currently not in the BTB.

6. The method of claim 4, further comprising a step of updating the branch target buffer (BTB) with a modified branch target entry upon resolution when the predicted branch target does not match an actual calculated target of a given branch.

7. The method of claim 4, further comprising a step of updating the branch target buffer (BTB) by setting a multiple target table ( MTT) tag bit when an entry was found in the branch target buffer (BTB);

but, however, the predicted branch target address was found to be incorrect based on the calculated target of the branch.

8. The method as defined in claim 1 wherein said predicting the dynamic target address includes predicting a target address of a given branch based on an associated target of the last occurrence of the branch based on the path of ‘

n’

taken and not taken branches in addition to the address of the predicted branch and saving a speculative history updated immediately after a branch prediction is used in the Global History Register (GHR) to provide acceptable accuracy in selecting the dynamic target address from the Multiple Target Table (MTT).

9. The method of claim 8, further comprising a step of selecting a multiple target table ( MTT) entry through the partial use of the global history register (GHR) based on speculative decode in a speculative path.

10. The method of claim 8, further comprising a step of updating an execute based GHR in addition to that of a decode based global history register (GHR) wherein, the execute GHR is updated on resolved branch direction.

11. The method of claim 10, further comprising a step of copying said updated execute GHR into the decode GHR when a pipe of said local microprocessor is to be flushed and restarted.

12. The method of claim 8, further comprising a step of updating the multiple target table ( MTT ) with a new branch address entry upon resolution when the new branch address entry is currently not in the BTB.

13. The method of claim 8, further comprising a step of updating the multiple target table ( MTT ) with a modified branch target entry upon resolution when a predicted target address does not match an actual calculated target address of a given branch.

14. The method of claim 1, further comprising of using an MTT tag bit within the BTB to select between the BTB and MTT target address.

15. The method of claim 1, further comprising of comparing an MTT tag of the MTT to a search address;

whereby, overriding the BTB'"'"'s MTT tag bit to select the BTB target if the MTT tag of the MTT does not equal the search address.