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

• US 9,176,879 B2
• Filed: 07/19/2013
• Issued: 11/03/2015
• 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:
  US13/946,327
• Publication Number:
  US 20150026404A1
• Time in Patent Office: 837 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:

selecting for eviction, from a cache memory that stores one or more cache lines, a least recently used cache line of a group of invalid cache lines, wherein each cache line stores a prefetch bit that indicates whether the cache line was generated in response to a cache memory prefetch operation;

in response to a determination that no cache lines are invalid, selecting for eviction from the 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 a higher level cache memory;

in response to a determination that no cache lines are invalid, and in response to a determination that all cache lines of the group of cache lines are also stored within the higher level cache memory, selecting for eviction from the cache memory a least recently used cache line of the one or more cache lines stored in the cache memory.

2. The method of claim 1, further comprising replaying a memory request in response to a determination that there are no least recently used cache lines available for eviction.

3. The method of claim 1, further comprising allocating a cached line within a least recently used priority scheme including priority positions zero through seven, wherein the lowest least recently used priority is assigned to positions zero and one, and allocating the lowest least recently used priority to a cache line associated with a non-temporal request, wherein a lower position may be selected for eviction before a higher position.

4. The method of claim 3, further comprising allocating a mid-level least recently used priority to a cache line associated with a cache memory prefetch request, wherein the mid-level least recently used priority is assigned to positions zero through three.

5. The method of claim 1, wherein each cache line stores a trip bit that is indicative of a number of times the corresponding cache line has been stored in the higher level cache memory and subsequently stored in the cache memory.

6. The method of claim 1, wherein each cache line stores a temporal bit that indicates whether the cache line was generated in response to a temporal memory request.

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 cache lines retrieved from the system memory, wherein each cache line stores a trip bit that is indicative of a number of times 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;

select for eviction, from the level two cache memory, a least recently used cache line of a group of invalid cache lines;

in response 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;

in response to a determination that no cache lines are invalid, and in response to a determination that all cache lines of the 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.

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

9. The integrated circuit of claim 7, wherein the control unit is further configured to allocate a cached line within a least recently used priority scheme including priority positions zero through seven, wherein position zero may be selected for eviction before a higher numbered position, and to allocate position zero through position one to a cache line associated with a non-temporal request.

10. The integrated circuit of claim 9, wherein the control unit is further configured to allocate a cache line associated with a level two cache memory prefetch request to positions zero through three.

11. The integrated circuit of claim 9, wherein the control unit is configured to promote a cache line to a higher position in response to a hit in the level two cache memory dependent upon whether a related memory request corresponds to a non-temporal request, a prefetch request, or a temporal request.

12. The integrated circuit of claim 7, wherein each cache line stores a prefetch bit that indicates whether or not the cache line was generated in response to a level two cache memory prefetch operation.

13. The integrated circuit of claim 7, wherein each cache line stores a temporal bit that indicates whether the cache line was generated in response to a temporal memory request.

14. A mobile device comprising:

a system memory configured to store instructions and data;

a processor unit coupled to the system memory and configured to execute the instructions, 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 cache lines retrieved from the system memory, wherein each cache line stores a prefetch bit that indicates whether or not the cache line was generated in response to a level two cache memory prefetch operation;

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

select for eviction, from the level two cache memory, a least recently used cache line of a group of invalid cache lines;

in response 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;

in response to a determination that no cache lines are invalid, and in response to a determination that all cache lines of the 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.

15. The mobile device of claim 14, wherein the control unit is further configured to allocate a cached line within a least recently used priority scheme including priority positions zero through seven, wherein position zero may be selected for eviction before a higher numbered position, and to allocate position zero through position one to a cache line associated with a non-temporal request.

16. The mobile device of claim 15, wherein the control unit is further configured to allocate a cache line associated with a level two cache memory prefetch request to positions zero through three.

17. The mobile device of claim 14, wherein each cache line stores a trip bit that is indicative of a number of times the corresponding cache line has been stored in the level one cache memory and subsequently stored in the level two cache memory.