# US 2008/0313445 A1 · Method and system for preventing livelock due to competing updates of prediction information

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0313445 A1
- Document ID: US20080313445A1
- Status: Published application
- Kind: A1
- Application number: 12/051,322
- Filed: 2008-03-19
- Published: 2008-12-18
- Earliest claimed: 2006-05-25
- Assignees: International Business Machines Corporation
- Inventors: ERIK R. ALTMAN; Vijayalakshmi Srinivasan
- Web page: https://patentgrep.com/patent/US20080313445A1

## CPC

- G06F 9/528: {by using speculative mechanisms}
- G06F 9/30043: {LOAD or STORE instructions; Clear instruction}
- G06F 9/3842: {Speculative instruction execution}
- G06F 9/3861: {Recovery, e.g. branch miss-prediction, exception handling (error detection or correction G06F11/00)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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.

## Claims

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 3)

The computer implemented method of claim 3, wherein the execution unit is a load/store execution unit.

### Claim 5 (depends on 2)

The computer implemented method of claim 2, wherein the instruction is a load instruction, and wherein the event is execution of the load instruction.

### Claim 6 (depends on 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.

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 1)

The computer implemented method of claim 1, wherein the real event outcome is a correct column address for the datum to be accessed.

### Claim 9 (depends on 2)

The computer implemented method of claim 2, wherein a mispredicted event is an incorrect column address prediction for the datum to be accessed.

### Claim 10 (depends on 1)

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.

### Claim 11 (depends on 3)

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.

### Claim 12 (depends on 2)

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.

### Claim 13 (depends on 2)

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.

### Claim 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.

### Claim 15 (depends on 14)

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.

### Claim 16 (depends on 15)

The data processing system of claim 15, wherein the processing unit includes one or more execution units.

### Claim 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.

### Claim 18 (depends on 17)

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.

### Claim 19 (depends on 18)

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.

### Claim 20 (depends on 18)

The computer program product of claim 18, wherein the instruction is a load instruction, and wherein the event is execution of the load instruction.
