Global History Branch Prediction Updating Responsive to Taken Branches

• US 20090198984A1
• Filed: 01/31/2008
• Published: 08/06/2009
• Est. Priority Date: 01/31/2008
• Status: Active Grant

• Current Assignee: MACOM Connectivity Solutions, LLC (MACOM Technology Solutions Holdings, Inc.)
• Original Assignee: Applied Micro Circuits Corporation (MACOM Technology Solutions Holdings, Inc.)
• Inventors: Potter, Terrence Matthew, Loschke, Jon A., Olson, Timothy A.
• Granted Patent: US 7,844,806 B2
• Time in Patent Office: Days
• US Class Current: 712/240
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques

Abstract

A system and method are provided for updating a global history prediction record in a microprocessor system using pipelined instruction processing. The method accepts a microprocessor instruction of consecutive operations, including a conditional branch operation with an associated branch address, at a first stage in a pipelined microprocessor execution process. A global history record (GHR) of conditional branch resolutions and predictions is accessed and hashed with the branch address, creating a first hash result. The first hash result is used to access an indexed branch history table (BHT) of branch direction counts and the BHT is used to make a branch prediction. If the branch prediction being “taken”, the current GHR value is left-shifted and hashed with the branch address, creating a second hash result which is used in creating an updated GHR.

Claims

1. In a microprocessor system using pipelined instruction processing, a method for updating a global history prediction record, the method comprising:

accepting a first microprocessor instruction of consecutive operations, including a first conditional branch operation with an associated first branch address, at a first stage in a pipelined microprocessor execution process;

accessing a current value from a global history record (GHR) of conditional branch resolutions and predictions;

hashing the current global history record value with the first branch address, creating a first hash result;

using the first hash result to access an indexed branch history table (BHT) of branch direction counts;

using the BHT, making a first branch prediction;

in response to the first branch prediction being “

taken”

, left-shifting the current GHR value;

hashing the left-shifted GHR with the first branch address, creating a second hash result; and

,

using the second hash result, creating an updated GHR.

2. The method of claim 1 wherein accepting the first microprocessor instruction of consecutive operations at the first stage in the pipelined microprocessor execution process includes accepting the first microprocessor instruction at a fetch stage;

wherein accessing the GHR includes accessing a speculative GHS (SGHR); and

,

wherein creating the updated GHR includes creating an updated SGHR.

3. The method of claim 1 wherein accepting the first microprocessor instruction of consecutive operations at the first stage in the pipelined microprocessor execution process includes accepting the first microprocessor instruction at a branch resolution stage;

wherein accessing the GHR includes accessing a non-speculative GHS; and

,

wherein creating the updated GHR includes creating an updated non-speculative GHR.

4. The method of claim 1 further comprising:

flushing subsequently accepted microprocessor instructions processed in dependence upon a first branch prediction selected from a group consisting of a “

taken”

prediction resolved as “

not taken” and

a “

not taken”

prediction resolved as “

taken”

.

5. The method of claim 1 wherein creating the first hash result includes performing an exclusive-OR (XOR) operation between a number representing the current global history record value and a number representing the first branch address.

6. The method of claim 1 wherein creating the second hash result includes performing an XOR operation between a number representing the left-shifted global history record and a number representing the first branch address.

7. The method of claim 6 wherein performing the XOR operation between the number representing the left-shifted global history record and the number representing the first branch address includes:

replacing the least significant bit (LSB) of the left-shifted GHR with a first value;

XORing the first value with the m least significant bits of the first branch address, creating the first result; and

,

replacing the m LSBs of the left-shifted GHR with the first result.

8. The method of claim 1 wherein using the first hash result to index the BHT includes indexing a count of the n-most recent first branch resolutions.

9. The method of claim 7 further comprising:

updating the BHT with a count associated with the first branch resolution.

10. The method of claim 8 wherein using the first hash result to index the BHT of previous branch direction counts includes indexing a BHT indicating a degree of confidence in the assumption that the first branch is “

taken”

.

11. The method of claim 1 wherein accepting the first microprocessor instruction of consecutive operations includes accepting the first conditional branch operation with a static prediction bit;

wherein making the first branch prediction using the BHT includes;

comparing the first branch prediction with the static prediction bit;

if the first branch prediction agrees with the static prediction bit, using the static prediction bit as the first branch prediction; and

,

if the first branch prediction disagrees with the static prediction bit, using a static prediction bit opposite value as the first branch prediction.

12. A pipelined instruction microprocessor system with a global history prediction record, the system comprising:

a pipeline including a plurality of sequential stages for parallel processing microprocessor instructions, each microprocessor instruction including a plurality of consecutive operations, the pipeline including a first stage for processing a first conditional branch operation from a first microprocessor instruction;

a sequencer with an interface for accessing the pipelined stages and processing the operations;

a first address register containing a first branch address associated with the first conditional branch operation;

a global history record (GHR) having an output to supply a current GHR value associated with a history of conditional branch resolutions and predictions;

a first hashing circuit having an input to accept the current GHR value, an input to accept the first branch address, and an output to provide a first hash result;

a branch history table (BHT) having an input to accept the first hash result, the BHT indexing a first branch direction counter associated with the first hash result and providing a first branch prediction;

a second hashing circuit having a register to accept the current GHR value in response to a first branch prediction of “

taken”

, left-shifting the current GHR value, hashing the left-shifted GHR with the first branch address to create a second hash result, and supplying the second hash to the GHR as an updated GHR value.

13. The system of claim 12 wherein the pipeline accepts the first microprocessor instruction at a fetch stage;

and,

wherein the GHR is a speculative GHS (SGHR).

14. The system of claim 12 wherein the pipeline accepts the first microprocessor instruction at a branch resolution stage;

and,

wherein the GHR is a non-speculative GHS.

15. The system of claim 12 wherein the pipeline accepts the first microprocessor instruction at an execute stage, resolves the first branch prediction, and flushes microprocessor instructions accepted subsequent to the first microprocessor instruction, processed in dependence upon a first branch prediction selected from a group consisting of a “

taken”

prediction resolved as “

not taken” and

a “

not taken”

prediction resolved as “

taken”

.

16. The system of claim 12 wherein the first hash circuit performs an exclusive-OR (XOR) operation between a number representing the current GHR value and a number representing the first branch address.

17. The system of claim 12 wherein the second hash circuit performs an XOR operation between a number representing the left-shifted global history record and a number representing the first branch address.

18. The system of claim 17 wherein the second hash circuit left shifts the current GHR value in the register, replaces the least significant bit (LSB) with a first value, XORs the first value with the m LSBs of the first branch address to create a first result, and replaces the m LSBs in the register with the first result to create the updated GHR.

19. The system of claim 12 wherein the BHT includes a count of the n-most recent first branch resolutions.

20. The system of claim 19 wherein the BHT is updated with a count associated with the first branch resolution.

21. The system of claim 12 wherein BHT first branch prediction indicates a degree of confidence in the assumption that the first branch is “

taken”

.

22. The system of claim 12 wherein the pipeline first stage processes a first conditional branch operation having a static prediction bit;

and,

wherein the BHT compares the first branch prediction with the static prediction bit, the BHT using the static prediction bit as the first branch prediction if the first branch prediction agrees with the static prediction bit, and the BHT using a static prediction bit opposite value as the first branch prediction if the first branch prediction disagrees with the static prediction bit.