# US 2014/0195788 A1 · Reducing instruction miss penalties in applications

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

- Number: US 2014/0195788 A1
- Document ID: US20140195788A1
- Status: Published application
- Kind: A1
- Application number: 13/738,811
- Filed: 2013-01-10
- Published: 2014-07-10
- Earliest claimed: 2013-01-10
- Assignees: Oracle International Corporation
- Applicants: Oracle International Corporation
- Inventors: Spiros KALOGEROPULOS; Partha TIRUMALAI
- Web page: https://patentgrep.com/patent/US20140195788A1

## CPC

- G06F 9/3802: {Instruction prefetching}
- G06F 8/4442: {Reducing the number of cache misses; Data prefetching (cache prefetching G06F12/0862)}
- G06F 9/30047: {Prefetch instructions; cache control instructions}
- G06F 9/45516: {Runtime code conversion or optimisation}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Embodiments include systems and methods for reducing instruction cache miss penalties during application execution. Application code is profiled to determine “hot” code regions likely to experience instruction cache miss penalties. The application code can be linearized into a set of traces that include the hot code regions. Embodiments traverse the traces in reverse, keeping track of instruction scheduling information, to determine where an accumulated instruction latency covered by the code blocks exceeds an amount of latency that can be covered by prefetching. Each time the accumulated latency exceeds the amount of latency that can be covered by prefetching, a prefetch instruction can be scheduled in the application code. Some embodiments insert additional prefetches, merge prefetches, and/or adjust placement of prefetches to account for scenarios, such as loops, merging or forking branches, edge confidence values, etc.

## Claims

### Claim 1

A system for reducing instruction cache miss penalties in application code execution, the system comprising:
a computer-implemented code profiler, operable to:
determine an instruction cache miss penalty for each of a plurality of code sections of application code, the instruction cache miss penalty indicating a likelihood that execution of the corresponding code section in the target execution environment will result in an instruction cache miss; and
generate execution traces from the application code, each execution trace comprising at least one of the plurality of code sections; and
a computer-implemented prefetcher, in communication with the computer-implemented code profiler, and operable, for each execution trace having a code section with a corresponding instruction cache miss penalty that exceeds a predetermined penalty threshold, to:
traverse a set of code blocks of the execution trace in reverse starting from a source code block of the execution trace until an accumulated instruction latency exceeds a prefetch latency by, for each of the set of code blocks, adding a latency covered by the code block to latencies of previously traversed code blocks of the set of code blocks to calculate the accumulated instruction latency, the prefetch latency corresponding to a predicted time to prefetch into an instruction cache a number of code blocks defined by a prefetch chunk size; and
insert a prefetch instruction ahead of a last-traversed code block in the execution trace when the accumulated instruction latency exceeds the prefetch latency.

### Claim 2 (depends on 1)

The system of claim 1, wherein the computer-implemented code profiler comprises a hardware counter based profiler operable to calculate the likelihood that execution of the corresponding code section will to result in an instruction cache miss.

### Claim 3 (depends on 1)

The system of claim 1, wherein the computer-implemented code profiler is operable to determine the instruction cache miss penalty for each of the plurality of code sections of the application code by identifying each code section as likely to result in an instruction cache miss during execution when the code section is targeted by a programmer user for instruction prefetching.

### Claim 4 (depends on 1)

The system of claim 1, wherein:
each execution trace comprises a sequence of instruction chunks each having the number of code blocks defined by the prefetch chunk size;
the source code block is a last code block of a second instruction chunk that directly precedes a first instruction chunk; and
the computer-implemented prefetcher is operable to insert the prefetch instruction as a first prefetch instruction that prefetches the first instruction chunk, thereby scheduling at least the prefetch latency between execution of the first prefetch instruction and execution of a first code block of the first instruction chunk.

### Claim 5 (depends on 4)

The system of claim 4, wherein the computer-implemented prefetcher is further operable to:
reset the source code block to a last code block of a third instruction chunk that directly precedes the second instruction chunk;
continue traversing the set of code blocks of the execution trace until the accumulated instruction latency from the reset source block exceeds the prefetch latency; and
insert a second prefetch instruction that prefetches the second instruction chunk in the execution trace according to where the accumulated instruction latency from the reset source block exceeds the prefetch latency, thereby scheduling at least the prefetch latency between execution of the second prefetch instruction and execution of a first code block of the second instruction chunk.

### Claim 6 (depends on 4)

The system of claim 4, wherein the execution trace is a first execution trace, and the computer-implemented prefetcher is further operable to:
reset the source code block to a last code block of a third instruction chunk that directly precedes the second instruction chunk;
continue traversing the set of code blocks of the first execution trace until a starting point of the execution trace is reached without the accumulated instruction latency from the reset source block exceeding the prefetch latency;
identify a second execution trace of the application code that is a predecessor of the first execution trace according to a function call graph of the application code;
traverse the set of code blocks of the second execution trace from a last code block of the second execution trace until the accumulated instruction latency from the reset source block exceeds the prefetch latency; and
insert a second prefetch instruction that prefetches the second instruction chunk in the first execution trace according to where the accumulated instruction latency from the reset source block exceeds the prefetch latency, thereby scheduling at least the prefetch latency between execution of the second prefetch instruction and execution of a first code block of the second instruction chunk.

### Claim 7 (depends on 1)

The system of claim 1, further comprising:
a computer-implemented cache analyzer operable to determine the prefetch latency and the prefetch chunk size according to cache characteristics of a target execution environment for the application code.

### Claim 8

A computer-implemented method for reducing instruction cache miss penalties in application code execution, the method comprising:
determining an instruction cache miss penalty for each of a plurality of code sections of application code, the instruction cache miss penalty indicating a likelihood that execution of the corresponding code section will result in an instruction cache miss;
generating execution traces from the application code, each execution trace comprising at least one of the plurality of code sections;
determining a prefetch latency corresponding to a predicted time to prefetch into an instruction cache a number of code blocks defined by a prefetch chunk size according to a target execution environment for the application code; and
for each execution trace having a code section with a corresponding instruction cache miss penalty that exceeds a predetermined penalty threshold:
traversing a set of code blocks of the execution trace in reverse starting from a source code block of the execution trace until an accumulated instruction latency exceeds the prefetch latency by, for each of the set of code blocks, adding a latency covered by the code block to latencies of previously traversed code blocks of the set of code blocks to calculate the accumulated instruction latency; and
inserting a prefetch instruction ahead of a last-traversed code block in the execution trace when the accumulated instruction latency exceeds the prefetch latency.

### Claim 9 (depends on 8)

The computer-implemented method of claim 8, wherein determining the instruction cache miss penalty for each of the plurality of code sections of application code comprises:
profiling each code section using a hardware counter based profiler to calculate the likelihood that execution of the corresponding code section will result in an instruction cache miss.

### Claim 10 (depends on 9)

The computer-implemented method of claim 9, wherein the hardware counter based profiler calculates the likelihood that execution of the corresponding code section will result in an instruction cache miss by calculating a likelihood that the corresponding code section will be executed during execution of the application code.

### Claim 11 (depends on 8)

The computer-implemented method of claim 8, wherein determining the instruction cache miss penalty for each of the plurality of code sections of application code comprises:
identifying each code section as likely to result in an instruction cache miss during execution when the code section is targeted by a programmer user for instruction prefetching.

### Claim 12 (depends on 11)

The computer-implemented method of claim 11, wherein the code section is targeted by a programmer user for instruction prefetching unless the code section includes an indication by the programmer user that the corresponding code section is unlikely to be executed during execution of the application code.

### Claim 13 (depends on 8)

The computer-implemented method of claim 8, wherein determining the instruction cache miss penalty for each of the plurality of code sections of application code comprises:
using feedback directed optimization to empirically calculate a likelihood that the corresponding code section will be executed during execution of the application code.

### Claim 14 (depends on 8)

The computer-implemented method of claim 8, further comprising:
computing whether instruction prefetching will reduce instruction cache miss penalties; and
performing the traversing and inserting steps only when instruction prefetching will reduce instruction cache miss penalties according to the computing step.

### Claim 15 (depends on 14)

The computer-implemented method of claim 14, wherein computing whether instruction prefetching will reduce instruction cache miss penalties comprises:
computing a total working size of all execution traces determined to have a code section with a corresponding instruction cache miss penalty that exceeds the predetermined threshold; and
determining that instruction prefetching will reduce instruction cache miss penalties only when the total working size exceeds a threshold size predetermined according to a capacity of at least one target cache.

### Claim 16 (depends on 8)

The computer-implemented method of claim 8, wherein:
each execution trace comprises a sequence of instruction chunks each having the number of code blocks defined by the prefetch chunk size;
the source code block is a last code block of a second instruction chunk that directly precedes a first instruction chunk; and
inserting the prefetch instruction ahead of the last-traversed code block in the execution trace comprises inserting the prefetch instruction as a first prefetch instruction that prefetches the first instruction chunk, thereby scheduling at least the prefetch latency between execution of the first prefetch instruction and execution of a first code block of the first instruction chunk.

### Claim 17 (depends on 16)

The computer-implemented method of claim 16, further comprising:
resetting the source code block to a last code block of a third instruction chunk that directly precedes the second instruction chunk;
continuing traversing the set of code blocks of the execution trace until the accumulated instruction latency from the reset source block exceeds the prefetch latency; and
inserting a second prefetch instruction that prefetches the second instruction chunk in the execution trace according to where the accumulated instruction latency from the reset source block exceeds the prefetch latency, thereby scheduling at least the prefetch latency between execution of the second prefetch instruction and execution of a first code block of the second instruction chunk.

### Claim 18 (depends on 16)

The computer-implemented method of claim 16, wherein the execution trace is a first execution trace, and further comprising:
resetting the source code block to a last code block of a third instruction chunk that directly precedes the second instruction chunk;
continuing traversing the set of code blocks of the first execution trace until a starting point of the execution trace is reached without the accumulated instruction latency from the reset source block exceeding the prefetch latency;
identifying a second execution trace of the application code that is a predecessor of the first execution trace according to a function call graph of the application code;
traversing the set of code blocks of the second execution trace from a last code block of the second execution trace until the accumulated instruction latency from the reset source block exceeds the prefetch latency; and
inserting a second prefetch instruction that prefetches the second instruction chunk in the first execution trace according to where the accumulated instruction latency from the reset source block exceeds the prefetch latency, thereby scheduling at least the prefetch latency between execution of the second prefetch instruction and execution of a first code block of the second instruction chunk.

### Claim 19 (depends on 8)

The computer-implemented method of claim 8, wherein, inserting the prefetch instruction ahead of the last-traversed code block in the execution trace comprises:
determining that the last-traversed code block is inside a body of a loop having a pre-header; and
inserting the prefetch instruction in the pre-header of the loop.

### Claim 20 (depends on 8)

The computer-implemented method of claim 8, wherein the execution trace is one of a plurality of execution traces, and further comprising:
calculating, at each edge between a child execution trace in the plurality of execution traces and one or more parent execution traces in the plurality of execution traces as defined by a function call graph, an edge confidence level that the child execution trace will be called by each of its parent execution traces;
calculating an accumulated confidence level as a function of the edge confidence level of each edge crossed while traversing the set of code blocks of the execution trace in reverse; and
inserting the prefetch instruction after a last-traversed edge when the accumulated confidence level falls below a predetermined confidence threshold before the accumulated instruction latency exceeds the prefetch latency.