Branch predictor with empirical branch bias override

Patent metadata

Field	Value
Publication number	US-10423422-B2
Application number	US-201615383832-A
Country	US
Kind code	B2
Filing date	Dec 19, 2016
Priority date	Dec 19, 2016
Publication date	Sep 24, 2019
Grant date	Sep 24, 2019

Abstract

A processor may include a baseline branch predictor and an empirical branch bias override circuit. The baseline branch predictor may receive a branch instruction associated with a given address identifier, and generate, based on a global branch history, an initial prediction of a branch direction for the instruction. The empirical branch bias override circuit may determine, dependent on a direction of an observed branch direction bias in executed branch instruction instances associated with the address identifier, whether the initial prediction should be overridden, may determine, in response to determining that the initial prediction should be overridden, a final prediction that matches the observed branch direction bias, or may determine, in response determining that the initial prediction should not be overridden, a final prediction that matches the initial prediction. The predictor may update an entry in the global branch history reflecting the resolved branch direction for the instruction following its execution.

First claim

What is claimed is:

1. A processor, comprising:
a baseline branch predictor; and
an empirical branch bias override circuit;
wherein:
the baseline branch predictor comprises hardware circuitry to:
receive data representing a branch instruction, the branch instruction being associated with a given address identifier; and
generate, based at least in part on a global branch history, an initial prediction of a branch direction for the branch instruction;

the empirical branch bias override circuit is to:
determine whether the initial prediction is to be overridden based on an empirical bias fraction indicating a measure of an observed branch direction bias in a plurality of executed branch instruction instances associated with the given address identifier and a predictor performance indicating a measure of accuracy in previous initial predictions made by the baseline branch predictor;
determine, in response to a determination that the initial prediction is to be overridden, a final prediction of the branch direction for the branch instruction that matches a direction of the observed branch direction bias;
determine, in response to a determination that the initial prediction is not to be overridden, a final prediction of the branch direction for the branch instruction that matches the initial prediction; and
update, subsequent to identification of a resolved branch direction for the branch instruction following execution of the branch instruction, an entry in the global branch history to reflect the resolved branch direction for the branch instruction.

2. The processor of claim 1 , wherein to determine whether the initial prediction into be overridden, the empirical branch bias override circuit is to:
obtain data representing the empirical bias fraction, the empirical bias fraction having been calculated as a percentage of the plurality of executed branch instruction instances associated with the given address identifier for which the resolved branch direction matches the direction of the observed branch direction bias;
obtain data representing the predictor performance of the baseline branch predictor, the predictor performance having been calculated as a percentage of the plurality of executed branch instruction instances associated with the given address identifier for which an initial prediction of a branch direction generated by the baseline branch predictor was correct; and
determine whether a difference between the empirical bias fraction and the predictor performance exceeds a predetermined performance difference threshold.

3. The processor of claim 2 , wherein:
the processor is further to store, in respective entries in a data structure in a memory, branch bias information for a plurality of branch instructions, each of which is associated with a respective address identifier;
each entry in the data structure comprises:
a first field to store data representing an empirical bias fraction for one of the plurality of branch instructions; and
a second field to store data representing a predictor performance for the one of the plurality of branch instructions;

to determine whether the initial prediction is to be overridden, the empirical branch bias override circuit is to:
obtain the data representing the empirical bias fraction and the data representing the predictor performance from an entry in the data structure storing branch bias information for branch instruction instances associated with the given address identifier.

4. The processor of claim 3 , wherein the empirical branch bias override circuit is further to:
determine, upon retirement of each branch instruction instance associated with the given address identifier, the direction of the observed branch direction bias for branch instruction instances associated with the given address identifier; and
calculate, upon retirement of each branch instruction instance associated with the given address identifier, the empirical bias fraction for branch instruction instances associated with the given address identifier as a percentage of the plurality of executed branch instruction instances associated with the given address identifier for which the resolved branch direction matches the direction of the observed branch direction bias.

5. The processor of claim 3 , wherein the empirical branch bias override circuit is further to:
calculate, upon retirement of each branch instruction instance associated with the given address identifier, the predictor performance of the baseline branch predictor for branch instruction instances associated with the given address identifier as a percentage of the plurality of executed branch instruction instances associated with the given address identifier for which an initial prediction of a branch direction determined by the baseline branch predictor was correct.

6. The processor of claim 1 , wherein to determine whether the initial prediction is to be overridden, the empirical branch bias override circuit is further to:
maintain a count of the number of executed branch instruction instances that are associated with the given address identifier;
compare the number of executed branch instruction instances that are associated with the given address identifier to a predetermined minimum occurrence threshold; and
determine, in response to a result of the comparison indicating that the number of executed branch instruction instances that are associated with the given address identifier is less than a predetermined minimum occurrence threshold, that the initial prediction is not to be overridden.

7. The processor of claim 1 , wherein:
the number of the plurality of executed branch instruction instances is a predetermined number of executed branch instruction instances; and
the predetermined number of executed branch instruction instances is configurable at runtime.

8. The processor of claim 1 , wherein:
the number of the plurality of executed branch instruction instances is a predetermined number of executed branch instruction instances; and
the plurality of executed branch instruction instances comprises executed branch instruction instances in a sliding window of executed branch instruction instances associated with the given address identifier, the sliding window having a width equal to the predetermined number of executed branch instruction instances.

9. A method comprising, in a processor:
receiving data representing a branch instruction, the branch instruction being associated with a given address identifier;
generating, based at least in part on a global branch history, an initial prediction of a branch direction for the branch instruction;
determining whether the initial prediction is to be overridden based on an empirical bias fraction indicating a measure of an observed branch direction bias in a plurality of executed branch instruction instances associated with the given address identifier and a predictor performance indicating a measure of accuracy in previous initial predictions made by the baseline branch predictor;
determining, dependent on whether the initial prediction is to be overridden, a selected one of a final prediction of the branch direction for the branch instruction that matches a direction of the observed branch direction bias and a final prediction of the branch direction for the branch instruction that matches the initial prediction; and
updating, subsequent to identifying a resolved branch direction for the branch instruction following execution of the branch instruction, an entry in the global branch history to reflect the resolved branch direction for the branch instruction.

10. The method of claim 9 , wherein determining whether the initial prediction into be ov

Assignees

• Intel Corp

Inventors

• Soundararajan Niranjan K
• Subramoney Sreenivas
• Pal Rahul
• Natarajan Ragavendra

Classifications

• G06F9/3848 Primary

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

• G06F9/38

  Concurrent instruction execution, e.g. pipeline or look ahead · CPC title

• G06F9/3854

  Instruction completion, e.g. retiring, committing or graduating · CPC title