Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or... – Reducing an impact of a stall or pipeline bubble
Reexamination Certificate
2003-05-05
2004-04-20
Kim, Kenneth S. (Department: 2111)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
Reducing an impact of a stall or pipeline bubble
C711S118000, C712S023000, C712S216000
Reexamination Certificate
active
06725359
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to the field of instruction execution in computers, and more particularly to an apparatus in a pipeline microprocessor for providing speculative address operands to address-dependent micro instructions.
2. Description of the Related Art
A pipeline microprocessor has an instruction path, or pipeline, that sequentially executes instructions from an application program in synchronization with a pipeline clock signal. The instruction pipeline is divided into stages and each of the stages perform specific sub-operations that together accomplish a higher level operation prescribed by a program instruction. The program instructions in the application program are executed in sequence by the microprocessor. As an instruction enters the first stage of the pipeline, certain sub-operations are accomplished. The instruction is then passed to subsequent stages in the pipeline where subsequent sub-operations are accomplished. After performing the last set of sub-operations in the last stage of the pipeline, the instruction completes execution and exits the pipeline. Execution of instructions by a pipeline microprocessor is very similar to the manufacture of items on an assembly line.
Early pipeline microprocessors were not sophisticated enough to allow the execution of multiple instructions in different pipeline stages at the same time; that is, they executed one instruction at a time. More specifically, a given instruction would be fetched from memory and would proceed through all of the pipeline stages until it completed execution. Following this, a next instruction would be fetched and proceed through the pipeline stages through completion. And although this approach is not very efficient in terms of instruction throughput, since early pipeline microprocessors had only a few pipeline stages, the inefficient utilization of stage resources was not deemed to be a significant performance limitation.
However, as microprocessors began to proliferate, more stringent requirements were imposed on microprocessor designers, particularly with respect to instruction throughput. And the obvious approach for increasing throughput was to provide for the execution of multiple instructions within the pipeline. Clearly this improvement increased performance because resources within each pipeline stage were more efficiently used. But with this architectural change came a problem: What if one instruction executing in an early pipeline stage required an operand that was yet to be generated by a preceding instruction executing in a subsequent pipeline stage? This issue is in fact frequently confronted in the art because one of the foremost characteristics of application programs is that instructions in close proximity to one another tend to perform tasks using the same operand. For instance, a typical control algorithm within an application program computes a true signal value by adding a small number to a currently generated signal value and then the sum is compared to a reference signal. The structure of the control algorithm is to add a first operand to a second operand to produce a result. Then the result is tested to see if the computed value is within tolerance. If not, then the first operand is added again to the computed result to obtain a second result. Then the second result is tested. And so on. Even in this simple algorithm it is evident that every other instruction utilizes the last computed result.
When a given instruction executing in one stage of the pipeline requires an operand that is yet to be generated by a preceding instruction that is proceeding through a subsequent stage of the pipeline, the given instruction is referred to as a dependent instruction. This is because the operand required by the dependent instruction depends upon generation of a result by the preceding instruction.
To deal with dependent instructions, microprocessor designers added interlock logic to existing pipeline designs. The interlock logic spans the stages of a microprocessor where dependencies occur. During execution of a sequence of instructions by the microprocessor, non-dependent instructions are successively advanced through the pipeline stages in synchronization with the clock. However, when a dependent instruction is detected, the interlock logic stalls execution of the dependent instruction by inserting slips into the pipeline until the operand required by the dependent instruction is generated by a preceding instruction. The number of slips that are inserted into the pipeline directly influence the amount of delay that is experienced by an application program executing on the microprocessor. Two factors drive the number of slips that are inserted: 1) the separation in the instruction pipeline between the preceding instruction and the dependent instruction; and 2) the number of clock cycles that are needed by the preceding instruction to actually generate the operand. This application focuses on problems associated with the separation between the two instructions in the pipeline.
In general, program instructions use operands for two distinct types of computations in a present day microprocessor: address computations and result computations. Address computations are performed early in the pipeline by address stage logic to compute addresses of memory operands that are to be loaded from memory or stored to memory. Result computations are performed in a later execution stage of the microprocessor to carry out arithmetic, logical, or other operations prescribed by program instructions.
A particular class of dependencies called address dependency occurs when a preceding instruction has not yet generated a result of a result computation that is presently required as an operand for a dependent-instruction for use in an address computation. The instruction prescribing the address computation is called an address-dependent instruction. And because the address-dependent instruction requires the result that has not yet been generated by the preceding instruction, the interlock logic prevents the address-dependent instruction from proceeding in the pipeline until the preceding instruction generates and provides the result.
If there are only two pipeline stages separating the address computation logic from the result computation logic, then at least two slips must be inserted into the pipeline to delay the address-dependent instruction until the preceding instruction provides the result. But if there are 10 stages separating the address computation logic from the result computation logic, then at least 10 slips are required. Furthermore, microprocessor designers are progressively increasing the number of stages in microprocessor pipelines to provide overall throughput improvements. Consequently, these improvements negatively impact address-dependency delays because address-dependent instructions must be stalled for a greater number of clock cycles.
Therefore, what is needed is an apparatus in a pipeline microprocessor that allows address-dependent instructions to proceed without experiencing stalls.
In addition, what is needed is an interim result computation apparatus that can provide speculative address operands to address-dependent instructions prior to when a preceding instruction generates a final result.
Furthermore, what is needed is an apparatus for generating and temporarily storing intermediate results, and for providing these results to address-dependent instructions, thus allowing the address-dependent instructions to proceed without being delayed.
SUMMARY OF THE INVENTION
To address the above-detailed deficiencies, it is an object of the present invention to provide a pipeline microprocessor apparatus for speculatively permitting address-dependent instructions to proceed without experiencing delays.
Accordingly, in the attainment of the aforementioned object, it is a feature of the present invention to provide an apparatus in a pipeline microprocessor for providing a speculative address operand associated with a re
Huffman James W.
Huffman Richard K.
IP-First L.L.C.
Kim Kenneth S.
LandOfFree
Address stage logic for generating speculative address... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Address stage logic for generating speculative address..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Address stage logic for generating speculative address... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3226325