Least recently used mechanism for cache line eviction from a cache memory

• US 9,563,575 B2
• Filed: 11/02/2015
• Issued: 02/07/2017
• Est. Priority Date: 07/19/2013
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Lilly, Brian P., Williams, Gerard R. III, Sadoughi-Yarandi, Mahnaz, Subramonium, Perumal R., Kannan, Hari S., Jain, Prashant
• Primary Examiner(s): NGUYEN, THAN VINH
• Application Number:
  US14/929,645
• Publication Number:
  US 20160055099A1
• Time in Patent Office: 463 Days
• Field of Search: 711/122, 711/136
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 12/127 using additional replacement algorithms
• CPC Class Codes: G06F 2212/1021 Hit rate improvement

Abstract

A mechanism for evicting a cache line from a cache memory includes first selecting for eviction a least recently used cache line of a group of invalid cache lines. If all cache lines are valid, selecting for eviction a least recently used cache line of a group of cache lines in which no cache line of the group of cache lines is also stored within a higher level cache memory such as the L1 cache, for example. Lastly, if all cache lines are valid and there are no non-inclusive cache lines, selecting for eviction the least recently used cache line stored in the cache memory.

Claims

1. A method comprising:

determining, in a cache memory that stores a plurality of cache lines, that a first eviction is to be performed from the cache memory;

identifying a first group of cache lines that are selectable for the first eviction;

identifying one or more invalid cache lines in the first group;

selecting a least recently used cache line from the one or more invalid cache lines for the first eviction;

determining that a second eviction is to be performed from the cache memory;

identifying a second group of cache lines that are selectable for the second eviction;

determining that none of the cache lines in the second group are invalid;

identifying one or more second cache lines in the second group that are not also stored in a higher level cache memory;

selecting the least recently used cache line of the one or more second cache lines for the second eviction;

determining that a third eviction is to be performed from the cache memory;

identifying a third group of cache lines that are selectable for the third eviction;

determining that none of the cache lines in the third group are invalid;

determining that the cache lines in the third group are also stored in the higher level cache memory;

selecting the least recently used cache line of the third group for the third eviction;

allocating a cache line within a least recently used hierarchy having a plurality of positions beginning with a position zero, wherein a cache line designated as being in position zero of the least recently used hierarchy is the least recently used cache line, and wherein cache lines in lower numbered positions of the least recently used hierarchy are selected for eviction before cache lines in higher numbered positions; and

storing a prefetch bit in each of the cache lines, the prefetch bit indicating whether the corresponding cache line was generated responsive to a cache memory prefetch operation, and wherein the method further comprises allocating a cache line associated with a memory prefetch request to one of positions zero through three of the least recently used hierarchy.

2. The method as recited in claim 1, further comprising replaying a memory request if there are no least recently used cache lines available for eviction.

3. The method as recited in claim 1, wherein the cache memory is a level two cache, and wherein the method comprises storing a trip bit in each of the cache lines, wherein the trip bit, when set, indicates multiple instances of the corresponding cache line being stored in a level one cache and subsequently stored in the level two cache, and wherein the method further comprises allocating a cache line having its respective trip bit set to one of positions zero through five of the least recently used hierarchy.

4. The method as recited in claim 1, further comprising storing a temporal bit in each of the cache lines, wherein the temporal bit indicates that its corresponding cache line was stored in the cache as a result of a temporal memory request, and wherein the method further comprises allocating a cache line that does not have its temporal bit set to one of positions zero or one in the least recently used hierarchy.

5. The method as recited in claim 1, further comprising allocating a given cache line to any position in the least recently used hierarchy if each of the following are true:

the given cache line is not associated with a temporal memory request;

the given cache line was not generated responsive to a prefetch operation; and

the given cache line has not been subject to multiple instances of being stored in a higher level cache and subsequently stored in the cache memory.

6. The method as recited in claim 1, further comprising promoting a given cache line in the least recently used hierarchy responsive to a hit on a cache request for the given cache line.

7. An integrated circuit comprising:

a processor unit coupled to a system memory and configured to execute instructions from the system memory, wherein the processor unit includes one or more processor cores, each including a level one cache memory;

a level two cache memory coupled to the processor unit and configured to store configured to store cache lines retrieved from the system memory, wherein each cache line includes a trip bit that, when set, indicates multiple instances of the corresponding cache line has been stored in the level one cache memory and subsequently stored in the level two cache memory;

wherein the level two cache memory includes a control unit configured to;

determine a hierarchy of least recently used cache lines, wherein a least recently used cache line is a lowest one in the hierarchy, wherein the hierarchy of least recently used cache lines includes a number of positions beginning with a position zero, wherein position zero is the least recently used cache line, wherein the control unit is configured to evict cache lines allocated to lower numbers in the hierarchy before evicting cache lines allocated to higher numbers in the hierarchy;

place cache lines having respective trip bits set lower in the hierarchy relative to cache lines not having their respective trip bit set during a time when cache lines are being inserted into the level two cache memory, wherein each cache line includes a temporal bit indicating whether that cache line was stored in the cache as a result of a temporal memory request, and wherein the control unit is configured to allocate cache lines not having their respective temporal bit set to one of position zero or position one of the least recently used hierarchy; and

select for eviction a least recently used cache line from the hierarchy of least recently used cache lines.

8. The integrated circuit as recited in claim 7, wherein the control unit is further configured to select for eviction, from the level two cache memory, a least recently used cache line of a group of invalid cache lines.

9. The integrated circuit as recited in claim 7, wherein the control unit is further configured to, responsive to a determination that no cache lines are invalid, select for eviction from the level two cache memory a least recently used cache line of a group of cache lines in which no cache line of the group of cache lines is also stored within the level one cache memory.

10. The integrated circuit as recited in claim 7, wherein the control unit is further configured to, responsive to a determination that no cache lines are invalid, and in response to a determination that all cache lines of a group of cache lines are also stored within the level one cache memory, select for eviction from the level two cache memory a least recently used cache line of the one or more cache lines stored in the level two cache memory.

11. The integrated circuit as recited in claim 7, wherein the control unit is configured to replay a memory request that misses in the level two cache memory responsive to a determination that there are no unlocked least recently used cache lines available for eviction.

12. The integrated circuit as recited in claim 7, wherein each cache line includes a prefetch bit indicating whether that cache line was generated responsive to a cache memory prefetch operation, and wherein the control unit is configured to allocate a cache line having its prefetch bit set to one of positions zero through three of the least recently used hierarchy.

13. The integrated circuit as recited in claim 7, wherein the control unit is configured to allocate a cache line having its trip bit set to one of positions zero through five in the least recently used hierarchy.

14. The integrated circuit as recited in claim 7, wherein the control unit is configured to allocate a given cache line into any position of the least recently used hierarchy if each of the following are true:

the given cache line is not associated with a temporal memory request;

the given cache line was not generated responsive to a prefetch operation; and

the given cache line has not been subject to multiple instances of being stored in a higher level cache and subsequently stored in the cache memory.

15. The integrated circuit as recited in claim 7, wherein the control unit is configured to promote a given cache line in the least recently used hierarchy responsive to a hit on a cache request for the given cache line.

16. The integrated circuit as recited in claim 15, wherein the control unit is configured to:

promote the given cache line from position zero to position one in the least recently used hierarchy responsive to a hit on a cache request for the given cache line if the given cache line is not associated with a temporal memory request;

promote the given cache line to position three from a lower position in the least recently used hierarchy responsive to a hit on a cache request for the given cache line if the given cache line is associated with a temporal memory request and is also associated with a prefetch operation; and

promote the given cache line to position three from a lower position in the least recently used hierarchy responsive to a hit on a cache request for the given cache line if the given cache line is associated with a temporal memory request but is not associated with a prefetch operation.