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.

1 . A computer implemented method in a data processing system to prevent livelock, the computer implemented method comprising:
 predicting an outcome of an event to form an event outcome prediction;   comparing the event outcome prediction with a correct value for a datum to be accessed;   appending to an instruction a real event outcome when the outcome of the event is mispredicted to form an appended instruction;   setting a prediction override bit on the appended instruction; and   executing the appended instruction with the real event outcome.   
     
     
         2 . The computer implemented method of  claim 1 , further comprising:
 responsive to receiving an instruction to access the datum, reading the instruction;   responsive to reading the instruction, generating an effective address of the datum to be accessed;   translating the effective address to a real address of the datum to be accessed;   accessing the datum using the real address; and   rejecting the instruction if the outcome of the event is mispredicted.   
     
     
         3 . The computer implemented method of  claim 2 , wherein the predicting, comparing, appending, setting, executing, reading, generating, translating, accessing, and rejecting steps are executed in an execution unit. 
     
     
         4 . The computer implemented method of  claim 3 , wherein the execution unit is a load/store execution unit. 
     
     
         5 . The computer implemented method of  claim 2 , wherein the instruction is a load instruction, and wherein the event is execution of the load instruction. 
     
     
         6 . The computer implemented method of  claim 6 , wherein the load instruction includes source operands, and wherein the source operands provides the effective address of the datum to be accessed. 
     
     
         7 . The computer implemented method of  claim 1 , wherein the correct value for the datum to be accessed is a correct column address for the datum. 
     
     
         8 . The computer implemented method of  claim 1 , wherein the real event outcome is a correct column address for the datum to be accessed. 
     
     
         9 . The computer implemented method of  claim 2 , wherein a mispredicted event is an incorrect column address prediction for the datum to be accessed. 
     
     
         10 . The computer implemented method of  claim 1 , wherein the prediction override bit is set to one, and wherein when the prediction override bit is set to one the predicting step is not performed during execution of the appended instruction. 
     
     
         11 . The computer implemented method of  claim 3 , wherein the execution unit uses a set-predict array to perform the predicting step, and wherein the execution unit uses a comparator to perform the comparing step. 
     
     
         12 . The computer implemented method of  claim 2 , wherein the real address of the datum to be accessed is stored in a data cache tag directory, and wherein the datum to be accessed is stored in a data cache memory, and wherein the data cache tag directory and the data cache memory store data in rows and columns, and wherein the data cache tag directory and the data cache memory have the same number of rows and columns. 
     
     
         13 . The computer implemented method of  claim 2 , wherein the effective address is used to determine a row address of the datum to be accessed, and wherein the real address is used to determine a column address of the datum to be accessed. 
     
     
         14 . A data processing system to prevent livelock, comprising:
 a bus system;   a storage device connected to the bus system, wherein the storage device includes a set of instructions; and   a processing unit connected to the bus system, wherein the processing unit executes the set of instructions to predict an outcome of an event to form an event outcome prediction, compare the event outcome prediction with a correct value for a datum to be accessed, append to an instruction a real event outcome when the outcome of the event is mispredicted to form an appended instruction, set a prediction override bit on the appended instruction, and execute the appended instruction with the real event outcome.   
     
     
         15 . The data processing system of  claim 14 , wherein the processing unit executes a further set of instructions to read an instruction to access the datum in response to receiving the instruction, generate an effective address of the datum to be accessed in response to reading the instruction, translate the effective address to a real address of the datum to be accessed, access the datum using the real address, and reject the instruction if the outcome of the event is mispredicted. 
     
     
         16 . The data processing system of  claim 15 , wherein the processing unit includes one or more execution units. 
     
     
         17 . A computer program product to prevent livelock, the computer program product comprising:
 a computer usable medium having computer usable program code embodied therein, the computer usable medium comprising:
 computer usable program code configured to predict an outcome of an event to form an event outcome prediction; 
 computer usable program code configured to compare the event outcome prediction with a correct value for a datum to be accessed; 
 computer usable program code configured to append to an instruction a real event outcome when the outcome of the event is mispredicted to form an appended instruction; 
 computer usable program code configured to set a prediction override bit on the appended instruction; and 
 computer usable program code configured to execute the appended instruction with the real event outcome. 
   
     
     
         18 . The computer program product of  claim 17 , further comprising:
 computer usable program code configured to read an instruction to access the datum in response to receiving the instruction;   computer usable program code configured to generate an effective address of the datum to be accessed in response to reading the instruction;   computer usable program code configured to translate the effective address to a real address of the datum to be accessed;   computer usable program code configured to access the datum using the real address; and   computer usable program code configured to reject the instruction if the outcome of the event is mispredicted.   
     
     
         19 . The computer program product of  claim 18 , wherein an execution unit executes the computer usable program code configured to predict the outcome of the event to form the event outcome prediction, the computer usable program code configured to compare the event outcome prediction with the correct value for the datum to be accessed, the computer usable program code configured to append to the instruction the real event outcome when the outcome of the event is mispredicted to form the appended instruction, the computer usable program code configured to set the prediction override bit on the appended instruction, the computer usable program code configured to execute the appended instruction with the real event outcome, the computer usable program code configured to read the instruction to access the datum in response to receiving the instruction, the computer usable program code configured to generate the effective address of the datum to be accessed in response to reading the instruction, the computer usable program code configured to translate the effective address to the real address of the datum to be accessed, the computer usable program code configured to access the datum using the real address, and the computer usable program code configured to reject the instruction if the outcome of the event is mispredicted. 
     
     
         20 . The computer program product of  claim 18 , wherein the instruction is a load instruction, and wherein the event is execution of the load instruction.