# US 2003/0084433 A1 · Profile-guided stride prefetching

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

- Number: US 2003/0084433 A1
- Document ID: US20030084433A1
- Status: Published application
- Kind: A1
- Application number: 09/999,889
- Filed: 2001-10-31
- Published: 2003-05-01
- Earliest claimed: 2001-10-31
- Inventors: Chi-Keung Luk; Harish Patil; Robert Muth; Paul Geoffrey Lowney; Robert Cohn; Richard Weiss
- Web page: https://patentgrep.com/patent/US20030084433A1

## CPC

- G06F 11/3612: {by runtime analysis (performance monitoring G06F11/3466)}
- G06F 8/4442: {Reducing the number of cache misses; Data prefetching (cache prefetching G06F12/0862)}
- G06F 11/3466: {Performance evaluation by tracing or monitoring}
- G06F 12/0862: with prefetch
- G06F 2201/865: Monitoring of software
- G06F 2201/885: Monitoring specific for caches
- G06F 2212/6026: Prefetching based on access pattern detection, e.g. stride based prefetch
- G06F 2212/6028: Prefetching based on hints or prefetch instructions
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Executable code is modified to include prefetch instructions for certain loads. The targeted loads preferably include those loads for which a compiler cannot compute a stride (which represents the difference in memory addresses used in consecutive executions of a given load). Whether prefetch instructions should be included for such loads is determined preferably by running the code with a training data set which determines the frequency of strides for each subsequent execution of a load. If a stride occurs more than once for a load, then that load is prefetched by inserting a prefetch instruction into the executable code for that load. Further, a stride value is associated with the inserted prefetch. Preferably, the stride value is the most frequently occurring stride, which can be determined based on the results of the training data set. Alternatively, the stride can be computed during run-time by the code itself.

## Claims

### Claim 1

A method of modifying executable software, comprising:
(a) instrumenting said software to collect information regarding load instructions;
(b) running a predetermined data set through said instrumented software to collect information regarding said load instructions; and
(c) determining whether to insert a prefetch instruction for a load instruction based on said information.

### Claim 2 (depends on 1)

The method of claim 1 further including performing an analysis of the cost associated with a prefetch instruction versus the benefit of a prefetch instruction and making the determination in (c) based on said cost/benefit analysis.

### Claim 3 (depends on 1)

The method of claim 1 wherein said prefetch instruction is inserted in (c) if (X−Y)>N, wherein X is the number of clock cycles to fetch data with the load if no prefetch instruction is inserted, Y is the number of clock cycles to fetch data with the load if a prefetch instruction is inserted, and N is the number of clock cycles needed to retire the prefetch instruction.

### Claim 4 (depends on 1)

The method of claim 1 further including determining the most frequently occurring stride value for said load instruction using the results of (b), a stride value being the difference between memory addresses used during two consecutive executions of said load instruction.

### Claim 5 (depends on 4)

The method of claim 4 further including inserting a prefetch instruction into said software associated with said load instruction, said prefetch instruction using the most frequently occurring stride value for said load instruction.

### Claim 6

A method of modifying executable software, comprising:
(a) determining the difference between pairs of memory addresses used in consecutive executions of a load instruction;
(b) determining the frequency of occurrence of said differences for said load instruction; and
(c) inserting a prefetch instruction for said load instruction if a difference occurs more than once for said load instruction.

### Claim 7 (depends on 6)

The method of claim 6 further including associating before run-time a difference with the inserted prefetch instruction, said difference being the most frequently occurring difference.

### Claim 8 (depends on 6)

The method of claim 6 further including computing during run-time a difference to be associated with the inserted prefetch instruction.

### Claim 9 (depends on 6)

The method of claim 6 wherein said prefetch instruction is inserted in (c) after considering the latency associated with such a prefetch instruction.

### Claim 10 (depends on 6)

The method of claim 6 wherein said prefetch instruction is inserted in (c) if (X−Y)>N, wherein X is the number of clock cycles to fetch data with the load if no prefetch instruction is inserted, Y is the number of clock cycles to fetch data with the load if a prefetch instruction is inserted, and N is the number of clock cycles needed to retire the prefetch instruction.

### Claim 11

A computer system, comprising:
a processor;
an I/O controller coupled to said processor;
an I/O device coupled to said I/O controller; and
memory coupled to said processor, said memory including software executed by said processor, wherein said software has been modified prior to run-time to include a prefetch instruction associated with a load instruction by instrumenting said software to collect information regarding load instructions, running a predetermined data set through said instrumented software, and inserting the prefetch instruction if a stride associated with said load occurs more than once.

### Claim 12 (depends on 11)

The computer system of claim 11 wherein said software modification also occurs by performing an analysis of the cost associated with the prefetch instruction versus the benefit of a prefetch instruction and inserting the prefetch instruction if the benefit outweighs the cost.

### Claim 13 (depends on 11)

The computer system of claim 11 wherein said prefetch instruction is inserted in if (X−Y)>N, wherein X is the number of clock cycles to fetch data with the load if no prefetch instruction is inserted, Y is the number of clock cycles to fetch data with the load if a prefetch instruction is inserted, and N is the number of clock cycles to prefetch the data.

### Claim 14 (depends on 11)

The computer system of claim 11 wherein said software modification also occurs by determining the most frequently occurring stride value for said load instruction.

### Claim 15 (depends on 14)

The computer system of claim 14 wherein said prefetch instruction is inserted into said software, said prefetch instruction using the most frequently occurring stride value.

### Claim 16

A computer system, comprising:
a processor;
an I/O controller coupled to said processor;
an I/O device coupled to said I/O controller; and
memory coupled to said processor, said memory including software executed by said processor, wherein said software has been modified prior to run-time to include a prefetch instruction associated with a load instruction by determining the difference between memory addresses used in consecutive executions of a load instruction, determining the frequency of occurrence of said differences for said load instruction, and inserting a prefetch instruction for said load instruction if a difference occurs more than once for said load instruction.

### Claim 17 (depends on 16)

The computer system of claim 16 wherein said software modification occurs by associating, before run-time, a difference with the inserted prefetch instruction, said difference being the most frequently occurring difference for the load instruction.

### Claim 18 (depends on 16)

The computer system of claim 16 wherein said software modification occurs by inserting stride computing instructions in addition to said prefetch instruction, said stride computing instructions permit a difference to be computed during run-time that is associated with the inserted prefetch instruction.

### Claim 19 (depends on 16)

The computer system of claim 16 wherein said prefetch instruction is inserted during the software modification after considering the latency associated with such a prefetch instruction.

### Claim 20 (depends on 16)

The computer system of claim 16 wherein said prefetch instruction is inserted during the software modification if (X−Y)>N, wherein X is the number of clock cycles to fetch data with the load if no prefetch instruction is inserted, Y is the number of clock cycles to fetch data with the load if a prefetch instruction is inserted, and N is the number of clock cycles to prefetch the data.
