Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or... – Scoreboarding – reservation station – or aliasing
Reexamination Certificate
1997-08-27
2001-09-11
Eng, Daivd Y. (Department: 2155)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
Scoreboarding, reservation station, or aliasing
Reexamination Certificate
active
06289437
ABSTRACT:
TECHNICAL FIELD
The present invention relates in general to a pipelined data processing system, and more particularly, to an out-of-order issue mechanism in a pipelined data processor.
BACKGROUND INFORMATION
As computers have been developed to perform a greater number of instructions at greater speeds, many types of architectures have been developed to optimize this process. For example, a reduced instruction set computer (RISC) device utilizes fewer instructions and greater parallelism in executing those instructions to ensure that computational results will be available more quickly than the results provided by more traditional data processing systems. In addition to providing increasingly parallel execution of instructions, some data processing systems implement out-of-order instruction execution to increase processor performance. Out-of-order instruction execution increases processor performance by dynamically allowing instructions dispatched with no data dependencies to execute before previous instructions in an instruction stream that have unresolved data dependencies. In some data processing systems, instructions are renamed and instruction sequencing tables, also referred to as re-order buffers, facilitate out-of-order execution by reordering instruction execution at instruction completion time.
Re-order buffer devices are also used to allow speculative instruction execution. Therefore, data processing systems which support speculative instruction execution can be adapted for out-of-order execution with the addition of relatively minimal hardware. A portion of this added hardware includes issue logic which is used to determine a time and order that instructions should be issued. Such issue logic can be extremely complex since the dependencies of instructions and a state of a pipeline in which the instructions are being executed must be examined to determine a time at which the instruction should issue. If the issue logic is not properly designed, such issue logic can become a critical path for the data processing system and limit the frequency of instruction execution such that performance gains which could be achieved by out-of-order issue are destroyed.
Therefore, a need exists for an out-of-order issue mechanism that efficiently issues independent instructions in a timely manner and that does not limit a frequency with which the processor executes instructions.
SUMMARY OF THE INVENTION
The previously mentioned needs are fulfilled with the present invention. Accordingly, there is provided, in a first form, a data processing system having a first execution unit. The data processing system includes an input circuit for receiving a plurality of instructions and a register for storing a plurality of validity values. The first one of the plurality of validity values corresponds to a first one of the plurality of instructions. The first one of plurality of validity values selectively indicates the first one of the plurality of instructions may be issued to the first execution unit.
Additionally, there is provided, in a second form, a method for issuing instructions in a data processing system having a first execution unit. The method includes the steps of receiving a plurality of instructions and storing a plurality of validity values in a register. Each of the plurality of validity values corresponds to a first one of the plurality of instructions. The method also includes the step of selectively enabling a first one of the plurality of validity values to indicate the first one of the plurality of instructions may be issued to the first execution unit.
There is also provided a data processing system having a first execution unit and a second execution unit. The data processing system includes an input circuit for receiving a first plurality of instructions. The data processing system also includes a detection circuit for detecting dependencies between a first one of the first plurality of instructions and a second instruction currently executing within the first execution unit and asserting a first dependency indicator in response to a first dependency. The detection circuit is connected to the input circuit for receiving the first plurality of instructions. The data processing system also includes an issue circuit connected to the first execution unit, the second execution unit and the detection circuit. The issue circuit selectively issues the first one of the plurality of instructions to one of the first execution unit and the second execution unit in response to the first dependency indicator.
There is also provided, in one form of the present invention, a method for operating a data processing system having a first execution unit and a second execution unit. The method includes the steps of receiving a first plurality of instructions and detecting dependencies between a first one of the first plurality of instructions and a second instruction currently executing within the first execution unit. The method also includes the steps of asserting a first dependency indicator in response to a first detected dependency, coupling an issue circuit to the first execution unit, the second execution unit and the detection circuit, and selectively issuing the first one of the first plurality of instructions to one of the first execution unit and the second execution unit in response to the first dependency indicator.
Additionally, the present invention includes, in one embodiment, a data processing system including a first execution unit for selectively executing a first plurality of instructions and an instruction issue logic circuit for generating a plurality of issue bits. A first preselected number of issue bits corresponds to one of the first plurality of instructions and wherein the first preselected number of issue bits selectively enables a first instruction to be executed.
Additionally, there is provided, in one form of the present invention, a method for operating a data processing system. The method includes the steps of selectively executing a first plurality of instructions in a first execution unit and generating a plurality of issue bits using an instruction issue logic circuit. A first preselected number of issue bits correspond to one of the first plurality of instructions. The method also includes the step of selectively enabling a first instruction to be executed in response to the first preselected number of issue bits.
These and other features, and advantages, will be more clearly understood from the following detailed description taken in conjunction with the accompanying drawings. It is important to note the drawings are not intended to represent the only form of the invention.
REFERENCES:
patent: 4991090 (1991-02-01), Emma et al.
patent: 5471593 (1995-11-01), Granigin
patent: 5553256 (1996-09-01), Fetterman et al.
patent: 5621910 (1997-04-01), Nagamatsu
patent: 5630157 (1997-05-01), Dwyer
patent: 5651125 (1997-07-01), Witt et al.
patent: 5699537 (1997-12-01), Sharangpant et al.
patent: 5721855 (1998-02-01), Hinton et al.
patent: 5778245 (1998-07-01), Papworth et al.
patent: 5819308 (1998-10-01), Tien et al.
patent: 0432774A2 (1990-12-01), None
patent: 0778519A2 (1996-11-01), None
Gurindar Sohi, “Instruction Issue Logic for High-Performance, Interruptible, Multiple Functional Unit, Pipelined Computer”, IEEE, vol. 39, No. 3, Mar. 1990, pp. 349-359.*
R. M. Tomasulo, “An Efficient Algorithm for Exploiting Multiple Arithmetic Units”, IBM Journal, Jan. 1967, pp. 25-33.
William Mangione-Smith et al., “Architectural vs. Delivered Performance of the IBM RS/6000 and the Astronautics ZS-1”, Proceedings of the Twenty-Fourth Annual IEEE Hawaii International Conference on System Sciences, 1991, vol. 1, pp. 397-408.
Eisen Susan Elizabeth
Phillips James Edward
Carwell Robert M.
Eng Daivd Y.
International Business Machines - Corporation
Newberger Barry S.
Winstead Sechrest & Minick P.C.
LandOfFree
Data processing system and method for implementing an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data processing system and method for implementing an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data processing system and method for implementing an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2450294