# US 12,118,355 B2 · Cache coherence validation using delayed fulfillment of L2 requests

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

- Number: US 12,118,355 B2
- Document ID: US12118355B2
- Status: Granted
- Kind: B2
- Application number: 17/506,122
- Filed: 2021-10-20
- Published: 2023-04-20
- Granted: 2024-10-15
- Earliest claimed: 2021-10-20
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Shakti Kapoor; Manoj Dusanapudi; Nelson Wu
- Web page: https://patentgrep.com/patent/US12118355B2

## CPC

- G06F 9/30043: {LOAD or STORE instructions; Clear instruction}
- G06F 9/30047: {Prefetch instructions; cache control instructions}
- G06F 9/3834: {Maintaining memory consistency}
- G06F 9/3836: {Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution}
- G06F 9/3838: {Dependency mechanisms, e.g. register scoreboarding}
- G06F 9/3851: {from multiple instruction streams, e.g. multistreaming}
- G06F 9/3861: {Recovery, e.g. branch miss-prediction, exception handling (error detection or correction G06F11/00)}
- G06F 12/0811: with multilevel cache hierarchies
- G06F 12/0815: Cache consistency protocols
- G06F 12/0835: {for main memory peripheral accesses (e.g. I/O or DMA)}
- G06F 12/0842: for multiprocessing or multitasking
- G06F 12/0831: using a bus scheme, e.g. with bus monitoring or watching means
- G06F 2212/1008: Correctness of operation, e.g. memory ordering
- G06F 2212/1024: Latency reduction
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Methods and systems for validating cache coherence in a data processing system are described. A processing element may detect a load instruction requesting the processing element to transfer data from a global memory location to a local memory location. The processing element may apply, in response to detecting the load instruction requesting the processing element to transfer data from the global memory location to the local memory location, a delay to the transfer of the data from the global memory location to the local memory location. The processing element may execute the load instruction and transferring the data from the global memory location to the local memory location with the applied delay. The processing element may validate, in response to executing the load instruction and transferring the data with the applied delay, a cache coherence of the data processing system.

## Claims

### Claim 1

A method for validating cache coherence in a data processing system, the method comprising:
detecting a load instruction requesting a processing element to transfer data from a target cache line in a global memory location to a local memory location, the processing element being among a plurality of processing elements of the data processing system;
applying, in response to detecting the load instruction requesting the processing element to transfer the data from the target cache line in the global memory location to the local memory location, a delay in the global memory location to delay the transfer of the data from the target cache line in the global memory location to the local memory location, wherein applying the delay to the transfer of the data increases a window of opportunity for another processing element to make changes to the target cache line in the global memory location to create an out-of-order hazard for the data processing system, and wherein the delay is based on a distance between the processing element and other processing elements in the data processing system;
executing the load instruction and transferring the data from the target cache line in the global memory location to the local memory location with the applied delay; and
validating, in response to executing the load instruction and transferring the data with the applied delay, a cache coherence of the data processing system.

### Claim 2 (depends on 1)

The method of claim 1, wherein:
the global memory location is a memory location in a level two (L2) cache connected to the plurality of processing elements in the data processing system; and
the local memory location is a memory location in a level one (L1) cache of the processing element.

### Claim 3 (depends on 1)

The method of claim 1, wherein the load instruction is a first load instruction, and applying the delay causes the execution of the first load instruction to be completed later than an execution of a second load instruction, the second load instruction being younger than the first load instruction, wherein the first load instruction and the second load instruction each loads from the target cache line.

### Claim 4 (depends on 3)

The method of claim 3, wherein validating the cache coherence of the data processing system comprises:
in response to completing the execution of the first load instruction, detecting whether the second load instruction is being re-executed;
in response to the second load instruction being re-executed, determining the cache coherence of the data processing system is successful; and
in response to the second load instruction not being re-executed, determining the cache coherence of the data processing system has failed.

### Claim 5 (depends on 3)

The method of claim 3, wherein:
validating the cache coherence of the data processing system comprises:
executing a logic that is programmed to re-execute the second load instruction after the first load instruction is executed with the applied delay;
in response to the second load instruction being re-executed after the first load instruction is executed with the applied delay, determining that the logic is functioning correctly; and
in response to the second load instruction not being re-executed after the first load instruction is executed with the applied delay, determining that the logic is not functioning correctly.

### Claim 6 (depends on 1)

The method of claim 1, wherein the delay is based on a random number.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
detecting a data forwarding request to transfer data from a load store unit of the processing element to the local memory location; and
executing the data forwarding request and transferring the data from the load store unit of the processing element to the local memory location without the delay.

### Claim 8 (depends on 1)

The method of claim 1, wherein the changes to the target cache line comprises writing to the target cache line.

### Claim 9 (depends on 1)

The method of claim 1, further comprising controlling one or more linear feedback shift registers to generate the delay.

### Claim 10

A computing system comprising:
a first processing element;
a second processing element;
an interconnect connected to the first processing element and the second processing element;
the first processing element being configured to:
detect a load instruction requesting a processing element to transfer data from a target cache line in a global memory location to a local memory location, the global memory location being accessible by the first processing element and the second processing element, and the local memory location being accessible by the first processing element;
apply, in response to detecting the load instruction requesting the first processing element to transfer the data from the target cache line in the global memory location to the local memory location, a delay in the global memory location to delay the transfer of the data from the target cache line in the global memory location to the local memory location, wherein application of the delay to the transfer of the data increases a window of opportunity for the second processing element to make changes to the target cache line in the global memory location to create an out-of-order hazard and wherein the delay is based on a distance between the first processing element and other processing elements in the computing system;
execute the load instruction and transfer the data from the target cache line in the global memory location to the local memory location with the applied delay; and
validate, in response to the execution of the load instruction and transferring the data with the applied delay, a cache coherence of the computing system.

### Claim 11 (depends on 10)

The computing system of claim 10, further comprising a level two (L2) cache connected to the first processing element and the second processing element, wherein:
the global memory location is a memory location in the L2 cache; and
the local memory location is a memory location in a level one (L1) cache of the first processing element.

### Claim 12 (depends on 10)

The computing system of claim 10, wherein the load instruction is a first load instruction, and the application of the delay causes the execution of the first load instruction to be completed later than an execution of a second load instruction, the second load instruction being younger than the first load instruction, wherein the first load instruction and the second load instruction each loads from the target cache line.

### Claim 13 (depends on 12)

The computing system of claim 12, wherein the first processing element is configured to:
in response to completing the execution of the first load instruction, detect whether the second load instruction is being re-executed;
in response to the second load instruction being re-executed, determine the cache coherence of the computing system is successful; and
in response to the second load instruction not being re-executed, determine the cache coherence of the computing system has failed.

### Claim 14 (depends on 10)

The computing system of claim 10, wherein the delay is based on a random number.

### Claim 15

A processing element comprising:
a processor pipeline comprising one or more load store units (LSUs) configured to execute load and store instructions, the one or more LSUs being configured to:
detect a load instruction requesting the processing element to transfer data from target cache line in a global memory location to a local memory location, the processing element being among a plurality of processing elements of a data processing system;
apply, in response to detecting the load instruction requesting the processing element to transfer the data from the target cache line in the global memory location to the local memory location, a delay in the global memory location to delay the transfer of the data from the target cache line in the global memory location to the local memory location, wherein application of the delay to the transfer of the data increases a window of opportunity for the another processing element to make changes to the target cache line in the global memory location to create an out-of-order hazard, and wherein the delay is based on a distance between the processing element and other processing elements in the data processing system;
execute the load instruction and transfer the data from the target cache line in the global memory location to the local memory location with the applied delay; and
validate, in response to executing the load instruction and transferring the data with the applied delay, a cache coherence of the data processing system including the processing element.

### Claim 16 (depends on 15)

The processing element of claim 15, wherein:
the global memory location is a memory location in a level two (L2) cache connected to the plurality of processing elements in the data processing system; and
the local memory location is a memory location in a level one (L1) cache of the processing element.

### Claim 17 (depends on 15)

The processing element of claim 15, wherein:
the load instruction is a first load instruction, and applying the delay causes the first load instruction to be fulfilled later than a fulfillment of a second load instruction, the second load instruction being younger than the first load instruction and the second load instruction has a target that overlaps with a target of the first load instruction;
the one or more LSUs being configured to:
in response to completing the execution of the first load instruction, detect whether the second load instruction is being re-executed;
in response to the second load instruction being re-executed, determine the cache coherence of the data processing system is successful; and
in response to the second load instruction not being re-executed, determine the cache coherence of the data processing system has failed.