System and method for cache replacement using conservative set dueling

Patent metadata

Field	Value
Publication number	US-10007620-B2
Application number	US-201615282841-A
Country	US
Kind code	B2
Filing date	Sep 30, 2016
Priority date	Sep 30, 2016
Publication date	Jun 26, 2018
Grant date	Jun 26, 2018

Abstract

A processor includes a set associative cache and a cache controller. The cache controller makes an initial association between first and second groups of sampled sets in the cache and first and second cache replacement policies. Follower sets in the cache are initially associated with the more conservative of the two policies. Following cache line insertions in a first epoch, the associations between the groups of sampled sets and cache replacement policies are swapped for the next epoch. If the less conservative policy outperforms the more conservative policy during two consecutive epochs, the follower sets are associated with the less conservative policy for the next epoch. Subsequently, if the more conservative policy outperforms the less conservative policy during any epoch, the follower sets are again associated with the more conservative policy. Performance may be measured based the number of cache misses associated with each policy.

First claim

The invention claimed is:

1. A processor, comprising:
a set associative cache to store data in a plurality of cache lines, the cache lines being organized in groups of sets;
a cache controller including circuitry to:
associate a first cache replacement policy with a first group of sets;
associate a second cache replacement policy with a second group of sets;
associate the first cache replacement policy with a third group of sets, the first, second and third groups of sets in the set associative cache being non-overlapping;
insert, during execution of instructions by the processor, a first plurality of cache lines into the set associative cache, including circuitry to:
insert each cache line in the first group of sets and in the third group of sets in accordance with the first cache replacement policy;
insert each cache line in the second group of sets in accordance with the second cache replacement policy;

detect a condition to indicate that the associations between the first and second groups of sets and the first and second cache replacement policies are to be swapped;
in response to detection of the condition:
associate the first cache replacement policy with the second group of sets;
associate the second cache replacement policy with the first group of sets.

2. The processor of claim 1 , wherein:
the cache controller further includes circuitry to:
determine that the first cache replacement policy resulted in better performance than the second cache replacement policy during insertion of the first plurality of cache lines;
maintain, responsive to the determination that the first cache replacement policy resulted in better performance than the second cache replacement policy during insertion of the first plurality of cache lines, the association of the first cache replacement policy with the third group of sets;
insert a second plurality of cache lines into the set associative cache, including circuitry to:
insert each cache line in the second group of sets in accordance with the first cache replacement policy;
insert each cache line in the first group of sets in accordance with the second cache replacement policy;
insert each cache line in the third group of sets in accordance with the first cache replacement policy.

3. The processor of claim 1 , wherein:
the cache controller further includes circuitry to:
determine that the second cache replacement policy resulted in better performance than the first cache replacement policy during insertion of the first plurality of cache lines;
associate, responsive to the determination that the second cache replacement policy resulted in better performance than the first cache replacement policy during insertion of the first plurality of cache lines, the second cache replacement policy with the third group of sets;
insert a second plurality of cache lines into the set associative cache, including circuitry to:
insert each cache line in the second group of sets in accordance with the first cache replacement policy;
insert each cache line in the first group of sets in accordance with the second cache replacement policy;
insert each cache line in the third group of sets in accordance with the second cache replacement policy.

4. The processor of claim 1 , wherein:
the cache controller further includes circuitry to:
determine, prior to insertion of the first plurality of cache lines, that the second cache replacement policy resulted in better performance than the first cache replacement policy during insertion of a third plurality of cache lines;
determine that the second cache replacement policy resulted in better performance than the first cache replacement policy during insertion of the first plurality of cache lines;
associate, responsive to the determination that the second cache replacement policy resulted in better performance than the first cache replacement policy during insertion of the third plurality of cache lines and during insertion of the first plurality of cache lines, the second cache replacement policy with the third group of sets;
insert a second plurality of cache lines into the set associative cache, including circuitry to:
insert each cache line in the second group of sets in accordance with the first cache replacement policy;
insert each cache line in the first group of sets in accordance with the second cache replacement policy;
insert each cache line in the third group of sets in accordance with the second cache replacement policy.

5. The processor of claim 1 , wherein:
the cache controller further includes:
a counter;
circuitry to:
increment the counter responsive to a cache miss for a cache line in the second group of sets;
decrement the counter responsive to a cache miss for a cache line in the first group of sets;

the circuitry to detect a condition to indicate that the associations between the first and second groups of sets and the first and second cache replacement policies are to be swapped includes circuitry to:
determine that the value of the counter meets a predetermined threshold value to indicate that the associations between the first and second groups of sets and the first and second cache replacement policies are to be swapped.

6. The processor of claim 1 , wherein:
the circuitry to detect a condition to indicate that the associations between the first and second groups of sets and the first and second cache replacement policies are to be swapped includes circuitry to:
determine that a predetermined amount of time has passed since the current associations between the first and second groups of sets and the first and second cache replacement policies were made.

7. The processor of claim 1 , wherein:
the circuitry to associate the first cache replacement policy with a first group of sets in the set associative cache includes circuitry to:
randomly select one or more sets for inclusion in the first group of sets from among all sets in the set associative cache;

the circuitry to associate the second cache replacement policy with a second group of sets in the set associative cache includes circuitry to:
randomly select one or more sets for inclusion in the second group of sets from among sets not included in the first group of sets.

8. The processor of claim 1 , wherein:
the first cache replacement policy specifies that each cache line is to be inserted in a manner that delays its eviction from the set associative cache;
the second cache replacement policy specifies that that each cache line is to be inserted in a manner that makes it eligible for eviction from the set associative cache.

9. A method, comprising, in a processor:
associating a first cache replacement policy with a first group of sets in a set associative cache, the set associative cache storing data in a plurality of cache lines in groups of sets;
associating a second cache replacement policy with a second group of sets;
associating the first cache replacement policy with a third group of sets;
inserting, during execution of instructions by the processor, a first plurality of cache lines into the set associative cache, including:
inserting each cache line in the first group of sets and in the third group of sets in accordance with the first cache replacement policy;
inserting each cache line in the second group of sets in accordance with the second cache replacement policy;

detecting a condition indicating that the associations between the first and second groups of sets and the first and second cache replacement policies are to be swapped;
associating the first cache replacement policy with the second group of sets;
associating the second cache replacement policy with the first group of sets.

Assignees

• Intel Corp

Inventors

• Pugsley Seth H
• Wilkerson Christopher B
• Gramunt Roger
• Hall Jonathan C
• Jain Prabhat

Classifications

• G06F12/0864

  using pseudo-associative means, e.g. set-associative or hashing · CPC title

• G06F12/0811

  with multilevel cache hierarchies · CPC title

• G06F12/121 Primary

  using replacement algorithms · CPC title

• G06F12/0842

  for multiprocessing or multitasking · CPC title

• G06F12/084

  with a shared cache · CPC title