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.

Description

[0001]This invention was made with Government support under Contract No.: NBCH3039004 awarded by Defense Advanced Research Projects Agency (DARPA). The Government has certain rights in this invention.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 ...

AI Technical Summary

Benefits of technology

[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

Problems solved by technology

However, this approach to event outcome prediction correction may lead to “livelock” in some prediction systems.

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.

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.

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.

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.

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.

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.

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.

However, using this approach may once again degrade computer processor performance during the period of assigning random event outcome predictions.

Images