SELECTIVE VICTIMIZATION IN A MULTI-LEVEL CACHE HIERARCHY

• US 20150149721A1
• Filed: 11/25/2013
• Published: 05/28/2015
• Est. Priority Date: 11/25/2013
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Kannan, Hari S., Lilly, Brian P., Subramoniam, Perumal R.
• Granted Patent: US 9,298,620 B2
• Time in Patent Office: Days
• US Class Current: 711/122
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 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/0888 using selective caching, e.g. bypass
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Systems, methods, and apparatuses for implementing selective victimization to reduce power and utilized bandwidth in a multi-level cache hierarchy. Each set of an upper-level cache includes a counter that keeps track of the number of times the set was accessed. These counters are periodically decremented by another counter that tracks the total number of accesses to the cache. If a given set counter is below a certain threshold value, clean victims are dropped from this given set instead of being sent to a lower-level cache. Also, a separate counter is used to track the total number of outstanding requests for the cache as a proxy for bus-bandwidth in order to gauge the total amount of traffic in the system. The cache will implement selective victimization whenever there is a large amount of traffic in the system.

Claims

1. A system comprising:

a first cache, wherein the first cache is set associative with a plurality of sets; and

a second cache, wherein the second cache is at a lower level of a cache hierarchy than the first cache;

wherein the first cache is configured to;

maintain a counter for each set of the plurality of sets, wherein each counter tracks a number of accesses made to a corresponding set;

responsive to evicting a clean victim from a first set;

drop the clean victim responsive to detecting a first counter corresponding to the first set is less than a first threshold; and

write back the clean victim to the second cache responsive to detecting the first counter is greater than the first threshold.

2. The system as recited in claim 1, wherein the first cache is further configured to decrement each counter by a predetermined amount responsive to determining a number of total accesses made to the first cache has exceeded a second threshold.

3. The system as recited in claim 2, wherein the first cache is further configured to maintain a counter for tracking the number of total accesses made to the first cache.

4. The system as recited in claim 1, wherein the first cache is further configured to:

maintain an outstanding request counter for tracking the number of outstanding requests of the first cache; and

write back the clean victim to the second cache responsive to determining the outstanding request counter is less than a second threshold.

5. The system as recited in claim 4, wherein the first cache is further configured to drop the clean victim responsive to determining the outstanding request counter is greater than the second threshold and the first counter corresponding to the first set is less than the first threshold.

6. The system as recited in claim 1, wherein the first cache is a level two (L2) cache, and wherein the second cache is a level three (L3) cache.

7. The system as recited in claim 1, wherein the first cache is a level one (L1) cache, and wherein the second cache is a level two (L2) cache.

8. A cache comprising:

a cache memory arranged as a set associative memory having a plurality of sets and a plurality of ways; and

a cache control unit coupled to the cache memory, wherein the cache control unit is configured to;

maintain a first counter, wherein the first counter tracks a number of accesses made to a first set;

responsive to evicting a first clean victim from the first set;

drop the first clean victim responsive to detecting the first counter is less than a first threshold; and

write back the first clean victim to a lower-level cache responsive to detecting the first counter is greater than the first threshold.

9. The cache as recited in claim 8, wherein the cache control unit is further configured to:

maintain a second counter, wherein the second counter tracks a number of accesses made to a second set;

responsive to evicting a second clean victim from the second set;

drop the second clean victim responsive to detecting the second counter is less than the first threshold; and

write back the second clean victim to the lower-level cache responsive to detecting the second counter is greater than the first threshold.

10. The cache as recited in claim 9, wherein the cache control unit is further configured to decrement the first and second counters by a predetermined amount responsive to determining a number of accesses made to the cache has exceeded a second threshold.

11. The cache as recited in claim 8, wherein the cache control unit is further configured to:

maintain a second counter to track a number of outstanding requests of the cache;

check the value of the second counter prior to determining whether to drop or write back the first clean victim; and

write back the second clean victim to the lower-level cache responsive to detecting the second counter is less than a second threshold.

12. The cache as recited in claim 11, wherein responsive to detecting the second counter is greater than the second threshold, the cache control unit is configured to:

drop the first clean victim responsive to detecting the first counter is less than the first threshold; and

write back the first clean victim to the lower-level cache responsive to detecting the first counter is greater than the first threshold.

13. The cache as recited in claim 8, wherein the lower-level cache is a level three (L3) cache.

14. The cache as recited in claim 8, wherein the lower-level cache is a memory controller cache.

15. A method comprising:

determining whether a thrash condition is present for a first set of a set associative cache responsive to evicting a first clean victim from the first set;

dropping the first clean victim responsive to determining the thrash condition is present for the first set; and

writing back the first clean victim to a lower-level cache responsive to determining the thrash condition is not present for the first set.

16. The method as recited in claim 15, wherein determining whether a thrash condition is present for the first set comprises determining whether a first access counter corresponding to the first set is greater than a first threshold.

17. The method as recited in claim 16, wherein the first access counter tracks a number of accesses made to the first set.

18. The method as recited in claim 17, wherein a second counter tracks a number of accesses made to the entire set associative cache, wherein the method further comprising decrementing the first access counter by a predetermined amount responsive to detecting the second counter has exceeded a second threshold.

19. The method as recited in claim 18, wherein a third counter tracks a number of outstanding requests of the set associative cache, wherein the method further comprising writing back the first clean victim to the lower-level cache responsive to determining the third counter is less than a third threshold.

20. The method as recited in claim 15, further comprising:

determining whether a thrash condition is present for a second set of the set associative cache responsive to evicting a second clean victim from the second set;

dropping the second clean victim responsive to determining the thrash condition is present for the second set; and

writing back the second clean victim to the lower-level cache responsive to determining the thrash condition is not present for the second set.