# US 2010/0169626 A1 · System and method for a multi-schema branch predictor

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

- Number: US 2010/0169626 A1
- Document ID: US20100169626A1
- Status: Published application
- Kind: A1
- Application number: 12/615,108
- Filed: 2009-11-09
- Published: 2010-07-01
- Earliest claimed: 2008-12-25
- Assignees: STMicroelectronics R&D Co. Ltd. (Beijing)
- Inventors: Kai-Feng WANG; Hong-Xia Sun
- Web page: https://patentgrep.com/patent/US20100169626A1

## CPC

- G06F 9/3806: {using address prediction, e.g. return stack, branch history buffer}
- 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

A system and method for predicting the execution of a branch of computer-executable instructions. In an embodiment, a branch predictor may include a program-counter register operable to store a program-counter value and a branch-history register operable to store a branch-history value. Additionally, the branch predictor may include a prediction hash table having a plurality of prediction values each uniquely corresponding to a plurality of memory locations. With these components, the branch predictor may generate a first prediction value that corresponds to the program-counter value and may generate a second prediction value that corresponds to a logical combination of the program-counter value and the branch-history value. With these two prediction values obtained from two different prediction schemas, the branch predictor is better suited to generate an overall prediction value based on the first and second prediction values that is more accurate than a single prediction value based upon a single prediction schema.

## Claims

### Claim 1

A computing module, comprising;
a first branch prediction module operable to generate a first prediction value corresponding to a branch prediction according to a first branch prediction schema;
a second branch prediction module operable to generate a second prediction value corresponding to a branch prediction according to a second branch prediction schema; and
a computation module operable to generate a third prediction value corresponding to a mathematical computation based upon the first branch prediction value and the second branch prediction value.

### Claim 2 (depends on 1)

The computing module of claim 1 wherein the first prediction schema comprises generation of a prediction value corresponding to a program-counter value the second prediction schema comprises generation of a prediction value corresponding to a logical combination of the program-counter value and another value.

### Claim 3 (depends on 2)

The computing module of claim 2 wherein the logical combination further comprises an XOR function of the program-counter value and a branch-history value.

### Claim 4 (depends on 1)

The computing module of claim 1, further comprising a prediction hash table operable to store a plurality of prediction values each corresponding uniquely to a memory location.

### Claim 5 (depends on 1)

The computing module of claim 1, further comprising a history register operable to store a plurality of bits, each bit corresponding to a previous execution of a branch.

### Claim 6 (depends on 5)

The computing module of claim 5, further comprising a shift register coupled to the branch-history register, the shift register operable to shift a bit value into a least significant bit of the history register based on the execution of a branch.

### Claim 8 (depends on 1)

The computing module of claim 1, further comprising an execution module operable to begin executing instruction in response to the third prediction value meeting a predetermined condition.

### Claim 9 (depends on 1)

The computing module of claim 1 wherein the first prediction schema comprises generation of a prediction value corresponding to a first value the second prediction schema comprises generation of a prediction value corresponding to a logical combination of the first value, a second value and a third value.

### Claim 10 (depends on 1)

The computing module of claim 1, further comprising:
a third branch prediction module operable to generate a fourth prediction value corresponding to a branch prediction according to a third branch prediction schema; and wherein
the computation module is further operable to generate the third prediction value corresponding to a mathematical computation based upon the first branch prediction value, the second branch prediction value, and the fourth branch prediction value.

### Claim 11

A method for predicting executing a branch instruction, the method comprising:
generating a first interim prediction value based upon a first prediction schema;
generating a second interim branch prediction value based upon a second branch prediction schema;
calculating a final branch prediction value based upon the first and second interim branch prediction values; and
executing the branch instruction if the final branch prediction meets a predetermined condition.

### Claim 12 (depends on 11)

The method of claim 11 wherein the generating the first prediction value further comprises retrieving a prediction value from a prediction hash table based upon identifying a memory location corresponding to a program-counter value.

### Claim 13 (depends on 11)

The method of claim 11 wherein the generating the second prediction value further comprises retrieving a prediction value from a prediction hash table based upon identifying a memory location corresponding to a mathematical combination of a program-counter value and a branch-history value.

### Claim 14 (depends on 11)

The method of claim 11 further comprising executing the branch instruction if the final predication value is equal to or greater than two.

### Claim 15 (depends on 11)

The method of claim 11, further comprising:
determining whether the branch instruction has been executed; and
updating the prediction value stored in the prediction hash table corresponding to the executed branch instruction.

### Claim 16 (depends on 15)

The method of claim 15, further comprising:
incrementing the stored prediction value if the associated branch instruction is executed; and
decrementing the stored prediction value if the associated branch instruction is not executed.

### Claim 17 (depends on 11)

The method of claim 11, further comprising:
determining whether the branch instruction has been executed; and
updating a branch-history value stored in a branch-history register by shifting a bit value into the branch-history register.

### Claim 18 (depends on 15)

The method of claim 15, further comprising shifting a bit value of one if the branch instruction is ultimately executed and shifting a bit value of zero if the branch instruction is not ultimately executed.

### Claim 19

A branch predictor, comprising:
a program-counter register operable to store a program-counter value;
a branch-history register operable to store a branch-history value;
a prediction hash table having a plurality of prediction values each uniquely corresponding to a plurality of memory locations; and
a prediction component operable to:
receive a first prediction value associated with a first memory location that corresponds to the program-counter value;
receive a second prediction value associated with a second memory location that corresponds to a logical combination of the program-counter value and the branch-history value; and
generate an overall prediction value based on the first and second prediction values.

### Claim 20 (depends on 19)

The branch predictor of claim 19, wherein the prediction hash table comprises a plurality of index values each corresponding uniquely to a respective memory location and associated prediction value, wherein each prediction value comprises a binary value of 0, 1, 2, or 3.

### Claim 21 (depends on 19)

The branch predictor of claim 19, wherein the generation of the final value is based on a summing function of the first and second prediction values.

### Claim 22 (depends on 19)

The branch predictor of claim 19, wherein the generation of the final value is based on an averaging function of the first and second prediction values.

### Claim 23

A pipeline processor, comprising
a processor controller; and
a processor having a branch predictor coupled to the controller, the branch predictor further comprising:
a first branch prediction module operable to generate a first prediction value corresponding to a branch prediction according to a first branch prediction schema;
a second branch prediction module operable to generate a second prediction value corresponding to a branch prediction according to a second branch prediction schema; and
a computation module operable to generate a third prediction value corresponding to a mathematical computation based upon the first branch prediction value and the second branch prediction value.

### Claim 24 (depends on 23)

The pipeline processor of claim 23 further comprising a single integrated circuit chip.

### Claim 25

A computer system, comprising:
a processing unit;
a memory coupled to the processing unit via a system bus; and
a pipeline processor disposed as part of the processing unit and operable to communicate with the memory, the pipeline processor further operable to predict the execution of a branch of instructions, by:
generating a first interim prediction value based upon a first prediction schema;
generating a second interim branch prediction value based upon a second branch prediction schema;
calculating a final branch prediction value based upon the first and second interim branch prediction values; and
communicating an instruction to execute the branch of instructions if the final branch prediction value exceeds a threshold.

### Claim 26

A computer-readable medium having computer-executable instructions for:
generating a first interim prediction value based upon a first prediction schema;
generating a second interim branch prediction value based upon a second branch prediction schema;
calculating a final branch prediction value based upon the first and second interim branch prediction values; and
executing the branch instruction if the final branch prediction meets a predetermined condition.
