# US 6,732,260 B1 · Presbyopic branch target prefetch method and apparatus

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

- Number: US 6,732,260 B1
- Document ID: US6732260B1
- Status: Granted
- Kind: B1
- Application number: 09/518,939
- Filed: 2000-03-06
- Granted: 2004-05-04
- Earliest claimed: 2000-03-06
- Assignees: Intel Corporation
- Inventors: Hong Wang; Ralph Kling; Edward T. Grochowski; Kalpana Ramakrishnan
- Web page: https://patentgrep.com/patent/US6732260B1

## CPC

- G06F 9/3806: {using address prediction, e.g. return stack, branch history buffer}
- G06F 9/30054: {Unconditional branch instructions}
- G06F 9/323: {for indirect branch instructions}
- G06F 9/3848: {using hybrid branch prediction, e.g. selection between prediction techniques}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

An instruction prefetch apparatus includes a branch target buffer (BTB), a presbyopic target buffer (PTB) and a prefetch stream buffer (PSB). The BTB includes records that map branch addresses to branch target addresses, and the PTB includes records that map branch target addresses to subsequent branch target addresses. When a branch instruction is encountered, the BTB can predict the dynamically adjacent subsequent block entry location as the branch target address in the record that also includes the branch instruction address. The PTB can predict multiple subsequent blocks by mapping the branch target address to subsequent dynamic blocks. The PSB holds instructions prefetched from subsequent blocks predicted by the PTB.

## Claims

### Claim 1

A branch target prefetch apparatus comprising:
a presbyopic target buffer configured to receive a presbyopic target buffer record, wherein the presbyopic target buffer record maps an entry location of a first code region to an entry location of a second code region; and
a prefetch stream buffer configured to receive instructions from the second code region responsive to if an instruction pointer is to encounter the entry location of the first code region.

### Claim 2 (depends on 1)

The branch target prefetch apparatus of claim 1 wherein the presbyopic target buffer is configured to receive the presbyopic target buffer record responsive to a branch instruction being encountered in the first code region, the branch instruction having a branch target address equal to the entry location of the second code region.

### Claim 3 (depends on 2)

The branch target prefetch apparatus of claim 2 further comprising a branch target buffer configured to receive a branch target buffer record that maps an address of the branch instruction to the entry location of the second code region.

### Claim 4 (depends on 3)

The branch target prefetch apparatus of claim 3 wherein the presbyopic target buffer is configured to receive a plurality of presbyopic target buffer records, and is further configured to be searched recursively.

### Claim 5 (depends on 4)

The branch target prefetch apparatus of claim 4 wherein the prefetch stream buffer is configured to receive instructions from a plurality of code regions responsive to a recursive search of the presbyopic target buffer.

### Claim 6 (depends on 5)

The branch target prefetch apparatus of claim 5 wherein the prefetch stream buffer is configured to differentiate between instructions such that instructions from different ones of the plurality of code regions can be invalidated.

### Claim 7 (depends on 3)

The branch target prefetch apparatus of claim 3 wherein the branch target buffer record includes a first confidence counter having a first number of bits, and the presbyopic target buffer record includes a second confidence counter having a second number of bits that is greater than the first number of bits.

### Claim 8 (depends on 1)

The branch target prefetch apparatus of claim 1 wherein the presbyopic target buffer record is configured to map the entry location of the first code region to entry locations of a plurality of second code regions.

### Claim 9 (depends on 1)

The branch target prefetch apparatus of claim 1 wherein a cache memory has a cache latency associated therewith, and the prefetch target buffer has a depth at least as deep as one cache latency.

### Claim 10

A processor comprising:
a branch target buffer responsive to fetched instruction addresses, wherein the branch target buffer is configured to map branch instruction addresses to branch target addresses; and
a presbyopic target buffer responsive to the branch target buffer, wherein the presbyopic target buffer is configured to map branch target addresses to subsequent branch target addresses.

### Claim 11 (depends on 10)

The processor of claim 10 further comprising:
a stream buffer configured to receive instructions fetched from subsequent branch target addresses specified in the presbyopic target buffer.

### Claim 12 (depends on 10)

The processor of claim 10 wherein the presbyopic target buffer is configured to be recursively searched to predict a plurality of subsequent branch target addresses.

### Claim 13 (depends on 10)

The processor of claim 10 wherein the presbyopic target buffer implements skip-adjacent mapping.

### Claim 14 (depends on 10)

The processor of claim 10 wherein a complete branch target address is specified by a fixed number of bits, and the presbyopic target buffer includes mapping records that specify branch target addresses using less than the fixed number of bits.

### Claim 15

A processor comprising:
a branch target buffer responsive to fetched instruction addresses, wherein the branch target buffer is configured to be searched for the fetched instruction addresses and corresponding branch target addresses;
a presbyopic target buffer responsive to the branch target buffer, wherein the presbyopic target buffer is configured to be searched for subsequent dynamic blocks as a function of branch target addresses.

### Claim 16 (depends on 15)

The processor of claim 15 wherein the presbyopic target buffer is configured to map branch target addresses to subsequent dynamic block exit addresses.

### Claim 17 (depends on 16)

The processor of claim 16 wherein the branch target buffer is further responsive to subsequent dynamic block exit addresses from the presbyopic target buffer.

### Claim 18 (depends on 17)

The processor of claim 17 wherein the branch target buffer and presbyopic target buffer are configured to be searched recursively in combination.

### Claim 19

A processor comprising:
a first fetch buffer configured to receive instructions prefetched from predicted branch target addresses; and
a second fetch buffer configured to receive instructions prefetched from predicted subsequent blocks, responsive to if an instruction pointer in the processor is to point to an entry location of a block of instructions, based on a presbyopic target buffer record that maps entry location of the block of instructions to entry locations of the predicted subsequent blocks.

### Claim 20 (depends on 19)

The processor of claim 19 wherein the second fetch buffer includes a coloring field for each instruction included therein, such that each instruction included therein can be assigned a color.

### Claim 21 (depends on 19)

The processor of claim 19 wherein the second fetch buffer includes a subsequent block demarcation mechanism to distinguish prefetched instructions from different predicted subsequent blocks.

### Claim 22 (depends on 19)

The processor of claim 19 further including a branch target buffer having records that when populated, map branches to predicted branch targets.

### Claim 23 (depends on 22)

The processor of claim 22 further including a presbyopic target buffer to store the presbyopic target buffer record.

### Claim 24 (depends on 23)

The processor of claim 23 wherein the presbyopic target buffer maps each predicted branch target address to a plurality of predicted subsequent blocks.

### Claim 25 (depends on 23)

The processor of claim 23 wherein the presbyopic target buffer is configured to be recursively searched.

### Claim 26

A method comprising:
in a first buffer that maps branch instruction addresses to block entry addresses, searching for a first buffer record having a branch instruction address that matches a current instruction address;
after the first buffer record is found, searching a second buffer that maps block entry addresses to subsequent block entry addresses for a second buffer record having a block entry address matching the first buffer record; and
after the second buffer record is found, prefetching instructions beginning at a subsequent block entry address included in the second buffer record.

### Claim 27 (depends on 26)

The method of claim 26 wherein prefetching comprises entering instructions into a stream buffer, the stream buffer having a coloring field for each instruction entered.

### Claim 28 (depends on 26)

The method of claim 26 further comprising:
searching the second buffer recursively; and
for each matching record found in the second buffer, each matching record having a corresponding subsequent block entry address, prefetching instructions from each of the corresponding subsequent block entry addresses.

### Claim 29 (depends on 28)

The method of claim 28 wherein prefetching comprises:
entering instructions into a stream buffer, the stream buffer having a coloring field for each instruction entered; and
assigning a different color to instructions fetched from different subsequent block entry addresses.

### Claim 30 (depends on 29)

The method of claim 29 wherein each recursive search represents a predicted branch, the method further comprising flushing from the stream buffer instructions prefetched as a result of a mispredicted branch.
