Branch prediction using multi-way pattern history table (PHT) and global path vector (GPV)
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.
1. A computer system for branch prediction using a multi-way pattern history table (PHT) that is indexed using a global path vector (GPV), the system comprising:
a memory; and
a processor, communicatively coupled to said memory, the computer system configured 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;
providing the plurality of branch predictions to the processor; 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, and
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.
2. The system 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 system 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 system 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 system 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.
6. The system 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.