Electrical computers and digital processing systems: processing – Processing architecture – Superscalar
Reexamination Certificate
2001-09-27
2004-10-19
Coleman, Eric (Department: 2183)
Electrical computers and digital processing systems: processing
Processing architecture
Superscalar
C712S244000
Reexamination Certificate
active
06807621
ABSTRACT:
This application claims priority under 35 U.S.C. §§119 and/or 365 to Application No. 0003446-2 filed in Sweden on Sep. 27, 2000; the entire content of which is hereby incorporated by reference.
TECHNICAL FIELD
The present invention relates to the field of pipelined microprocessors and particularly to a pipelined microprocessor capable of handling instruction irregularities such as exceptions, interrupts and branch mispredictions and to a method of handling instruction irregularities in a pipelined microprocessor.
STATE OF THE ART
So called pipelined processors have been developed to speed up the processing speed of computer processors and to improve or increase the instruction flow through a microprocessor. A pipelined processor includes a plurality of independently operating stages. When a first instruction has been handled in one of the pipeline stages, it is moved on to the next stage whereas a subsequent instruction is received in the stage that a preceding instruction just left. Generally several instructions are processed simultaneously in the pipeline since each stage may bold an instruction. So called super-scalar processors are also known which comprise multiple pipelines processing instructions simultaneously when adjacent instructions have no data dependencies between them. A super-scalar processor commits more than one instruction per cycle. Through the provision of out-of-order processors an even higher degree of parallellism and a higher performance can be provided for. An out-of-order processor includes multiple parallell stages/units in which instructions are processed in parallell in any efficient order taking advantage of parallell processing. Out-of-order processing is much more complex than conventional processing among others due to the need of state recovery following unpredicted changes in the instruction flow.
Microprocessors may implement the technique of overlapping a fetching stage, a decoding stage, an execution stage and possibly a write back stage. In a so called deeply pipelined microprocessor each processing stage is divided into sub-stages to still further increase the performance.
Generally state recovery mechanisms are introduced in order to provide for state recovery following an exception, an interrupt or a branch misprediction which in the present application are gathered under a common concept of instruction irregularity.
Exceptions are generally unexpected events associated with the instructions such as page fault and memory accesses, data break point traps or divided-by-zero conditions.
Interrupts are events occurring from outside of the processor that may be initiated for example by the devices coupled to the same buses or processors.
A branch instruction is an instruction that expressly changes the flow of program. Branch instructions may be conditional or unconditional. An unconditional branch instruction is always taken whereas a conditional branch instruction either is taken or not taken depending on the results of the condition expressed within the instruction. Conditional branch instructions within an instruction stream generally prevent the instruction fetching stage from fetching subsequent instructions until the branch condition is fully resolved.
In a pipelined microprocessor a conditional branch instruction will not be fully resolved until it reaches an instruction execution stage close to the end of the pipeline. The instruction fetching stage will then stall because the unresolved branch condition prevents the instruction fetching stage from knowing which instructions to fetch next. This is clearly disadvantageous.
Therefore it is known to implement various branch prediction mechanisms to predict the outcome of a branch instruction. The instruction fetching stage then uses the branch predictions to fetch subsequent instructions. Therethrough it is not necessary to wait until the branch instruction has been fully resolved.
If a branch prediction has made a correct prediction, the processing of instructions is not affected. If however the mechanism has mispredicted the branch, the instruction pipeline has to be flushed and execution is to be restarted at the corrected address. It is therefore desirable to detect and correct a branch misprediction as early as possible, particularly for deeply pipelined processors where a long pipeline needs to be flushed each time a misprediction is made.
U.S. Pat. No. 5,812,839 suggests a solution to this problem through using a four stage branch instruction resolution system. A first stage predicts the existence and outcome of branch instructions within an instruction stream such that an instruction fetching stage continually can fetch instructions. The second stage decodes all the instructions fetched. If the decode stage determines that a supposed branch instruction predicted by the first stage is not actually a branch instruction, the decode stage flushes the pipeline and restarts the processor at a corrected address. The decode stage verifies all branch predictions made by the branch prediction stage. The decode stage makes branch predictions for branches not predicted by the branch prediction stage. A third stage executes the branch instructions to determine a final branch outcome and a final branch target address. The branch execution stage compares the final branch outcome and the final branch target address with the prediction to determine if the processor has to flush the front-end of the microprocessor pipeline and restart again at a corrected address. The final branch resolution stage retires all branch instructions ensuring that any instructions fetched after a mispredicted branch are not committed into permanent state. It is clearly disadvantageous that the whole front-end needs to be flushed if there has been a misprediction.
It is also a serious drawback in all known pipelined microprocessors, implementing speculative prediction, that at several different locations and stages a part of the information has to be disposed of. All data belonging to the instructions after a mispredicted branch need to be flushed. The more steps the pipeline contains, the more serious the problem will be since larger memories and longer queues have to be searched in order to find the data that is to be disposed of. This of course seriously affects the performance.
SUMMARY OF THE INVENTION
What is needed is therefore a pipelined microprocessor capable of handling instruction irregularities, such as one or more of exceptions, interrupts and branch mispredictions, in a more efficient manner compared to hitherto known pipelined processors. Particularly a pipelined microprocessor is needed through which instruction irregularities can be handled in an efficient manner with a minimum of performance reduction, compared to the situation when there is no instruction irregularity. Further a pipelined microprocessor is needed through which invalid instructions associated with an instruction irregularity can be handled as efficiently as possible. Particularly a pipelined processor is needed through which branch mispredictions to a minimum extent affect execution and through which no flushing is needed in those execution units that are not handling a branch misprediction.
Particularly a pipelined microprocessor that implements speculative execution is needed, through which mispredicted branch instructions do not require flushing of the front-end with a corresponding restart when a mispredicted branch instruction is detected.
In addition to a pipelined microprocessor, a method of handling instruction irregularities, and through which one or more above mentioned objects can be fulfilled, is also needed.
In the present application the concept functional stage is introduced to indicate that the functionality referred to may be provided in one or more separate “sub”-stages providing the same functionality, or more than one functionality may be provided in a combined stage. As an example the “conventional” decoding stage could be provided in more than one stage; this is of course applicable to any one of the functio
Carlsson Magnus
Strömbergson Joachim
Vasell Jonas
Coleman Eric
Telefonaktiebolaget LM Ericsson
LandOfFree
Pipelined microprocessor and a method relating thereto does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Pipelined microprocessor and a method relating thereto, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pipelined microprocessor and a method relating thereto will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3298394