BRANCH PREDICTION USING MULTI-WAY PATTERN HISTORY TABLE (PHT) AND GLOBAL PATH VECTOR (GPV)

• US 20160034280A1
• Filed: 10/30/2014
• Published: 02/04/2016
• 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., Prasky, Brian R., Lipetz, Daniel
• Granted Patent: US 10,642,619 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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;

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; and

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.

2. The method of claim 1, further comprising inputting a target address of the branch instruction associated with the taken prediction into the branch prediction logic as the search address.

3. 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.

4. 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.

5. The method of claim 1, 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.

6. The method of claim 5, wherein the plurality of branch predictions comprises one of:

(i) N−

1 not taken predictions and the single taken prediction, and (ii) N not taken predictions.

7. The method of claim 5, 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.

8. The method of claim 5, 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.

9. 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;

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; and

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.

10. The computer program product of claim 9, 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.

11. The computer program product of claim 9, 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.

12. The computer program product of claim 9, 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.

13. The computer program product of claim 12, wherein the plurality of branch predictions comprises one of:

(i) N−

1 not taken predictions and the single taken prediction, and (ii) N not taken predictions.

14. The computer program product of claim 12, 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.

15. The computer program product of claim 12, 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.