Lru error detection using the collection of read and written lru bits

Abstract

At least-recently used (LRU) storage means and its associated logic maintain usage history for associativity class entries of a cache directory. The storage means includes an independent storage array for each of the bit positions of an LRU binary code pattern. Parity bits are provided in the arrays for each LRU bit. Separate read/write controls simultaneously write updated LRU bits to some of the arrays and read out unchanged LRU bits from the remaining arrays during updating of a usage history entry when its associativity class is used. Pattern checking logic collects the update bits and the unchanged bits during the update cycle to determine whether or not the new entry is a valid LRU combination. A parity bit is written with each of the update LRU bits written into the arrays and parity bits are read out from the arrays with the unchanged LRU bits for parity checking of each unchanged LRU bit during updating of usage history entries.