# US 10,481,912 B2 · Variable branch target buffer (BTB) line size for compression

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

- Number: US 10,481,912 B2
- Document ID: US10481912B2
- Status: Granted
- Kind: B2
- Application number: 15/191,783
- Filed: 2016-06-24
- Published: 2017-12-28
- Granted: 2019-11-19
- Earliest claimed: 2016-06-24
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: James J. Bonanno; Michael J. Cadigan, Jr.; Brian R. Prasky
- Web page: https://patentgrep.com/patent/US10481912B2

## CPC

- G06F 9/3806: {using address prediction, e.g. return stack, branch history buffer}
- G06F 9/30058: {Conditional branch instructions}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Embodiments include method, systems and computer program products for variable branch target buffer line size for compression. In some embodiments, a branch target buffer (BTB) congruence class for a line of a first parent array of a BTB may be determined. A threshold indicative of a maximum number branches to be stored in the line may be set. A branch may be received to store in the line of the first parent array. A determination may be made that storing the branch in the line would exceed the threshold and the line can be responsively split into an even half line and an odd half line.

## Claims

### Claim 1

A system comprising:
a branch target buffer (BTB); and
a processing circuit coupled to the branch target buffer, the processing circuit configured to perform a method comprising:
determining a BTB congruence class for a line of a first parent array of the BTB, wherein the BTB congruence class includes a hash, and
wherein the BTB comprises at least two levels of associativity based on the BTB congruence class;
setting a threshold indicative of a maximum number branches to be stored in the line;
receiving a branch to store in the line of the first parent array;
determining that storing the branch in the line would exceed the threshold; and
splitting the line into an even half line and an odd half line responsive to determining that storing the branch in the line would exceed the threshold, wherein the branch is stored in a second parent array based on an address of a branching mapping to either the even half line or the odd half line; and
reinstalling entries to a newly allocated parent array when a branch is detected in a pipeline, which was not found by a branch predictor upon earlier searching of the pipeline.

### Claim 2 (depends on 1)

The system of claim 1, wherein the even half line and the odd half line are each stored in a different parent array.

### Claim 3 (depends on 1)

The system of claim 1, wherein the second parent array has a size that is half of the first parent array.

### Claim 4 (depends on 1)

The system of claim 1, wherein the processing circuit is further configured to perform:
moving entries from the first parent array to the second parent array.

### Claim 5 (depends on 1)

The system of claim 1, wherein an index into the second parent array uses a different hash than an index into the first parent array.

### Claim 6

A computer-implemented method comprising:
determining a branch target buffer (BTB) congruence class for a line of a first parent array of a BTB, wherein the BTB congruence class includes a hash, and
wherein the BTB comprises at least two levels of associativity based on the BTB congruence class;
setting a threshold indicative of a maximum number branches to be stored in the line;
receiving a branch to store in the line of the first parent array;
determining that storing the branch in the line would exceed the threshold;
splitting the line into an even half line and an odd half line responsive to determining that storing the branch in the line would exceed the threshold, wherein the branch is stored in a second parent array based on an address of a branching mapping to either the even half line or the odd half line; and
reinstalling entries to a newly allocated parent array when a branch is detected in a pipeline, which was not found by a branch predictor upon earlier searching of the pipeline.

### Claim 7 (depends on 6)

The computer-implemented method of claim 6, wherein the even half line and the odd half line are each stored in a different parent array.

### Claim 8 (depends on 6)

The computer-implemented method of claim 6, wherein the second parent array has a size that is half of the first parent array.

### Claim 9 (depends on 6)

The computer-implemented method of claim 6, further comprising:
moving entries from the first parent array to the second parent array.

### Claim 10 (depends on 6)

The computer-implemented method of claim 6, wherein an index into the second parent array uses a different hash than an index into the first parent array.

### Claim 11

A computer program product, the computer program product comprising:
a tangible storage medium readable by a processing circuit and storing instructions for execution by the processing circuit for performing a method comprising:
determining a branch target buffer (BTB) congruence class for a line of a first parent array of a BTB, wherein the BTB congruence class includes a hash, and
wherein the BTB comprises at least two levels of associativity based on the BTB congruence class;
setting a threshold indicative of a maximum number branches to be stored in the line;
receiving a branch to store in the line of the first parent array;
determining that storing the branch in the line would exceed the threshold;
splitting the line into an even half line and an odd half line responsive to determining that storing the branch in the line would exceed the threshold, wherein the branch is stored in a second parent array based on an address of a branching mapping to either the even half line or the odd half line; and
reinstalling entries to a newly allocated parent array when a branch is detected in a pipeline, which was not found by a branch predictor upon earlier searching of the pipeline.

### Claim 12 (depends on 11)

The computer program product of claim 11, wherein the even half line and the odd half line are each stored in a different parent array.

### Claim 13 (depends on 11)

The computer program product of claim 11, wherein the second parent array has a size that is half of the first parent array.

### Claim 14 (depends on 11)

The computer program product of claim 11, wherein the method further comprises: moving entries from the first parent array to the second parent array.