Apparatus and method for branch prediction utilizing a predictor combination in parallel with a global predictor

• US 7,219,217 B1
• Filed: 10/16/1998
• Issued: 05/15/2007
• Est. Priority Date: 10/16/1998
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Baweja, Gunjeet, Kumar, Harsh
• Primary Examiner(s): Patel; Gautam R.
• Application Number:
  US09/174,434
• Time in Patent Office: 3,133 Days
• Field of Search: 712/239, 712/240, 712/237, 712/238
• US Class Current: 712/239
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques

Abstract

An apparatus and method for branch prediction are disclosed. The branch predictor has four portions. The first includes a bimodal branch predictor in series with a local branch predictor; the second includes a global branch predictor. The first and second portions are in parallel and operate concurrently, and each provide an output received by the fourth portion. The third portion receives address data and selection data, and also provides output to the fourth portion. The fourth portion receives these outputs, and provides a branch prediction. The branch prediction is a selection of either the output from the first portion or the output from the second portion, based upon selection criteria received from the third portion.

Claims

1. An apparatus comprising:

a first portion including a bimodal branch predictor and a local branch predictor;

a second portion in parallel with the first portion, the second portion including a global branch predictor.

2. The apparatus of claim 1, further comprising:

a third portion to receive address data and selection data; and

a fourth portion to receive input from the first portion, the second portion, and the third portion, and to provide a branch prediction.

3. The apparatus of claim 2, wherein the third portion comprises an array of 2-bit counters, and wherein the fourth portion comprises a multiplexor.

4. An apparatus comprising:

a first branch predictor portion including a bimodal branch predictor and a local branch predictor, the first branch predictor portion to provide a first output;

a global branch predictor in parallel with the first branch predictor portion to provide a second output.

5. The apparatus of claim 4, further comprising:

a first portion to receive data regarding a branch instruction address, and to provide a third output; and

a second portion to receive the first output, the second output, and the third output, and to provide an output representative of a branch to be taken.

6. The apparatus of claim 5, wherein the first portion comprises an array of 2-bit counters, and wherein the second portion comprises a multiplexor.

7. The apparatus of claim 5, wherein the data regarding the branch instruction address comprises:

a branch instruction address; and

data regarding whether previously the first branch predictor portion or the second branch predictor portion performed better for the branch instruction address.

8. An apparatus comprising:

a first portion including a bimodal branch predictor means and a local branch predictor means; and

a second portion in parallel with the first portion, the second portion including a global branch predictor means.

9. The apparatus of claim 8, further comprising:

a third portion comprising an array of 2-bit counters to receive address data and selection data; and

a multiplexor to receive input from the first portion, the second portion, and the third portion, and to provide a branch prediction.

10. A method comprising:

performing a global branch prediction;

performing, in parallel with said performing the global branch prediction, a bimodal branch prediction and a local branch prediction.

11. The method of claim 10, further comprising:

receiving address data and selection data; and

creating a branch prediction using the global branch prediction, the bimodal branch prediction, the local branch prediction, the address data, and the selection data.

12. The method of claim 11, further comprising, in parallel with said performing the global branch prediction, selecting the local branch prediction if there is a hit in a local history table of a local predictor, otherwise selecting the bimodal branch prediction.

13. A method comprising:

performing, in parallel,

a bimodal branch prediction and a local branch prediction, and selecting either the bimodal branch prediction or the local branch prediction, and

a global branch prediction; and

selecting either the selected prediction or the global branch prediction.

14. The method of claim 13, wherein said selecting either the bimodal branch prediction or the local branch prediction comprises selecting the local branch prediction if there is a hit in a local history table of a local predictor, otherwise selecting the bimodal branch prediction.

15. A method comprising:

performing a bimodal branch prediction and creating a bimodal output;

performing a local branch prediction and creating a local output;

creating a first branch prediction by using the bimodal output and the local output;

in parallel with said performing the bimodal branch prediction, said performing the local branch prediction, and said creating the first branch prediction, performing a global branch prediction and creating a second branch prediction; and

selecting either the first branch prediction or the second branch prediction.

16. The method of claim 15, wherein said performing the local branch prediction and said creating the local output comprises storing local history data.

17. The method of claim 16, wherein said creating the first branch prediction comprises selecting either the bimodal output or the local output as the first branch prediction, using the local history data.

18. The method of claim 15, further comprising storing history data regarding the first branch prediction and the second branch prediction.

19. The method of claim 18, wherein said selecting either the first branch prediction or the second branch prediction comprises using the history data regarding the first branch prediction and the second branch prediction in making the selection.

20. A method comprising:

performing a bimodal branch prediction;

performing a local branch prediction;

selecting either the bimodal branch prediction or the local branch prediction; and

concurrently with at least one of said performing the bimodal branch prediction, said performing the local branch prediction, or said selecting, performing a global branch prediction.

21. The method of claim 20, further comprising selecting either the selected branch prediction or the global branch prediction based on information indicating whether, in the past, the selected branch prediction or the global branch prediction has been a better predictor.

22. The method of claim 20, wherein said selecting either the bimodal branch prediction or the local branch prediction comprises selecting the local branch prediction if there is a hit in a local history table of a local predictor, otherwise selecting the bimodal branch prediction.