# US 2015/0106590 A1 · Filtering out redundant software prefetch instructions

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2015/0106590 A1
- Document ID: US20150106590A1
- Status: Published application
- Kind: A1
- Application number: 14/053,378
- Filed: 2013-10-14
- Published: 2015-04-16
- Earliest claimed: 2013-10-14
- Assignees: Oracle International Corporation
- Applicants: Oracle International Corporation
- Inventors: Yuan C. Chou
- Web page: https://patentgrep.com/patent/US20150106590A1

## CPC

- G06F 9/30072: {to perform conditional operations, e.g. using predicates or guards}
- G06F 9/30047: {Prefetch instructions; cache control instructions}
- G06F 9/3832: {Value prediction for operands; operand history buffers}
- 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)}
- G06F 2201/865: Monitoring of software
- G06F 2201/88: Monitoring involving counting
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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 redundant if the software prefetch instruction accesses a cache line that has already been fetched from memory; and
as software prefetch instructions are encountered during execution of the program, selectively filtering out the 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 1)

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 cache misses for the software prefetch instruction.

### Claim 5 (depends on 1)

The method of claim 1, wherein selectively filtering out a given software prefetch instruction in the individual software prefetch instructions includes:
upon decoding the given software prefetch instruction at a decode unit in the processor, performing a lookup for the given 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 given software prefetch instruction, filtering out the given software prefetch instruction so that the given software prefetch instruction is not executed; and
if the lookup does not find an entry for the given software prefetch instruction, allowing the given software prefetch instruction to execute.

### Claim 6 (depends on 5)

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.

### Claim 7 (depends on 1)

The method of claim 1, wherein selectively filtering out the individual software prefetch instructions includes adjusting a hit-rate threshold for the filtering technique based on a utilization rate for the load-store unit, wherein the hit-rate threshold becomes higher as the utilization rate of the load-store unit increases, and becomes lower as the utilization rate of the load-store unit decreases.

### Claim 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 redundant if the software prefetch instruction accesses a cache line that has already been fetched from memory; and
as software prefetch instructions are encountered during execution of the program, selectively filter out the 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.

### Claim 9 (depends on 8)

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.

### Claim 10 (depends on 9)

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.

### Claim 11 (depends on 8)

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 cache misses for the software prefetch instruction.

### Claim 12 (depends on 8)

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 given software prefetch instruction at a decode unit in the processor, the execution mechanism is configured to perform a lookup for the given software prefetch instruction in the filter table;
wherein if the lookup finds an entry for the given software prefetch instruction, the execution mechanism is configured to filter out the given software prefetch instruction so that the given software prefetch instruction is not executed; and
wherein if the lookup does not find an entry for the given software prefetch instruction, the execution mechanism is configured to allow the given software prefetch instruction to execute.

### Claim 13 (depends on 12)

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; and
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.

### Claim 14 (depends on 8)

The processor of claim 8, wherein while selectively filtering out the individual software prefetch instructions, the execution mechanism is configured to adjust a hit-rate threshold for the filtering technique based on a utilization rate for the load-store unit, wherein the hit-rate threshold becomes higher as the utilization rate of the load-store unit increases, and lower as the utilization rate of the load-store unit decreases.

### Claim 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 redundant if the software prefetch instruction accesses a cache line that has already been fetched from memory; and
as software prefetch instructions are encountered during execution of the program, selectively filter out the 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.

### Claim 16 (depends on 15)

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.

### Claim 17 (depends on 16)

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.

### Claim 18 (depends on 15)

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 cache misses for the software prefetch instruction.

### Claim 19 (depends on 15)

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 given software prefetch instruction at a decode unit in the processor, the execution mechanism is configured to perform a lookup for the given software prefetch instruction in the filter table;
wherein if the lookup finds an entry for the given software prefetch instruction, the execution mechanism is configured to filter out the given software prefetch instruction so that the given software prefetch instruction is not executed; and
wherein if the lookup does not find an entry for the given software prefetch instruction, the execution mechanism is configured to allow the given software prefetch instruction to execute.

### Claim 20 (depends on 19)

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; and
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.
