Patent ID: 8140767

Claim:
A method for managing a number of cache lines in a cache, the method comprising: determining whether activity on a memory bus in communication with the cache exceeds a threshold activity level; responsive to determining that the threshold activity level is exceeded, locating a least important cache line in the cache, wherein the least important cache line is located using a cache replacement scheme; responsive to determining that the threshold activity level is exceeded, determining whether the least important cache line is clean; responsive to determining that the least important cache line is clean, selecting the least important cache line for replacement in the cache; responsive to determining that the least important cache line is not clean, locating a clean cache line within a subset of the number of cache lines and selecting the clean cache line for replacement, wherein the each cache line in the subset is examined in ascending order of importance according to the cache replacement scheme; wherein the cache replacement scheme is pseudo-least recently used; wherein a desired rank within the subset is zero, and wherein locating the clean cache line within the subset of the number of cache lines comprises: creating a binary representation of the desired rank within the subset, wherein the binary representation comprises a set of bits; traversing the set of bits, starting with a least significant bit, and a binary tree built from a set of least recently used bits, starting with a root node; responsive to observing a ‘1’ in a current bit in the set of bits during a set of bits traversal, inverting a least recently used bit in the set of least recently used bits corresponding to the current bit, wherein the least recently used bit corresponds to the current bit when a binary tree level number of the least recently used bit matches a distance of the current bit from the least significant bit in the set of bits; determining whether the set of bits traversal and a binary tree traversal are complete; responsive to a determination that the set of bits traversal and the binary tree traversal are not complete, advancing the set of bits traversal and the binary tree traversal and repeating steps of inverting and determining; responsive to a determination that the set of bits traversal and the binary tree traversal are complete, forming a target cache line from a desired rank cache way located in the binary tree traversal; determining whether the target cache line is clean; and responsive to a determination that the target cache line is not clean, repeating steps of creating, traversing, inverting, determining the target cache line based on the binary tree traversal, and determining whether the target cache line is clean, wherein the desired rank is increased by one.