Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
2000-08-03
2004-06-01
Tsai, Henry W. H. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S233000
Reexamination Certificate
active
06745323
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to data processing, and in particular to branch prediction circuits and methods and systems using the same.
BACKGROUND INFORMATION
In deeply pipelined processors, successful dynamic branch prediction is crucial to high speed operation. Consequently, a number of branch prediction mechanisms have been developed. One specific mechanism is the Gshare branch prediction mechanism in which a vector is created which captures the outcome of a fixed number of branches that have been fetched immediately before the current instruction fetch. This vector is typically created by shifting a logic
1
or logic
0
into the last position of a shift register when the outcome of a given branch is determined, with a logic
1
representing a branch taken outcome and a logic
0
representing a branch not taken outcome. The bits of the vector are then bitwise XORed with appropriate bits of the current address. The resulting address is used to index into a branch history table entry which typically is a counter which maintains a value which is used for making the prediction (taken
ot taken) for the branch.
In highly pipelined superscalar processors, however, instructions are fetched into the pipeline well in advance of their actual execution. As a result, in a high frequency processor, the vector in a conventional global history (global history vector or GHV) register will be based on branch outcomes which have been determined several cycles before the predicted execution of the current instruction. In other words, outcome data for more temporally proximate branches are not available in the vector at the time the vector is needed to make the current prediction.
Consequently, the need has arisen for circuits and methods for improving branch prediction accuracy. Additionally, the values of the GHV generated by such a “fast forwarded” instruction fetch may be subject to loss of synchronization with instruction fetches or other errors which become manifest due to events occurring several processor cycles subsequent to the GHV generation. Examples of such events, which may be referred to as fetch redirection events, include cache misses and branch mispredictions. Thus, there is also a need in the art for circuits and methods for recovering the GHV when a fetch redirection event occurs.
SUMMARY OF THE INVENTION
The aforementioned needs are addressed by the present invention. Accordingly, there is provided in a first form, a method of recovering a global history vector. The method includes storing first, second and third global history vectors in respective storage elements. A fetch redirection event, corresponding to one of a predetermined set of redirection event types is detected. In response, a current global history vector is reset to a value derived from a selected global history vector selected from one of said first, second and third storage elements.
There is also provided, in a second form, a data processing system. The system includes a central processing unit (CPU) which itself includes a first storage element, a second storage element and a third storage element. The first, second and third storage elements are, respectively, operable for storing a first global history vector generated in a first cycle of the CPU, operable for storing a second global history vector generated in a first succeeding cycle of the CPU, and operable for storing a third global history vector generated in a second succeeding cycle of the CPU. The CPU also contains first logic operable for detecting a fetch redirection event corresponding to one of a predetermined set of fetch redirection event types, and second logic operable for resetting a current global history vector to a value derived from a selected global history vector. The selected global history vector is selected from one of the first, second and third storage elements in response to detecting the redirection event.
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: 5142634 (1992-08-01), Fite et al.
patent: 5367703 (1994-11-01), Levitan
patent: 5553253 (1996-09-01), Pan et al.
patent: 5564118 (1996-10-01), Steely, Jr. et al.
patent: 5794028 (1998-08-01), Tran
patent: 5805878 (1998-09-01), Rahman et al.
patent: 5875325 (1999-02-01), Talcott
patent: 5964869 (1999-10-01), Talcott et al.
patent: 6108776 (2000-08-01), Check et al.
patent: 6272623 (2001-08-01), Talcott
patent: 6496891 (2002-12-01), Cluff et al.
patent: 6502188 (2002-12-01), Zuraski et al.
patent: 6598152 (2003-07-01), Sinharoy
McBurney Mark E.
Newberger Barry S.
Tsai Henry W. H.
Winstead Sechrest & Minick P.C.
LandOfFree
Global history vector recovery circuits and methods and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Global history vector recovery circuits and methods and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Global history vector recovery circuits and methods and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3366245