Prediction of data values read from memory by a microprocessor using a dynamic confidence threshold

• US 7,856,548 B1
• Filed: 12/26/2006
• Issued: 12/21/2010
• Est. Priority Date: 12/26/2006
• Status: Active Grant

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation), Sun Microsystems Technology Ltd. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Ashcraft, Matthew, Nelson, Chris, Favor, John Gregory
• Primary Examiner(s): Chan; Eddie P
• Assistant Examiner(s): Alrobaye; Idriss N
• Application Number:
  US11/645,901
• Time in Patent Office: 1,456 Days
• Field of Search: 712/220, 712/219, 712/225
• US Class Current: 712/225
• CPC Class Codes: G06F 9/3832 Value prediction for operands; operand history buffers

Abstract

Prediction of data values to be read from memory by a microprocessor for load operations. In one aspect, a method for predicting a data value that will result from a load operation to be executed by the microprocessor includes accessing an entry in a load value prediction table that stores a predicted data value corresponding to the load operation. The predicted data value is provided as a result of the load operation without waiting for execution of the load operation to complete based on a confidence parameter stored in the entry compared to a dynamic confidence threshold.

Claims

1. A method for predicting a data value that will result from a load operation to be executed by a microprocessor, the method comprising:

accessing an entry in a load value prediction table that stores a predicted data value corresponding to the load operation;

providing the predicted data value as a result of the load operation without waiting for execution of the load operation to complete a confidence parameter stored in the entry exceeds a current value of a dynamic confidence threshold;

adjusting the confidence parameter based on a first pre-determined criterion, wherein the first pre-determined criterion comprises an actual data value from executing the load operation to the predicted data value;

determining a new value of the dynamic confidence threshold based on a second pre-determined criterion, wherein the second pre-determined criterion comprises calculating a prediction parameter representing statistical accuracy of predicting the data value;

accessing another entry in the load value prediction table that stores another predicted data value corresponding to another load operation, wherein the load value prediction table is accessed, at least in part, from recent branch history prior to an instruction that triggers the load operation;

providing said another predicted data value as a result of said another load operation without waiting for execution of said another load operation to complete another confidence parameter stored in said another entry compared to exceeds the new value of the dynamic confidence threshold; and

wherein the new value is determined to adjust the dynamic confidence by an amount proportional to a difference between the confidence parameter and the dynamic confidence threshold.

2. The method of claim 1 further comprising decrementing the confidence parameter and incrementing a number of inaccurate predicted data values if the actual data value from executing the load operation does not equal the predicted data value.

3. The method of claim 1 further comprising incrementing the confidence parameter and incrementing a number of accurate predicted data values if the actual data value from executing the load operation equals the predicted data value.

4. The method of claim 2 wherein calculating the prediction parameter comprises comparing the number of inaccurate predicted data values to a predetermined threshold.

5. The method of claim 3 wherein calculating the prediction parameter comprises comparing the number of accurate predicted data values to a predetermined threshold.

6. The method of claim 1 wherein calculating the prediction parameter comprises tallying a number of accurate predicted data values having a confidence parameter less than and within a predetermined range of the dynamic confidence threshold.

7. The method of claim 1 wherein the new value of the dynamic confidence threshold is a value outside of a possible range for the confidence parameter for load operations in a sequence of instructions known to have poor prediction accuracy.

8. The method of claim 1 wherein calculating the prediction parameter tall, in a number of accurate predicted data values having a confidence parameter value equaling the dynamic confidence threshold minus one.

9. The method of claim 5 wherein after a predetermined number of load operations, the dynamic confidence threshold is changed if the number of accurate predicted data values is greater than the predetermined threshold.

10. The method of claim 9 wherein the predetermined threshold is determined by balancing average performance penalty for an inaccurate predicted data value with average performance gain for an accurate predictive data value.

11. The method of claim 1 wherein calculating the prediction parameter comprises tallying a number of accurate predicted data values having a confidence parameter value equaling the confidence threshold.

12. The method of claim 5 wherein after a predetermined number of load operations, the dynamic confidence threshold is changed if the number of accurate predicted data values is less than the predetermined threshold percentage.

13. The method of claim 1 wherein the second pre-determined criterion is based on a number of predicted data values that matched corresponding loaded data values and were not provided for use as predicted data values.

14. The method of claim 1 wherein the confidence parameter for the entry is changed in one direction when the predicted data value and the loaded data value resulting from executing the load operation are found to be equal, and wherein the confidence parameter for the entry is changed in an opposite direction when the predicted data value and the loaded data value are found not to be equal.

15. The method of claim 14 wherein if the confidence parameter of an entry in the load value prediction table goes below a threshold that is lower than the dynamic confidence threshold, the data value stored in that entry is considered unpredictable and is not accessed for prediction for every load operation corresponding to that entry.

16. The method of claim 1 wherein when the confidence parameter is adjusted, the confidence parameter is changed in one direction by a first amount and changed in an opposite direction by a second amount different than the first amount.

17. The method of claim 1 wherein a key is used to access the entry in the load value prediction table, wherein the key is derived, at least in part, from recent branch history prior to an instruction that triggers the load operation.

18. The method of claim 1 wherein the predicted data value is stored in a register, and wherein if the predicted data value does not equal the loaded data value, the method further comprises checking a bit associated with the register in which the predicted data value was stored to determine whether or not the predicted data value has already been used by one or more subsequent operations to the load operation to determine whether the subsequent operations are to be rolled back.

19. A microprocessor operative to predict a data value that will result from a load operation to be executed by the microprocessor, the microprocessor comprising:

a mechanism operative to access an entry in a load value prediction table that stores a predicted data value corresponding to the load operation;

a mechanism operative to provide the predicted data value as a result of the load operation without waiting for execution of the load operation to complete if a confidence parameter stored in the entry exceeds a current value of a dynamic confidence threshold;

a mechanism operative to adjust the confidence parameter based on a first pre-determined criterion, wherein the first pre-determined criterion comprises comparing an actual data value from executing the load operation to the predicted data value;

a mechanism operative to determine a new value of the dynamic confidence threshold based on a second pre-determined criterion, wherein the second pre-determined criterion comprises calculating a prediction parameter representing statistical accuracy of predicting the data value;

a mechanism operative to access another entry in the load value prediction table that stores another predicted data value corresponding to another load operation, wherein the load value prediction table is accessed, at least in part, from recent branch history prior to an instruction that triggers the load operation;

a mechanism operative to provide said another predicted data value as a result of said another load operation without waiting for execution of said another load operation to complete if another confidence parameter stored in said another entry exceeds the new value of the dynamic confidence threshold; and

wherein the new value is determined to adjust the dynamic confidence by an amount proportional to a difference between the confidence parameter and the dynamic confidence threshold.

20. The microprocessor of claim 19 further comprising a mechanism operative to decrement the confidence parameter and increment a number of inaccurate predicted data values if the actual data value from executing the load operation does not equal the predicted data value.

21. The microprocessor of claim 19 further comprising a mechanism to increment the confidence parameter and increment a number of accurate predicted data values if the actual data value from executing the load operation equals the predicted data value.

22. The microprocessor of claim 21 wherein calculating the prediction parameter comprises comparing the number of accurate predicted data values to a predetermined threshold.

23. The microprocessor of claim 19 wherein calculating the prediction parameter comprises tallying a number of accurate predicted data values having a confidence parameter less than and within a predetermined range of the dynamic confidence threshold.

24. The microprocessor of claim 19 wherein calculating the prediction parameter comprises tallying a number of accurate predicted data values having a confidence parameter value equaling the dynamic confidence threshold minus one.

25. The microprocessor of claim 19 wherein after a predetermined number of load operations, the dynamic confidence threshold is changed if the number of accurate predicted data values is greater than the predetermined threshold.

26. The microprocessor of claim 19 wherein calculating the prediction parameter comprises tallying a number of accurate predicted data values having a confidence parameter value equaling the confidence threshold.

27. The microprocessor of claim 22 wherein after a predetermined number of load operations, the dynamic confidence threshold is changed if the number of accurate predicted data values is less than the predetermined threshold percentage.

28. A tangible non-transitory computer readable medium including program instructions to be implemented by a computer and for predicting a data value that will result from a load operation to be executed by the microprocessor, the program instructions for:

accessing an entry in a load value prediction table that stores a predicted data value corresponding to the load operation;

providing the predicted data value as a result of the load operation without waiting for execution of the load operation to complete if a confidence parameter stored in the entry exceeds a current value of a dynamic confidence threshold;

adjusting the confidence parameter based on a first pre-determined criterion, wherein the first pre-determined criterion comprises comparing an actual data value from executing the load operation to the predicted data value;

determining a new value of the dynamic confidence threshold based on a second pre-determined criterion, wherein the second pre-determined criterion comprises calculating a prediction parameter representing statistical accuracy of predicting the data value,

accessing another entry in the load value prediction table that stores another predicted data value corresponding to another load operation, wherein the load value prediction table is accessed, at least in part, from recent branch history prior to an instruction that triggers the load operation;

providing said another predicted data value as a result of said another load operation without waiting for execution of said another load operation to complete if another confidence parameter stored in said another entry exceeds the new value of the dynamic confidence threshold; and

wherein the new value is determined to adjust the dynamic confidence by an amount proportional to a difference between the confidence parameter and the dynamic confidence threshold.