Using cache hit information to manage prefetches

• US 9,262,328 B2
• Filed: 11/27/2012
• Issued: 02/16/2016
• Est. Priority Date: 11/27/2012
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Chaudhary, Anurag
• Primary Examiner(s): Elmore, Reba I
• Application Number:
  US13/686,556
• Publication Number:
  US 20140149678A1
• Time in Patent Office: 1,176 Days
• Field of Search: 711/137, 711/141, 711/145, 710/11, 710/35, 710/39, 710/56, 712/207
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch

Abstract

Cache hit information is used to manage (e.g., cap) the prefetch distance for a cache. In an embodiment in which there is a first cache and a second cache, where the second cache (e.g., a level two cache) has greater latency than the first cache (e.g., a level one cache), a prefetcher prefetches cache lines to the second cache and is configured to receive feedback from that cache. The feedback indicates whether an access request issued in response to a cache miss in the first cache results in a cache hit in the second cache. The prefetch distance for the second cache is determined according to the feedback.

Claims

1. A system comprising:

a plurality of caches comprising first cache and a second cache, the second cache having greater latency than the first cache; and

a prefetcher configured to monitor addresses included in access requests to the second cache, detect a pattern to the access requests, and determine a prefetch distance based on the pattern, the prefetcher further configured to prefetch cache lines to the second cache that are selected according to the prefetch distance and receive feedback from the second cache, the feedback indicating whether an access request issued in response to a cache miss in the first cache results in a cache hit in the second cache, the prefetch distance also determined according to the feedback.

2. The system of claim 1 wherein the prefetch distance increases to a first value according to the pattern, wherein further the prefetch distance is held at the first value in response to the cache hit.

3. The system of claim 1 wherein the prefetch distance increases to a first value according to the pattern, wherein further the prefetch distance continues to increase after the cache hit until the prefetch distance reaches a second value that is larger than the first value by a specified margin.

4. The system of claim 1 wherein the prefetch distance increases to a first value according to a confidence level associated with the pattern, the confidence level comprising a value that increases as the pattern increases in length, and wherein the prefetch distance is held at the first value in response to the cache hit even if the confidence level increases.

5. The system of claim 1 wherein the prefetch distance has a maximum value, wherein the prefetch distance is held at a first value in response to the cache hit, the first value less than the maximum value.

6. The system of claim 1 wherein the prefetcher is further configured to prefetch cache lines to the first cache, wherein the feedback further indicates whether a demand request issued to the first cache results in a cache hit in the first cache.

7. A computer system comprising:

a processing unit;

a plurality of caches comprising a first cache and a second cache coupled to the processing unit, the second cache having greater latency than the first cache; and

memory coupled to the processing unit and having stored therein instructions that, if executed by the computer system, cause the computer system to execute a prefetcher that performs operations comprising;

monitoring addresses included in access requests to the second Cache;

detecting a pattern to the access requests;

determining a prefetch distance based on the pattern and also according to feedback from the second cache, the feedback indicating whether an access request issued in response to a cache miss in the first cache results in a cache hit in the second cache;

prefetching cache lines to the second cache, wherein the cache lines are selected according to the prefetch distance.

8. The computer system of claim 7 wherein the operations performed by the prefetcher further comprise:

increasing the prefetch distance to a first value according to a pattern of cache misses in the second cache, wherein the cache misses occur prior to the cache hit in the second cache; and

maintaining the prefetch distance at the first value in response to the cache hit.

9. The computer system of claim 7 wherein the operations performed by the prefetcher further comprise increasing the prefetch distance to a first value according to a pattern of cache misses in the second cache, wherein the cache misses occur prior to the cache hit in the second cache, wherein further the prefetch distance continues to increase to greater than the first value after the cache hit until the prefetch distance reaches a second value that is larger than the first value by a specified margin.

10. The computer system of claim 9 wherein the first value corresponds to a confidence level associated with the pattern, the confidence level comprising a value that increases as the pattern increases in length, and wherein further the prefetch distance is not increased beyond the first value even if the confidence level increases in response to the cache hit.

11. The computer system of claim 9 wherein the prefetch distance has a maximum value, wherein the first value is less than the maximum value.

12. The computer system of claim 7 wherein the operations performed by the prefetcher further comprise prefetching cache lines to the first cache, wherein the feedback further indicates whether a demand request issued to the first cache results in a cache hit in the first cache.

13. A method implemented by a computer system comprising a processor, a memory, and a plurality of caches coupled to the processor and the memory and comprising a first cache and a second cache, the second cache having greater latency than the first cache, the method comprising:

monitoring addresses included in access requests to the second cache;

detecting a pattern to the access requests;

determining a first value for the prefetch distance based on the pattern and also according to feedback from the second cache, the feedback indicating whether an access request issued in response to a cache miss in the first cache results in a cache hit in the second cache;

in response to a cache miss in the first cache, sending an access request to the second cache; and

if the access request results in a cache hit in the second cache, then capping the prefetch distance even if the pattern continues to increase in length.

14. The method of claim 13 wherein the prefetch distance is capped at a second value that is equal to the first value.

15. The method of claim 13 wherein the prefetch distance is capped at a second value that is larger than the first value by a specified margin, wherein the prefetch distance is allowed to increase after the cache hit until the second value is reached.

16. The method of claim 13 wherein the first value corresponds to a confidence level associated with the pattern, the confidence level comprising a value that increases as the pattern increases in length.

17. The method of claim 13 wherein the prefetch distance has a maximum value, wherein the prefetch distance is capped at a value that is less than the maximum value.

18. The method of claim 13 further comprising:

prefetching cache lines to the first cache; and

determining whether an access request issued to the first cache results in a cache hit in the first cache.