Caching override indicators for statistically biased branches to selectively override a global branch predictor

Patent metadata

Field	Value
Publication number	US-11526359-B2
Application number	US-201816150372-A
Country	US
Kind code	B2
Filing date	Oct 3, 2018
Priority date	Oct 3, 2018
Publication date	Dec 13, 2022
Grant date	Dec 13, 2022

Abstract

A data processing apparatus is provided that includes global-history prediction circuitry that provides a prediction of an outcome of a given control flow instruction based on a result of execution of one or more previous control flow instructions. Correction circuitry provides a corrected prediction of the global-history prediction circuitry in respect of the given control flow instruction and cache circuitry, separate from the correction circuitry, stores the corrected prediction in respect of the given control flow instruction.

First claim

We claim:

1. A data processing apparatus comprising:
global-history prediction circuitry to provide a prediction of an outcome of a given control flow instruction based on a result of execution of one or more previous control flow instructions;
correction circuitry to store a corrected prediction of the global-history prediction circuitry in respect of the given control flow instruction; and
detection circuitry to perform a determination of whether the given control flow instruction is performed in at least partial dependence on a random variable,
wherein in response to the determination that the given control flow instruction is performed in at least partial dependence on a random variable, the detection circuitry is configured to store the corrected prediction in cache circuitry in association with the given control flow instruction and an indication of whether to use the corrected prediction,
wherein in response to the determination that the given control flow instruction is performed in at least partial dependence on a random variable, the detection circuitry is configured to set the indication to indicate that the corrected prediction is to be used, otherwise, to set the indication to indicate that the corrected prediction is not to be used,
wherein the cache circuitry is separate from the correction circuitry, and comprises at least one of:
branch target prediction circuitry to store a prediction of a target of the given control flow instruction when the given control flow instruction is taken, in association with the corrected prediction and the indication of whether to use the corrected prediction, and
an instruction cache to store the given control flow instruction in encoded form, in association with the corrected prediction and the indication of whether to use the corrected prediction, wherein

the corrected prediction is provided in response to the control flow instruction without the correction circuitry being activated.

2. A data processing apparatus according to claim 1 , wherein
the correction circuitry comprises bimodal prediction circuitry to provide the corrected prediction; and
the corrected prediction is based on previous results of executing the given control flow instruction.

3. A data processing apparatus according to claim 2 , wherein
the bimodal prediction circuitry comprises a taken table and an untaken table;
the taken table comprises corrected predictions in respect of control flow instructions that are predicted taken by the global-history prediction circuitry; and
the untaken table comprises corrected predictions in respect of control flow instructions that are predicted untaken by the global-history prediction circuitry.

4. A data processing apparatus according to claim 3 , wherein
the detection circuitry is adapted to determine that the given control flow instruction is performed in at least partial dependence on a random variable in response to the corrected prediction in both the taken table and the untaken table being equal in respect of the given control flow instruction.

5. A data processing apparatus according to claim 1 , wherein
the corrected prediction comprises a 1-bit value to indicate whether the given control flow instruction should be taken.

6. A data processing apparatus according to claim 1 , wherein
the corrected prediction is stored as part of an encoding of the control flow instruction.

7. A data processing apparatus according to claim 1 , comprising:
update circuitry to update the corrected prediction in response to the prediction of the global-history prediction circuitry being updated.

8. A data processing apparatus according to claim 1 , wherein
the global-history prediction circuitry comprises TAGE prediction circuitry.

9. A data processing apparatus according to claim 1 , wherein
the cache circuitry comprises a validity flag to indicate whether the corrected prediction should be used in place of the prediction.

10. A data processing method comprising:
providing a prediction of an outcome of a given control flow instruction based on a result of execution of one or more previous control flow instructions;
storing, at correction circuitry, a corrected prediction of the global-history prediction circuitry in respect of the given control flow instruction; and
performing a determination, with detection circuitry, of whether the given control flow instruction is performed in at least partial dependence on a random variable,
and in response to the determination that the given control flow instruction is performed in at least partial dependence on a random variable, storing the corrected prediction in cache circuitry in association with the given control flow instruction and an indication of whether to use the corrected prediction,
wherein in response to the determination that the given control flow instruction is performed in at least partial dependence on a random variable, setting the indication to indicate that the corrected prediction is to be used, otherwise, setting the indication to indicate that the corrected prediction is not to be used,
wherein the cache circuitry is separate from the correction circuitry, and comprises at least one of:
branch target prediction circuitry storing a prediction of a target of the given control flow instruction when the given control flow instruction is taken, in association with the corrected prediction and the indication of whether to use the corrected prediction, and
an instruction cache storing the given control flow instruction in encoded form, in association with the corrected prediction and the indication of whether to use the corrected prediction, wherein
the corrected prediction is provided in response to the control flow instruction without the correction circuitry being activated.

Assignees

• Advanced Risc Mach Ltd

Inventors

• Ishii Yasuo
• Farooq Muhammad Umar
• Abernathy Chris

Classifications

• G06F9/3848 Primary

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

• G06F9/3861

  Recovery, e.g. branch miss-prediction, exception handling (error detection or correction G06F11/00) · CPC title

• G06F9/3806

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

• G06F9/3005

  to perform operations for flow control · CPC title

• G06F9/323

  for indirect branch instructions · CPC title