# US 2026/0086952 A1 · Time-efficient implementation of cache replacement policy

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

- Number: US 2026/0086952 A1
- Document ID: US20260086952A1
- Status: Published application
- Kind: A1
- Application number: 19/111,200
- Filed: 2022-09-12
- Published: 2026-03-26
- Earliest claimed: 2022-09-12
- Assignees: Google Inc.
- Applicants: Google LLC
- Inventors: Ganesh Manikanta Sai Pavan Kumar Seelam; Raj Shekhar Kashyap
- Web page: https://patentgrep.com/patent/US20260086952A1

## CPC

- G06F 12/123: with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
- G06F 12/0864: using pseudo-associative means, e.g. set-associative or hashing
- G06F 12/126: with special data handling, e.g. priority of data or instructions, handling errors or pinning
- G06F 12/128: adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A cache includes multiple sets with each set having multiple respective ways, and replacement logic configured to implement a two-stage least recently used (LRU) replacement computation. The two-stage LRU replacement computation causes the cache to perform a first stage during which the cache computes an LRU way for a set, and a second stage during which the cache updates an LRU data structure with information of a transaction accessed way.

## Claims

### Claim 1

A cache comprising:
multiple sets with each set having multiple respective ways; and
replacement logic configured to implement a two-stage least recently used (LRU) replacement computation, wherein the two-stage LRU replacement computation causes the cache to perform operations comprising:
a first stage during which the cache computes an LRU way for a set, and
a second stage during which the cache updates an LRU data structure with information of a transaction accessed way.

### Claim 2 (depends on 1)

The cache of claim 1, wherein the cache is configured to perform the two-stage LRU replacement computation in consecutive clock cycles.

### Claim 3 (depends on 1)

The cache of claim 1, wherein the cache is configured to implement an LRU replacement policy using the computed LRU way.

### Claim 4 (depends on 1)

The cache of claim 1, wherein the replacement logic comprises a plurality of nodes storing respective way values for each set, and wherein performing the second stage comprises shifting the way values stored between the nodes for the set.

### Claim 5 (depends on 4)

The cache of claim 4, wherein performing the second stage comprises updating each node for a set with data the node already stores or data shifted from another node.

### Claim 6 (depends on 5)

The cache of claim 5, wherein performing the first stage for a current transaction comprises:
in response to a hazard condition resulted from the second stage of a previous transaction being performed on a same particular set, performing hazard resolution for the current transaction.

### Claim 7 (depends on 6)

The cache of claim 6, wherein performing the hazard resolution for the current transaction comprises:
in response to determining that all of the respective ways in the particular set are eligible for replacement, determining the LRU way for the current transaction based on the LRU data structure after the LRU data structure has been updated for the previous transaction.

### Claim 8 (depends on 6)

The cache of claim 6, wherein the replacement logic is configured to, in response to determining that not all of the respective ways in the particular set are eligible for replacement:
determining hazard-resolved eligible nodes from the plurality of nodes;
selecting an eligible node from the hazard-resolved eligible nodes; and
determining the LRU way using the way value stored in the selected eligible node.

### Claim 9 (depends on 8)

The cache of claim 8, wherein the replacement logic is configured to start determining the hazard-resolved eligible nodes from the plurality of nodes before the second stage of the previous transaction has been completed.

### Claim 10 (depends on 9)

The cache of claim 9, wherein determining the hazard-resolved eligible nodes from the plurality of nodes comprises:
generating un-resolved node data that identifies eligible nodes from the plurality of nodes based on eligible ways and the LRU data structure before the LRU data structure been updated by the second stage of the previous transaction; and
shifting the un-resolved node data using shift information generated during the second stage of the previous transaction to generate hazard-resolved node data that identifies the hazard-resolved eligible nodes.

### Claim 11

A method for performing LRU replacement computation for a cache including multiple sets with each set having multiple respective ways:
computing an LRU way for a set during a first stage; and
updating an LRU data structure with information of a transaction accessed way during a second stage.

### Claim 12 (depends on 11)

The method of claim 11, wherein the first stage and the second stage are performed in consecutive clock cycles.

### Claim 13 (depends on 11)

The method of claim 11, wherein the cache is configured to implement an LRU replacement policy using the computed LRU way.

### Claim 14 (depends on 11)

The method of claim 11, wherein:
the method further comprises: storing respective way values for each set in a plurality of nodes; and
performing the second stage comprises shifting the way values stored between the nodes for the set.

### Claim 15 (depends on 14)

The method of claim 14, wherein performing the second stage comprises updating each node for a set with data the node already stores or data shifted from another node.

### Claim 16 (depends on 15)

The method of claim 15, wherein performing the first stage for a current transaction comprises:
in response to a hazard condition resulted from the second stage of a previous transaction being performed on a same particular set, performing hazard resolution for the current transaction.

### Claim 17 (depends on 16)

The method of claim 16, wherein performing the hazard resolution for the current transaction comprises:
in response to determining that all of the respective ways in the particular set are eligible for replacement, determining the LRU way for the current transaction based on the LRU data structure after the LRU data structure has been updated for the previous transaction.

### Claim 18 (depends on 16)

The method of claim 16, wherein performing the hazard resolution for the current transaction comprises, in response to determining that not all of the respective ways in the particular set are eligible for replacement:
determining hazard-resolved eligible nodes from the plurality of nodes;
selecting an eligible node from the hazard-resolved eligible nodes; and
determining the LRU way using the way value stored in the selected eligible node.

### Claim 19 (depends on 18)

The method of claim 18, wherein determining hazard-resolved eligible nodes comprises: start determining the hazard-resolved eligible nodes from the plurality of nodes before the second stage of the previous transaction has been completed.

### Claim 20 (depends on 19)

The method of claim 19, wherein determining the hazard-resolved eligible nodes comprises:
generating un-resolved node data that identifies eligible nodes from the plurality of nodes based on eligible ways and the LRU data structure before the LRU data structure been updated by the second stage of the previous transaction; and
shifting the un-resolved node data using shift information generated during the second stage of the previous transaction to generate hazard-resolved node data that identifies the hazard-resolved eligible nodes.
