Patent ID: 8364898

Claim:
In a data processing system having one or more processors and multiple levels of cache, including a lower level cache and a higher level cache, a method comprising: detecting a data request at the lower level cache; in response to a cache miss in the lower level cache, selecting a cache-line for eviction based upon (a) presence bits and (b) less recently used (LRU) bits; determining whether a copy of the cache-line selected for eviction is present in the higher level cache; in response to the copy of the cache-line selected for eviction being present in the higher level cache, invalidating the copy of the cache-line selected for eviction; and updating pseudo-LRU bits, wherein said invalidating further comprises: in response to the selection of the cache-line for eviction from the lower level cache: determining whether one or more copies of the cache-line selected for eviction is present in one or more higher level caches based on an inspection of a presence bit in the lower level cache associated with the selected cache-line; in response to the one or more copies of the selected cache-line being present in corresponding higher level caches, invalidating the one or more copies in corresponding lower level caches to maintain an inclusive policy; in response to no copies of the selected cache-line being present in corresponding higher level caches, evicting a cache-line from a requesting core's higher level cache using LRU policy for higher level caches in order to make space for a new incoming cache-line; in response to the eviction of cache-lines from one or more higher level caches and the lower level cache: placing new lines into (a) the one or more higher level caches, (b) the lower level cache, and (c) internal core registers; and setting (a) the respective presence bits in the one or more higher level caches to a second value and (b) the respective LRU bits and state bits in the corresponding one or more higher level caches and the lower level cache, appropriately; and in response to a replacement of a cache-line in a higher level cache, re-setting the corresponding presence bit in the lower level cache to a first value.