Method, system and apparatus for generation of global branch history

• US 20080189533A1
• Filed: 02/02/2007
• Published: 08/07/2008
• Est. Priority Date: 02/02/2007
• Status: Active Grant

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Hayashi, Hiroo
• Granted Patent: US 7,565,512 B2
• Time in Patent Office: Days
• US Class Current: 712/240
• CPC Class Codes: G06F 9/3844 using dynamic branch prediction, e.g. using branch history tables
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming

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

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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

9. 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;

10. 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.

11. 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.

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

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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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.

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

20. 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;

21. 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.

22. 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.

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.

24. 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.

25. 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.

26. 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.

27. 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.

28. 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.

29. 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.

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

32. 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;

33. 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.

34. 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.

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.