Optimizing A Cache Back Invalidation Policy

• US 20100191916A1
• Filed: 01/23/2009
• Published: 07/29/2010
• 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 8,364,898 B2
• Time in Patent Office: Days
• US Class Current: 711/134
• 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 and a system for utilizing less recently used (LRU) bits and presence bits in selecting cache-lines for eviction from a lower level cache in a processor-memory sub-system. A cache back invalidation (CBI) logic utilizes LRU bits to evict only cache-lines within a LRU group, following a cache miss in the lower level cache. In addition, the CBI logic uses presence bits to (a) indicate whether a cache-line in a lower level cache is also present in a higher level cache and (b) evict only cache-lines in the lower level cache that are not present in a corresponding higher level cache. However, when the lower level cache-line selected for eviction is also present in any higher level cache, CBI logic invalidates the cache-line in the higher level cache. The CBI logic appropriately updates the values of presence bits and LRU bits, following evictions and invalidations.

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) the presence bits and (b) the less recently used (LRU) bits;

determining whether a copy of the cache-line selected for eviction is present in a higher level cache;

when the copy of the cache-line selected for eviction is present in the higher level cache, invalidating the copy of the cache-line selected for eviction; and

updating the pseudo-LRU bits.

2. The method of claim 1, 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) when the value of the presence bits is set to a first value, receiving an indication that a copy of the cache-line is not present in a corresponding higher level cache;

(c) when the value of the presence bits is 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;

when the least recently used cache-line does not have 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, 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

when the least recently used cache-line has a corresponding presence bit set to the second value and one or more elements of the LRU group does not have 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.

3. 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 (a) 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 (b) identify a second cache-way which replaces the first cache-way as a member of the LRU group;

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;

when said cache line in said least recently used cache-way is selected for eviction;

replacing the evicted cache line with a new cache line;

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

when the one or more copies of the selected cache-line is present in corresponding higher level caches, invalidating the one or more copies in corresponding lower level caches to maintain an inclusive policy;

when no copies of the selected cache-line is 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 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-setting the corresponding presence bit in the lower level cache to the first value.

5. The method of claim 4, further comprising:

when a processor core initiates 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 caches and a lower adjacent level having one or more level 2 caches;

the level 1 cache dedicated to one processor core or shared by multiple cores;

a cache controller;

a logic which when executed on the processor provides the functions of;

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) the presence bits and (b) the less recently used (LRU) bits;

determining whether a copy of the cache-line selected for eviction is present in a higher level cache;

when the copy of the cache-line selected for eviction is present in the higher level cache, invalidating the copy of the cache-line selected for eviction; and

updating the pseudo-LRU bits.

7. The data processing system of claim 6, wherein said functions for selecting further comprises functions for:

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) when the value of the presence bits is set to a first value, receiving an indication that a copy of the cache-line is not present in a corresponding higher level cache;

(c) when the value of the presence bits is 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;

when the least recently used cache-line does not have 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, 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

when the least recently used cache-line has a corresponding presence bit set to the second value and one or more elements of the LRU group does not have 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.

8. The data processing system of claim 6, wherein said functions for updating further comprises function for:

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

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

replacing the evicted cache line with a new cache line;

switching the 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, maintaining a same set of values of the LRU bits.

9. The data processing system of claim 6, wherein said functions for invalidating further comprises functions for:

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

when the one or more copies of the selected cache-line is present in corresponding higher level caches, invalidating the one or more copies in corresponding lower level caches to maintain an inclusive policy;

when no copies of the selected cache-line is 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 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-setting the corresponding presence bit in the lower level cache to the first value.

10. The data processing system of claim 9, further comprising functions for:

when a processor core initiates 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.

11. 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 executes to perform the following functions;

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) the presence bits and (b) the less recently used (LRU) bits;

determining whether a copy of the cache-line selected for eviction is present in a higher level cache;

when the copy of the cache-line selected for eviction is present in the higher level cache, invalidating the copy of the cache-line selected for eviction; and

updating the pseudo-LRU bits.

12. The processor chip of claim 11, wherein said functions for selecting further comprises functions for:

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) when the value of the presence bits is set to a first value, receiving an indication that a copy of the cache-line is not present in a corresponding higher level cache;

(c) when the value of the presence bits is 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;

when the least recently used cache-line does not have 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, 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

when the least recently used cache-line has a corresponding presence bit set to the second value and one or more elements of the LRU group does not have 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.

13. The processor chip of claim 11, wherein said functions for updating further comprises functions for:

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

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

replacing the evicted cache line with a new cache line;

switching the 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, maintaining a same set of values of the LRU bits.

14. The processor chip of claim 11, wherein said functions for invalidating further comprises functions for:

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

when the one or more copies of the selected cache-line is present in corresponding higher level caches, invalidating the one or more copies in corresponding lower level caches to maintain an inclusive policy;

when no copies of the selected cache-line is 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 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-setting the corresponding presence bit in the lower level cache to the first value.

15. The processor chip of claim 14, further comprising functions for:

when a processor core initiates 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.