FILTERING PRE-FETCH REQUESTS TO REDUCE PRE-FETCHING OVERHEAD

• US 20130246708A1
• Filed: 03/15/2012
• Published: 09/19/2013
• Est. Priority Date: 03/15/2012
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Ono, Tarik, Greenstreet, Mark R.
• Granted Patent: US 9,176,878 B2
• Time in Patent Office: Days
• US Class Current: 711/122
• 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
• CPC Class Codes: G06F 9/30185 according to one or more bits in the instruction, e.g. prefix, sub-opcode
• CPC Class Codes: G06F 9/3802 Instruction prefetching
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

The disclosed embodiments provide a system that filters pre-fetch requests to reduce pre-fetching overhead. During operation, the system executes an instruction that involves a memory reference that is directed to a cache line in a cache. Upon determining that the memory reference will miss in the cache, the system determines whether the instruction frequently leads to cache misses. If so, the system issues a pre-fetch request for one or more additional cache lines. Otherwise, no pre-fetch request is sent. Filtering pre-fetch requests based on instructions'"'"' likelihood to miss reduces pre-fetching overhead while preserving the performance benefits of pre-fetching.

Claims

1. A computer-implemented method for filtering pre-fetch requests to reduce pre-fetching overhead, the method comprising:

executing an instruction that involves a memory reference which is directed to a cache line in a cache;

determining that the memory reference will miss in the cache; and

determining whether the instruction frequently leads to cache misses, and if so, issuing a pre-fetch request for one or more additional cache lines.

2. The computer-implemented method of claim 1,

wherein issuing the pre-fetch request comprises detecting an access pattern for additional memory references following the instruction;

and

wherein selectively issuing a pre-fetch request based on an instruction'"'"'s likelihood to of a cache miss reduces the instruction'"'"'s pre-fetching overhead.

3. The computer-implemented method of claim 1, wherein determining whether the instruction frequently leads to cache misses comprises one or more of the following:

receiving an indication associated with the instruction that the cache line frequently misses in the cache; and

using tracking data stored during the execution of a program to determine that the cache line frequently misses in the cache.

4. The computer-implemented method of claim 3, wherein the method further comprises:

performing profiling operations while executing the program on a processor to generate profiling information;

analyzing the profiling information to identify that the instruction is likely to involve a cache miss; and

modifying the instruction to indicate that the instruction is likely to involve a cache miss.

5. The computer-implemented method of claim 4,

wherein modifying the instruction comprises marking a field in the instruction to indicate a likely cache miss;

wherein a marked field indicates that the pre-fetching request should be issued when executing the instruction.

6. The computer-implemented method of claim 3,

wherein the tracking data is generated using a counter that tracks previous hits and misses for the memory reference;

and

wherein the method further comprises using the values tracked in the counter to determine whether the instruction frequently leads to cache misses.

7. The computer-implemented method of claim 6, wherein tracking previous hits and misses for the memory reference comprises:

using the counter to track the number of times that the instruction has executed; and

calculating the difference between the counter and a miss counter or a hit counter to determine the hit and miss rates for the memory reference.

8. The computer-implemented method of claim 6, wherein tracking previous hits and misses for the memory reference comprises one or more of the following:

tracking previous hits and misses for the memory reference using a hit counter and a miss counter; and

tracking previous hits and misses for the memory reference using a saturating counter.

9. The computer-implemented method of claim 6, wherein the method further comprises comparing a calculated value derived using the tracked hit and miss values with a threshold to determine whether to send the pre-fetch request.

10. The computer-implemented method of claim 9, wherein calculating the calculated value comprises weighing previous misses differently than previous hits.

11. The computer-implemented method of claim 1,

wherein the cache is part of a multi-level memory hierarchy;

wherein upon determining that the instruction frequently leads to cache misses, the method further comprises simultaneously sending a speculative request for the cache line to a lower level of the multi-level memory hierarchy prior to completing a full lookup operation in the cache; and

wherein preemptively sending the speculative request facilitates reducing the cache miss delay when the cache line is not available in the cache.

12. The computer-implemented method of claim 1, wherein the instruction is a load instruction.

13. The computer-implemented method of claim 1,

wherein determining whether the instruction frequently leads to cache misses further comprises determining a predicted performance penalty associated with cache misses for the instruction;

and

wherein the method further comprises determining whether to issue the pre-fetch request based on the predicted performance penalty.

14. A computer system that filters pre-fetch requests to reduce pre-fetching overhead, comprising:

a processor;

a cache; and

a memory;

wherein the cache and the memory are part of a multi-level memory hierarchy; and

wherein while executing an instruction that involves a memory reference which is directed to a cache line in the cache, upon determining that the memory reference will miss in the cache, the processor is configured to determine whether the instruction frequently leads to cache misses, and if so, issue a pre-fetch request for one or more additional cache lines.

15. The computer system of claim 14,

wherein issuing the pre-fetch request comprises detecting an access pattern for additional memory references following the instruction;

and

wherein selectively issuing a pre-fetch request based on an instruction'"'"'s likelihood to of a cache miss reduces the instruction'"'"'s pre-fetching overhead.

16. The computer system of claim 14, wherein determining whether the instruction frequently leads to cache misses comprises one or more of the following:

receiving an indication associated with the instruction that the cache line frequently misses in the cache; and

using tracking data stored during the execution of a program to determine that the cache line frequently misses in the cache.

17. The computer system of claim 16,

wherein the tracking data is generated using a counter that tracks previous hits and misses for the memory reference;

and

wherein the processor uses the values tracked in the counter to determine whether the instruction frequently leads to cache misses.

18. The computer system of claim 17, wherein tracking previous hits and misses for the memory reference comprises:

using the counter to track the number of times that the instruction has executed; and

calculating the difference between the counter and a miss counter or a hit counter to determine the hit and miss rates for the memory reference.

19. The computer system of claim 14, wherein the cache is part of a multi-level memory hierarchy;

wherein upon determining that the instruction frequently leads to cache misses, the processor simultaneously sends a speculative request for the cache line to a lower level of the multi-level memory hierarchy prior to completing a full lookup operation in the cache; and

wherein preemptively sending the speculative request facilitates reducing the cache miss delay when the cache line is not available in the cache.

20. A processor that filters pre-fetch requests to reduce pre-fetching overhead, comprising:

a cache, wherein the cache is part of a multi-level memory hierarchy;

an executing mechanism configured to execute an instruction that involves a memory reference which is directed to a cache line in the cache;

a determining mechanism configured to determine that the memory reference will miss in the cache; and

a speculation mechanism configured to determine whether the instruction frequently leads to cache misses, and if so, issue a pre-fetch request for one or more additional cache lines.