Simplified least-recently-used entry replacement in associative cache

Abstract

A simplified or pseudo least-recently-used (LRU) process and circuit in a cache memory or translation lookaside table (TLB) maintains status bits to identify which entries are valid and which entries have been recently used. If none of the entries are invalid, only entries not indicated as recently used are replaced (or overwritten). When all entries are indicated as valid and recently used, status bits other than the status bits for the entry last accessed are changed to indicate that the corresponding entries have not been recently used. Accordingly, those entries can be replaced, but the most recently used entry still cannot be replaced. This makes the pseudo LRU process closer to a full LRU process when compared to pseudo LRU processes which clear all status bits simultaneously. Complexity for the LRU process is not greatly increased because the address generated for the most recent access of an entry can be used to identify the bit which is not changed.