| Method and system for preventing livelock due to competing updates of prediction information -> Monitor Keywords |
|
|
  Method and system for preventing livelock due to competing updates of prediction informationUSPTO Application #: 20070277025Title: Method and system for preventing livelock due to competing updates of prediction information Abstract: A system to prevent livelock. An outcome of an event is predicted to form an event outcome prediction. The event outcome prediction is compared with a correct value for a datum to be accessed. An instruction is appended with a real event outcome when the outcome of the event is mispredicted to form an appended instruction. A prediction override bit is set on the appended instruction. Then, the appended instruction is executed with the real event outcome. (end of abstract) Agent: Duke W. Yee - Dallas, TX, US Inventors: Erik R. Altman, Vijayalakshmi Srinivasan USPTO Applicaton #: 20070277025 - Class: 712245 (USPTO) The Patent Description & Claims data below is from USPTO Patent Application 20070277025. Brief Patent Description - Full Patent Description - Patent Application Claims
BACKGROUND OF THE INVENTION [0002]1. Field of the Invention [0003]The present invention relates generally to an improved data processing system. More specifically, the present invention is directed to a computer implemented method, apparatus, and computer useable program code to prevent livelock created by competing updates of event outcome prediction information. [0004]2. Description of the Related Art [0005]Computer processors and other data processing systems sometimes find that event outcome prediction expedites the processing of data. Later, if the event outcome prediction is proven to be incorrect, these systems recover from the mispredictions. Then, these systems use the actual event outcome to update a prediction mechanism, such as a history-based hardware predictor table, in order to have a better chance of making correct event outcome predictions in the future. [0006]However, this approach to event outcome prediction correction may lead to "livelock" in some prediction systems. Livelock is an endless loop in program execution that occurs when a process repeats itself because the process continues to receive erroneous information. For example, one event, or set of events, identified as A, serves to counter-act the forward progress of another event, or set of events, identified as B. Likewise, B serves to counter-act the forward progress of A. [0007]Assume that events A and B only make forward progress if they receive a successful event outcome prediction from the prediction mechanism. Furthermore, assume an erroneous event outcome prediction puts in motion a sequence of actions that updates the prediction mechanism so that the next time the system executes the event, the event receives a correct prediction and is able to proceed forward. Using the two assumptions above in an example, the system executes event A, which receives an erroneous event outcome prediction from the prediction mechanism and then the system executes event B, which also receives an erroneous event outcome prediction. In this situation where both events A and B receive an erroneous event outcome prediction, it is possible for the system to update the prediction mechanism for event B prior to the system re-executing event A. The updates to the prediction mechanism for event B may serve to overwrite, or undo, the updates to the prediction mechanism for event A. [0008]Consequently, when the system tries to re-execute event A, event A once again receives a wrong event outcome prediction. This second wrong event outcome prediction for event A occurs because after the system updated the prediction mechanism for event A, and before the system re-executes event A, the system updates the prediction mechanism for event B destroying event A's updates. Then, the updates to the prediction mechanism for the re-execution of event A destroy the updates to the prediction mechanism for the re-execution of event B. [0009]As a result, event B also receives a wrong event outcome prediction when the system re-executes event B. Thus, any forward progress in the system for events A and B comes to a standstill because of the resultant livelock. This livelock situation may continue forever or until a user stops the system due to frustration with the lack of forward progress. [0010]One known solution to livelock is exponential back-off. Exponential back-off is an algorithm that uses feedback to multiplicatively decrease the rate of some process, in order to gradually find an acceptable rate. Exponential back-off is often used in network congestion avoidance to help determine the correct sending rate. In a livelock situation, upon incurring an event outcome misprediction, the event waits a random amount of time before trying again. If the event fails a second time, the event waits a longer random amount of time. If the event fails a third time, the event waits an even longer random amount of time and so on. [0011]As these exponential back-offs continue, the probability that two conflicting events will keep conflicting rapidly drops toward zero. Therefore, this exponential back-off mechanism serves to disentangle two conflicting events. However, in a computer processor this exponential back-off solution is impractical for at least two reasons. First, no simple mechanism currently exists to calculate the random back-offs required for the event. Second, processor performance may significantly degrade due to increasing time intervals between event execution. [0012]A second known solution to this livelock problem is to use a livelock detection counter. The livelock detection counter detects when an event is repeatedly executing. After the livelock detection counter reaches a predetermined threshold for execution of the event, the livelock detection counter assumes that livelock exists within the system, even if there is not, because it may be impossible to know for sure whether livelock actually exists. When the livelock detection counter assumes that there is livelock, the system executes one event at a time in a very simple mode until the system is reasonably confident that the livelocking events have passed. Like the previous approach above, this approach may significantly degrade computer processor performance due to slowing execution of events to one-at-a-time until livelock no longer exists within the system. [0013]A variation to the second approach above is to introduce pipeline stalls, or bubbles, in the system when livelock is determined. Thus, when the first event re-executes after a livelock condition has been detected, the first event does not wait for an event outcome prediction, but delays execution until the correct value is computed. Here again, accurately detecting a livelock situation is expensive. [0014]A more sophisticated version of the second approach above may be to actually identify the conflicting events causing livelock and delay execution of one of the events until the other event has completed. This approach still may degrade computer processor performance, although probably not as much as with the previously mentioned approaches. However, this approach is more expensive in terms of memory area and processor cycles used for implementation. Also, it is more difficult to validate that this approach works in all cases. [0015]A variation of the immediately preceding approach is to lock an event outcome prediction after updating the prediction mechanism for the first executing event of a livelocking pair of events. Thus, the next time the first event executes, the first event receives the correct value and is no longer in a livelock condition with the second event. Accurately detecting this livelock condition is a problem as with the other approaches. In addition, locking event outcome predictions may create a problem if a third event executes and interrupts the normal event execution flow within the system. Any such third event must then check for locked event outcome predictions and release them. [0016]Another known approach is to assign random event outcome predictions for a brief period when apparent livelock is detected. If the set of possible values for the event outcome prediction is small, this approach is likely to let one or both conflicting events pass, thus, resolving the livelock condition. However, using this approach may once again degrade computer processor performance during the period of assigning random event outcome predictions. [0017]Therefore, it would be beneficial to have an improved computer implemented method, system, and computer useable program code to prevent livelock created by competing updates of event outcome prediction information. SUMMARY OF THE INVENTION [0018]Illustrative embodiments provide a computer implemented method, system, and computer useable program code to prevent livelock. An outcome of an event is predicted to form an event outcome prediction. The event outcome prediction is compared with a correct value for a datum to be accessed. An instruction is appended with a real event outcome when the outcome of the event is mispredicted to form an appended instruction. A prediction override bit is set on the appended instruction. Then, the appended instruction is executed with the real event outcome. BRIEF DESCRIPTION OF THE DRAWINGS [0019]The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself, however, as well as a preferred mode of use, further objectives and advantages thereof, will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein: [0020]FIG. 1 is a pictorial representation of a data processing system in which illustrative embodiments may be implemented; [0021]FIG. 2 is a block diagram of a data processing system in which illustrative embodiments may be implemented; [0022]FIG. 3 is a block diagram of a data processing system that includes one or more execution units in accordance with an illustrative embodiment; Continue reading... Full patent description for Method and system for preventing livelock due to competing updates of prediction information Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this Method and system for preventing livelock due to competing updates of prediction information patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like Method and system for preventing livelock due to competing updates of prediction information or other areas of interest. ### Previous Patent Application: Methods and systems for secure address handling in a processor Next Patent Application: Processor, method, and data processing system employing a variable store gather window Industry Class: Electrical computers and digital processing systems: processing architectures and instruction processing (e.g., processors) ### FreshPatents.com Support Thank you for viewing the Method and system for preventing livelock due to competing updates of prediction information patent info. IP-related news and info Results in 0.40887 seconds Other interesting Feshpatents.com categories: Computers: Graphics , I/O , Processors , Dyn. Storage , Static Storage , Printers |
||
