# US 2008/0189533 A1 · Method, system and apparatus for generation of global branch history

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

- Number: US 2008/0189533 A1
- Document ID: US20080189533A1
- Status: Published application
- Kind: A1
- Application number: 11/701,720
- Filed: 2007-02-02
- Published: 2008-08-07
- Earliest claimed: 2007-02-02
- Assignees: Kabushiki Kaisha Toshiba
- Inventors: Hiroo Hayashi
- Web page: https://patentgrep.com/patent/US20080189533A1

## CPC

- G06F 9/3844: {using dynamic branch prediction, e.g. using branch history tables}
- G06F 9/3851: {from multiple instruction streams, e.g. multistreaming}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Systems, methods and apparatuses for the generation of a global history are disclosed. Embodiments of the present invention may provide logic operable to generate a global history and a global history register operable to store a global history. More specifically, in one embodiment the global history logic comprises a set of multiplexers, each set corresponding to one of a set of instructions fetched in a cycle of a microprocessor, the number of multiplexers in each set equal to the number of bits of global history and each multiplexer within a set having a select signal corresponding to the same instruction to which that set of multiplexers corresponds.

## Claims

### Claim 1

An apparatus for generating a global history; comprising:
a global history register operable to store a first set of bits; and
global history generation logic operable to generate a set of global history bits, the global history logic comprising:
a plurality of sets of multiplexers, each set of multiplexers corresponding to one of a set of instructions fetched during a cycle, wherein each multiplexer in a set of multiplexers has a select signal coupled to a bit of a shift_in signal corresponding to the one of the set of instructions to which the set of multiplexers corresponds, the plurality of sets of multiplexers including a first set of multiplexers comprising a first multiplexer having a first input coupled to a bit of a branch history signal corresponding to the one of the set of instructions to which the first set of multiplexers corresponds and a second input coupled to a first bit of the global history register.

### Claim 2 (depends on 1)

The apparatus of claim 1, wherein the first set of multiplexers comprises at least one multiplexer wherein a first input of the at least one multiplexer is coupled to a second input of a previous multiplexer.

### Claim 3 (depends on 2)

The apparatus of claim 2, wherein the first set of multiplexers comprises a last multiplexer, having a first input coupled to a second input of a previous multiplexer and a second input coupled to a last bit of the global history register.

### Claim 4 (depends on 3)

The apparatus of claim 3, wherein the bit of the branch history signal corresponds to a branch history generated for the one of the set of instructions to which the first set of multiplexers corresponds.

### Claim 5 (depends on 4)

The apparatus of claim 4, wherein the value of the bit of the shift_in signal is based on whether the corresponding instruction is valid and if no previous instruction in the set of instructions is a taken branch and the corresponding instruction is a conditional branch.

### Claim 6 (depends on 4)

The apparatus of claim 4, comprising a second set of multiplexers, each of the second set of multiplexers corresponding to one of the set of global history bits wherein one input of each multiplexer in the second set of multiplexers is a corresponding global history bit generated by the global history logic and a select signal of the multiplexer is a mispredict signal operable to indicate that a branch instruction has been mispredicted.

### Claim 7 (depends on 6)

The apparatus of claim 6, wherein a second input of each of the multiplexers of the second set of multiplexers is a bit of a correct global history.

### Claim 8 (depends on 8)

The apparatus of claim 8, wherein the correct global history is generated by a branch execution unit.

### Claim 9 (depends on 5)

The apparatus of claim 5, wherein whether the corresponding instruction is valid and if any previous instruction in the set of instructions is a not taken branch is determined by logic, comprising:
a first OR gate having a first input coupled to a first predecode bit corresponding to a first instruction of the set of instructions and a second input coupled to a first bit of a branch history corresponding to the first instruction;
a first AND gate having a first input coupled to the second predecode bit corresponding to the first instruction, a second input coupled to the output of the first OR gate and a third input coupled to a first bit of a valid signal corresponding to the first instruction;
a second OR gate having a first input coupled to a first predecode bit corresponding to a second instruction of the set of instructions and a second input coupled to a second bit of a branch history corresponding to the second instruction;
a second AND gate having a first input coupled to the second predecode bit corresponding to the second instruction, a second input coupled to the output of the second OR gate and a third input coupled to a second bit of a valid signal corresponding to the second instruction;
a third OR gate having a first input coupled to a first predecode bit corresponding to a third instruction of the set of instructions and a second input coupled to a third bit of a branch history corresponding to the third instruction;
a third AND gate having a first input coupled to the second predecode bit corresponding to the third instruction, a second input coupled to the output of the third OR gate and a third input coupled to a third bit of a valid signal corresponding to the third instruction;
a fourth OR gate having a first input coupled to an output of the first AND gate and a second input coupled to an output of the second AND gate;
a fifth OR gate having a first input coupled to the output of the first AND, a second input coupled to the second AND gate and a third input coupled to an output of the third AND gate;
a fourth AND gate having a first input coupled to the second bit of the valid signal corresponding to the second instruction and a second input coupled to an output of a first inverter, an input of the first inverter coupled to the output of the first AND gate;
a fifth AND gate having a first input coupled to the third bit of the valid signal corresponding to the third instruction and a second input coupled to an output of a second inverter, an input of the second inverter coupled to the output of the fifth OR gate;
a sixth AND gate having a first input coupled to a fourth bit of the valid signal corresponding to a fourth instruction of the set of instructions and a second input coupled to an output of a third inverter, an input of the third inverter coupled to the output of the sixth OR gate;

### Claim 10 (depends on 5)

The apparatus of claim 5, wherein whether the corresponding instruction is a conditional branch is determined by logic, comprising:
a seventh AND gate having a first input coupled to a second predecode bit corresponding to the first instruction and a second input coupled to the output of a fourth inverter, an input of the fourth inverter coupled to a first predecode bit corresponding to the first instruction;
an eighth AND gate having a first input coupled to a second predecode bit corresponding to the second instruction and a second input coupled to the output of a fifth inverter, an input of the fifth inverter coupled to a first predecode bit corresponding to the second instruction;
a ninth AND gate having a first input coupled to a second predecode bit corresponding to the third instruction and a second input coupled to the output of a sixth inverter, an input of the sixth inverter coupled to a first predecode bit corresponding to the third instruction; and
a tenth AND gate having a first input coupled to a second predecode bit corresponding to the fourth instruction and a second input coupled to the output of a seventh inverter, an input of the seventh inverter coupled to a first predecode bit corresponding to the fourth instruction.

### Claim 11 (depends on 10)

The apparatus of claim 10, wherein the shift_in signal is generated by logic, comprising:
an AND gate operable to logically and the output of the seventh AND gate and the first bit of the valid signal to produce a first bit of the shift_in signal, logically and the output of the eighth AND gate and the output of the fourth AND gate to produce a second bit of the shift_in signal, logically and the output of the ninth AND gate and the output of the fifth AND gate to produce a third bit of the shift_in signal and logically and the output of the tenth AND gate and the output of the sixth AND gate to produce a fourth bit of the shift_in signal.

### Claim 12

A method for generating a global history; comprising:
generating a set of global history bits; and
storing the set of global history bits in a global history register operable to store a first set of bits, wherein the global history bits are generated by global history logic, comprising:
a plurality of sets of multiplexers, each set of multiplexers corresponding to one of a set of instructions fetched during a cycle, wherein each multiplexer in a set of multiplexers has a select signal coupled to a bit of a shift_in signal corresponding to the one of the set of instructions to which the set of multiplexers corresponds, the plurality of sets of multiplexers including a first set of multiplexers comprising a first multiplexer having a first input coupled to a first bit of a branch history signal corresponding to the one of the set of instructions to which the first set of multiplexers corresponds and a second input coupled to a first bit of the global history register.

### Claim 13 (depends on 12)

The method of claim 12, wherein the first set of multiplexers comprises at least one multiplexer wherein a first input of the at least one multiplexer is coupled to a second input of a previous multiplexer.

### Claim 14 (depends on 13)

The method of claim 13, wherein the first set of multiplexers comprises a last multiplexer, having a first input coupled to a first bit of a branch history signal corresponding to the one of the set of instructions to which the first set of multiplexers corresponds and a second input coupled to a last bit of the global history register.

### Claim 15 (depends on 14)

The method of claim 14, wherein the first bit of the branch history signal corresponds to a branch history generated for the one of the set of instructions to which the first set of multiplexers corresponds.

### Claim 16 (depends on 15)

The method of claim 15, wherein the value of the bit of the shift_in signal is based on whether the corresponding instruction is valid and if no previous instruction in the set of instructions is a taken branch and the corresponding instruction is a conditional branch.

### Claim 17 (depends on 15)

The method of claim 15, wherein a second set of multiplexers, each of the second set of multiplexers corresponding to one of the set of global history bits wherein one input of each multiplexer is corresponding global history bit generated by the global history logic and a select signal of the multiplexer is a mispredict signal operable to indicate that a branch instruction has been mispredicted.

### Claim 18 (depends on 17)

The method of claim 17, wherein a second input of each of the multiplexers of the second set of multiplexers is a bit of a correct global history.

### Claim 19 (depends on 18)

The method of claim 18, wherein the correct global history is generated by a branch execution unit.

### Claim 20 (depends on 16)

The method of claim 16, further comprising determining whether the corresponding instruction is valid and if any previous instruction in the set of instructions is a not taken branch using logic comprising:
a first OR gate having a first input coupled to a first predecode bit corresponding to a first instruction of the set of instructions and a second input coupled to a first bit of a branch history corresponding to the first instruction;
a first AND gate having a first input coupled to the second predecode bit corresponding to the first instruction, a second input coupled to the output of the first OR gate and a third input coupled to a first bit of a valid signal corresponding to the first instruction;
a second OR gate having a first input coupled to a first predecode bit corresponding to a second instruction of the set of instructions and a second input coupled to a second bit of a branch history corresponding to the second instruction;
a second AND gate having a first input coupled to the second predecode bit corresponding to the second instruction, a second input coupled to the output of the second OR gate and a third input coupled to a second bit of a valid signal corresponding to the second instruction;
a third OR gate having a first input coupled to a first predecode bit corresponding to a third instruction of the set of instructions and a second input coupled to a third bit of a branch history corresponding to the third instruction;
a third AND gate having a first input coupled to the second predecode bit corresponding to the third instruction, a second input coupled to the output of the third OR gate and a third input coupled to a third bit of a valid signal corresponding to the third instruction;
a fourth OR gate having a first input coupled to an output of the first AND gate and a second input coupled to an output of the second AND gate;
a fifth OR gate having a first input coupled to the output of the first AND, a second input coupled to the second AND gate and a third input coupled to an output of the third AND gate;
a fourth AND gate having a first input coupled to the second bit of the valid signal corresponding to the second instruction and a second input coupled to an output of a first inverter, an input of the first inverter coupled to the output of the first AND gate;
a fifth AND gate having a first input coupled to the third bit of the valid signal corresponding to the third instruction and a second input coupled to an output of a second inverter, an input of the second inverter coupled to the output of the fifth OR gate;
a sixth AND gate having a first input coupled to a fourth bit of the valid signal corresponding to a fourth instruction of the set of instructions and a second input coupled to an output of a third inverter, an input of the third inverter coupled to the output of the sixth OR gate;

### Claim 21 (depends on 16)

The method of claim 16, further comprising determining whether the corresponding instruction is a conditional branch using logic comprising:
a seventh AND gate having a first input coupled to a second predecode bit corresponding to the first instruction and a second input coupled to the output of a fourth inverter, an input of the fourth inverter coupled to a first predecode bit corresponding to the first instruction;
an eighth AND gate having a first input coupled to a second predecode bit corresponding to the second instruction and a second input coupled to the output of a fifth inverter, an input of the fifth inverter coupled to a first predecode bit corresponding to the second instruction;
a ninth AND gate having a first input coupled to a second predecode bit corresponding to the third instruction and a second input coupled to the output of a sixth inverter, an input of the sixth inverter coupled to a first predecode bit corresponding to the third instruction; and
a tenth AND gate having a first input coupled to a second predecode bit corresponding to the fourth instruction and a second input coupled to the output of a seventh inverter, an input of the seventh inverter coupled to a first predecode bit corresponding to the fourth instruction.

### Claim 22 (depends on 21)

The method of claim 21, further comprising determining the shift_in signal using logic comprising:
an AND gate operable to logically and the output of the seventh AND gate and the first bit of the valid signal to produce a first bit of the shift_in signal, logically and the output of the eighth AND gate and the output of the fourth AND gate to produce a second bit of the shift_in signal, logically and the output of the ninth AND gate and the output of the fifth AND gate to produce a third bit of the shift_in signal and logically and the output of the tenth AND gate and the output of the sixth AND gate to produce a fourth bit of the shift_in signal.

### Claim 23

An system, comprising:
an instruction fetch unit operable to fetch a set of instructions;
a branch history table operable to generate a branch history bit for each of the set of instructions;
logic operable to generate a shift-in signal, the shift in signal comprising a set of shift_in bits, each shift_in bit corresponding to one of the set of instructions;
a global history register operable to store a first set of bits; and
global history generation logic operable to generate a set of global history bits, the global history logic comprising:
a plurality of sets of multiplexers, each set of multiplexers corresponding to one of the set of instructions, wherein each multiplexer in a set of multiplexers has a select signal coupled to the bit of the shift_in signal corresponding to the one of the set of instructions, the plurality of sets of multiplexers including a first set of multiplexers comprising a first multiplexer having a first input coupled to the branch history bit corresponding to the one of the set of instructions to which the first set of multiplexers corresponds and a second input coupled to a first bit of the global history register.

### Claim 24 (depends on 23)

The system of claim 23, wherein the first set of multiplexers comprises at least one second multiplexer wherein a first input of the at least one second multiplexer is coupled to a second input of a previous multiplexer.

### Claim 25 (depends on 24)

The system of claim 24, wherein the first set of multiplexers comprises a last multiplexer, having a first input coupled to a second input of one of the at least one second multiplexers and a second input coupled to a last bit of the global history register.

### Claim 26 (depends on 25)

The system of claim 25, wherein the first bit of the branch history signal corresponds to a branch history generated for the one of the set of instructions to which the first set of multiplexers corresponds.

### Claim 27 (depends on 26)

The system of claim 26, wherein the value of the bit of the shift_in signal is based on whether the corresponding instruction is valid and if no previous instruction in the set of instructions is a taken branch and the corresponding instruction is a conditional branch.

### Claim 28 (depends on 26)

The system of claim 26, wherein a second set of multiplexers, each of the second set of multiplexers corresponding to one of the set of global history bits wherein one input of each multiplexer is corresponding global history bit generated by the global history logic and a select signal of the multiplexer is a mispredict signal operable to indicate that a branch instruction has been mispredicted.

### Claim 29 (depends on 28)

The system of claim 28, wherein a second input of each of the multiplexers of the second set of multiplexers is a bit of a correct global history.

### Claim 31 (depends on 29)

The system of claim 29, wherein the correct global history is generated by a branch execution unit.

### Claim 32 (depends on 27)

The system of claim 27, wherein whether the corresponding instruction is valid and if any previous instruction in the set of instructions is a not taken branch is determined by logic, comprising:
a first OR gate having a first input coupled to a first predecode bit corresponding to a first instruction of the set of instructions and a second input coupled to a first bit of a branch history corresponding to the first instruction;
a first AND gate having a first input coupled to the second predecode bit corresponding to the first instruction, a second input coupled to the output of the first OR gate and a third input coupled to a first bit of a valid signal corresponding to the first instruction;
a second OR gate having a first input coupled to a first predecode bit corresponding to a second instruction of the set of instructions and a second input coupled to a second bit of a branch history corresponding to the second instruction;
a second AND gate having a first input coupled to the second predecode bit corresponding to the second instruction, a second input coupled to the output of the second OR gate and a third input coupled to a second bit of a valid signal corresponding to the second instruction;
a third OR gate having a first input coupled to a first predecode bit corresponding to a third instruction of the set of instructions and a second input coupled to a third bit of a branch history corresponding to the third instruction;
a third AND gate having a first input coupled to the second predecode bit corresponding to the third instruction, a second input coupled to the output of the third OR gate and a third input coupled to a third bit of a valid signal corresponding to the third instruction;
a fourth OR gate having a first input coupled to an output of the first AND gate and a second input coupled to an output of the second AND gate;
a fifth OR gate having a first input coupled to the output of the first AND, a second input coupled to the second AND gate and a third input coupled to an output of the third AND gate;
a fourth AND gate having a first input coupled to the second bit of the valid signal corresponding to the second instruction and a second input coupled to an output of a first inverter, an input of the first inverter coupled to the output of the first AND gate;
a fifth AND gate having a first input coupled to the third bit of the valid signal corresponding to the third instruction and a second input coupled to an output of a second inverter, an input of the second inverter coupled to the output of the fifth OR gate;
a sixth AND gate having a first input coupled to a fourth bit of the valid signal corresponding to a fourth instruction of the set of instructions and a second input coupled to an output of a third inverter, an input of the third inverter coupled to the output of the sixth OR gate;

### Claim 33 (depends on 27)

The system of claim 27, wherein whether the corresponding instruction is a conditional branch is determined by logic, comprising:
a seventh AND gate having a first input coupled to a second predecode bit corresponding to the first instruction and a second input coupled to the output of a fourth inverter, an input of the fourth inverter coupled to a first predecode bit corresponding to the first instruction;
an eighth AND gate having a first input coupled to a second predecode bit corresponding to the second instruction and a second input coupled to the output of a fifth inverter, an input of the fifth inverter coupled to a first predecode bit corresponding to the second instruction;
a ninth AND gate having a first input coupled to a second predecode bit corresponding to the third instruction and a second input coupled to the output of a sixth inverter, an input of the sixth inverter coupled to a first predecode bit corresponding to the third instruction; and
a tenth AND gate having a first input coupled to a second predecode bit corresponding to the fourth instruction and a second input coupled to the output of a seventh inverter, an input of the seventh inverter coupled to a first predecode bit corresponding to the fourth instruction.

### Claim 34 (depends on 33)

The system of claim 33, wherein the shift_in signal is generated by logic, comprising:
an AND gate operable to logically and the output of the seventh AND gate and the first bit of the valid signal to produce a first bit of the shift_in signal, logically and the output of the eighth AND gate and the output of the fourth AND gate to produce a second bit of the shift_in signal, logically and the output of the ninth AND gate and the output of the fifth AND gate to produce a third bit of the shift_in signal and logically and the output of the tenth AND gate and the output of the sixth AND gate to produce a fourth bit of the shift_in signal.

### Claim 35

An apparatus for generating a global history; comprising:
a global history register operable to store a first set of bits; and
global history generation logic operable to generate a set of global history bits, the global history logic comprising:
a plurality of sets of multiplexers, each set of multiplexers corresponding to one of a set of instructions fetched during a cycle, wherein each multiplexer in a set of multiplexers has a select signal coupled to a bit of a signal line corresponding to the one of the set of instructions to which the set of multiplexers corresponds, the plurality of sets of multiplexers including:
a first set of multiplexers, comprising:
a first multiplexer having a first input coupled to a first bit of a branch history signal corresponding to the one of the set of instructions to which the first set of multiplexers corresponds and a second input coupled to a first bit of the global history register, and
a second multiplexer having a first input coupled to a first bit of the global history register and a second input coupled to a second bit of the global history register; and
a second set of multiplexers, comprising:
a first multiplexer having a first input coupled to a second bit of a branch history signal corresponding to the one of the set of instructions to which the second set of multiplexers corresponds and a second input coupled to the output of the first multiplexer of the first set of multiplexers, and
a second multiplexer having a first input coupled to the output of the first multiplexer of the first set of multiplexers and a second input coupled to the output of the second multiplexer of the first set of multiplexers.