Method and apparatus which implements a multi-ported lru in a multiple-clock system

Abstract

An apparatus for implementing a least-recently used (LRU) mechanism in a multi-port cache memory includes an LRU array and a shift decoder. The LRU array has multiple entries. The shift decoder includes a shifting means for shifting the entries within the LRU array. The shifting means shifts a current one of the entries and adjacent entries once, and loading new address, in response to a single cache hit in the current one of the entries. The shifting means shifts a current one of the entries and adjacent entries once, and loading an address of only one of multiple requesters into the most-recently used (MRU) entry, in response to multiple cache hits in the current one of the entries. The shifting means shifts all subsequent entries, including the current entries, n times, and loading addresses of all requesters contributed to the multiple cache hits in consecutive entries into the MRU entry and subsequent entries, in response to multiple cache hits in consecutive entries. The shifting means shifts some of the entries n times, some of the entries n−1 times, etc., and loading addresses of all requesters that have a cache hit in the multiple cache hits into the MRU entry and subsequent entries, in response to multiple cache hits not in the same entry or consecutive entries.