Electrical computers and digital processing systems: processing – Instruction issuing
Reexamination Certificate
1998-12-16
2001-05-22
Ellis, Richard L. (Department: 2183)
Electrical computers and digital processing systems: processing
Instruction issuing
C712S205000
Reexamination Certificate
active
06237081
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates generally to the field of processors which support out-of-order execution of instructions and, more particularly, to a method and apparatus in which dispatched instructions may be rejected by an execution unit.
High-performance processors may be capable of “superscalar” operation and may have “pipelined” elements. A superscalar processor has multiple elements which operate in parallel to process multiple instructions in a single processing cycle. Pipelining involves processing instructions in stages. The pipelined stages may process a number of instructions concurrently.
In a typical first stage, referred to as an “instruction fetching” stage, an instruction is fetched from memory. In a “decode” stage, the instruction is decoded into different control bits. These control bits may, for example, designate the functional unit for performing the operation specified by the instruction, source operands for the operation, and a destination for the results of the operation. After the decode stage, the decoded instruction enters a “dispatch” stage from which the instruction is dispatched to an execution unit for performing an “execution” stage. An issue queue may be associated with the execution unit for temporarily holding the dispatched instructions prior to execution. In any case, the execution stage processes the operation specified by the instruction. Processing an operation specified by an instruction includes accepting one or more operands and producing one or more results.
Instructions to be processed may originally be prepared for processing in some programmed, logical sequence. However, at least in some respects, the instructions may be processed in a sequence different from the original sequence. This type of processing may be referred to as “out-of-order” processing. Complications arise in out-of-order processing because instructions are not totally independent of each other. That is, the processing of one instruction may depend on a result from another instruction. For example, the processing of an instruction which follows a branch instruction will depend on the branch path chosen by the branch instruction. In another example, the processing of an instruction which reads the contents of a memory element depends on the result of a preceding instruction which writes information to that memory element.
Regardless of the order in which instructions should be executed, or are preferably executed, execution units employed in prior systems have either accepted the instruction unconditionally or generated a “busy” condition. The execution unit processed all instructions which were unconditionally accepted unless the instruction required some condition which was not satisfied at that time. These unconditional acceptance-type systems required some mechanism for dealing with the situation in which the instruction could not be properly executed, such as when the instruction required data which was not yet available. These systems provided means for restoring some previous state in the processor to recover from the execution error caused by the attempt to execute the unconditionally accepted instruction.
A “busy” condition stopped the issue of all instructions to the busy execution unit. In some processing schemes, the issue queue responded to a busy condition by simply holding all instructions until the particular execution unit was not busy. Another method for responding to a busy condition in an execution unit was to abort the instruction that caused the unit to be busy, delete it and all younger instructions, re-fetch and re-dispatch the deleted instructions, and then re-issue the instructions in a different order to avoid the busy condition. In either case, allowing the execution unit to generate a busy condition resulted in an unacceptable penalty on processing speed.
SUMMARY OF THE INVENTION
It is an object of the invention to provide a method and apparatus for overcoming the above-described problems associated with processors which support out-of-order execution of instructions. More particularly, it is an object of invention to provide a method and apparatus for allowing an execution unit to reject an instruction while continuing to process additional instructions.
The method according to the invention includes storing an instruction in an issue queue associated with an issue unit, and then issuing the stored instruction from the issue queue to an execution unit responsible for executing the instruction. A counter associated with the issue queue counts pipeline stages occurring after the instruction is issued from the queue. Also, the issue unit monitors for a reject indication for the issued instruction. The execution unit produces a reject indication in the event that a reject condition is detected as the unit attempts to execute the instruction. The issue queue retains the instruction for a critical period after the instruction is issued. This critical period may be defined in terms of pipeline stages which have occurred after the instruction is issued. If the execution unit does not detect a reject condition during the critical number of pipeline stages, the issue unit may remove the instruction from the issue queue. However, if a reject condition is detected within the critical number of pipeline stages after the instruction is issued, then the instruction remains in the issue queue to be reissued at a later time.
By retaining the instruction in the issue queue for the critical number of pipeline stages after issuance, the instruction remains available in the event that the instruction cannot be processed at that time, or is preferably processed at another time. That is, retaining the instruction in the issue queue for the critical number of pipeline stages or critical period allows the execution unit to drop the issued instruction without requiring that the instruction be re-dispatched and without stopping further issues from the issue queue. The execution unit continues to process the next issued and unrejected instruction and the rejected instruction remains in the issue queue to be reissued at a later time.
In the preferred form of the invention, the critical period comprises a critical number of pipeline stages during which a reject condition for the instruction is expected if such a reject condition is to occur. In one form of the invention, the critical number of pipeline stages is a fixed number for each instruction stored in the issue queue. In other forms of the invention, the critical number of pipeline stages may vary depending upon the type of instruction. Other forms of the invention may hold a rejected instruction from reissuance for a predefined correction period after the critical period in order to give the execution unit time to take some corrective action to prevent the reject condition from occurring when the instruction is reissued. In any of these cases, the counter preferably uses a counter field associated with the instruction in the issue queue. The counter field is set to the critical number of pipeline stages when the instruction is issued and then decremented upon the occurrence of each pipeline stage after issuance. Thus, the value of the counter field for an issued instruction can be used to determine if the critical number of pipeline stages have occurred.
These and other objects, advantages, and features of the invention will be apparent from the following description of the preferred embodiments, considered along with the accompanying drawings.
REFERENCES:
patent: 5548735 (1996-08-01), Chen et al.
patent: 5784603 (1998-07-01), Leung et al.
patent: 6098166 (2000-08-01), Leibholz et al.
Le Hung Qui
Ronchetti Bruce Joseph
Shippy David James
Thatcher Larry Edward
Culbertson Russell D.
Ellis Richard L.
International Business Machines - Corporation
Salys Casimer K.
Shaffer & Culbertson LLP
LandOfFree
Queuing method and apparatus for facilitating the rejection... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Queuing method and apparatus for facilitating the rejection..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Queuing method and apparatus for facilitating the rejection... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2557305