Placement policy for memory hierarchies

Patent metadata

Field	Value
Publication number	US-10019368-B2
Application number	US-201514702169-A
Country	US
Kind code	B2
Filing date	May 1, 2015
Priority date	May 29, 2014
Publication date	Jul 10, 2018
Grant date	Jul 10, 2018

Abstract

A placement policy enables the selective storage of cachelines in a multi-level cache hierarchy: Reuse behavior of a cacheline is tracked during execution of an application in both a first level cache memory and a second level cache memory. A cache placement policy for the cacheline is determined based on the tracked reuse behavior.

First claim

What is claimed is:

1. A method for selectively storing cachelines in a multi-level cache hierarchy comprising a plurality of cache memories, the method comprising:
tracking reuse behavior of at least one cacheline, during execution of an application, in both a first level cache memory and a second level cache memory;
the first level cache memory being smaller and faster than the second level cache memory; and determining a cache placement policy by tracking reuse behavior for the at least one cacheline in both the first level cache memory and the second level cache memory and determining the cache placement policy for both the first and the second level cache memories based on the reuse behavior,
wherein the cache placement policy includes selectively placing the at least one cacheline in both the first level cache memory and the second level cache memory,
wherein each cacheline is part of one of a plurality of datasets and further where the reuse behavior observed for the at least one cacheline is used to determine a cache placement policy for the plurality of cachelines being part of the same dataset as the at least one cacheline.

2. The method of claim 1 , wherein a data portion of cachelines stored in the first level cache memory is stored using SRAM technology.

3. The method of claim 1 , wherein the at least one cacheline is associated with the dataset based, at least in part, on a program counter value associated with an access to the at least one cacheline.

4. The method of claim 3 , wherein the program counter value is one of: (a) a program counter value of a load instruction which brought the at least one cacheline into one of the first level cache memory or the second level cache memory, (b) a program counter value of a load instruction which brought the at least one cacheline into either the first level cache memory or the second level cache memory, (c) a program counter value of an instruction which caused a translation look-aside buffer (TLB) fault, (d) a program counter value of an instruction which caused a cache location buffer (CLB) miss, and (e) a program counter value of an instruction that generated at least one of the cacheline requests that initiated a hardware prefetch stream to start.

5. The method of claim 1 , wherein the at least one cacheline is associated with the dataset based on information from one or more of: (a) a compiler, (b) a runtime system, and (c) a programmer.

6. The method of claim 1 , further comprising:
tracking reuse behavior for a plurality of cachelines, which are a subset of all of the cachelines in the first level and second level cache memories.

7. The method of claim 6 , wherein each cacheline stores a learning indicator identifying whether or not it belongs to the subset and indicating that the at least one cacheline's reuse behavior should be tracked.

8. The method of claim 6 , wherein a location table entry stores a learning indicator identifying whether or not its associated cachelines belong to the subset.

9. The method of claim 1 , wherein each cacheline in a cache level stores reuse information recording its reuse in that cache level since it was installed in that cache level, and wherein the cacheline's reuse in that cache level is recorded when the cacheline is replaced by recording the reuse information.

10. The method of claim 9 , wherein the reuse information is a counter of one or more bits that counts a number of reuses at that cache level and stops at the counter's maximum value.

11. The method of claim 9 , wherein the reuse at a cache level is assessed with respect to a dataset by aggregating the reuse information collected from several cachelines belonging to the dataset when the several cachelines are evicted from that cache level.

12. The method of claim 11 , where the aggregated reuse information is collected for a plurality of datasets with respect to a plurality of the cache levels using a reuse history table.

13. The method of claim 11 , where a cache placement policy for a dataset is determined based on the collective reuse behavior information from several cachelines replaced from several cache levels and belonging to the dataset.

14. The method of claim 11 , wherein when the reuse has been determined to be less than a predetermined reuse level at a cache level for a dataset identified at least in part by a program counter value of an instruction that generated at least one of the cacheline requests that initiated a hardware prefetch stream to start, then the instruction associated with that program counter value's ability to start new hardware prefetch streams is downgraded.

15. The method of claim 1 , wherein the reuse behavior is tracked using a reuse history table having a plurality of entries, each entry in the table having a dataset identifier identifying a dataset associated with that table entry, a plurality of reuse counters which count a number of cacheline reuses at both the first cache level and at the second cache level, and a plurality of unused counters which count a number of cachelines which are unused at both the first cache level and the second cache level.

16. The method of claim 1 , wherein the step of determining a cache placement policy for the at least one cacheline based on the tracked reuse behavior further comprises:
determining whether the at least one cacheline will be permitted to be installed in either the first level cache or the second level cache.

17. The method of claim 1 , wherein the plurality of cachelines is associated with the dataset based, at least in part, on call stack information associated with accesses to the at least one cacheline.

18. A computer processing system, comprising:
at least one processor core for executing an application;
a multi-level cache hierarchy comprising a plurality of cache memories at different cache levels; and
a mechanism configured to track reuse behavior of at least one cacheline, during execution of the application in both a first level cache memory and a second level cache memory; and determining a cache placement policy based on the tracked reuse behavior, wherein the cache placement policy includes selectively placing one copy of the at least one cacheline in each of the first level cache memory and the second level cache memory;
wherein each cacheline is part of one of a plurality of datasets and further where the reuse behavior observed for the at least one cacheline is used to determine a cache placement policy for the plurality of cachelines being part of the same dataset as the at least one cacheline.

19. The computer processing system of claim 18 , wherein the mechanism further comprises each cacheline in a cache level storing reuse information recording its reuse in that cache level since it was installed in that cache level, and wherein the cacheline's reuse in that cache level is recorded when the cacheline is replaced by recording the reuse information.

20. The computer processing system of claim 18 , wherein the mechanism further comprises:
a reuse history table having a plurality of entries, each entry in the table having a dataset identifier identifying a dataset associated with that table entry, a plurality of reuse counters which count a number of cacheline reuses at both the first cache level and at the second cache level, and a plurality of unused counters which count a number of cachelines which are unused at both the first cache level and the second cache level.

21. A method for selectively storing cachelines in a multi-level ca

Assignees

• Samsung Electronics Co Ltd

Inventors

• Hagersten Erik
• Sembrant Andreas
• Black-Schaffer David

Classifications

• G06F12/0888

  using selective caching, e.g. bypass · CPC title

• G06F2212/1016

  Performance improvement · CPC title

• G06F2212/6046

  Using a specific cache allocation policy other than replacement policy · CPC title

• G06F12/0862

  with prefetch · CPC title

• G06F12/0846

  Cache with multiple tag or data arrays being simultaneously accessible · CPC title