Patent ID: 7085896

Claim:
An apparatus for implementing a least-recently used (LRU) cache replacement scheme in a multi-port cache memory, said apparatus comprising: an LRU array having a plurality of entries; and a shift decoder, coupled to said LRU array, having means for shifting a current one of said entries and adjacent entries once, and loading new address, in response to a single cache hit in said current one of said entries; means for shifting a current one of said entries and adjacent entries once, and loading an address of only one of multiple requesters that has multiple cache hits in said current one of said entries, in response to said multiple cache hits in said current one of said entries; means for shifting all subsequent entries, including said current entries, n times, and loading addresses of all requesters contributed to multiple cache bits in consecutive entries, in response to said multiple cache hits in consecutive entries; and means for shifting some of said entries n times, some of said entries n−1 times. and loading addresses of all requestors that have a cache hit in multiple cache bits but not in said same entry or consecutive entries, in response to said multiple cache hits not in said same entry or consecutive entries.