Branch prediction using multi-way pattern history table (PHT) and global path vector (GPV)
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
10 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. - View Dependent Claims (2, 3, 4, 5)
-
-
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; andproviding 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. - View Dependent Claims (7, 8, 9, 10)
-
Specification