Least recently used (LRU) cache replacement implementation using a FIFO storing indications of whether a way of the cache was most recently accessed
US9720847B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jul 17, 2013 |
| Grant date | Aug 1, 2017 |
| Priority date | — |
| Expiry date | Mar 30, 2034 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F7/78
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method and apparatus for calculating a victim way that is always the least recently used way. More specifically, in an m-set, n-way set associative cache, each way in a cache set comprises a valid bit that indicates that the way contains valid data. The valid bit is set when a way is written and cleared upon being invalidated, e.g., via a snoop address, The cache system comprises a cache LRU circuit which comprises an LRU logic unit associated with each cache set. The LRU logic unit comprises a FIFO of n-depth (in certain embodiments, the depth corresponds to the number of ways in the cache) and m-width. The FIFO performs push, pop and collapse functions. Each entry in the FIFO contains the encoded way number that was last accessed.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.