Optimizing a cache back invalidation policy
First Claim
1. 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, wherein said selecting further comprises;
partitioning multiple “
cache-ways”
of a cache set into a less recently used (LRU) group and a more recently used (MRU) group using one or more of (a) pseudo-LRU bits; and
(b) non-LRU based replacement policy parameters;
in response to a cache miss in the lower level cache, initiating a process to determine which cache line is consequently selected for eviction in the lower level cache, based on values of one or more of;
(a) a presence bit;
(b) a LRU bit or a pseudo LRU bit; and
(c) parameters from non-LRU based replacement policies, wherein the initiating comprises;
(a) checking the value of the presence bits;
(b) in response to the value of the presence bits being set to a first value, receiving an indication that a copy of the cache-line is not present in a corresponding higher level cache; and
(c) in response to the value of the presence bits being set to a second value, receiving an indication that a copy of the cache-line is present in the corresponding higher level cache;
identifying a least recently used cache-line in said lower level cache using said pseudo-LRU bits;
in response to the least recently used cache-line not having a corresponding presence bit set to the second value or a group of cache-lines constituting the LRU group not having the corresponding presence bits set to the second value, executing one or more of;
(a) a selection of the least recently used cache-line for eviction;
(b) replacement of the least recently used cache-line with a new cache-line; and
(c) a change to the LRU bits; and
in response to the least recently used cache-line having a corresponding presence bit set to the second value and one or more elements of the LRU group not having the corresponding presence bit set to the second value, executing one or more of;
(a) a random selection of a less recently used cache-line from the LRU group for eviction, wherein said less recently cache-line that is randomly selected is not the least recently used cache-line;
(b) replacement of said less recently used cache-line with a new cache-line; and
(c) a modification of the LRU bits;
determining whether a copy of the cache-line selected for eviction is present in the higher level cache; and
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.
1 Assignment
0 Petitions
Accused Products
Abstract
A method, a system and a computer program product for enhancing a cache back invalidation policy by utilizing least recently used (LRU) bits and presence bits in selecting cache-lines for eviction. A cache back invalidation (CBI) utility evicts cache-lines by using presence bits to avoid replacing a cache-line in a lower level cache that is also present in a higher level cache. Furthermore, the CBI utility selects the cache-line for eviction from an LRU group. The CBI utility ensures that dormant cache-lines in the higher level caches do not retain corresponding presence bits set in the lower level caches by unsetting the presence bits in the lower level cache when a line is replaced in the higher level cache. Additionally, when a processor core becomes idle, the CBI utility invalidates the corresponding higher level cache by unsetting the corresponding presence bits in the lower level cache.
-
Citations
18 Claims
-
1. 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, wherein said selecting further comprises; partitioning multiple “
cache-ways”
of a cache set into a less recently used (LRU) group and a more recently used (MRU) group using one or more of (a) pseudo-LRU bits; and
(b) non-LRU based replacement policy parameters;in response to a cache miss in the lower level cache, initiating a process to determine which cache line is consequently selected for eviction in the lower level cache, based on values of one or more of;
(a) a presence bit;
(b) a LRU bit or a pseudo LRU bit; and
(c) parameters from non-LRU based replacement policies, wherein the initiating comprises;
(a) checking the value of the presence bits;
(b) in response to the value of the presence bits being set to a first value, receiving an indication that a copy of the cache-line is not present in a corresponding higher level cache; and
(c) in response to the value of the presence bits being set to a second value, receiving an indication that a copy of the cache-line is present in the corresponding higher level cache;identifying a least recently used cache-line in said lower level cache using said pseudo-LRU bits; in response to the least recently used cache-line not having a corresponding presence bit set to the second value or a group of cache-lines constituting the LRU group not having the corresponding presence bits set to the second value, executing one or more of;
(a) a selection of the least recently used cache-line for eviction;
(b) replacement of the least recently used cache-line with a new cache-line; and
(c) a change to the LRU bits; andin response to the least recently used cache-line having a corresponding presence bit set to the second value and one or more elements of the LRU group not having the corresponding presence bit set to the second value, executing one or more of;
(a) a random selection of a less recently used cache-line from the LRU group for eviction, wherein said less recently cache-line that is randomly selected is not the least recently used cache-line;
(b) replacement of said less recently used cache-line with a new cache-line; and
(c) a modification of the LRU bits;determining whether a copy of the cache-line selected for eviction is present in the higher level cache; and 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. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A data processing system comprising:
-
one or more processors; a cache memory system hierarchically organized into multiple levels including a highest level having one or more level 1 (L1) caches and an adjacent lower level cache having one or more level 2 (L2) caches, wherein the level 1 cache is dedicated to one processor core or shared by multiple processor cores; a cache controller; logic which executes on a processor and causes the processor to; detect a data request at the lower level cache; in response to a cache miss in the lower level cache;
select a cache-line for eviction based upon (a) presence bits and (b) less recently used (LRU) bits;
determine whether a copy of the cache-line selected for eviction is present in a higher level cache based on an inspection of a presence bit in the lower level cache associated with the selected cache-line;
in response to the copy of the cache-line selected for eviction being present in the higher level cache, invalidate the copy of the cache-line selected for eviction; and
update pseudo-LRU bits;wherein said logic that causes the processor to invalidate the copy of the cache-line further comprises logic that causes the system to;
in response to determining that one or more copies of the selected cache-line is present in corresponding higher level caches, invalidate the one or more copies in corresponding lower level caches to maintain an inclusive policy. - View Dependent Claims (7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. A processor chip comprising:
-
one or more processors each having a higher level cache; a lower level cache associated with one or more higher level caches; and a cache controller which includes logic that; detects a data request at the lower level cache; in response to a cache miss in the lower level cache, selects a cache-line for eviction based upon (a) presence bits and (b) less recently used (LRU) bits; determines whether a copy of the cache-line selected for eviction is present in the higher level cache of at least one of the one or more processors based on an inspection of a presence bit in the lower level cache associated with the selected cache-line; in response to the copy of the cache-line selected for eviction being present in the higher level cache, invalidates the copy of the cache-line selected for eviction; and updates pseudo-LRU bits; and in response to a processor core initiating a process to attain an idle status, invalidates the higher level cache associated with said processor core in order to re-set presence bits in the lower level cache to the corresponding first values, wherein said process is selected from among processes which include a process to conclude an execution of a particular program. - View Dependent Claims (16, 17, 18)
-
Specification