Method and apparatus for updating global branch history information

• US 20060149951A1
• Filed: 12/15/2004
• Published: 07/06/2006
• Est. Priority Date: 12/15/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Heil, Timothy H., Bradford, Jeffrey P., Dale, Jason N., Abernathy, Chris M.
• Granted Patent: US 7,454,602 B2
• Time in Patent Office: Days
• US Class Current: 712/240
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques

Abstract

A method and apparatus for updating global branch history information are disclosed. A dynamic branch predictor within a data processing system includes a global branch history (GBH) buffer and a branch history table. The GBH buffer contains GBH information of a group of the most recent branch instructions. The branch history table includes multiple entries, each entry is associated with one or more branch instructions. The GBH information from the GBH buffer can be used to index into the branch history table to obtain a branch prediction signal. In response to a fetch group of instructions, a fixed number of GBH bits is shifted into the GBH buffer. The number of GBH bits is the same regardless of the number of branch instructions within the fetch group of instructions. In addition, there is a unique bit pattern associated with the case of no taken branch in the fetch group, regardless of the number of not-taken branches of even if there are any branches in the fetch group.

Claims

1. A method for updating global branch history (GBH) information, said method comprising:

providing a branch history table having a plurality of entries, each entry is associated with a branch instruction;

providing a global branch history buffer to contain GBH information of a plurality of most recent branch instructions, wherein said GBH information to used to index to said branch history table to obtain a prediction signal; and

in response to a fetch group of instructions, shifting zero, one or more GBH bits into said global branch history buffer, wherein a fetch group containing or predicted to contain no taken branch is represented by the same pattern of said GBH bits regardless of the number of branch instructions within said fetch group of instructions.

2. The method of claim 1, wherein said branch prediction takes multiple processor cycles.

3. The method of claim 2, wherein said processor fetches along a not-taken path each cycle until said branch predictions from an earlier fetch groups are known.

4. The method of claim 2, wherein said processor uses a fast single-cycle predictor to follow taken paths until said branch predictions from an earlier fetch groups are known;

and, in the case where said fast single-cycle predictor indicates a taken path should be followed, said fast single-cycle predictor also indicates the pattern to be shifted into said GBH.

5. The method of claim 4, wherein said fast single-cycle predictor contains a branch target buffer to predict target addresses.

6. The method of claim 1, wherein the number of GBH bits in said shifting depends on characteristics of instructions within a fetch group.

7. The method of claim 6, wherein said characteristic include whether or not an instruction is a branch instruction, whether or not said branch instruction is taken, and/or whether or not said branch instruction is conditional.

8. The method of claim 1, wherein said method further includes maintaining a “

front-end”

version of GBH bits in an early stage of a pipeline before branch instructions have been resolved to read said global branch history buffer, and maintaining a “

back-end”

version of said GBH bits in a late stage of said pipeline after said branch instructions have been resolved to update said global branch history buffer and/or said global branch history table.

9. An apparatus for updating global branch history (GBH) information within a data processing system, said apparatus comprising:

a branch history table having a plurality of entries, each entry is associated with a branch instruction;

a global branch history buffer contains GBH information of a plurality of most recent branch instructions, wherein said GBH information to used to index to said branch history table to obtain a prediction signal; and

means for immediately shifting zero, one or more of GBH bits into said global branch history buffer, in response to a fetch group of instructions, wherein a fetch group containing or predicted to contain no taken branch is represented by the same pattern of said GBH bits regardless of the number of branch instructions within said fetch group of instructions.

10. The apparatus of claim 9, wherein said global branch history buffer is an n-bit wide shift register containing GBH information of p most recent branch instructions.

11. The apparatus of claim 9, wherein the number of GBH bits in said shifting depends on characteristics of instructions within a fetch group.

12. The apparatus of claim 11, wherein said characteristic include whether or not an instruction is a branch instruction, whether or not said branch instruction is taken, and/or whether or not said branch instruction is conditional.

13. The apparatus of claim 9, wherein said apparatus further includes means for maintaining a “

front-end”

version of GBH bits in an early stage of a pipeline before branch instructions have been resolved to read said global branch history buffer, and maintaining a “

back-end”

version of said GBH bits in a late stage of said pipeline after said branch instructions have been resolved to update said global branch history buffer and/or said global branch history table.

14. A computer program product residing on a computer usable medium for updating global branch history (GBH) information within a data processing system, said computer program product comprising:

program code means for providing a branch history table having a plurality of entries, each entry is associated with a branch instruction;

program code means for providing a global branch history buffer contains GBH information of a plurality of most recent branch instructions, wherein said GBH information to used to index to said branch history table to obtain a prediction signal; and

program code means for immediately shifting zero, one or more of GBH bits into said global branch history buffer, in response to a fetch group of instructions, wherein a fetch group containing or predicted to contain no taken branch is represented by the same pattern of said GBH bits regardless of the number of branch instructions within said fetch group of instructions.

15. The computer program product of claim 14, wherein said global branch history buffer is an n-bit wide shift register containing GBH information of p most recent branch instructions.

16. The computer program product of claim 14, wherein the number of GBH bits in said shifting depends on characteristics of instructions within a fetch group.

17. The computer program product of claim 16, wherein said characteristic include whether or not an instruction is a branch instruction, whether or not said branch instruction is taken, and/or whether or not said branch instruction is conditional.

18. The computer program product of claim 14, wherein said computer program product further includes program code means for maintaining a “

front-end”

version of GBH bits in an early stage of a pipeline before branch instructions have been resolved to read said global branch history buffer, and maintaining a “

back-end”

version of said GBH bits in a late stage of said pipeline after said branch instructions have been resolved to update said global branch history buffer and/or said global branch history table.