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

Images