Scaled set dueling for cache replacement policies

Patent metadata

Field	Value
Publication number	US-10430349-B2
Application number	US-201615180995-A
Country	US
Kind code	B2
Filing date	Jun 13, 2016
Priority date	Jun 13, 2016
Publication date	Oct 1, 2019
Grant date	Oct 1, 2019

Abstract

A processing system includes a cache that includes a cache lines that are partitioned into a first subset of the cache lines and a second subsets of the cache lines. The processing system also includes one or more counters that are associated with the second subsets of the cache lines. The processing system further includes a processor configured to modify the one or more counters in response to a cache hit or a cache miss associated with the second subsets. The one or more counters are modified by an amount determined by one or more characteristics of a memory access request that generated the cache hit or the cache miss.

First claim

What is claimed is:

1. An apparatus comprising:
a cache including cache lines that are partitioned into a first subset of the cache lines and second subsets of the cache lines;
at least one counter associated with the second subsets of the cache lines; and
a processor configured to modify the at least one counter in response to a cache hit associated with the second subsets, wherein the at least one counter is modified by an amount based on a degree of speculation of a memory access request that generated the cache hit, the degree of speculation based on at least one of: whether the memory access request is directed to an instruction cache or a data cache; and whether the cache hit is a result of a page table walk.

2. The apparatus of claim 1 , wherein the processor further is configured to increment the at least one counter in response to a cache hit to a first one of the second subsets and decrement the at least one counter in response to a cache hit to a second one of the second subsets.

3. The apparatus of claim 2 , wherein the processor is further configured to:
increment the at least one counter by an amount that is determined based on a degree of speculation of the memory access request that generated the cache hit to the first one of the second subsets, and
decrement the at least one counter by an amount that is determined based on a degree of speculation of the memory access request that generated the cache hit to the second one of the second subsets.

4. The apparatus of claim 1 , wherein the processor is further configured to:
decrement the at least one counter in response to a cache miss associated with a first one of the second subsets; and
increment the at least one counter in response to a cache miss to a second one of the second subsets.

5. The apparatus of claim 4 , wherein the processor is further configured to:
decrement the at least one counter by an amount that is determined based on a latency associated with the cache miss associated with the first one of the second subsets; and
increment the at least one counter by an amount that is determined based on a latency associated with the cache miss associated with the second one of the second subsets.

6. The apparatus of claim 5 , wherein the processor is further configured to:
decrement the at least one counter by the same amount for all cache misses associated with the first one of the second subsets in response to detecting bandwidth limited operation based on feedback indicating bandwidth consumption, and
increment the at least one counter by the same amount for all cache misses associated with the second one of the second subsets in response to detecting the bandwidth limited operation.

7. The apparatus of claim 1 , wherein:
the second subsets use a corresponding plurality of cache replacement policies; and
the processor is further configured to:
select one of the plurality of cache replacement policies based on at least one value of the at least one counter; and
configure the first subset to use the selected one of the plurality of cache replacement policies.

8. A method, comprising:
partitioning cache lines into a first subset of the cache lines and second subsets of the cache lines;
detecting a cache hit associated with the second subsets; and
modifying at least one counter associated with the second subsets of the cache lines in response to the cache hit, wherein the at least one counter is modified by an amount based on a degree of speculation of a memory access request that generated the cache hit, the degree of speculation based on at least one of: whether the memory access request is directed to an instruction cache or a data cache; and whether the cache hit is a result of a page table walk.

9. The method of claim 8 , wherein modifying the at least one counter comprises:
incrementing the at least one counter in response to a cache hit to a first one of the second subsets, and
decrementing the at least one counter in response to a cache hit to a second one of the second subsets.

10. The method of claim 9 , wherein:
incrementing the at least one counter comprises incrementing the at least one counter by an amount that is determined based on a degree of speculation of the memory access request that generated the cache hit to the first one of the second subsets; and
decrementing the at least one counter comprises decrementing the at least one counter by an amount that is determined based on a degree of speculation of the memory access request that generated the cache hit to the second one of the second subsets.

11. The method of claim 8 , wherein modifying the at least one counter further comprises:
decrementing the at least one counter in response to a cache miss associated with a first one of the second subsets; and
incrementing the at least one counter in response to a cache miss to a second one of the second subsets.

12. The method of claim 11 , wherein:
decrementing the at least one counter comprises decrementing the at least one counter by an amount that is determined based on a latency associated with the cache miss associated with the first one of the second subsets; and
incrementing the at least one counter comprises incrementing the at least one counter by an amount that is determined based on a latency associated with the cache miss associated with the second one of the second subsets.

13. The method of claim 11 , wherein:
decrementing the at least one counter comprises decrementing the at least one counter by the same amount for all cache misses associated with the first one of the second subsets in response to detecting bandwidth limited operation based on feedback indicating bandwidth consumption; and
incrementing the at least one counter comprises incrementing the at least one counter by the same amount for all cache misses associated with the second one of the second subsets in response to detecting the bandwidth limited operation.

14. The method of claim 8 , wherein the second subsets use a corresponding plurality of cache replacement policies, the method further comprising:
selecting one of the plurality of cache replacement policies based on at least one value of the at least one counter; and
configuring the first subset to use the selected one of the plurality of cache replacement policies.

15. An apparatus, comprising:
a cache including cache lines that are partitioned into a first subset and second subsets for storing information from a memory;
at least one counter associated with the second subsets; and
a processor configured to:
selectively enable or disable set dueling to determine a cache replacement policy for the cache based on feedback indicating whether operation of at least one of the memory or the cache is bandwidth limited, wherein the set dueling chooses between first and second cache replacement policies implemented by the first and second subsets, respectively, on the basis of the at least one counter; and
modify the at least one counter in response to a cache hit associated with the second subsets, wherein the at least one counter is modified by an amount based on a degree of speculation of a memory access request that generated the cache hit, the degree of speculation based on at least one of: whether the memory access request is directed to an instruction cache or a data cache; and whether the cache hit is a result of a page table walk.

16. The apparatus of claim 15 , wherein:
the processor is further configured to modify the at least one counter in response to at least one of a cache hit or a cache miss associated with the seco

Assignees

• Advanced Micro Devices Inc

Inventors

• Moyer Paul James

Classifications

• G06F12/0864

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

• G06F12/0811 Primary

  with multilevel cache hierarchies · CPC title

• G06F2212/601

  Reconfiguration of cache memory · CPC title

• G06F12/126

  with special data handling, e.g. priority of data or instructions, handling errors or pinning · CPC title

• G06F12/0866

  for peripheral storage systems, e.g. disk cache · CPC title