Polymorphic Branch Predictor And Method With Selectable Mode Of Prediction

• US 20080005542A1
• Filed: 05/04/2006
• Published: 01/03/2008
• Est. Priority Date: 05/04/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gschwind, Michael
• Granted Patent: US 7,523,298 B2
• Time in Patent Office: Days
• US Class Current: 712/239
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/3844 using dynamic branch prediction, e.g. using branch history tables
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques

Abstract

A polymorphic branch predictor and method includes a plurality of branch prediction methods. The methods are selectively enabled to perform branch prediction. A selection mechanism is configured to select one or more of the branch prediction methods in accordance with a dynamic setting to optimize performance of the branch predictor during operation in accordance with a current task.

Claims

1. A polymorphic branch predictor, comprising:

a plurality of branch prediction methods;

a mechanism for dynamically configuring a mode of prediction formed from at least one of the plurality of branch prediction methods responsive to a dynamic setting to optimize performance of the branch predictor during operation where the dynamic setting selects the mode of prediction in accordance with task specific information; and

a storage array for concurrently storing data for at least a first mode of prediction corresponding to a first one of the plurality of branch prediction methods and for a second mode of prediction corresponding to a second one of the plurality of branch prediction methods.

2. The polymorphic branch predictor as recited in claim 1, wherein when the first one of the plurality of branch prediction methods is configured, the data in said storage array relating to the second one of the plurality of branch prediction methods is irretrievable, and wherein when the second one of the plurality of branch prediction methods is configured, the data in said storage array relating to the first one of the plurality of branch prediction methods is irretrievable.

3. The polymorphic branch predictor as recited in claim 1, wherein the mechanism configures at least two branch prediction methods to work together to provide a result.

4. The polymorphic branch predictor as recited in claim 1, wherein the mechanism configures the at least one branch prediction method for one of an application and a partition by one of an operating system and a hypervisor in advance as the configured mode of prediction for branches being predicted by said polymorphic predictor.

5. The polymorphic branch predictor as recited in claim 1, wherein the mechanism configures the at least one branch prediction methods based upon an analysis of runtime behavior as the configured mode of prediction for branches being predicted by said polymorphic predictor.

6. The polymorphic branch predictor as recited in claim 1, wherein the mechanism receives information from one of a compiler and a runtime component to configure the at least one branch prediction method as the configured mode of prediction for branches being predicted by said polymorphic predictor.

7. The polymorphic branch predictor as recited in claim 1, wherein the mechanism is updated during runtime of an application when a configuration function is invoked by the application.

8. The polymorphic branch predictor as recited in claim 1, wherein the at least one of the plurality of branch prediction methods is configured prior to a prediction result being computed, and wherein the at least one of the plurality of branch prediction methods is dynamically configured further responsive to a configuration mode for the branches predicted by said polymorphic predictor.

9. The polymorphic branch predictor as recited in claim 1, wherein said storage array comprises an array of predictor entries wherein the predictor entries stored in the array of predictor entries are configured with respect to a number and bits of information wherein the first one of the plurality of branch prediction methods is configured to use the predictor entries with m bits in the first mode of prediction, wherein the second one of the plurality of branch prediction methods is configured to use the predictor entries with n bits in the second mode of prediction, wherein m>

n, wherein said storage array stores either k predictor entries with m bits, or 1 predictor entries with n bits, wherein k<

1, wherein said storage array has at least two storage bits b0 and b1, wherein the bits b0 and b1 correspond to a single one of the predictor entries with m bits in the first mode of prediction, and wherein the bits b0 and b1 correspond to a first one of the predictor entries with n bits and a second one of the predictor entries with n bits, respectively.

10. The polymorphic branch predictor as recited in claim 1, wherein the storage array comprises an array of predictor entries wherein storage in the array of predictor entries is implemented using one of a per-bit write enable signal and a multi-bit write enable signal to permit a write operation to the array of predictor entries,

wherein the array of predictor entries has a data write port,

wherein when per-bit write enable signals are present in said array of predictor entries and the at least one branch prediction method is configured to use multi-bit predictor entries, multiple per-bit write enable signals are asserted when a multi-bit predictor entry is to be written,

wherein when the per-bit write enable signals are present in said array of predictor entries and the at least one prediction method is configured to use single bit predictor entries, a single per-bit write enable signal is asserted when a single bit predictor entry is to be written,

wherein when multi-bit write enable signals are present in said array of predictor entries and the at least one branch prediction method is configured to use the multi-bit predictor entries, a multi-bit write enable signal is asserted when the multi-bit predictor entry is to be written and a single multi-bit predictor entry is presented at the data write port of said array of predictor entries, and

wherein when the multi-bit write enable signals are present in said array of predictor entries and the at least one branch prediction method is configured to use the single bit predictor entries, the multi-bit write enable signal is asserted when the single bit predictor entry is to be written and multiple single bit predictor entries, corresponding to at least one write updated single bit predictor entry, and at least one unmodified single bit predictor entry corresponding to a previously read and non-updated single bit predictor entry, are present at the data write port of said array of predictor entries.

11. The polymorphic branch predictor as recited in claim 1, wherein each branch prediction method includes logic elements such that the logic elements are shared such that a computation of at least one of a prediction result and a prediction update for the at least one of the plurality of branch prediction methods and involving at least some of the logic elements prohibits a concurrent use of the at least some of the logic elements for computing at least one of another prediction result and another prediction update for at least another one of the plurality of branch prediction methods.

12. The polymorphic branch predictor as recited in claim 11, wherein the logic elements shared between branch prediction methods include at least one of arrays, predictor update logic, and address generation logic,

wherein said storage array includes a plurality of bits,

wherein when the logic elements shared between the branch prediction methods include arrays and the first one of the plurality of branch prediction methods is configured, one of the plurality of bits is used to store a portion of a predictor entry corresponding to the first one of the plurality of branch prediction methods without simultaneously storing a portion of a predictor entry corresponding to the second one of the plurality of branch prediction methods,

wherein when the logic elements shared between the branch prediction methods include arrays and the second one of the plurality of branch prediction methods is configured, one of the plurality of bits is used to store the portion of a predictor entry corresponding to the second one of the plurality of branch prediction methods without simultaneously storing the portion of a predictor entry corresponding to the first one of the plurality of branch prediction methods,

wherein when the logic elements shared between the branch prediction methods include the predictor update logic and the first one of the plurality of branch prediction methods is configured, the predictor update logic includes circuits for computing an update in accordance with the first one of the plurality of branch prediction methods without concurrently computing an update in accordance with the second one of the plurality of branch prediction methods,

wherein when the logic elements shared between the branch prediction methods include the predictor update logic and the second one of the plurality of branch prediction methods is configured, the predictor update logic includes circuits for computing an update in accordance with the second one of the plurality of branch prediction methods without concurrently computing an update in accordance with the first one of the plurality of branch prediction methods,

wherein when the logic elements shared between the branch prediction methods include the address generation logic and the first one of the plurality of branch prediction methods is configured, the address generation logic includes circuits for computing an address in accordance with the first one of the plurality of branch prediction methods without concurrently computing an address in accordance with the second one of the plurality of branch prediction methods, and

wherein when the logic elements shared between the branch prediction methods include the address generation logic and the second one of the plurality of branch prediction methods is configured, the address generation logic includes circuits for computing an address in accordance with the second one of the plurality of branch prediction methods without concurrently computing an address in accordance with the first one of the plurality of branch prediction methods.

13. The polymorphic branch predictor as recited in claim 1, further comprising an array of predictor entries and a branch information queue wherein information is used from the branch information queue to rewrite previously read information from the array of predictor entries, wherein the re-written information is maintained unmodified from an initial reading from the array of predictor entries until and including being re-written to the array of predictor entries.

14. The polymorphic branch predictor as recited in claim 1, further comprising addressing logic for generating and selecting address for two arrays corresponding to a storage of two predictors of a multi-component predictor when the first one of the plurality of branch prediction methods is configured, and for generating addresses corresponding to a use of the two arrays as a single unified array of a single unified predictor having an absence of multiple components when the second one of the plurality of branch prediction methods is configured,

wherein a first one of the two arrays stores all predictor entries corresponding to a first one of the two predictors of the multi-component predictor when the first one of the plurality of branch prediction methods is configured, and stores a portion of the predictor entries corresponding to the single unified predictor when the second one of the plurality of branch prediction methods is configured,

wherein a second one of the two arrays stores all predictor entries corresponding to a second one of the two predictors of the multi-component predictor when the first one of the plurality of branch prediction methods is configured, and stores another portion of the predictor entries corresponding to the single unified predictor when the second one of the plurality of branch prediction methods is configured, and

wherein a predictor entry of the single unified predictor corresponds exclusively to either the portion of the predictor entries in the first one of the two arrays or the other portion of the predictor entries in the second one of the two arrays, when the second one of the plurality of branch prediction methods is configured.

16. The polymorphic branch predictor as recited in claim 14, wherein said mechanism selects one of the two arrays having a predictor stored therein corresponding to a particular address, by computing a hash code of the particular address.

17. A method for dynamically selecting a branch prediction method, comprising:

providing a plurality of branch prediction methods;

configuring a mode of prediction formed from at least one of the plurality of branch prediction methods in accordance with a dynamic setting to optimize performance of the branch predictor during operation where the dynamic setting selects the mode of prediction in accordance with task specific information; and

updating a configuration of the mode of prediction to provide improved prediction results,

wherein the mode of prediction is configured before the at least one of the plurality of branch prediction methods is performed, and wherein when the at least one of the plurality of branch prediction methods is configured, remaining ones of the plurality of branch prediction methods are in an un-configured state constrained from being simultaneously performed with the at least one of the plurality of branch prediction methods.

15. The method as recited in claim 17, wherein said configuring step configures the at least one branch prediction method for one of an application and a partition by one of an operating system and a hypervisor in advance as the configured mode of prediction for branches being predicted by said polymorphic predictor, and the method further comprises storing a configuration mode corresponding to one of a previously scheduled application and a partition and reading configuration information for a next one of an application process and a partition to be configured.

18. The method as recited in claim 17, wherein selecting a mode of prediction includes selecting a mode of prediction based on one of an application being run, a phase of an application being run, runtime behavior and an operational metric.

19. The method as recited in claim 17, further comprising generating program code to cause a reconfiguration of the mode of prediction for branches predicted by said polymorphic predictor.

20. A computer program product comprising a computer useable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to perform the steps of claim 19.