# US 2003/0204840 A1 · Apparatus and method for one-pass profiling to concurrently generate a frequency profile and a stride profile to enable data prefetching in irregular programs

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

- Number: US 2003/0204840 A1
- Document ID: US20030204840A1
- Status: Published application
- Kind: A1
- Application number: 10/136,755
- Filed: 2002-04-30
- Published: 2003-10-30
- Earliest claimed: 2002-04-30
- Inventors: Youfeng Wu
- Web page: https://patentgrep.com/patent/US20030204840A1

## CPC

- G06F 11/3612: {by runtime analysis (performance monitoring G06F11/3466)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

An apparatus and method for one-pass profiling to concurrently generate a frequency profile and a stride profile to enable pre-fetching of irregular program data are described. In one embodiment, the method includes the selective generation of stride profile information according to partially generated frequency profile information to concurrently form a stride profile and a frequency profile during execution of a user program instrumented during a single profiling pass. Once the stride profile and frequency profile are generated, prefetch instructions are inserted into the user program utilizing the stride profile and the frequency profile. In one embodiment, the present invention utilizes profiling to identify regular stride patterns in irregular program code, which is referred to herein as stride profiling. Consequently, by identifying regular stride patterns within the irregular program code, one embodiment of the invention enables prefetching of irregular program data to reduce system stalls due to data cache misses.

## Claims

### Claim 1

A method comprising:
selectively generating stride profile information according to concurrently generated frequency profile information to concurrently form a stride profile and a frequency profile according to user program code instrumented during a single compiler profiling pass; and
inserting prefetch instructions within a user program utilizing the stride profile and the frequency profile.

### Claim 2 (depends on 1)

The method of claim 1, wherein prior to collecting the stride profile information, the method further comprises:
instrumenting a user program to collect frequency profile information to form the frequency profile;
instrumenting each load loop within the user program to selectively collect stride profile information utilizing partially collected frequency profile information; and
executing the instrumented user program to concurrently generate the stride profile and the frequency profile.

### Claim 3 (depends on 1)

The method of claim 1, wherein selectively collecting the stride profile information further comprises:
detecting an instrumented user program loop wherein a data load instruction is performed as an instrumented load loop;
determining an average trip count of the detected loop according to partially generated frequency information of the detected loop;
when the average trip count of the detected loop exceeds a predetermined average trip count value, generating stride profile information for one or more loads within the detected loop; and
repeating the selecting, determining and collecting for each instrumented load loop within the user program.

### Claim 4 (depends on 1)

The method of claim 1, wherein selectively collecting the frequency information further comprises:
once the stride profile is complete, determining one or more loads having an average trip count below the pre-determined average trip count;
selecting a load loop from the one or more determined load loops;
filtering, from the stride profile, stride profile information corresponding to the selected load loop; and
repeating the selecting and filtering for each of the one or more determined load loops to form a final stride profile.

### Claim 5 (depends on 2)

The method of claim 2, wherein instrumenting the user program to collect frequency profile information further comprises:
selecting a program block/edge from the user program;
instrumenting the program block/edge to collect block/edge frequency profile information; and
repeating the selecting and instrumenting for each program block/edge within the user program to complete frequency instrumenting of the user program.

### Claim 6 (depends on 2)

The method of claim 2, wherein instrumenting each load loop further comprises:
determining a plurality of loops within the user program where a data load instruction is performed as a plurality of load loops;
selecting a load loop from the plurality of load loops wherein a data load instruction is performed within the user program;
instrumenting a loop prolog of the selected load loop to set a loop predicate according to an average trip count condition of the selected load loop;
instrumenting one or more loads inside the selected load loop to selectively collect stride profile information according to the loop predicate; and
repeating the selecting of a load loop, instrumenting of a loop prolog and instrumenting one or more loads inside a loop for each of the plurality of determined load loops within the user program.

### Claim 7 (depends on 6)

The method of claim 6, wherein instrumenting the loop prolog further comprises:
instrumenting the loop prolog to determine an average trip count of the selected load loop utilizing partially collected frequency information; and
instrumenting the loop prolog to set the loop predicate according to whether the average trip count exceeds a predetermined average trip count value to collect stride profile information when the average trip count exceeds the predetermined average trip count value.

### Claim 8 (depends on 6)

The method of claim 6, wherein instrumenting the loop prolog further comprises:
instrumenting the loop prolog to determine an average trip count of the selected load loop utilizing partially collected frequency information;
instrumenting the loop prolog to determine an execution count of the selected load loop;
instrumenting the loop prolog to set a temporary loop predicate according to whether the execution count exceeds a predetermined average execution count value; and
instrumenting the loop prolog to set a loop predicate according to the temporary loop predicate, such that the loop predicate is not set according to the average trip count condition until the execution count exceeds a predetermined average execution count value.

### Claim 9 (depends on 6)

The method of claim 6, wherein instrumenting the loop prolog further comprises:
instrumenting the loop prolog to determine an average trip count of the selected load loop utilizing partially collected frequency information;
instrumenting the loop prolog to set a temporary predicate according to whether the average trip count exceeds the predetermined average trip count value;
instrumenting the loop prolog to increment a high trip count according to the temporary loop predicate; and
instrumenting the loop prolog to set the loop predicate once the high trip count exceeds a predetermined high trip count value.

### Claim 10 (depends on 6)

The method of claim 6 wherein instrumenting the loop prolog further comprises:
selecting a loop prolog block from one or more loop prolog blocks of the selected loop head block;
instrumenting the selected loop prolog to generate a prolog frequency total as a sum of a prolog frequency of each of the one or more prolog blocks of the selected loop ahead block;
instrumenting the selected loop prolog block to determine an average trip count as a ratio of a frequency of the selected loop head block and the prolog frequency total;
instrumenting the loop predicate to set according to whether the average trip count exceeds a predetermined average trip count value; and
repeating the instrumenting, instrument and instrumenting for each loop prolog block of the selected loop head block.

### Claim 11

A computer readable storage medium including program instructions that direct a computer to function in a specified manner when executed by a processor, the program instructions comprising:
selectively generating stride profile information according to concurrently generated frequency profile information to concurrently form a stride profile and a frequency profile according to user program code instrumented during a single compiler profiling pass; and
inserting prefetch instructions within a user program utilizing the stride profile and the frequency profile.

### Claim 12 (depends on 11)

The computer readable storage medium of claim 11, wherein prior to collecting the stride profile information, the method further comprises:
instrumenting a user program to collect frequency profile information to form the frequency profile;
instrumenting each load loop within the user program to selectively collect stride profile information utilizing partially collected frequency profile information; and
executing the instrumented user program to concurrently generate the stride profile and the frequency profile.

### Claim 13 (depends on 11)

The computer readable storage medium of claim 11, wherein collecting the stride profile information further comprises:
detecting an instrumented user program loop wherein a data load instruction is performed as an instrumented load loop;
determining an average trip count of the detected loop according to partially generated frequency information of the detected loop;
when the average trip count of the detected loop exceeds a predetermined average trip count value, generating stride profile information for one or more loads within the detected loop; and
repeating the selecting, determining and collecting for each instrumented load loop within the user program.

### Claim 14 (depends on 11)

The computer readable storage medium of claim 11, wherein selectively collecting the frequency information further comprises:
once the stride profile is complete, determining one or more load loops having an average trip count below the pre-determined average trip count;
selecting a load loop from the one or more determined load loops;
filtering, from the stride profile, stride profile information corresponding to the selected load loop; and
repeating the selecting and filtering for each of the one or more determined load loops to form a final stride profile.

### Claim 15 (depends on 12)

The computer readable storage medium of claim 12, wherein instrumenting the user program to collect frequency profile information further comprises:
selecting a program block/edge from the user program;
instrumenting the program block/edge to collect block/edge frequency profile information; and
repeating the selecting and instrumenting for each program block/edge within the user program to complete frequency instrumenting of the user program.

### Claim 16 (depends on 12)

The computer readable storage medium of claim 12, wherein instrumenting each load loop further comprises:
determining a plurality of loops within the user program where a data load instruction is performed as a plurality of load loops;
selecting a load loop from the plurality of load loops wherein a data load instruction is performed within the user program;
instrumenting a loop prolog of the selected load loop to set a loop predicate according to an average trip count condition of the selected load loop;
instrumenting one or more loads within the selected load loop to selectively collect stride profile information according to the loop predicate; and
repeating the selecting of a load loop, instrumenting a loop prolog and instrumenting one or more loads inside a loop for each of the plurality of determined load loops within the user program.

### Claim 17 (depends on 16)

The computer readable storage medium of claim 16, wherein instrumenting the loop prolog further comprises:
instrumenting the loop prolog to determine an average trip count of the selected load loop utilizing partially collected frequency information; and
instrumenting the loop to set the loop predicate according to whether the average trip count exceeds a predetermined average trip count value to collect stride profile information when the average trip count exceeds the predetermined average trip count value.

### Claim 18 (depends on 16)

The computer readable storage medium of claim 16, wherein instrumenting the loop prolog further comprises:
instrumenting the loop prolog to determine an average trip count of the selected load loop utilizing partially collected frequency information;
instrumenting the loop prolog to determine an execution count of the selected load loop;
instrumenting the loop prolog to set a temporary loop predicate once the execution count exceeds a predetermined execution count value; and
instrumenting the loop predicate to set according to whether the average trip count exceeds a predetermined average trip count value once the temporary loop predicate is set.

### Claim 19 (depends on 16)

The computer readable storage medium of claim 16, wherein instrumenting the loop prolog further comprises:
instrumenting the loop prolog to determine an average trip count of the selected load loop utilizing partially collected frequency information;
instrumenting the loop prolog to set a temporary predicate according to whether the average trip count exceeds the predetermined average trip count value;
instrumenting the loop prolog to increment a high trip count according to the temporary loop predicate; and
instrumenting the loop prolog to set the loop predicate once the high trip count exceeds a predetermined high trip count value.

### Claim 20 (depends on 16)

The computer readable storage medium of claim 16 wherein instrumenting the loop prolog further comprises:
selecting a loop prolog block from one or more loop prolog blocks of the selected loop head block;
instrumenting the selected loop prolog to generate a prolog frequency total as a sum of a prolog frequency of each of the one or more prolog blocks of the selected loop head block;
instrumenting the selected loop prolog block to determine an average trip count as a ratio of a frequency of the selected loop head block and the prolog frequency total;
instrumenting the loop predicate to set according to whether the average trip count exceeds a predetermined average trip count value; and
repeating the instrumenting, instrument and instrumenting for each loop prolog block of the selected loop head block.

### Claim 21

A method comprising:
instrumenting a user program to generate frequency profile information to form a frequency profile;
instrumenting each loop within the user program to selectively generate stride profile information utilizing concurrently generated frequency profile information during a single compiler profiling pass; and
executing the instrumented user program to concurrently generate the stride profile and the frequency profile.

### Claim 22 (depends on 21)

The method of claim 21, wherein instrumenting the user program to collect frequency profile information further comprises:
selecting a program block/edge from the user program;
instrumenting the program block/edge to collect block/edge frequency profile information; and
repeating the selecting and instrumenting for each program block/edge within the user program.

### Claim 23 (depends on 21)

The method of claim 21, wherein instrumenting each load loop further comprises:
determining a plurality of loops within the user program where a load instruction is performed;
selecting a load loop from the plurality of loops wherein a load instruction is performed;
instrumenting a loop prolog of the selected load loop to set the loop predicate according to an average trip count condition of the selected load loop;
instrumenting one or more loads within the selected load loop to selectively collect stride profile information according to the loop predicate; and
repeating the selecting, instrumenting and instrumenting for each of the plurality of determined load loops within the user program.

### Claim 24 (depends on 23)

The method of claim 23, wherein instrumenting the loop prolog block further comprises:
instrumenting the loop prolog to determine an average trip count of the selected load loop utilizing partially collected frequency information; and
instrumenting the loop prolog to set the loop predicate according to whether the average trip count exceeds a predetermined average trip count value, to collect stride profile information when the average trip count exceeds the predetermined average trip count value.

### Claim 25 (depends on 21)

The method of claim 21, further comprising:
selectively generating stride profile information according to partially generated frequency profile information to concurrently form the stride profile and the frequency profile during execution of the instrumented user program; and
inserting prefetch instructions within the user program utilizing the concurrently generated stride profile and frequency profile.

### Claim 26

A computer readable storage medium including program instructions that direct a computer to function in a specified manner when executed by a processor, the program instructions comprising:
instrumenting a user program to generate frequency profile information to form a frequency profile;
instrumenting each loop within the user program to selectively generate stride profile information utilizing concurrently generated frequency profile information during a single compiler profiling pass; and
executing the instrumented user program to concurrently generate the stride profile and the frequency profile.

### Claim 27 (depends on 26)

The computer readable storage medium of claim 26, wherein instrumenting the user program to collect frequency profile information further comprises:
selecting a program block/edge from the user program;
instrumenting the program block/edge to collect block/edge frequency profile information; and
repeating the selecting and instrumenting for each program block/edge within the user program.

### Claim 28 (depends on 26)

The computer readable storage medium of claim 26, wherein instrumenting each load loop further comprises:
determining a plurality of loops within the user program where a load instruction is performed;
selecting a load loop from the plurality of loops wherein a data load instruction is performed;
instrumenting a loop prolog of the selected load loop to set a loop predicate according to an average trip count condition of the selected load loop;
instrumenting one or more loads of the selected load loop to selectively collect stride profile information according to the loop predicate; and
repeating the selecting, instrumenting and instrumenting for each of the plurality of determined load loops within the user program.

### Claim 29 (depends on 28)

The computer readable storage medium of claim 28, wherein instrumenting the loop prolog block further comprises:
instrumenting the loop prolog to determine an average trip count of the selected load loop utilizing partially collected frequency information; and
instrumenting the loop prolog to set the loop predicate according to whether the average trip count exceeds a predetermined average trip count value to collect stride profile information when the average trip count exceeds the predetermined average trip count value.

### Claim 30 (depends on 26)

The computer readable storage medium of claim 26, further comprising:
selectively generating stride profile information according to partially generated frequency profile information to concurrently form the stride profile and the frequency profile during execution of the instrumented user program; and
inserting prefetch instructions within the user program utilizing the concurrently generated stride profile and frequency profile.

### Claim 31

A system comprising:
a processor having circuitry to execute instructions;
a communications interface coupled to the processor, the communications interface to receive a user program from a user and to provide a compiled target program executable to the user;
a storage device coupled to the processor, having sequences of instructions stored therein, which when executed by the processor cause the processor to:
instrument a user program to generate frequency profile information,
instrument each load loop within the user program to selectively generate stride profile information utilizing concurrently generated frequency profile information during a single compiler profiling pass, and
execute the instrumented user program to concurrently generate the stride profile and the frequency profile.

### Claim 32 (depends on 31)

The system of claim 31, wherein the processor is further caused to:
select a frequency profile and a stride profile concurrently generated during execution of the user program instrumented during a single compiler profiling pass; and
insert prefetch instructions within the user program utilizing the stride profile and the frequency profile.

### Claim 33 (depends on 32)

The system of claim 32, wherein the processor is further caused to:
execute, in response to a user request, an instrumented, target program executable; and
prefetch program data according to the inserted prefetch instructions.
