System, apparatus and method for controlling allocations into a branch prediction circuit of a processor

• US 10,642,621 B2
• Filed: 12/29/2017
• Issued: 05/05/2020
• Est. Priority Date: 12/29/2017
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Natarajan, Ragavendra, Soundararajan, Niranjan, Subramoney, Sreenivas
• Primary Examiner(s): Metzger, Michael J
• Application Number:
  US15/857,863
• Publication Number:
  US 20190205143A1
• Time in Patent Office: 858 Days
• CPC Class Codes: G06F 9/3005 to perform operations for flow control
• CPC Class Codes: G06F 9/321 Program or instruction counter, e.g. incrementing
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/3844 using dynamic branch prediction, e.g. using branch history tables
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques

Abstract

In one embodiment, a branch prediction circuit includes: a first bimodal predictor having a first plurality of entries each to store first prediction information for a corresponding branch instruction; a global predictor having a plurality of global entries each to store global prediction information for a corresponding branch instruction; a second bimodal predictor having a second plurality of entries each to store second prediction information for a corresponding branch instruction; a monitoring table having a plurality of monitoring entries each to store a counter value based on the second prediction information for a corresponding branch instruction; and a control circuit to allocate a global entry within the global predictor based at least in part on the counter value of a monitoring entry of the monitoring table for a corresponding branch instruction. Other embodiments are described and claimed.

Claims

1. An apparatus comprising:

a first local predictor circuit having a first plurality of entries each to store local prediction information for a corresponding branch instruction;

a global predictor circuit having a plurality of global entries each to store global prediction information for a corresponding branch instruction;

a second local predictor circuit having a second plurality of entries each to store second local prediction information for a corresponding branch instruction, wherein an entry of the second local predictor circuit is to be updated in response to every execution of the corresponding branch instruction; and

a comparator to determine whether a first entry of the second plurality of entries of the second local predictor circuit provided a correct prediction for the corresponding branch instruction, based at least in part on feedback information regarding branch execution of the corresponding branch instruction.

2. The apparatus of claim 1, further comprising a monitoring table coupled to the comparator, the comparator to probabilistically update the monitoring table based at least in part on the determination.

3. The apparatus of claim 2, wherein the comparator is to probabilistically increment a counter of an entry of the monitoring table in response to a determination of a correct prediction by the second local predictor circuit.

4. The apparatus of claim 3, further comprising a control circuit to prevent allocation of an entry in the global predictor circuit for a first branch instruction in response to a misprediction of the first branch instruction by the first local predictor circuit, when a value of an entry of the monitoring table associated with the first branch instruction exceeds a threshold.

5. The apparatus of claim 4, wherein the control circuit is to request allocation of the entry in the global predictor circuit for the first branch instruction in response to the misprediction of the first branch instruction by the first local predictor circuit, when the value of the entry of the monitoring table associated with the first branch instruction is less than the threshold.

6. The apparatus of claim 5, wherein the global predictor circuit is to prevent the allocation of the global entry in response to the allocation request based at least in part on prediction information of a victim entry.

7. The apparatus of claim 3, wherein the probabilistic increment is according to a predetermined ratio.

8. The apparatus of claim 2, wherein the comparator is to reset a counter of an entry of the monitoring table in response to a determination of a misprediction by the second local predictor circuit.

9. The apparatus of claim 2, further comprising a target array including a plurality of entries to store target information, wherein at least some of the plurality of entries of the target array are to store at least some counter information of the first plurality of entries of the first local predictor circuit.

10. The apparatus of claim 9, wherein the at least some of the plurality of entries of the target array are to store at least some prediction information of the monitoring table.

11. A machine-readable medium having stored thereon instructions, which if performed by a machine cause the machine to perform a method comprising:

receiving, in a branch predictor of a processor, feedback information regarding execution of a branch instruction from an execution circuit of the processor;

upon a determination that the feedback information indicates that an entry of a shadow bimodal predictor of the branch predictor correctly predicted the branch instruction, probabilistically updating a counter of an entry of a monitoring table of the branch predictor, the entry associated with the branch instruction; and

allocating a new entry in a global predictor of the branch predictor in response to a misprediction regarding the branch instruction by a local predictor when the counter of the entry of the monitoring table is less than a threshold.

12. The machine-readable medium of claim 11, wherein probabilistically updating the counter comprises probabilistically setting the counter.

13. The machine-readable medium of claim 11, wherein the method further comprises probabilistically updating the counter according to a predetermined ratio.

14. The machine-readable medium of claim 11, wherein the method further comprises decrementing the counter of the monitoring table entry in response to a misprediction regarding the branch instruction by the shadow bimodal predictor.

15. The machine-readable medium of claim 11, wherein the method further comprises preventing allocation of an entry for the branch instruction within the global predictor when the counter of the monitoring table entry exceeds the threshold.

16. A processor comprising:

a branch prediction circuit comprising;

a first bimodal predictor having a first plurality of entries each to store first prediction information for a corresponding branch instruction;

a global predictor having a plurality of global entries each to store global prediction information for a corresponding branch instruction;

a second bimodal predictor having a second plurality of entries each to store second prediction information for a corresponding branch instruction;

a monitoring table having a plurality of monitoring entries each to store a counter value based on the second prediction information for a corresponding branch instruction; and

a control circuit to allocate a global entry within the global predictor based at least in part on the counter value of a monitoring entry of the monitoring table for a corresponding branch instruction; and

an execution circuit to execute instructions, wherein the execution circuit is to provide feedback information regarding branch instructions to the branch prediction circuit.

17. The processor of claim 16, further comprising a comparator to determine whether a first entry of the second plurality of entries of the second bimodal predictor provided a correct prediction for the corresponding branch instruction, based at least in part on the feedback information.

18. The processor of claim 17, wherein the comparator is to probabilistically update a first monitoring entry of the monitoring table based at least in part on the determination.

19. The processor of claim 16, wherein the control circuit is to:

allocate the global entry within the global predictor for the corresponding branch instruction when a counter value of a first monitoring entry of the monitoring table for the corresponding branch instruction is less than a threshold; and

prevent allocation of the global entry within the global predictor for the corresponding branch instruction when the counter value of the first monitoring entry of the monitoring table for the corresponding branch instruction exceeds the threshold.