# US 2017/0286304 A1 · Pipelined Prefetcher for Parallel Advancement Of Multiple Data Streams

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

- Number: US 2017/0286304 A1
- Document ID: US20170286304A1
- Status: Published application
- Kind: A1
- Application number: 15/087,917
- Filed: 2016-03-31
- Published: 2017-10-05
- Earliest claimed: 2016-03-31
- Assignees: Intel Corporation
- Applicants: Intel Corporation
- Inventors: Leeor Peled; Joseph Nuzman; Larisa Novakovsky
- Web page: https://patentgrep.com/patent/US20170286304A1

## CPC

- G06F 12/0862: with prefetch
- G06F 12/0897: with two or more cache hierarchy levels (with multilevel cache hierarchies G06F12/0811)
- G06F 2212/1024: Latency reduction
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A processor includes a front end to decode instructions, an execution unit to execute instructions, multiple caches at different cache hierarchy levels, a pipelined prefetcher, and a retirement unit to retire instructions. The prefetcher includes circuitry to receive a demand request for data at a first address within a first line in a memory and, in response, to provide the data at the first address to the execution unit for consumption, to prefetch a second line at a first offset distance from the first line into a mid-level cache, and to prefetch a third line at a second offset distance from the second line into a last-level cache. The prefetcher includes circuitry to prefetch, in response to another demand request, the third line into the mid-level cache, and a fourth line into the last-level cache. The prefetcher enforces minimum or maximum offset distances between prefetched data streams.

## Claims

### Claim 1

A processor, comprising:
a front end including circuitry to decode an instruction;
an execution unit including circuitry to execute the instruction;
a first cache in a cache hierarchy;
a second cache in the cache hierarchy, the second cache to be at a lower level in the cache hierarchy than the first cache;
a prefetcher, including circuitry to:
receive a first demand request for data at a first memory address, the data at the first memory address to be consumed by execution of the instruction, and the first memory address to be within a first line in a memory;
provide, in response to the first demand request, the data at the first memory address to the execution unit for consumption by the execution of the instruction;
prefetch into the first cache, in response to the first demand request, a second line in the memory at a first offset distance from the first line;
prefetch into the second cache, in response to the first demand request, a third line in the memory at a second offset distance from the second line, the third line to be farther from the first line than is the second line; and
a retirement unit to retire the instruction.

### Claim 2 (depends on 1)

The processor of claim 1, wherein the prefetcher further includes circuitry to:
receive a second demand request for data at a second memory address, the second memory address to be within the second line in the memory;
provide, in response to the second demand request, the data at the second memory address to the execution unit from the first cache; and
prefetch the third line into the first cache, including circuitry to:
promote the third line from the second cache to the first cache.

### Claim 3 (depends on 1)

The processor of claim 1, wherein the prefetcher further includes:
circuitry to prefetch into the first cache, in response to the first demand request, a fourth line in the memory in addition to the second line in the memory, the fourth line to be adjacent to the second line in the memory; or
circuitry to prefetch into the second cache, in response to the first demand request, a fifth line in the memory in addition to the third line in the memory, the fifth line to be adjacent to the third line in the memory.

### Claim 4 (depends on 1)

The processor of claim 1, wherein the prefetcher further includes circuitry to:
track a next line to be prefetched into the first cache;
receive a second demand request for data at a second memory address, the second memory address to be within a fourth line in the memory;
determine whether or not the distance between the fourth line in the memory and the next line to be prefetched into the first cache exceeds a predetermined maximum offset distance; and
elide a prefetch of the next line to be prefetched into the first cache in response to a determination that the distance between the fourth line in the memory and the next line to be prefetched into the first cache exceeds the predetermined maximum offset distance.

### Claim 5 (depends on 1)

The processor of claim 1, wherein the prefetcher further includes circuitry to:
receive a second demand request for data at a second memory address;
determine, based on a first heuristic, whether to issue a request to prefetch a line into the first cache in response to the second demand request;
elide issuance of a request to prefetch a line into the first cache in response to a determination that a request to prefetch a line into the first cache should not be issued;
determine, based on a second heuristic, whether to issue a request to prefetch a line into the second cache in response to the second demand request; and
elide issuance of a request to prefetch a line into the second cache in response to a determination that a request to prefetch a line into the second cache should not be issued.

### Claim 6 (depends on 1)

The processor of claim 1, wherein:
the processor further comprises circuitry to:
detect that the instruction is an instruction within an instruction stream that generates accesses to sequential addresses in the memory; and
the prefetcher further includes circuitry to:
prefetch the second line into the first cache in response to the detection that the instruction is an instruction within an instruction stream that generates accesses to sequential addresses in the memory; and
prefetch the third line into the second cache in response to the detection that the instruction is an instruction within an instruction stream that generates accesses to sequential addresses in the memory.

### Claim 7 (depends on 1)

The processor of claim 1, wherein:
the processor further comprises:
a third cache in the cache hierarchy, the third cache to be at a lower level in the cache hierarchy than the second cache; and
the prefetcher further includes circuitry to:
prefetch into the third cache, in response to the first demand request, a fourth line in the memory at a third offset distance from the third line, the fourth line to be farther from the first line than is the third line.

### Claim 8

A method, comprising, in a processor:
receiving an instruction;
decoding the instruction;
executing the instruction, including:
receiving a first demand request for data at a first memory address, the data at the first memory address being for consumption while executing the first instruction, and the first memory address being within a first line in a memory;
providing, in response to receiving the first demand request, the data at the first memory address for consumption during the executing;
prefetching into a first cache in a cache hierarchy, in response to receiving the first demand request, a second line in the memory at a first offset distance from the first line;
prefetching into a second cache in the cache hierarchy, in response to receiving the first demand request, a third line in the memory at a second offset distance from the second line, the third line being farther from the first line than is the second line; and
retiring the instruction.

### Claim 9 (depends on 8)

The method of claim 8, further comprising:
receiving a second demand request for data at a second memory address, the second memory address being within the second line in the memory;
providing, in response to the second demand request, the data at the second memory address to the execution unit from the first cache; and
prefetching the third line into the first cache, including:
promoting the third line from the second cache to the first cache.

### Claim 10 (depends on 8)

The method of claim 8, further comprising:
prefetching into the first cache, in response to the first demand request, a fourth line in the memory in addition to the second line in the memory, the fourth line being adjacent to the second line in the memory; or
prefetching into the second cache, in response to the first demand request, a fifth line in the memory in addition to the third line in the memory, the fifth line being adjacent to the third line in the memory.

### Claim 11 (depends on 8)

The method of claim 8, further comprising:
tracking a next line to be prefetched into the first cache;
receiving a second demand request for data at a second memory address, the second memory address being within a fourth line in the memory;
determining whether or not the distance between the fourth line in the memory and the next line to be prefetched into the first cache exceeds a predetermined maximum offset distance; and
refraining from prefetching the next line to be prefetched into the first cache in response to determining that the distance between the fourth line in the memory and the next line to be prefetched into the first cache exceeds the predetermined maximum offset distance.

### Claim 12 (depends on 8)

The method of claim 8, further comprising:
receiving a second demand request for data at a second memory address;
determining, based on a first heuristic, whether or not to issue a request to prefetch a line into the first cache in response to the second demand request;
determining, based on a second heuristic, whether or not to issue a request to prefetch a line into the second cache in response to the second demand request.

### Claim 13 (depends on 8)

The method of claim 8, wherein:
the method further comprises detecting that the instruction is an instruction within an instruction stream that generates accesses to sequential addresses in the memory;
prefetching the second line into the first cache is performed in response to detecting that the instruction is an instruction within an instruction stream that generates accesses to sequential addresses in the memory; and
prefetching the third line into the second cache is performed in response to detecting that the instruction is an instruction within an instruction stream that generates accesses to sequential addresses in the memory.

### Claim 14

A system, comprising:
a memory; and
a processor, including:
a front end including circuitry to decode an instruction;
an execution unit including circuitry to execute the instruction;
a mid-level cache in a cache hierarchy;
a last-level cache in the cache hierarchy, the last-level cache to be at a lower level in the cache hierarchy than the mid-level cache;
a prefetcher, including circuitry to:
receive a first demand request for data at a first memory address, the data at the first memory address to be consumed by execution of the instruction, and the first memory address to be within a first line in a memory;
provide, in response to the first demand request, the data at the first memory address to the execution unit for consumption by the execution of the instruction;
prefetch into the mid-level cache, in response to the first demand request, a second line in the memory at a first offset distance from the first line;
prefetch into the last-level cache, in response to the first demand request, a third line in the memory at a second offset distance from the second line, the third line to be farther from the first line than is the second line; and
a retirement unit to retire the instruction.

### Claim 15 (depends on 14)

The system of claim 14, wherein the prefetcher further includes circuitry to:
receive a second demand request for data at a second memory address, the second memory address to be within the second line in the memory;
provide, in response to the second demand request, the data at the second memory address to the execution unit from the mid-level cache; and
prefetch the third line into the mid-level cache, including circuitry to:
promote the third line from the last-level cache to the mid-level cache.

### Claim 16 (depends on 14)

The system of claim 14, wherein the prefetcher further includes:
circuitry to prefetch into the mid-level cache, in response to the first demand request, a fourth line in the memory in addition to the second line in the memory, the fourth line to be adjacent to the second line in the memory; or
circuitry to prefetch into the last-level cache, in response to the first demand request, a fifth line in the memory in addition to the third line in the memory, the fifth line to be adjacent to the third line in the memory.

### Claim 17 (depends on 14)

The system of claim 14, wherein the prefetcher further includes circuitry to:
track a next line to be prefetched into the mid-level cache;
receive a second demand request for data at a second memory address, the second memory address to be within a fourth line in the memory;
determine whether or not the distance between the fourth line in the memory and the next line to be prefetched into the mid-level cache exceeds a predetermined maximum offset distance; and
elide a prefetch of the next line to be prefetched into the mid-level cache in response to a determination that the distance between the fourth line in the memory and the next line to be prefetched into the mid-level cache exceeds the predetermined maximum offset distance.

### Claim 18 (depends on 14)

The system of claim 14, wherein the prefetcher further includes circuitry to:
receive a second demand request for data at a second memory address;
determine, based on a first heuristic, whether to issue a request to prefetch a line into the mid-level cache in response to the second demand request;
elide issuance of a request to prefetch a line into the mid-level cache in response to a determination that a request to prefetch a line into the mid-level cache should not be issued;
determine, based on a second heuristic, whether to issue a request to prefetch a line into the last-level cache in response to the second demand request; and
elide issuance of a request to prefetch a line into the last-level cache in response to a determination that a request to prefetch a line into the last-level cache should not be issued.

### Claim 19 (depends on 14)

The system of claim 14, wherein:
the processor further comprises circuitry to:
detect that the instruction is an instruction within an instruction stream that generates accesses to sequential addresses in the memory; and
the prefetcher further includes circuitry to:
prefetch the second line into the mid-level cache in response to the detection that the instruction is an instruction within an instruction stream that generates accesses to sequential addresses in the memory; and
prefetch the third line into the last-level cache in response to the detection that the instruction is an instruction within an instruction stream that generates accesses to sequential addresses in the memory.

### Claim 20 (depends on 14)

The system of claim 14, wherein:
the processor further comprises:
a first-level cache in the cache hierarchy, the first-level cache to be at a higher level in the cache hierarchy than the mid-level cache; and
the prefetcher further includes circuitry to:
promote the first line from the mid-level cache to the first-level cache; and
provide the data at the first memory address to the execution unit for consumption by the execution of the instruction from the first-level cache.
