Filtering out redundant software prefetch instructions

• US 9,442,727 B2
• Filed: 10/14/2013
• Issued: 09/13/2016
• Est. Priority Date: 10/14/2013
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Chou, Yuan C.
• Primary Examiner(s): Nam, Hyun
• Application Number:
  US14/053,378
• Publication Number:
  US 20150106590A1
• Time in Patent Office: 1,065 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/3037 where the computing system component is a memory, e.g. virtual memory, cache accessing, addressing or allocating within memory systems or architectures G06F12/00; checking stores for correct operation G11C29/00
• CPC Class Codes: G06F 2201/865 Monitoring of software
• CPC Class Codes: G06F 2201/88 Monitoring involving counting
• CPC Class Codes: G06F 9/30047 Prefetch instructions; cache control instructions
• CPC Class Codes: G06F 9/30072 to perform conditional operations, e.g. using predicates or guards
• CPC Class Codes: G06F 9/3832 Value prediction for operands; operand history buffers

Abstract

The disclosed embodiments relate to a system that selectively filters out redundant software prefetch instructions during execution of a program on a processor. During execution of the program, the system collects information associated with hit rates for individual software prefetch instructions as the individual software prefetch instructions are executed, wherein a software prefetch instruction is redundant if the software prefetch instruction accesses a cache line that has already been fetched from memory. As software prefetch instructions are encountered during execution of the program, the system selectively filters out individual software prefetch instructions that are likely to be redundant based on the collected information, so that likely redundant software prefetch instructions are not executed by the processor.

Claims

1. A method for selectively filtering out redundant software prefetch instructions during execution of a program on a processor, comprising:

during execution of the program,

collecting information associated with hit rates for individual software prefetch instructions as the individual software prefetch instructions are executed, wherein a software prefetch instruction is determined to be redundant upon determining that the software prefetch instruction accesses a cache line that has already been fetched from memory, wherein determining that the software prefetch instruction is redundant comprises determining that a redundant count associated with an entry for the software prefetch instruction in a learning table exceeds a pre-determined threshold; and

as software prefetch instructions are encountered during execution of the program, selectively filtering out individual software prefetch instructions that are likely to be redundant based on the collected information, so that likely redundant software prefetch instructions are not executed by the processor.

2. The method of claim 1, wherein selectively filtering out individual software prefetch instructions includes enabling filtering operations when a utilization rate of a load-store unit in the processor exceeds a threshold.

3. The method of claim 2, wherein the method further comprises periodically determining the utilization rate for the load-store unit by determining how many loads, stores and software prefetch instructions are processed in a given time interval.

4. The method of claim 1, wherein collecting the information associated with hit rates includes using one or more counters associated with each software prefetch instruction to keep track of cache hits and/or cache misses for the software prefetch instruction.

5. The method of claim 1, wherein selectively filtering out a software prefetch instruction includes:

upon decoding the software prefetch instruction at a decode unit in the processor, performing a lookup for the software prefetch instruction in a filter table, wherein the filter table includes entries for software prefetch instructions that are to be filtered out;

if the lookup finds an entry for the software prefetch instruction, filtering out the software prefetch instruction so that the software prefetch instruction is not executed; and

if the lookup does not find an entry for the software prefetch instruction, allowing the software prefetch instruction to execute.

6. The method of claim 5, wherein collecting the information associated with hit rates for a software prefetch instruction includes:

performing a lookup for the software prefetch instruction in a learning table, wherein the learning table includes entries for software prefetch instructions that are executed by the program;

if an entry does not exist for the software prefetch instruction in the learning table, allocating and initializing an entry for the software prefetch instruction in the learning table;

determining whether executing the software prefetch instruction causes a cache hit or a cache miss;

updating information in the entry for the software prefetch instruction based on the determination;

if the updated information indicates the software prefetch instruction is likely to be redundant, creating an entry in the filter table for the software prefetch instruction if an entry does not already exist; and

if the updated information indicates the software prefetch instruction is unlikely to be redundant, invalidating an entry in the filter table for the software prefetch instruction if such an entry exists.

7. The method of claim 1, wherein selectively filtering out the individual software prefetch instructions includes adjusting an aggressiveness of the filtering technique based on a utilization rate for the load-store unit, wherein the filtering technique becomes more aggressive as the utilization rate of the load-store unit increases, and becomes less aggressive as the utilization rate of the load-store unit decreases.

8. A processor that selectively filters out redundant software prefetch instructions during execution of a program, comprising:

an instruction cache;

a data cache; and

an execution mechanism including an execution pipeline, wherein during execution of the program, the execution mechanism is configured to,

collect information associated with hit rates for individual software prefetch instructions as the individual software prefetch instructions are executed, wherein a software prefetch instruction is determined to be redundant upon determining that the software prefetch instruction accesses a cache line that has already been fetched from memory, wherein determining that the software prefetch instruction is redundant comprises determining that a redundant count associated with an entry for the software prefetch instruction in a learning table exceeds a pre-determined threshold; and

as software prefetch instructions are encountered during execution of the program, selectively filter out individual software prefetch instructions that are likely to be redundant based on the collected information, so that likely redundant software prefetch instructions are not executed by the processor.

9. The processor of claim 8, wherein while selectively filtering out individual software prefetch instructions, the execution mechanism is configured to enable filtering operations when a utilization rate of a load-store unit in the processor exceeds a threshold.

10. The processor of claim 9, wherein the execution mechanism is configured to periodically determine the utilization rate for the load-store unit by determining how many loads, stores and software prefetch instructions are processed in a given time interval.

11. The processor of claim 8, wherein while collecting the information associated with hit rates, the execution mechanism is configured to use one or more counters associated with each software prefetch instruction to keep track of cache hits and/or cache misses for the software prefetch instruction.

12. The processor of claim 8,

wherein the execution mechanism includes a filter table, which includes entries for software prefetch instructions that are to be filtered out;

wherein upon decoding a software prefetch instruction at a decode unit in the processor, the execution mechanism is configured to perform a lookup for the software prefetch instruction in the filter table;

wherein if the lookup finds an entry for the software prefetch instruction, the execution mechanism is configured to filter out the software prefetch instruction so that the software prefetch instruction is not executed; and

wherein if the lookup does not find an entry for the software prefetch instruction, the execution mechanism is configured to allow the software prefetch instruction to execute.

13. The processor of claim 12,

wherein the execution mechanism includes a learning table, which includes entries for software prefetch instructions that are executed by the program;

wherein while collecting the information associated with hit rates for a software prefetch instruction, the execution mechanism is configured to,

perform a lookup for the software prefetch instruction in the learning table,

if an entry does not exist for the software prefetch instruction in the learning table, allocate and initialize an entry for the software prefetch instruction in the learning table;

determine whether executing the software prefetch instruction causes a cache hit or a cache miss;

update information in the entry for the software prefetch instruction based on the determination;

if the updated information indicates the software prefetch instruction is likely to be redundant, create an entry in the filter table for the software prefetch instruction if an entry does not already exist; and

if the updated information indicates the software prefetch instruction is unlikely to be redundant, invalidate an entry in the filter table for the software prefetch instruction if such an entry exists.

14. The processor of claim 8, wherein while selectively filtering out the individual software prefetch instructions, the execution mechanism is configured to adjust an aggressiveness of the filtering technique based on a utilization rate for the load-store unit, wherein the filtering technique becomes more aggressive as the utilization rate of the load-store unit increases and becomes less aggressive as the utilization rate of the load-store unit decreases.

15. A computer system that selectively filters out redundant software prefetch instructions during execution of a program, comprising:

a processor;

a memory;

an instruction cache within the processor;

a data cache within the processor; and

an execution mechanism including an execution pipeline within the processor, wherein during execution of the program, the execution mechanism is configured to,

collect information associated with hit rates for individual software prefetch instructions as the individual software prefetch instructions are executed, wherein a software prefetch instruction is determined to be redundant upon determining that the software prefetch instruction accesses a cache line that has already been fetched from memory, wherein determining that the software prefetch instruction is redundant comprises determining that a redundant count associated with an entry for the software prefetch instruction in a learning table exceeds a pre-determined threshold; and

as software prefetch instructions are encountered during execution of the program, selectively filter out individual software prefetch instructions that are likely to be redundant based on the collected information, so that likely redundant software prefetch instructions are not executed by the processor.

16. The computer system of claim 15, wherein while selectively filtering out individual software prefetch instructions, the execution mechanism is configured to enable filtering operations when a utilization rate of a load-store unit in the processor exceeds a threshold.

17. The computer system of claim 16, wherein the execution mechanism is configured to periodically determine the utilization rate for the load-store unit by determining how many loads, stores and software prefetch instructions are processed in a given time interval.

18. The computer system of claim 15, wherein while collecting the information associated with hit rates, the execution mechanism is configured to use one or more counters associated with each software prefetch instruction to keep track of cache hits and/or cache misses for the software prefetch instruction.

19. The computer system of claim 15,

wherein the execution mechanism includes a filter table, which includes entries for software prefetch instructions that are to be filtered out;

wherein upon decoding a software prefetch instruction at a decode unit in the processor, the execution mechanism is configured to perform a lookup for the software prefetch instruction in the filter table;

wherein if the lookup finds an entry for the software prefetch instruction, the execution mechanism is configured to filter out the software prefetch instruction so that the software prefetch instruction is not executed; and

wherein if the lookup does not find an entry for the software prefetch instruction, the execution mechanism is configured to allow the software prefetch instruction to execute.

20. The computer system of claim 19,

wherein the execution mechanism includes a learning table, which includes entries for software prefetch instructions that are executed by the program;

wherein while collecting the information associated with hit rates for a software prefetch instruction, the execution mechanism is configured to,

perform a lookup for the software prefetch instruction in the learning table,

if an entry does not exist for the software prefetch instruction in the learning table, allocate and initialize an entry for the software prefetch instruction in the learning table;

determine whether executing the software prefetch instruction causes a cache hit or a cache miss;

update information in the entry for the software prefetch instruction based on the determination;

if the updated information indicates the software prefetch instruction is likely to be redundant, create an entry in the filter table for the software prefetch instruction if an entry does not already exist; and

if the updated information indicates the software prefetch instruction is unlikely to be redundant, invalidate an entry in the filter table for the software prefetch instruction if such an entry exists.