Patent ID: 7577793

Claim:
A method for cache line replacement including the steps of: Identifying, without incurring throughput performance penalties, a first cache line in a higher level cache that does not exist in a lower level cache, the identifying further comprising: determining, by a patrol snoop sequencer, a first time when a higher level cache directory is not being otherwise used; reading one or more cache entries from the higher level cache directory during the first time; forming an address of the first cache line in the higher level cache using a tag field from the one or more cache entries from the higher level cache directory; transmitting a snoop read via a processor memory bus to the lower level cache using the address of the first cache line; sending via the processor memory bus, by a cache directory of the lower level cache, a cache miss signal if the address of the first cache line is not found in the cache directory of the lower level cache; and sending via the processor memory bus, by the cache directory of the lower level cache, a cache hit signal if the address of the first cache line is found in the cache directory of the lower level cache; and if a cache miss signal is received by the higher level cache, updating a corresponding entry in the higher level cache directory to identify the first cache line as an eviction candidate; wherein the patrol snoop sequencer performs a cycle through all cache entries in the higher level cache directory and then repeats the cycle; and wherein the step of making a snoop read to the lower level cache further comprising the steps of: determining a second time when a lower level cache directory is not being otherwise used; accessing the lower level cache directory using the address of the cache line in the higher level directory during the second time; returning the miss in the lower level cache if the accessing the lower level cache directory using the address of the cache line in the higher level directory during the second time results in a miss in the lower level cache directory; and returning the hit in the lower level cache if the accessing the lower level cache directory using the address of the cache line in the higher level directory during the second time results in a hit in the lower level cache directory.