Branch prediction using multi-way pattern history table (PHT) and global path vector (GPV)

• US 10,642,619 B2
• Filed: 10/30/2014
• Issued: 05/05/2020
• Est. Priority Date: 07/31/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bonanno, James J., Heizmann, Matthias D., Lipetz, Daniel, Prasky, Brian R.
• Primary Examiner(s): Giroux, George
• Application Number:
  US14/528,214
• Publication Number:
  US 20160034280A1
• Time in Patent Office: 2,014 Days
• Field of Search: None
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques

Abstract

Embodiments relate to branch prediction using a pattern history table (PHT) that is indexed using a global path vector (GPV). An aspect includes receiving a search address by a branch prediction logic that is in communication with the PHT and the GPV. Another aspect includes starting with the search address, simultaneously determining a plurality of branch predictions by the branch prediction logic based on the PHT, wherein the plurality of branch predictions comprises one of: (i) at least one not taken prediction and a single taken prediction, and (ii) a plurality of not taken predictions. Another aspect includes updating the GPV by shifting an instruction identifier of a branch instruction associated with a taken prediction into the GPV, wherein the GPV is not updated based on any not taken prediction.

Claims

1. A computer implemented method for branch prediction using a multi-way pattern history table (PHT) that is indexed using a global path vector (GPV), the method comprising:

receiving a search address by a branch prediction logic that is in communication with the PHT and the GPV, wherein the branch prediction logic comprises a branch target buffer (BTB) and a plurality of hit detection modules that each determine a respective branch prediction,

wherein a number N of the plurality of hit detection modules is equal to a number N of ways in the BTB, and wherein each of the plurality of hit detection modules receives an input from a single respective way in the BTB; and

wherein the plurality of hit detection modules receives at least one input from the PHT;

starting with the search address, simultaneously determining a plurality of branch predictions by the branch prediction logic based on the PHT and the BTB, wherein the plurality of branch predictions comprises one of;

(i) N−

1 not taken predictions and a single taken prediction, and (ii) N not taken predictions;

providing the plurality of branch predictions to the processor;

updating the GPV by shifting an instruction identifier of a branch instruction associated with a taken prediction into the GPV, wherein the GPV is not updated based on any not taken prediction, wherein the GPV is updated at prediction time to generate a PHT read index and at a completion time to generate a PHT write index; and

inputting a target address of the branch instruction associated with the taken prediction into the branch prediction logic as the search address and repeating each of the previous steps using the updated search address.

2. The method of claim 1, wherein shifting the instruction identifier of the branch instruction associated with the taken prediction into the GPV comprises inputting the instruction identifier into a history generator function configured to reduce a number of bits in the instruction identifier, and shifting the reduced number of bits into the GPV.

3. The method of claim 1, further comprising, based on a branch completion, updating the PHT based on the GPV by inputting a branch address of the branch instruction associated with the branch completion and a value stored in the GPV into an index generator, and updating the PHT based on an index that is output by the index generator.

4. The method of claim 1, wherein the PHT comprises an N-way PHT, and wherein each of the plurality of hit detection modules receives an input from a single respective way in the PHT.

5. The method of claim 1, wherein the PHT comprises an M-way PHT, and wherein each of the plurality of hit detection modules receives an input from each of the M ways in the PHT.

6. A computer program product for implementing branch prediction using a multi-way pattern history table (PHT) that is indexed using a global path vector (GPV), the computer program product comprising:

a computer readable storage medium having program instructions embodied therewith, the program instructions readable by a processing circuit to cause the processing circuit to perform a method comprising;

receiving a search address by a branch prediction logic that is in communication with the PHT and the GPV, wherein the branch prediction logic comprises a branch target buffer (BTB) and a plurality of hit detection modules that each determine a respective branch prediction,

wherein a number N of the plurality of hit detection modules is equal to a number N of ways in the BTB, and wherein each of the plurality of hit detection modules receives an input from a single respective way in the BTB; and

wherein the plurality of hit detection modules receives at least one input from the PHT;

starting with the search address, simultaneously determining a plurality of branch predictions by the branch prediction logic based on the PHT and the BTB, wherein the plurality of branch predictions comprises one of;

(i) N−

1 not taken predictions and a single taken prediction, and (ii) N not taken predictions; and

providing the plurality of branch predictions to the processor;

updating the GPV by shifting an instruction identifier of a branch instruction associated with a taken prediction into the GPV, wherein the GPV is not updated based on any not taken prediction, wherein the GPV is updated at prediction time to generate a PHT read index and at a completion time to generate a PHT write index; and

inputting a target address of the branch instruction associated with the taken prediction into the branch prediction logic as the search address and repeating each of the previous steps using the updated search address.

7. The computer program product of claim 6, wherein shifting the instruction identifier of the branch instruction associated with the taken prediction into the GPV comprises inputting the instruction identifier into a history generator function configured to reduce a number of bits in the instruction identifier, and shifting the reduced number of bits into the GPV.

8. The computer program product of claim 6, further comprising, based on a branch completion, updating the PHT based on the GPV by inputting a branch address of the branch instruction associated with the branch completion and a value stored in the GPV into an index generator, and updating the PHT based on an index that is output by the index generator.

9. The computer program product of claim 6, wherein the PHT comprises an N-way PHT, and wherein each of the plurality of hit detection modules receives an input from a single respective way in the PHT.

10. The computer program product of claim 6, wherein the PHT comprises an M-way PHT, and wherein each of the plurality of hit detection modules receives an input from each of the M ways in the PHT.