Cache replacement policy that considers memory access type

Patent metadata

Field	Value
Publication number	US-9652398-B2
Application number	US-201414890904-A
Country	US
Kind code	B2
Filing date	Dec 14, 2014
Priority date	Dec 14, 2014
Publication date	May 16, 2017
Grant date	May 16, 2017

Abstract

An associative cache memory, comprising: an array of storage elements arranged as M sets by N ways; an allocation unit allocates the storage elements in response to memory accesses that miss in the cache memory. Each memory access selects a set. Each memory access has an associated memory access type (MAT) of a plurality of predetermined MATs. Each valid storage element has an associated MAT; a mapping that includes, for each MAT, a MAT priority. In response to a memory access that misses in the array, the allocation unit: determines a most eligible way and a second most eligible way of the selected set for replacement based on a replacement policy; and replaces the second most eligible way rather than the most eligible way when the MAT priority of the most eligible way is greater than the MAT priority of the second most eligible way.

First claim

The invention claimed is:

1. An associative cache memory, comprising:
an array of storage elements arranged as M sets by N ways;
an allocation unit that allocates the storage elements of the array in response to memory accesses that miss in the cache memory, wherein each of the memory accesses selects a set of the M sets;
wherein each of the memory accesses has an associated memory access type (MAT) of a plurality of predetermined MATs, wherein the MAT is received by the cache memory;
wherein each valid storage element of the array has an associated MAT of the plurality of predetermined MATs;
a mapping that includes, for each MAT of the plurality of predetermined MATs, a MAT priority;
wherein in response to a memory access that misses in the array, the allocation unit:
determines a most eligible way and a second most eligible way of the selected set for replacement based on a replacement policy; and
replaces the second most eligible way rather than the most eligible way when the MAT priority of the most eligible way is greater than the MAT priority of the second most eligible way.

2. The associative cache memory of claim 1 , wherein the mapping maps each MAT of the plurality of MATs into one of a plurality of mutually exclusive MAT groups, wherein the mapping further includes a priority for each of the MAT groups, wherein the MAT priority of each MAT is the priority of its MAT group.

3. The associative cache memory of claim 1 , wherein the plurality of predetermined MATs includes at least three from the following list:
a memory access generated by a hardware prefetcher of the processor;
a memory access generated by a floating point instruction;
a memory access generated by a fused microinstruction;
a memory access generated by a media instruction;
a memory access generated by an instruction that modifies a memory address;
a memory access generated by a software prefetch instruction;
a memory access that loads an architectural descriptor;
a memory access generated by an instruction that specifies non-temporal data;
a memory access generated by an instruction that performs no alignment checks;
a memory access generated by a supervisor privilege level instruction;
a memory access generated by a zero extend instruction;
a memory access generated by a masked move instruction;
a memory access generated by a stack push instruction; and
a memory access generated by a hardware tablewalk engine of the processor.

4. A method for operating an associative cache memory having an array of storage elements arranged as M sets by N ways and an allocation unit that allocates the storage elements of the array in response to memory accesses that miss in the cache memory, wherein each of the memory accesses selects a set of the M sets, wherein each of the memory accesses has an associated memory access type (MAT) of a plurality of predetermined MATs, wherein the MAT is received by the cache memory, the method comprising:
storing, for each valid storage element of the array, an associated MAT of the plurality of predetermined MATs;
storing a mapping that includes, for each MAT of the plurality of predetermined MATs, a MAT priority;
in response to a memory access that misses in the array:
determining a most eligible way and a second most eligible way of the selected set for replacement based on a replacement policy; and
replacing the second most eligible way rather than the most eligible way when the MAT priority of the most eligible way is greater than the MAT priority of the second most eligible way.

5. The method of claim 4 , further comprising:
updating the mapping during operation of the cache memory.

6. The method of claim 5 , further comprising:
determining that a program is running on the processor; and
said updating the mapping in response to said determining that the program is running on the processor.

7. The method of claim 6 , wherein the mapping is determined by offline analysis of the program.

8. The method of claim 7 , wherein, for each MAT of the plurality of predetermined MATs, the priority included in the mapping for the MAT is based on an average cache line lifetime of cache lines allocated in response to memory accesses having the MAT determined by the offline analysis.

9. The method of claim 7 , wherein, for each MAT of the plurality of predetermined MATs, the priority included in the mapping for the MAT is based on an average hit rate of cache lines allocated in response to memory accesses having the MAT determined by the offline analysis.

10. An associative cache memory, comprising:
an array of storage elements arranged as M sets by N ways;
an allocation unit that allocates the storage elements of the array in response to memory accesses that miss in the cache memory, wherein each of the memory accesses selects a set of the M sets;
for each set of the N sets, associated replacement bits used by a replacement policy of the allocation unit to indicate how recently the ways of the selected set have been used relative to one another;
wherein each of the memory accesses has an associated memory access type (MAT) of a plurality of predetermined MATs, wherein the MAT is received by the cache memory;
a mapping that includes, for each MAT of the plurality of predetermined MATs, a MAT priority;
wherein in response to a memory access that misses in the array, the allocation unit:
allocates into a replacement way of the selected set; and
inserts the replacement way into a position other than at the most recently used position of the replacement bits when the MAT priority of the memory access is lower than a threshold.

11. The associative cache memory of claim 10 , wherein the mapping maps each MAT of the plurality of MATs into one of a plurality of mutually exclusive MAT groups, wherein the mapping further includes a priority for each of the MAT groups, wherein the MAT priority of each MAT is the priority of its MAT group.

12. The associative cache memory of claim 11 , wherein the plurality of predetermined MATs includes at least three from the following list:
a memory access generated by a hardware prefetcher of the processor;
a memory access generated by a floating point instruction;
a memory access generated by a fused microinstruction;
a memory access generated by a media instruction;
a memory access generated by an instruction that modifies a memory address;
a memory access generated by a software prefetch instruction;
a memory access that loads an architectural descriptor;
a memory access generated by an instruction that specifies non-temporal data;
a memory access generated by an instruction that performs no alignment checks;
a memory access generated by a supervisor privilege level instruction;
a memory access generated by a zero extend instruction;
a memory access generated by a masked move instruction;
a memory access generated by a stack push instruction; and
a memory access generated by a hardware tablewalk engine of the processor.

13. A method for operating an associative cache memory having an array of storage elements arranged as M sets by N ways and an allocation unit that allocates the storage elements of the array in response to memory accesses that miss in the cache memory, wherein each of the memory accesses selects a set of the M sets, wherein each of the memory accesses has an associated memory access type (MAT) of a plurality of predetermined MATs, wherein the MAT is received by the cache memory, wherein the cache memory also includes for each set of the N sets, associated replacement bits used by a replacement policy of the allocation unit to indicate how recently th

Assignees

• Via Alliance Semiconductor Co Ltd

Inventors

• Hooker Rodney E
• Reed Douglas R
• Greer John Michael
• Eddy Colin
• Parks Terry

Classifications

• G06F8/4442

  Reducing the number of cache misses; Data prefetching (cache prefetching G06F12/0862) · CPC title

• G06F2212/1021

  Hit rate improvement · CPC title

• G06F2212/604

  Details relating to cache allocation · CPC title

• G06F12/126

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

• G06F12/123

  with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list · CPC title