US 9,176,879 B2Granted

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

AssigneeApple Inc.

InventorsBrian P. Lilly, Gerard R. Williams, III, Mahnaz Sadoughi-Yarandi, Perumal R. Subramonium, Hari S. Kannan, Prashant Jain

Life of this patent

Estimating the term…

patentgrep

Loading patent…

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.

Claims17

Dependent claims

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.

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.

3 more elements

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.

4 more elements

Dependencies are inferred from the claim text.

Facts

Application: 13/946,327Filed 19 Jul 2013
Published: US 2015/0026404 A122 Jan 2015
Granted: 3 Nov 2015
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

G06F 12/123
Using replacement algorithms: with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
G06F 12/0862
Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches: with prefetch
G06F 12/0897
Caches characterised by their organisation or structure: with two or more cache hierarchy levels
G06F 12/127
With special data handling, e.g. priority of data or instructions, handling errors or pinning: using additional replacement algorithms