Filtering out redundant software prefetch instructions

Patent metadata

Field	Value
Publication number	US-9442727-B2
Application number	US-201314053378-A
Country	US
Kind code	B2
Filing date	Oct 14, 2013
Priority date	Oct 14, 2013
Publication date	Sep 13, 2016
Grant date	Sep 13, 2016

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.

First claim

What is claimed is:

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 i

Assignees

• Oracle Int Corp

Inventors

• Chou Yuan C

Classifications

• G06F2201/865

  Monitoring of software · CPC title

• G06F9/30047

  Prefetch instructions; cache control instructions · CPC title

• G06F11/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 title

• G06F2201/88

  Monitoring involving counting · CPC title

• G06F9/3832

  Value prediction for operands; operand history buffers · CPC title