Branch prediction in a data processing apparatus

• US 20040210749A1
• Filed: 04/15/2003
• Published: 10/21/2004
• Est. Priority Date: 04/15/2003
• Status: Active Grant

• Current Assignee: Arm Limited (SoftBank Group Corp.)
• Original Assignee: Arm Limited (SoftBank Group Corp.)
• Inventors: Biles, Stuart David
• Granted Patent: US 7,831,817 B2
• Time in Patent Office: Days
• US Class Current: 712/240
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques

Abstract

The present invention relates to a branch prediction logic and method for generating a branch bias providing a prediction as to whether execution of a branch instruction will result in a branch being taken or not taken. The branch prediction logic comprises a first branch bias storage operable to store for each of a plurality of first address portions a corresponding first branch bias value, the first branch bias storage being operable upon receipt of a first address portion of the branch instruction'"'"'s address to output the corresponding first branch bias value from the first branch bias storage. The history storage is also provided for storing history data identifying an outcome for a number of preceding branch instructions. In addition, a single second branch bias storage is provided having a number of entries, each entry being operable to store a replacement branch bias value and a TAG value indicative of an instance in which the replacement branch bias value should be used as the generated branch bias in preference to the first branch bias value. Index generation logic is used to generate an index identifying a corresponding entry in the single second branch bias storage, with the index being derived from the history data. The single second branch bias storage is operable upon receipt of the index to cause the content of the corresponding entry to be output from the single second branch bias storage. Selection logic is then operable to select, as the branch bias generated by the branch prediction logic, the first branch bias value, unless the TAG value output from the single second branch bias storage corresponds to a comparison TAG value derived from a second address portion of the branch instruction'"'"'s address, in which event the selection logic is operable to select as the branch bias generated by the branch prediction logic the replacement branch bias value output from the single second branch bias storage.

Claims

1. Branch prediction logic for generating a branch bias providing a prediction as to whether execution of a branch instruction will result in a branch being taken or not taken, the branch prediction logic comprising:

a first branch bias storage operable to store for each of a plurality of first address portions a corresponding first branch bias value, the first branch bias storage being operable upon receipt of a first address portion of the branch instruction'"'"'s address to output the corresponding first branch bias value from the first branch bias storage;

a history storage operable to store history data identifying an outcome for a number of preceding branch instructions;

a single second branch bias storage having a number of entries, each entry being operable to store a replacement branch bias value and a TAG value indicative of an instance in which the replacement branch bias value should be used as the generated branch bias in preference to the first branch bias value;

index generation logic operable to generate an index identifying a corresponding entry in the single second branch bias storage, the index being derived from the history data;

the single second branch bias storage being operable upon receipt of the index to cause the content of the corresponding entry to be output from the single second branch bias storage; and

selection logic operable to select as the branch bias generated by the branch prediction logic the first branch bias value, unless the TAG value output from the single second branch bias storage corresponds to a comparison TAG value derived from a second address portion of the branch instruction'"'"'s address, in which event, the selection logic is operable to select as the branch bias generated by the branch prediction logic the replacement branch bias value output from the single second branch bias storage.

2. Branch prediction logic as claimed in claim 1, wherein said index generation logic is operable to generate the index from a logical combination of the history data and the branch instruction'"'"'s address.

3. Branch prediction logic as claimed in claim 1, wherein the single second branch bias storage is a set associative storage, wherein the index identifies multiple corresponding entries in the single second branch bias storage, the selection logic being operable to determine whether any of the TAG values output from the corresponding entries correspond to the comparison TAG value, and in the event of such correspondence with the TAG value of one of said corresponding entries, to select the replacement branch bias value for that one corresponding entry as the branch bias generated by the branch prediction logic.

4. Branch prediction logic as claimed in claim 3, wherein the selection logic further comprises a priority encoder operable, in the event that the selection logic determines correspondence with the TAG value from more than one of said corresponding entries, to perform a predetermined prioritisation routine to determine which of those corresponding entries'"'"' replacement branch bias value is to be selected as the branch bias generated by the branch prediction logic.

5. Branch prediction logic as claimed in claim 1, further comprising update logic operable to update the history data in the history storage to take account of whether execution of the branch instruction results in a branch being taken or not taken.

6. Branch prediction logic as claimed in claim 1, further comprising update logic operable, following subsequent execution of the branch instruction, to update within the first branch bias storage the first branch bias value associated with the first address portion of the branch instruction so as to take account of whether the execution of the branch instruction resulted in a branch being taken or not taken, unless one of said replacement branch bias values was used as the generated branch bias, that replacement branch bias value correctly predicted the branch, and the first branch bias value would have incorrectly predicted the branch, in which event no update of the first branch bias value is performed.

7. Branch prediction logic as claimed in claim 1, further comprising update logic operable, following subsequent execution of the branch instruction, and if one of said replacement branch bias values was used as the generated branch bias, to update that replacement branch bias value within the corresponding entry of the single second branch bias storage so as to take account of whether the execution of the branch instruction resulted in a branch being taken or not taken.

8. Branch prediction logic as claimed in claim 1, wherein the first branch bias storage is a table.

9. Branch prediction logic as claimed in claim 1, wherein the single second branch bias storage is a single cache.

10. A data processing apparatus comprising:

an execution unit operable to execute a sequence of instructions; and

a prefetch unit operable to prefetch instructions from a memory for passing to the execution unit;

the prefetch unit including branch prediction logic operable to generate a branch bias providing a prediction as to whether execution of a branch instruction by the execution unit will result in a branch being taken or not taken;

the branch prediction logic comprising;

a first branch bias storage operable to store for each of a plurality of first address portions a corresponding first branch bias value, the first branch bias storage being operable upon receipt of a first address portion of the branch instruction'"'"'s address to output the corresponding first branch bias value from the first branch bias storage;

a history storage operable to store history data identifying an outcome for a number of preceding branch instructions;

a single second branch bias storage having a number of entries, each entry being operable to store a replacement branch bias value and a TAG value indicative of an instance in which the replacement branch bias value should be used as the generated branch bias in preference to the first branch bias value;

index generation logic operable to generate an index identifying a corresponding entry in the single second branch bias storage, the index being derived from the history data;

the single second branch bias storage being operable upon receipt of the index to cause the content of the corresponding entry to be output from the single second branch bias storage; and

selection logic operable to select as the branch bias generated by the branch prediction logic the first branch bias value, unless the TAG value output from the single second branch bias storage corresponds to a comparison TAG value derived from a second address portion of the branch instruction'"'"'s address, in which event, the selection logic is operable to select as the branch bias generated by the branch prediction logic the replacement branch bias value output from the single second branch bias storage.

11. A method of generating within a data processing apparatus a branch bias providing a prediction as to whether execution of a branch instruction will result in a branch being taken or not taken, the method comprising the steps of:

referencing a first branch bias storage using a first address portion of the branch instruction'"'"'s address, the first branch bias storage being operable to store for each of a plurality of first address portions a corresponding first branch bias value, and being responsive to said referencing to output the first branch bias value corresponding to the first address portion of the branch instruction'"'"'s address;

storing history data identifying an outcome for a number of preceding branch instructions;

generating an index identifying a corresponding entry in a single second branch bias storage, the index being derived from the history data, the single second branch bias storage having a number of entries, each entry being operable to store a replacement branch bias value and a TAG value indicative of an instance in which the replacement branch bias value should be used as the generated branch bias in preference to the first branch bias value;

referencing the single second branch bias storage using the index to cause the content of the corresponding entry to be output from the single second branch bias storage; and

selecting as the generated branch bias the first branch bias value, unless the TAG value output from the single second branch bias storage corresponds to a comparison TAG value derived from a second address portion of the branch instruction'"'"'s address, in which event, selecting as the generated branch bias the replacement branch bias value output from the single second branch bias storage.

12. A method as claimed in claim 11, wherein the index is generated from a logical combination of the history data and the branch instruction'"'"'s address.

13. A method as claimed in claim 11, wherein the single second branch bias storage is a set associative storage, wherein the index identifies multiple corresponding entries in the single second branch bias storage, the selecting step further comprising the steps of:

determining whether any of the TAG values output from the corresponding entries correspond to the comparison TAG value; and

in the event of such correspondence with the TAG value of one of said corresponding entries, selecting the replacement branch bias value for that one corresponding entry as the generated branch bias.

14. A method as claimed in claim 13, wherein said determining step further comprises the step of:

in the event that correspondence with the TAG value from more than one of said corresponding entries is determined, performing a predetermined prioritisation routine to determine which of those corresponding entries'"'"' replacement branch bias value is to be selected as the generated branch bias.

15. A method as claimed in claim 11, further comprising the step of:

updating the history data in the history storage to take account of whether execution of the branch instruction results in a branch being taken or not taken.

16. A method as claimed in claim 11, further comprising the step of:

following subsequent execution of the branch instruction, updating within the first branch bias storage the first branch bias value associated with the first address portion of the branch instruction so as to take account of whether the execution of the branch instruction resulted in a branch being taken or not taken, unless one of said replacement branch bias values was used as the generated branch bias, that replacement branch bias value correctly predicted the branch, and the first branch bias value would have incorrectly predicted the branch, in which event no update of the first branch bias value is performed.

17. A method as claimed in claim 11, further comprising the step of:

following subsequent execution of the branch instruction, and if one of said replacement branch bias values was used as the generated branch bias, updating that replacement branch bias value within the corresponding entry of the single second branch bias storage so as to take account of whether the execution of the branch instruction resulted in a branch being taken or not taken.

18. A method as claimed in claim 11, wherein the first branch bias storage is a table.

19. A method as claimed in claim 11, wherein the single second branch bias storage is a single cache.