Tagged indirect branch predictor (TIP)

Patent metadata

Field	Value
Publication number	US-10936318-B2
Application number	US-201816190309-A
Country	US
Kind code	B2
Filing date	Nov 14, 2018
Priority date	Nov 14, 2018
Publication date	Mar 2, 2021
Grant date	Mar 2, 2021

Abstract

A computer system includes a first predictor circuit configured to generate a first predictor signal, and a second predictor circuit configured to generate a second predictor signal different from the first predictor signal. The computer system further includes a TIP arbiter configured to receive the first predictor signal and the second predictor signal, and to select one of the first predictor signal or the second predictor signal as a final prediction of a target address for a fetched branch instruction. The selection is based at least in part on a comparison between a branch address of the fetched branch instruction and a stored tag value, along with a counter value stored in the arbiter entry.

First claim

What is claimed is:

1. A computer system comprising:
a first predictor circuit configured to generate a first predictor signal;
a second predictor circuit configured to generate a second predictor signal different from the first predictor signal;
a Tagged Indirect Branch Predictor (TIP) arbiter configured to receive the first predictor signal and the second predictor signal, and to select one of the first predictor signal or the second predictor signal as a final prediction of a target address for a fetched branch instruction; and
a TIP unit in signal communication with the TIP arbiter, the TIP unit configured to selectively override the final prediction determined by the TIP arbiter,
wherein selecting one of the first predictor signal or the second predictor signal is based at least in part on a first comparison between a branch address of the fetched branch instruction and a stored tag value, along with a second comparison between a counter value stored in the TIP arbiter and a count threshold, the second comparison indicating a confidence level determined as a number of correctly and incorrectly supplied targets,
wherein the TIP arbiter initially selects one of the first predictor signal and the second predictor signal as the final prediction of a target address for a fetched branch instruction, and
wherein the TIP unit overrides the initial selection and commands the TIP arbiter to select the remaining signal among first predictor signal and the second predictor signal as the final prediction in response to the count value being less than the count threshold.

2. The computing system of claim 1 , wherein the TIP arbiter selects the second predictor signal as the final prediction of a target address for the fetched branch instruction in response to detecting a match between the branch address of the fetched branch instruction and the stored tag, along with detecting that the stored counter value is greater than a threshold, and wherein the TIP arbiter selects the first predictor signal as the final prediction of a target address for the fetched branch instruction in response to detecting a mismatch between the branch address of the fetched branch instruction and the stored tag, or in response to detecting that the stored counter value is below a threshold.

3. The computer system of claim 2 , wherein the first predictor signal is based at least in part on a number of previous taken or not taken branch results, and wherein the second predictor signal is based at least in part on addresses of previous jump targets independent from the previous taken or not taken branch results, and wherein the first and second predictor signals are generated by a predictor circuit.

4. The computer system of claim 3 , wherein the first predictor signal is based at least in part on a current process location in a source code independent from past behavior of the fetched branch instruction and the second predictor signal is based at least in part on the current process location in the source code along with a history of the number of previous taken or not taken branch results.

5. The computer system of claim 3 , wherein the TIP arbiter includes a TIP counter that is incremented in response to a match between the target address of the fetched branch instruction and the second predictor signal when there is mismatch between the target address of the fetched branch instruction and the first predictor signal, and decrements the TIP counter in response to a mismatch between the target address of the fetched branch instruction and the second predictor signal when there is a match between the target address of the fetched branch instruction and the first predictor signal.

6. The computer system of claim 5 , wherein the TIP arbiter selects the second predictor signal when a count value of the TIP counter exceeds a TIP count threshold and selects the first predictor signal when the count value of the TIP counter does not exceed the TIP count threshold.

7. A method of performing tagged indirect branch predictions, the method comprising:
generating, via a first predictor circuit, a first predictor signal;
generating, via a second predictor circuit, a second predictor signal different from the first predictor signal; and
selecting, via a Tagged Indirect Branch Predictor (TIP) arbiter, one of the first predictor signal or the second predictor signal as a final prediction of a target address for a fetched branch instruction,
wherein selecting one of the first predictor signal or the second predictor signal is based at least in part on a first comparison between a branch address of the fetched branch instruction and a stored tag value, along with a second comparison between a counter value stored in the TIP arbiter and a count threshold, the second comparison indicating a confidence level determined as a number of correctly and incorrectly supplied targets,
wherein the TIP arbiter initially selects one of the first predictor signal and the second predictor signal as the final prediction of a target address for a fetched branch instruction, and
wherein the TIP unit overrides the initial selection and commands the TIP arbiter to select the remaining signal among first predictor signal and the second predictor signal as the final prediction in response to the count value being less than the count threshold.

8. The method of claim 7 , further comprising:
selecting, via the TIP arbiter, the second predictor signal as the final prediction of a target address for the fetched branch instruction in response to detecting a match between the branch address of the fetched branch instruction and the stored tag, along with a detection that the stored counter value is greater than a threshold; and
selecting, via the TIP arbiter, the first predictor signal as the final prediction of a target address for the fetched branch instruction in response to detecting a mismatch between the branch address of the fetched branch instruction and the stored tag, or in response to the stored counter being below a threshold.

9. The method of claim 8 , further comprising:
generating the first predictor signal based at least in part on a number of previous taken or not taken branch results; and
generating the second predictor signal based at least in part on addresses of previous jump targets independent from the previous taken or not taken branch results.

10. The method of claim 9 , further comprising generating the first predictor signal based at least in part on a current process location in a source code independent from past behavior of the fetched branch instruction, and generating the second predictor signal is based at least in part on the current process location in the source code along with a history of the number of previous taken or not taken branch results.

11. The method of claim 9 , further comprising:
incrementing a TIP counter in response to a match between the target address of the fetched branch instruction and the second predictor signal in response to a mismatch between the target address of the fetched branch instruction and the first predictor signal; and
decrementing the TIP counter in response to a mismatch between the target address of the fetched branch instruction and the second predictor signal in response to detecting a match between the target address of the fetched branch instruction and the first predictor signal.

12. The method of claim 11 , further comprising:
selecting, via the TIP arbiter, the second predictor signal when a count value of the TIP counter exceeds a TIP count threshold; and
selecting, via the TIP arbiter, the first predictor signal when the count value of the TIP counter does not

Assignees

• IBM

Inventors

• Fatehi Ehsan
• Gorti Naga
• Orzol Nicholas
• Zoellin Christian

Classifications

• G06F9/30054

  Unconditional branch instructions · CPC title

• G06F9/30061 Primary

  Multi-way branch instructions, e.g. CASE · CPC title

• G06F9/3806 Primary

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

• G06F9/3848

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

• G06F9/3842

  Speculative instruction execution · CPC title