Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1999-10-19
2004-03-02
Ellis, Richard L. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S238000, C712S209000, C712S227000
Reexamination Certificate
active
06701426
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to devices that execute a plurality of different instruction sets and more particularly to methods and apparatus for providing instruction branch prediction for a plurality of different instruction sets.
BACKGROUND OF THE INVENTION
Many microprocessors and other instruction execution devices employ some type of branch prediction to determine whether an instruction that has been fetched requires that the processor jump, or branch, to another address to obtain the next instruction to be fetched. Many microprocessors and other devices employ pipeline structures used to fetch, decode, execute and commit each instruction. In addition, processors are known that employ variable length instruction sets, such as Intel® X.86 family of microprocessors. Also, processors are known that execute different instruction sets, such as a variable length instruction set (e.g., X.86 type instructions) and another instruction set such as fixed length RISC instruction sets.
With branch prediction, there are different types of branches, such as unconditional branches and conditional branches. An unconditional branch, for example, may require that a processor always jump to a same address. Alternatively, a conditional branch may only require that a branch be taken if certain conditions are met and jump to a same address.
With pipeline based instruction execution, if there is a branch, the branch will not be known until after the operational code or command has been decoded. Filling the pipeline with the branch target address requires flushing the pipeline so that the branch address is the next address to be executed. It is desired to keep the pipeline filled since when commands are fetched, the branches are not typically known, nor which directions they may go. After decoding, when the system knows that a branch is necessary in the case of unconditional and after executing in the case of conditional, it may know which direction the branch is going, namely, in a taken
ot taken direction to indicate which address needs to be examined next. As such, fetch based branch prediction is used to attempt to predict what the next address to fetch should be before branch decoding and execution.
Branch prediction can find increased advantage the earlier the branch prediction is made in the pipeline. For example, fetch based branch prediction is known, which attempts to provide branch prediction prior to the instruction being fully decoded and executed. As such, fetch based branch prediction may include prediction at a fetch stage or each stage in the pipeline.
Several types of branch prediction include, for example, the use of a correlation of previous branches. With dynamic branch prediction, for example, prediction techniques may use a program counter of a branch to index into a branch history table. The index bits that are used may be some bits of the program counter associated with the instruction requiring a branch. However, a problem arises if the index bits of the program counter are the same for multiple addresses. In such an instance, there can be two branches using the same counter so there is an increase in the number of counters required, thereby adding to the size of the die required to fabricate the branch prediction function.
Branch target buffers are also known to be used to facilitate branch prediction. Branch target buffers, as known in the art, may be used in fetch based prediction techniques and typically serve as a table that stores a program counter value that corresponds to instructions having branches. Stored with the program counter value is typically a target address for the branch.
Global branch histories typically include histories of all branches and are used to avoid dual counters. These are typically used after the instructions have been processed and are fed back as actual branch information to use as an index. In addition, multiple level branch predictions are used which may use two tables of data wherein one table may be dedicated for the global history of all branches and another table may be dedicated for the history of a particular branch.
Branch prediction techniques are known for variable length instruction sets, such as the X.86 instruction set, and are widely used in microprocessor technology. However, branch prediction should be performed for each of the multiple different instruction sets to help insure efficient operation when any instruction set is being executed. One way of addressing branch prediction for multiple instruction sets is to duplicate branch prediction related circuits and memory wherein each instruction set may have dedicated branch prediction operations. However, this may unnecessarily increase the cost and reduce the efficiency of the processor.
Consequently, there exists a need for an instruction branch prediction method and apparatus that can efficiently perform branch prediction for multiple instruction sets executed on a multiple instruction set processor.
REFERENCES:
patent: 3631405 (1971-12-01), Hoff et al.
patent: 5481693 (1996-01-01), Blomgren et al.
patent: 5870575 (1999-02-01), Kahle et al.
patent: 5909567 (1999-06-01), Novak et al.
patent: 709767 (1996-05-01), None
Flynn, Michael J., Computer Architecture Pipelined and Parallel Processor Design, 1995, Jones and Bartlett Publishers, Inc., pp. 236-237.*
Hennessy, John L. & David A. Patterson, Computer Architecture A Quantitative Approach, 1996, Morgan Kaufmann Publishers, Inc., 2nd Ed., pp. 262-278.*
Hennessy, John L. & David A. PAtterson, Computer Architecture A Quantative Approach, 1996, Morgan Kaufman Publishers, Inc., 2nded., pages .
Patel Ronak S.
Patkar Niteen
Ramesh T. R.
Ries Greg L.
Van Dyke Korbin S.
ATI International Srl
Ellis Richard L.
Meonske Tonia L.
Vedder Price Kaufman & Kammholz P.C.
LandOfFree
Switching between a plurality of branch prediction processes... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Switching between a plurality of branch prediction processes..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Switching between a plurality of branch prediction processes... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3287556