Usefulness indication for indirect branch prediction training

Patent metadata

Field	Value
Publication number	US-9311100-B2
Application number	US-201313735694-A
Country	US
Kind code	B2
Filing date	Jan 7, 2013
Priority date	Jan 7, 2013
Publication date	Apr 12, 2016
Grant date	Apr 12, 2016

Abstract

A circuit for implementing a branch target buffer. The branch target buffer may include a memory that stores a plurality of entries. Each entry may include a tag value, a target value, and a prediction accuracy value. A received index value corresponding to an indirect branch instruction may be used to select one of entries of the plurality of entries, and a received tag value may then be compared to the tag value of the selected entries in the memory. An entry in the memory may be selected in response to a determination that the received tag does not match the tag value of compared entries. The selected entry may be allocated to the indirect instruction branch dependent upon the prediction accuracy values of the plurality of entries.

First claim

What is claimed is:

1. An apparatus, comprising:
a first memory configured to store a first plurality of entries, wherein each entry of the first plurality of entries includes a tag value, a target value, and a prediction accuracy value;
a second memory configured to store a second plurality of entries, wherein each entry of the second plurality of entries includes a tag value, a target value, a prediction accuracy value, and a hysteresis value that includes information indicative of a number of mispredictions of a corresponding entry of the second plurality of entries; and
a control module coupled to the memory and configured to receive an index value and a tag value corresponding to an indirect instruction branch, wherein the index value is used to read one or more entries of the first and second plurality of entries;
wherein the control module is further configured to, in response to a determination that the received tag value corresponding to the indirect instruction branch does not match the tag value of the first and second plurality of entries, select an entry in the first plurality of entries dependent upon the prediction accuracy values of the first plurality of entries, and allocate the selected entry to the instruction branch.

2. The apparatus of claim 1 , wherein the control module is further configured to prevent allocation of the selected entry in response to a determination that the prediction accuracy value of the selected entry is indicative of a correct prediction from the entry.

3. The apparatus of claim 2 , wherein the control module is further configured to reset the prediction accuracy value of the selected entry in response to the prevention of allocation.

4. The apparatus of claim 1 , wherein the control module is further configured to, in response to a determination that the received tag value matches the tag value corresponding to the indirect instruction branch of one of the one of more first and second plurality of entries, set the prediction accuracy value to a value indicative of a correct prediction from the one of the one or more first and second plurality of entries.

5. The apparatus of claim 1 , wherein the first memory comprises a cache memory.

6. A method, comprising:
storing, in a first memory, a first plurality of entries, wherein each entry of the first plurality of entries includes a tag value, a target value, and prediction accuracy value;
storing, in a second memory, a second plurality of entries, wherein each entry of the second plurality of entries includes a tag value, a target value, a prediction accuracy value, and a hysteresis value that includes information indicative of a number of mispredictions of corresponding entry of the second plurality of entries;
receiving an index value and a tag value corresponding to an indirect branch;
comparing, dependent upon the received index value, tag values in each or the first and second plurality of entries to the received tag value corresponding to the indirect branch;
selecting, in response to determining that the received tag value does not match the tag value of compared entries, an entry of the first plurality of entries dependent upon the prediction accuracy values of the plurality of entries;
allocating the selected entry to the indirect branch; and
setting the prediction accuracy value of the allocated entry to indicate an accurate prediction.

7. The method of claim 6 , further comprising, preventing the allocation of the selected entry in response to determining that the prediction accuracy value of the selected entry is indicative of an accurate prediction.

8. The method of claim 7 , further comprising, re-setting the prediction accuracy value of the selected entry in response to the prevention of the allocation.

9. The method of claim 6 , further comprising, in response to determining that the received tag value corresponding to the indirect branch matches the tag value of an entry of the compared entries, setting the prediction accuracy value of the entry whose tag value matches the received tag value to a value indicative of an accurate prediction.

10. The method of claim 6 , further comprising, updating the tag value and the target value of the selected entry of the first plurality of entries.

11. A system, comprising:
a processor; and
one or more memories;
wherein the processor includes a first branch target buffer, a second branch target buffer, and a control module coupled to the first and second branch target buffers, and configured to receive an indirect branch;
wherein the first branch target buffer is configured to store a first plurality of entries, wherein each entry includes a tag value, a target value, and a prediction accuracy value;
wherein the second branch target buffer is configured to store a second plurality of entries, wherein each entry of the second plurality of entries includes a tag value, a target value, a prediction accuracy value, and a hysteresis value that includes information indicative of a number of mispredictions of corresponding entry of the second plurality of entries;
wherein the control module is further configured to, in response to a determination that the received indirect branch does not match an entry in either of the first or second branch target buffers, select a least frequently used entry in the first branch target buffer, and allocate the received indirect branch to the least frequently used entry dependent upon the prediction accuracy value of the least frequently used entry.

12. The system of claim 11 , wherein the control module is further configured to, in response to a determination that the received indirect branch matches an entry in the second branch target buffer, increase the prediction accuracy value of the matched entry.

13. The system of claim 11 , wherein the control module is further configured to update the tag value and the target value of the least frequently used entry responsive to the allocation.

14. The system of claim 11 , wherein the control module is further configured to decrease the prediction accuracy value of the least frequently used entry responsive to the allocation.

15. The system of claim 11 , wherein the first branch target buffer comprises a cache memory.

16. A branch predictor, comprising:
a first branch target buffer configured to store a first plurality of entries, wherein each entry of the first plurality of entries includes a tag value, a target value, and a prediction accuracy value;
a second branch target buffer configured to store a second plurality of entries, where in each entry of the second plurality of entries includes a tag value, a target value, a prediction accuracy value, and a hysteresis value that includes information indicative of a number of mispredictions of corresponding entry of the second plurality of entries; and
a control module coupled to the first branch target buffer and the second branch target buffer, and configured to receive an indirect branch;
wherein the control module is configured to, in response to a determination that the received indirect branch does not match an entry in either the first plurality of entries and the second plurality of entries, select a least frequently used entry in the first branch target buffer, and allocate the indirect branch to the selected least frequently used entry dependent upon the accuracy of the selected least frequently used entry.

17. The branch predictor of claim 16 , wherein the control module is further configured to update a path history.

18. The branch predictor of claim 17 , wherein

Assignees

• Apple Inc

Inventors

• Gupta Sandeep
• Sundar Shyam
• Lien Wei-Han
• Williams Iii Gerard R
• Blasco-Allue Conrado

Classifications

• G06F9/30072

  to perform conditional operations, e.g. using predicates or guards · CPC title

• G06F9/3848

  using hybrid branch prediction, e.g. selection between prediction techniques · CPC title

• G06F9/3844 Primary

  using dynamic branch prediction, e.g. using branch history tables · CPC title

• G06F9/3806

  using address prediction, e.g. return stack, branch history buffer · CPC title

• G06F9/323

  for indirect branch instructions · CPC title