Optimizing a Cache Back Invalidation Policy

• US 20130111139A1
• Filed: 12/21/2012
• Published: 05/02/2013
• Est. Priority Date: 01/23/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Balakrishnan, Ganesh, Krishna, Anil
• Granted Patent: US 9,043,556 B2
• Time in Patent Office: Days
• US Class Current: 711/122
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/0808 with cache invalidating means G06F12/0815 takes precedence
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list

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.

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; 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.

2. The method of claim 1, wherein said updating further comprises:

in response to (a) a cache hit within a LRU group, wherein said cache hit does not occur in a least recently used cache-way or (b) the eviction of a cache-line from the LRU group followed by a replacement of the evicted cache-line with a new cache-line, wherein the least recently used cache-line is not evicted, modifying a first level-1 LRU bit value to a current level-1 LRU bit value to (1) indicate that a first cache-way corresponding to the cache hit or the replacement of the evicted cache-line with the new cache-line is currently a member of a more recently used (MRU) group and is no longer a member of the LRU group and (2) identify a second cache-way which replaces the first cache-way as a member of the LRU group.

3. The method of claim 1, further comprising:

in response to a cache miss, determining whether to evict the cache-line in the least recently used way by using one or more of presence bits, LRU bits and a cache level location of the cache miss;

in response to said cache-line in said least recently used cache-way being selected for eviction;

replacing the evicted cache-line with a new cache-line;

switching one or more corresponding higher level LRU bit values to indicate the modified and current designation of one or more cache-way pairs, as a result of the eviction of the least recently used cache-line, wherein said current designation is defined for one or more pairs as (a) more recently used (MRU) pairs or (b) less recently used (LRU) pairs;

changing lower level LRU bit values to;

(a) indicate that a cache-way previously containing the least recently used cache-line and currently containing the new cache-line is currently a more recently used cache way within a MRU group;

(b) identify a cache-line as a currently designated LRU cache-line as a result of a replacement of the previously designated least recently used cache-line of a LRU group; and

in response to a cache hit in a MRU group, maintaining a same set of values of the LRU bits.

4. The method of claim 1, 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.

5. The method of claim 1, further comprising:

in response to a processor core initiating a process to attain an idle status, invalidating 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.

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 a lower adjacent level 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;

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.

7. The data processing system of claim 6, 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 the selection of the cache-line for eviction from the lower level cache;

determine 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 the presence bit in the lower level cache associated with the selected cache-line; and

in response to the one or more copies of the selected cache-line being present in corresponding higher level caches, invalidate the one or more copies in corresponding lower level caches to maintain an inclusive policy.

8. The data processing system of claim 7, 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 no copies of the selected cache-line being present in corresponding higher level caches, evict 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.

9. The data processing system of claim 7, 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 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

set (a) the respective presence bits in the one or more higher level caches to the 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-set the corresponding presence bit in the lower level cache to the first value.

10. The data processing system of claim 6, wherein said logic that causes the processor to select the cache line for eviction further comprises logic that causes the processor to:

partition 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; and

in response to a cache miss in the lower level cache, initiate 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 processor;

(a) checks the value of the presence bits;

(b) in response to the value of the presence bits being set to a first value, receives 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, receives an indication that a copy of the cache-line is present in the corresponding higher level cache.

11. The data processing system of claim 6, wherein said logic that causes the processor to select the cache line for eviction further comprises logic that causes the processor to:

identify 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 does have the corresponding presence bits set to the second value, execute 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.

12. The data processing system of claim 11, wherein said logic that causes the processor to select the cache line for eviction further comprises logic that causes the processor to:

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, execute 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.

13. The data processing system of claim 6, wherein said logic that causes the processor to update pseudo-LRU bits further comprises logic that causes the processor to:

in response to (a) a cache hit within a LRU group, wherein said cache hit does not occur in a least recently used cache-way or (b) the eviction of a cache-line from the LRU group followed by a replacement of the evicted cache-line with a new cache-line, wherein the least recently used cache-line is not evicted, modify a first level-1 LRU bit value to a current level-1 LRU bit value to (i) indicate that a first cache-way corresponding to the cache hit or the replacement of the evicted cache-line with the new cache-line is currently a member of a more recently used (MRU) group and (ii) identify a second cache-way which replaces the first cache-way as a member of the LRU group.

14. The data processing system of claim 6, wherein said logic that causes the processor to update pseudo-LRU bits further comprises logic that causes the processor to:

in response to the cache-line in the least recently used cache-way being selected for eviction;

replace the evicted cache-line with a new cache-line;

switch one or more corresponding higher level LRU bit values to indicate the modified and current designation of one or more cache-way pairs, as a result of the evicted cache-line, wherein said current designation is defined for one or more pairs as (a) more recently used (MRU) pairs or (b) less recently used (LRU) pairs;

change lower level LRU bit values to;

(a) indicate that a cache-way previously containing the least recently used cache-line and currently containing the new cache-line is currently a more recently used cache way within a MRU group; and

(b) identify a cache-line as a currently designated LRU cache-line as a result of a replacement of the previously designated least recently used cache-line of a LRU group; and

in response to a cache hit in a MRU group, maintaining a same set of values of the LRU bits.

15. The data processing system of claim 6, further comprising logic that causes the processor to:

in response to a processor core initiating a process to attain an idle status, invalidate 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.

16. 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;

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.

17. The processor chip of claim 16, wherein said logic that causes invalidates the copy of the cache line selected for eviction further comprises logic that:

in response to the selection of the cache-line for eviction from the lower level cache;

determines 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 the 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, invalidates 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, evicts 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;

places new lines into (a) the one or more higher level caches, (b) the lower level cache and (c) internal core registers; and

sets (a) the respective presence bits in the one or more higher level caches to the 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-sets the corresponding presence bit in the lower level cache to the first value.

18. The processor chip of claim 16, wherein said logic that causes the controller to select further comprises logic that causes the controller to:

partition 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, initiate 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 logic that initiates comprises logic that;

(a) checks the value of the presence bits;

(b) in response to the value of the presence bits being set to a first value, receives an indication that a copy of the cache-line is not present in a corresponding higher level cache;

(c) in response to the value of the presence bits being set to a second value, receives an indication that a copy of the cache-line is present in the corresponding higher level cache;

identifies 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 having the corresponding presence bits set to the second value, executes 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, executes 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.

19. The processor chip of claim 16, wherein said logic that updates pseudo-LRU bits further comprises logic that:

in response to (a) a cache hit within a LRU group, wherein said cache hit does not occur in a least recently used cache-way or (b) the eviction of a cache-line from the LRU group followed by a replacement of the evicted cache-line with a new cache-line, wherein the least recently used cache-line is not evicted, modifies a first level-1 LRU bit value to a current level-1 LRU bit value to (i) indicate that a first cache-way corresponding to the cache hit or the replacement of the evicted cache-line with the new cache-line is currently a member of a more recently used (MRU) group and (ii) identify a second cache-way which replaces the first cache-way as a member of the LRU group;

in response to the cache-line in the least recently used cache-way is selected for eviction;

replacing the evicted cache-line with a new cache-line;

switches one or more corresponding higher level LRU bit values to indicate the modified and current designation of one or more cache-way pairs, as a result of the evicted cache-line, wherein said current designation is defined for one or more pairs as (a) more recently used (MRU) pairs or (b) less recently used (LRU) pairs;

changing lower level LRU bit values to;

(a) indicate that a cache-way previously containing the least recently used cache-line and currently containing the new cache-line is currently a more recently used cache way within a MRU group;

(b) identify a cache-line as a currently designated LRU cache-line as a result of a replacement of the previously designated least recently used cache-line of a LRU group; and

in response to a cache hit in a MRU group, maintains a same set of values of the LRU bits.

20. The processor chip of claim 16, further comprising logic that:

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.