Global weak pattern history table filtering

Patent metadata

Field	Value
Publication number	US-9229723-B2
Application number	US-201213492946-A
Country	US
Kind code	B2
Filing date	Jun 11, 2012
Priority date	Jun 11, 2012
Publication date	Jan 5, 2016
Grant date	Jan 5, 2016

Abstract

Embodiments relate to global weak pattern history table (PHT) filtering. An aspect includes receiving a search address associated with a branch prediction, and receiving a prediction strength indicator and a tag from a PHT. Based on determining that the tag matches the search address and the prediction strength indicator is weak, an accuracy counter is compared to a comparison threshold to determine whether a PHT direction prediction from the PHT is more likely accurate than a branch history table (BHT) direction prediction from a BHT. The PHT direction prediction is selected as a direction prediction based on determining that the accuracy counter indicates that the PHT direction prediction is more likely accurate than the BHT direction prediction. The BHT direction prediction is selected as the direction prediction based on determining that the accuracy counter indicates that the BHT direction prediction is more likely accurate than the PHT direction prediction.

First claim

What is claimed is:

1. A computer program product for pattern history table filtering, the computer program product comprising:
a non-transitory storage medium readable by a processing circuit and storing instructions for execution by the processing circuit for performing a method comprising:
receiving a search address associated with a branch prediction;
receiving a prediction strength indicator and a tag from a pattern history table, the prediction strength indicator having a value of weak or strong defined relative to a pattern history table direction prediction of a corresponding branch as taken or not taken, wherein the prediction strength indicator transitions between weak and strong based on receiving a resolved branch indication of taken or not taken such that a combination of the prediction strength indicator and the pattern history table direction prediction supports transitions between a range of predictions comprising: strong not taken, weak not taken, weak taken, and strong taken;
determining, by the processing circuit, whether a pattern history table match exists based on the tag matching the search address;
based on determining that the pattern history table match exists and the prediction strength indicator is weak, comparing an accuracy counter to a comparison threshold to determine by the processing circuit whether the pattern history table direction prediction from the pattern history table is more likely accurate than a branch history table direction prediction from a branch history table;
selecting, by the processing circuit, the pattern history table direction prediction as a direction prediction based on determining that the accuracy counter indicates that the pattern history table direction prediction is more likely accurate than the branch history table direction prediction, the pattern history table match exists, and the prediction strength indicator is weak;
selecting, by the processing circuit, the branch history table direction prediction as the direction prediction based on determining that the accuracy counter indicates that the branch history table direction prediction is more likely accurate than the pattern history table direction prediction, the pattern history table match exists, and the prediction strength indicator is weak;
selecting, by the processing circuit, the pattern history table direction prediction as the direction prediction based on determining that the pattern history table match exists and the prediction strength indicator is strong; and
selecting, by the processing circuit, the branch history table direction prediction as the direction prediction based on determining that the pattern history table match does not exist.

2. The computer program product of claim 1 , the method further comprising:
receiving the resolved branch indication; and
based on determining that the pattern history table match exists and the prediction strength indicator is weak:
modifying the accuracy counter in a direction towards indicating that the pattern history table direction prediction is more likely accurate than the branch history table direction prediction based on the pattern history table direction prediction matching the resolved branch indication and the branch history table direction prediction not matching the resolved branch indication; and
modifying the accuracy counter in an opposite direction towards indicating that the branch history table direction prediction is more likely accurate than the pattern history table direction prediction based on the branch history table direction prediction matching the resolved branch indication and the pattern history table direction prediction not matching the resolved branch indication.

3. The computer program product of claim 1 , the method further comprising:
updating the branch history table based on determining that the branch history table direction prediction was selected as the direction prediction; and
updating the pattern history table based on determining that the pattern history table match exists to adjust one or more of: the prediction strength indicator and the pattern history table direction prediction.

4. The computer program product of claim 1 , the method further comprising:
installing a new entry in the pattern history table based on determining that the branch history table direction prediction was selected as the direction prediction, the branch history table direction prediction did not match the resolved branch indication, and the pattern history table match does not exist.

5. The computer program product of claim 1 , the method further comprising:
receiving a second prediction strength indicator and a second tag from a second pattern history table;
determining, by the processing circuit, that a second pattern history table match exists based on the second tag matching the search address;
based on determining that the second pattern history table match exists and the second prediction strength indicator is weak, comparing a second accuracy counter to the comparison threshold to determine by the processing circuit whether a second pattern history table direction prediction is more likely accurate than the branch history table direction prediction; and
selecting, by the processing circuit, one of: the pattern history table direction prediction and the second pattern history table direction prediction as the direction prediction.

6. A computer-implemented method for pattern history table filtering, the method comprising:
receiving a search address associated with a branch prediction;
receiving a prediction strength indicator and a tag from a pattern history table, the prediction strength indicator having a value of weak or strong defined relative to a pattern history table direction prediction of a corresponding branch as taken or not taken, wherein the prediction strength indicator transitions between weak and strong based on receiving a resolved branch indication of taken or not taken such that a combination of the prediction strength indicator and the pattern history table direction prediction supports transitions between a range of predictions comprising: strong not taken, weak not taken, weak taken, and strong taken;
determining, by a computer, whether a pattern history table match exists based on the tag matching the search address;
based on determining that the pattern history table match exists and the prediction strength indicator is weak, comparing an accuracy counter to a comparison threshold to determine by the processing circuit whether the pattern history table direction prediction from the pattern history table is more likely accurate than a branch history table direction prediction from a branch history table;
selecting, by the computer, the pattern history table direction prediction as a direction prediction based on determining that the accuracy counter indicates that the pattern history table direction prediction is more likely accurate than the branch history table direction prediction, the pattern history table match exists, and the prediction strength indicator is weak;
selecting, by the computer, the branch history table direction prediction as the direction prediction based on determining that the accuracy counter indicates that the branch history table direction prediction is more likely accurate than the pattern history table direction prediction, the pattern history table match exists, and the prediction strength indicator is weak;
selecting, by the processing circuit, the pattern history table direction prediction as the direction prediction based on determining that the pattern history table match exists and the prediction strength indicator is strong; and
selecting, by the processing circuit, the branch history table direction prediction as the d

Assignees

• Bonanno James J
• Prasky Brian R
• IBM

Inventors

• Bonanno James J
• Prasky Brian R

Classifications

• G06F9/3848

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

• G06F9/3806 Primary

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