Error detection/correction and fault detection/recovery – Data processing system error or fault handling – Reliability and availability
Reexamination Certificate
1999-11-19
2003-09-23
Iqbal, Nadeem (Department: 2184)
Error detection/correction and fault detection/recovery
Data processing system error or fault handling
Reliability and availability
C714S010000
Reexamination Certificate
active
06625744
ABSTRACT:
FIELD OF THE INVENTION
The present invention pertains to the field of confidence predictions. More particularly, the present invention pertains to a method and mechanism for dynamically controlling the population size of confidence assignments to which confidence level predictions are assigned.
BACKGROUND OF THE INVENTION
Improvement in microprocessor performance has been partly due to the exploitation of parallelism among machine instructions. A parallel microprocessor that can concurrently execute instructions that are not dependent upon each other is likely to execute more instructions for a given cycle than a purely sequential microprocessor that does not take advantage of the lack of dependency (i.e., parallelism). However, there are limitations on the increase in performance that a parallel microprocessor will achieve over a purely sequential microprocessor. One limitation on the increase in performance achievable by parallel microprocessors is due to the uncertainties in the way branches will execute. When a microprocessor is faced with a branch instruction, it is uncertain whether the next instruction to be executed is the instruction after the branch (i.e., branch not taken) or the instruction at the branch target address (i.e., branch taken) until the microprocessor has evaluated (resolved) the branch's condition. There are at least two known ways to handle this uncertainty while improving performance and/or power savings over a purely sequential microprocessor that would have waited for the branch condition to be resolved before continuing execution: single-path speculative execution and eager execution.
In single-path speculative execution, when the microprocessor encounters a branch, the path that the branch will take is predicted, and execution proceeds down the predicted path. Since the branch is unresolved, all writes to architectural registers or memory and all I/O (Input/Output) operations must be made conditionally, and only finalized or committed if all previously speculated branches are predicted correctly. If there is a misprediction before a conditional operation, then that operation must not be committed, but squashed. Mispredictions affect both performance and power consumption. Power used to process the instructions along the mispredicted path is wasted.
Wasted power can be lessened by providing a confidence assignment for the confidence value of a prediction. If the confidence value exceeds a threshold, a high-confidence assignment is generated. If the confidence value is less than or equal to a threshold, a low-confidence assignment is generated. Branches are speculatively executed only if the confidence assignment is a high-confidence assignment. By setting the value of the threshold, the number of predictions that are given the high-confidence assignment can be controlled. If a branch has a low-confidence assignment, the processor does not execute the instructions on either path of the branch, but rather waits for the branch to be resolved. The processor may do something else (e.g., process another thread) while it waits for the branch to be resolved. Waiting for the branch to be resolved has an impact on performance, but saves power. Consequently, the measure of performance-per unit power consumed can increase. This measure is very important for mobile computers. Power consumption is a function of the observed ratio of low-confidence assignments to the total number of assignments (observed low-confidence ratio) which in turn is a function of the threshold value. However, there is a problem with simply setting the threshold to some value in order to achieve a desired ratio of low-confidence assignments to the total number of assignments (desired low-confidence ratio) and, thus, a desired power budget. Depending on the code being executed and runtime data, during a finite period of time, the observed low-confidence ratio may deviate from the desired low-confidence ratio. This deviation is undesirable because it means that the power budget is not being achieved during the period of time under examination.
In the second known method for handling branch uncertainty, eager execution, the microprocessor proceeds down both paths of a branch. Similar to single-path speculative execution, when a branch resolves, all of the states on the not-to-be-followed paths are discarded. Unfortunately, eager execution consumes microprocessor resources exponentially with the levels of pending branches. With unlimited resources, eager execution gives superb performance. With constrained resources, eager execution has a limited performance.
However, by providing a confidence assignment for a prediction associated with a branch it is possible to limit the amount of eager execution that occurs, thereby minimizing the unnecessary consumption of resources. By minimizing the unnecessary consumption of resources, it is possible to improve performance. Improvement in performance occurs because resources will only be expended on one path of the branch rather than two paths when a high-confidence assignment branch is encountered. Unfortunately, performance is a function of the number of high-confidence assignments that are produced out of a total number of confidence assignments. Depending on the code being executed and runtime data, during a finite period of time, the observed ratio of high-confidence assignments to the total number of confidence assignments may deviate from a desired ratio resulting in an undesirable impact on performance.
SUMMARY OF THE INVENTION
According to an embodiment of the invention a confidence assignment population control apparatus is provided. The apparatus includes a comparator that is to compare a current confidence level prediction and a current threshold indication and to generate a current confidence assignment. The apparatus includes a threshold generator that is to receive the current confidence assignment and to generate a next threshold indication.
REFERENCES:
patent: 6029006 (2000-02-01), Alexander et al.
patent: 6029228 (2000-02-01), Cai et al.
patent: 6041405 (2000-03-01), Green
patent: 6092187 (2000-07-01), Killian
patent: 6189091 (2001-02-01), Col et al.
patent: 6233645 (2001-05-01), Chrysos et al.
patent: 6308322 (2001-10-01), Serocki et al.
patent: 6324616 (2001-11-01), Chrysos et al.
patent: 6353883 (2002-03-01), Gruchowski et al.
patent: 6367004 (2002-04-01), Grochowski et al.
Erik Jacobsen, et al.; Assigning Confidence to Conditional Branch Predictions; 1996 IEEE, Proceedings of the 29th Annual International symposium on Microarchitecture, Dec. 2-4, 1996, Paris, France.
James E. Smith; A Study of Branch Prediction Strategies; In Proceedings of the 8th International Symposium on Computer Architecture, 1981 IEEE; pp. 135-148.
Rappoport Lihu
Ronen Ronny
Intel Corporation
Iqbal Nadeem
Kenyon & Kenyon
LandOfFree
Controlling population size of confidence assignments does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Controlling population size of confidence assignments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Controlling population size of confidence assignments will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3043526