Time-efficient implementation of cache replacement policy
AssigneeGoogle Inc.
InventorsGanesh Manikanta Sai Pavan Kumar Seelam, Raj Shekhar Kashyap
Life of this patent
Estimating the term…
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.
Claims20
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.
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.
Dependencies are inferred from the claim text.