System and method for speculative global history prediction updating

• US 20090125707A1
• Filed: 11/13/2007
• Published: 05/14/2009
• Est. Priority Date: 11/13/2007
• 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,707,398 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
• CPC Class Codes: G06F 9/3863 using multiple copies of the architectural state, e.g. shadow registers

Abstract

A system and method are provided for updating a speculative global history prediction record in a microprocessor system using pipelined instruction processing. The method accepts microprocessor instructions with consecutive operations, including a conditional branch operation with an associated first branch address. A speculative global history record (SGHR) of conditional branch resolutions and predictions is accessed and hashed with the first branch address, creating a first hash result. The first hash result is used to index a branch history table (BHT) of previous first branch resolutions. As a result, a first branch prediction is made, and the SGHR is updated with the first branch prediction. A non-speculative global history record (NSGHR) of branch resolutions is updated with the resolution of the first branch operation, and if the first branch prediction is incorrect, the SGHR is corrected using the NSGHR.

Claims

1. In a microprocessor system using pipelined instruction processing, a method for updating a speculative 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 speculative global history record (SGHR) of conditional branch resolutions and predictions;

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

using the first hash result to index a branch history table (BHT) of previous first branch resolutions;

in response to indexing the BHT, making a first branch prediction;

updating the speculative global history record with the first branch prediction;

resolving the first branch operation;

updating a non-speculative global history record (NSGHR) of branch resolutions with the resolution of the first branch operation; and

,

in response to the first branch prediction being incorrect, correcting the speculative global history record using the non-speculative global history record.

2. The method of claim 1 wherein correcting the speculative global history record includes copying the value from the non-speculative global history record into the speculative global history record.

3. The method of claim 2 further comprising:

in response to the first branch prediction being incorrect, flushing subsequently accepted microprocessor instructions processed in dependence upon the first branch prediction in the speculative global history record.

4. The method of claim 1 wherein updating the speculative global history record with the first branch prediction includes entering a value representing the first branch prediction into a speculative global history shift register.

5. The method of claim 1 wherein updating the non-speculative global history record of branch resolutions includes entering a value representing the first branch resolution into a non-speculative global history shift register.

6. The method of claim 1 wherein hashing the speculative global history record with the first branch address includes performing an exclusive-OR (XOR) operation between a value representing the speculative global history record and a value representing the first branch address.

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

8. The method of claim 7 further comprising:

updating the BHT with the first branch resolution.

9. The method of claim 8 wherein updating the BHT with the first branch resolution includes:

incrementing the count in response to the first branch being taken; and

,

decrementing the count in response to the first branch not being taken.

10. The method of claim 9 wherein incrementing the count includes clamping the count to a maximum value of m=2ⁿ−

1; and

,

wherein decrementing to the count includes clamping the count to a minimum value of zero.

11. The method of claim 8 wherein using the first hash result to index the BHT of previous first branch resolutions includes indexing a BHT indicating a degree of confidence in the assumption that the first branch is taken.

12. The method of claim 11 wherein updating the BHT with the first branch resolution includes modifying the degree of confidence in response to the first branch resolution.

13. A pipelined instruction microprocessor system with a speculative 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 speculative global history record (SGHR) having an output to supply a history of conditional branch resolutions and predictions;

a hashing circuit having an input to accept the SGHR output, 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 previous first branch resolutions associated with the first hash result and providing a first branch prediction;

wherein the SGHR is updated with the first branch prediction;

The system further comprising;

a non-speculative global history record (NSGHR) of branch resolutions having an input to accept first branch resolutions and an output for over-writing the SGHR in response to the first branch prediction being incorrect.

14. The system of claim 13 wherein the pipeline flushes microprocessor instructions accepted subsequent to the first microprocessor instruction in response to the subsequently accepted microprocessor instructions being processed using the incorrect first branch prediction in the speculative global history.

15. The system of claim 13 wherein the speculative global history record is a shift register.

16. The system of claim 13 wherein the non-speculative global history record is a shift register.

17. The system of claim 13 wherein the hashing circuit performs an exclusive-OR (XOR) operation between a value representing the speculative global history record and a value representing the first branch address.

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

19. The system of claim 18 wherein the BHT is updated with the first branch resolution.

20. The system of claim 19 wherein the BHT increments the count in response to the first branch instruction being taken and decrements the count in response to the first branch instruction not being taken.

21. The system of claim 20 wherein the BHT clamps the count to a maximum value of m=2ⁿ−

1 and clamps the count to a minimum value of zero.

22. The system of claim 19 wherein BHT first branch prediction indicates a degree of confidence in the assumption that the first branch is taken.

23. The system of claim 22 wherein the BHT first branch prediction degree of confidence is modified in response to updating the BHT with the first branch resolution.