Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1998-08-20
2004-09-14
Whitmore, Stacy A. (Department: 2812)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S234000, C712S240000
Reexamination Certificate
active
06792524
ABSTRACT:
TECHNICAL FIELD
The present invention relates in general to data processing systems, and in particular, to the speculative execution of instructions within a processor.
BACKGROUND INFORMATION
In modern microprocessors, there are mechanisms for speculatively executing instructions. When a branch instruction is executed, and the condition required to determine which path is taken from the branch is not available, the path is predicted, and instructions along the predicted path are then speculatively executed.
Speculative execution can improve performance significantly if the speculation is correct. In speculatively executing branch instructions, prediction algorithms can improve the accuracy of the guess of which path to take from a branch instruction. However, if the prediction is wrong, then some type of recovery mechanism must be utilized to cancel the effect of instructions that should not be completed.
In actual practice, it is sometimes difficult and expensive to selectively cancel instructions as a result of a bad branch speculation. Therefore, there is a need in the art for an improved technique for speculative branching within a processor.
SUMMARY OF THE INVENTION
The present invention addresses the foregoing need by providing a system and method for cancelling speculative dispatching of instructions under certain circumstances. In a first embodiment of the present invention, a branch history table is modified to include a bit field associated with each entry (branch instruction) within the table, which indicates the past performance of the associated branch prediction within the branch history table. Each time the particular branch instruction is predicted within the processor, the accuracy of that prediction is then taken into account in modifying this bit field.
In an embodiment of the present invention, the bit field is a counter field, which increments each time the prediction is incorrect, and decrements each time the prediction is correct. Whenever the number within the counter field exceeds a threshold value, the instruction dispatch associated with the predicted branch is cancelled.
In a second embodiment of the present invention, a single counter is maintained and incremented each time a branch prediction is incorrect, and decremented each time the prediction is correct. Whenever the number within the counter field exceeds a threshold value, instruction dispatches are cancelled, or suspended, until the counter field no longer exceeds the threshold value.
In a third embodiment of the present invention, a 2-bit state field is maintained and stored in the branch history table with each entry in the table. One of the states indicates that the particular branch instruction has been previously strongly predicted as taken. A second state indicates that the branch instruction has previously weakly been predicted as taken. A third state indicates that its associated branch instruction has previously been weakly predicted as not taken. And a fourth state associated with a branch instruction entry in the branch history table indicates that it has been previously strongly predicted as not taken. For each branch prediction, a determination is made whether the state associated with the particular branch instruction has been previously strongly or weakly predicted as taken or not taken. If it has previously been strongly predicted as taken or not taken, then instruction dispatch along the chosen instruction path is allowed to continue. However, if the particular branch instruction has been previously weakly predicted as taken or not taken, then instruction dispatch is suspended, or cancelled.
In a fourth embodiment of the present invention, if a predetermined number of weakly predicted taken or not taken states are encountered in succession, then instruction dispatch for all of the entries in the branch history table is suspended until a “strong” state is encountered.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention.
REFERENCES:
patent: 5828874 (1998-10-01), Steely, Jr. et al.
patent: 5857098 (1999-01-01), Talcott et al.
patent: 5864697 (1999-01-01), Shiell
patent: 5909573 (1999-06-01), Sheaffer
patent: 6029228 (2000-02-01), Cai et al.
patent: 6170053 (2001-01-01), Anderson
Peterson Milford John
Schroter David Andrew
Van Norstrand Albert James
Carwell Robert M.
Kordzik Kelly K.
Whitmore Stacy A.
Winstead Sechrest & Minick P.C.
LandOfFree
System and method cancelling a speculative branch does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method cancelling a speculative branch, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method cancelling a speculative branch will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3262053