Pseudo-LRU cache memory replacement method and apparatus utilizing nodes
US5594886A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | May 31, 1995 |
| Grant date | Jan 14, 1997 |
| Priority date | — |
| Expiry date | May 31, 2015 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F12/126
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
An apparatus and method implementing an algorithm for determining the most likely least recently used cache line in a cache so that this cache line can be written back to main memory. This algorithm is implemented on a bus control unit bridging a 50 Mhz multi-processor interconnect bus with a 33 Mhz peripheral component interconnect bus through an asynchronous interface. All data being transferred between the multi-processor interconnect bus and the peripheral component interconnect bus must pass through the input/output cache on the bus control unit. The algorithm determines a unique locating path to the last used cache lines and from this determines a unique locating path to a memory location which likely contains a least recently used cache line which can then be written back to main memory. Each memory location is identified by a unique locating path which passes through a nodal tree. Each node on the lowest level of nodes is associated with two memory locations, and, each pair of nodes is associated with one node on a next high level of nodes. Each node is associated with a bit in a register which is used to identify and record the unique path through the nodes of the cache li…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.