Pseudo-lru cache memory replacement method and apparatus utilizing nodes

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 lines being used and stored. The unique locating path to the memory location with the cache lines to be written back to memory, or otherwise evicted, is determined based on the stored value of bits.