COMBINED LEVEL 1 AND LEVEL 2 BRANCH PREDICTOR

• US 20120166775A1
• Filed: 12/22/2010
• Published: 06/28/2012
• Est. Priority Date: 12/22/2010
• Status: Active Grant

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Krishnamurthy, Trivikram, Jarvis, Anthony
• Granted Patent: US 8,788,797 B2
• Time in Patent Office: Days
• US Class Current: 712/239
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques

Abstract

A branch predictor for use in a processor includes a Level 1 branch predictor, a Level 2 branch predictor, a match determining circuit, and an override determining circuit. The Level 1 branch predictor generates a Level 1 branch prediction. The Level 2 branch predictor generates a Level 2 branch prediction. The match determining circuit determines whether the Level 1 and Level 2 branch predictions match. The override determining circuit determines whether to override the Level 1 branch prediction with the Level 2 branch prediction. The Level 1 branch prediction is used when the Level 1 and Level 2 branch predictions match or when the Level 1 and Level 2 branch predictions do not match and the Level 1 branch prediction is not overridden. The Level 2 branch prediction is used when the Level 1 and Level 2 branch predictions do not match and the Level 1 branch prediction is overridden.

Claims

1. A method for generating a prediction in a processor, comprising:

generating a first prediction;

generating a second prediction;

using the first prediction if;

the first prediction and the second prediction match;

or

the first prediction and the second prediction do not match and the first prediction is not overridden by the second prediction.

2. The method according to claim 1, wherein:

the prediction is a branch prediction in a processor;

the first prediction is a Level 1 branch prediction; and

the second prediction is a Level 2 branch prediction.

3. The method according to claim 1, further comprising:

using the second prediction if the first prediction and the second prediction do not match and the first prediction is overridden by the second prediction.

4. A branch predictor for use in a processor, comprising:

a Level 1 branch predictor configured to generate a Level 1 branch prediction;

a Level 2 branch predictor configured to generate a Level 2 branch prediction;

a match determining circuit configured to determine whether the Level 1 branch prediction matches the Level 2 branch prediction; and

an override determining circuit configured to determine whether to override the Level 1 branch prediction with the Level 2 branch prediction.

5. The branch predictor according to claim 4, wherein a portion of the Level 1 branch predictor is shared with the Level 2 branch predictor.

6. The branch predictor according to claim 4, wherein the Level 1 branch predictor is configured to:

receive a program counter value and a global history value; and

generate the Level 1 branch prediction based on the program counter value and the global history value.

7. The branch predictor according to claim 6, wherein the global history value is the least significant bits of the global history of the branch predictor.

8. The branch predictor according to claim 4, wherein the Level 2 branch predictor is configured to:

receive a program counter value and a global history value; and

generate the Level 2 branch prediction based on the program counter value and the global history value.

9. The branch predictor according to claim 8, wherein the global history value is the most significant bits of the global history of the branch predictor.

10. The branch predictor according to claim 4, wherein the branch predictor uses the Level 1 branch prediction if the Level 1 branch prediction and the Level 2 branch prediction match.

11. The branch predictor according to claim 4, wherein the branch predictor uses the Level 1 branch prediction if the Level 1 branch prediction and the Level 2 branch prediction do not match and the Level 1 branch prediction is not overridden.

12. The branch predictor according to claim 4, wherein the branch predictor uses the Level 2 branch prediction if the Level 1 branch prediction and the Level 2 branch prediction do not match and the Level 1 branch prediction is overridden.

13. The branch predictor according to claim 4, wherein the Level 1 branch predictor includes:

a bias weight array;

a first predictor, including a first hash generator and a bimodal counter array;

a bimodal chooser; and

a multiplexer connected to the bias weight array, the first predictor, and the bimodal chooser.

14. The branch predictor according to claim 13, wherein the bias weight array is an array of weights indexed by a hash of a program counter value and is configured to generate a weight value.

15. The branch predictor according to claim 14, wherein the first predictor is configured to:

generate a hash of the program counter value and least significant bits of a global history value; and

index into the bimodal counter array using the hash to select a predictor value.

16. The branch predictor according to claim 15, wherein the bimodal counter is configured to:

receive the program counter value as an input;

generate a selection value based on the program counter value; and

provide the selection value to the multiplexer to select between the weight value of the bias weight array and the predictor value of the first predictor to use as the Level 1 branch prediction.

17. The branch predictor according to claim 15, wherein the Level 2 branch predictor includes:

the bias weight array;

the first predictor;

a second predictor, including a second hash generator and a weight array;

a weight translator; and

an adder.

18. The branch predictor according to claim 17, wherein the second predictor is configured to:

generate a hash of the program counter value and most significant bits of the global history value; and

index into the weight array using the hash to select a second weight.

19. The branch predictor according to claim 18, wherein the weight translator is configured to translate the predictor value into a translated weight value.

20. The branch predictor according to claim 19, wherein the adder is configured to add the weight value of the bias weight array, the translated weight value of the first predictor, and the second weight of the second predictor to generate the Level 2 branch prediction.

21. The branch predictor according to claim 4, wherein the override determining circuit includes a bimodal override predictor configured to generate an override signal based on a program counter value.

22. A computer-readable storage medium storing a set of instructions for execution by one or more processors to facilitate manufacture of a branch predictor, the branch predictor comprising:

a Level 1 branch predictor configured to generate a Level 1 branch prediction;

a Level 2 branch predictor configured to generate a Level 2 branch prediction;

a match determining circuit configured to determine whether the Level 1 branch prediction matches the Level 2 branch prediction; and

an override determining circuit configured to determine whether to override the Level 1 branch prediction with the Level 2 branch prediction.

23. The computer-readable storage medium of claim 22, wherein the instructions are hardware description language (HDL) instructions used for the manufacture of a device.