# US 9,519,586 B2 · Methods and apparatus to reduce cache pollution caused by data prefetching

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

- Number: US 9,519,586 B2
- Document ID: US9519586B2
- Status: Granted
- Kind: B2
- Application number: 13/746,000
- Filed: 2013-01-21
- Published: 2014-07-24
- Granted: 2016-12-13
- Earliest claimed: 2013-01-21
- Assignees: QUALCOMM Incorporated
- Applicants: QUALCOMM Incorporated
- Inventors: Matthew M. Gilbert
- Web page: https://patentgrep.com/patent/US9519586B2

## CPC

- G06F 12/0862: with prefetch
- G06F 9/30065: {Loop control instructions; iterative instructions, e.g. LOOP, REPEAT}
- G06F 9/325: {for loops, e.g. loop detection or loop counter}
- G06F 9/3455: {using stride}
- G06F 9/383: {Operand prefetching (cache prefetching G06F12/0862)}
- G06F 9/3832: {Value prediction for operands; operand history buffers}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Efficient techniques are described for reducing cache pollution by use of a prefetch logic that recognizes exits from software loops or function returns to cancel any pending prefetch request operations. The prefetch logic includes a loop data address monitor to determine a data access stride based on repeated execution of a memory access instruction in a program loop. Data prefetch logic then speculatively issues prefetch requests according to the data access stride. A stop prefetch circuit is used to cancel pending prefetch requests in response to an identified loop exit. The prefetch logic may also recognize a return from a called function and cancel any pending prefetch request operations associated with the called function. When prefetch requests are canceled, demand requests, such as based on load instructions, are not canceled. This approach to reduce cache pollution uses program flow information to throttle data cache prefetching.

## Claims

### Claim 1

A method for canceling prefetch requests, the method comprising:
issuing cache prefetch requests in response to memory access instructions in a program loop;
identifying a loop exit situation in the program loop based on an evaluation of program flow information; and
canceling pending cache prefetch requests in response to the identified loop exit situation.

### Claim 2 (depends on 1)

The method of claim 1, wherein the pending cache prefetch requests that are canceled do not include existing demand requests in the program loop.

### Claim 3 (depends on 1)

The method of claim 1, wherein the loop exit situation is based on identifying a loop ending branch that evaluates to exit the program loop.

### Claim 4 (depends on 1)

The method of claim 1, wherein the loop exit situation is based on an incorrect branch prediction which caused speculative instruction fetch and execution to be canceled.

### Claim 5 (depends on 1)

The method of claim 1 further comprising:
detecting a conditional branch instruction has resolved to end the program loop as the loop exit situation; and
canceling pending prefetch requests except for demand prefetch requests in the program loop.

### Claim 6 (depends on 1)

The method of claim 1 further comprising:
detecting a conditional branch instruction has not resolved to end the program loop, wherein monitoring for the loop exit situation continues.

### Claim 7

A method for canceling prefetch requests, the method comprising:
speculatively prefetching data with data prefetch requests according to a called function in a program loop; and
canceling pending data prefetch requests in response to a function exit from the called function.

### Claim 8 (depends on 7)

The method of claim 7, wherein existing demand requests in the program loop are not canceled.

### Claim 9 (depends on 7)

The method of claim 7, wherein the function exit is based on detecting execution of a return from the called function.

### Claim 10 (depends on 7)

The method of claim 7, wherein the function exit is based on detecting speculative execution of a return from the called function.

### Claim 11

An apparatus for canceling prefetch requests, the apparatus comprising:
a loop data address monitor configured to determine a data access stride based on repeated execution of a memory access instruction in a program loop;
data prefetch logic configured to speculatively issue prefetch requests based on memory access instructions in the program loop according to the data access stride; and
a stop prefetch circuit configured to cancel pending prefetch requests in response to an identified loop exit.

### Claim 12 (depends on 11)

The apparatus of claim 11, wherein the loop data address monitor comprises:
a stride circuit configured to monitor the repeated execution of the memory access instruction to determine a difference in an operand address for each execution of the memory access instruction, wherein the difference in the operand address is a stride address value; and
an add function circuit configured to add the stride address value to the operand address of a most recently executed memory access instruction to determine a next operand address.

### Claim 13 (depends on 11)

The apparatus of claim 11, wherein existing demand requests in the program loop are not canceled.

### Claim 14 (depends on 11)

The apparatus of claim 11, wherein the identified loop exit is based on identifying a loop ending branch that evaluates to exit the program loop.

### Claim 15 (depends on 11)

The apparatus of claim 11, wherein the identified loop exit is based on an incorrect branch prediction which cancels speculative instruction fetch and execution.

### Claim 16 (depends on 11)

The apparatus of claim 11, wherein the stop prefetch circuit is further configured to detect a conditional branch instruction has resolved to end the program loop as the identified loop exit and to cancel pending prefetch requests except for demand prefetch requests.

### Claim 17 (depends on 11)

The apparatus of claim 11, wherein the stop prefetch circuit is further configured to detect a conditional branch instruction has not resolved to end the program loop and wherein the program loop continues until the identified loop exit is identified.

### Claim 18 (depends on 11)

The apparatus of claim 11, wherein the stop prefetch circuit is further configured to not cancel pending prefetch requests in the program loop based on a weakly predicted loop exit.

### Claim 19

A computer-readable non-transitory medium encoded with computer-readable program data and code, the computer-readable program data and code when executed operable to:
issue cache prefetch requests in response to memory access instructions in a program loop;
identify a loop exit situation in the program loop based on program flow information; and
cancel pending cache prefetch requests in response to the identified loop exit situation.

### Claim 20

An apparatus for canceling prefetch requests comprising:
means for determining a data access stride based on repeated execution of a memory access instruction in a program loop;
means for speculatively issuing prefetch requests in response to memory access instructions in the program loop according to the data access stride; and
means for canceling pending data cache prefetch requests in response to an identified loop exit.