Apparatus and method for implementing a least recently used cache replacement algorithm
US6408364B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Mar 17, 2000 |
| Grant date | Jun 18, 2002 |
| Priority date | — |
| Expiry date | Mar 17, 2020 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F12/123
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A least recently used (LRU) cache replacement algorithm is implemented with a set of N pointer registers that point to respective ways of an N-way set of memory blocks. One of the pointer registers is an LRU pointer, pointing to a least recently used way and another of the pointer registers is a most recently used (MRU) pointer, pointing to a most recently used way. For a cache fill operation in which a new memory block is written to one of the N ways, the new memory block is written into the way (wayn), pointed to by the LRU pointer. All the pointers except the MRU pointer are promoted to point to a way pointed to by respective newer neighboring pointers, the newer neighboring pointers being neighbors towards the MRU pointer. The MRU pointer is updated to point to the wayn in which the new memory block was written. For a cache hit in which one of the memory blocks in the set, waym, is accessed for a write or read operation, all the pointers waym and newer, except for the MRU pointer, are promoted to point to a way pointed to by a newer neighboring pointer. The MRU pointer is changed to point to waym. For an invalidate operation in which one of the ways, wayk is invalidated, all th…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.