Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or...
Reexamination Certificate
1998-08-24
2001-04-03
Chan, Eddie (Department: 2183)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
C712S002000, C712S005000, C712S007000, C712S234000, C712S239000
Reexamination Certificate
active
06212622
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention is related to the field of processors and, more particularly, to instruction scheduling mechanisms in processors.
2. Description of the Related Art
Superscalar processors attempt to achieve high performance by issuing and executing multiple instructions per clock cycle and by employing the highest possible clock frequency consistent with the design. One method for increasing the number of instructions executed per clock cycle is out of order execution. In out of order execution, instructions may be executed in a different order than that specified in the program sequence (or “program order”). Certain instructions near each other in a program sequence may have dependencies which prohibit their concurrent execution, while subsequent instructions in the program sequence may not have dependencies on the previous instructions. Accordingly, out of order execution may increase performance of the superscalar processor by increasing the number of instructions executed concurrently (on the average).
Unfortunately, scheduling instructions for out of order execution presents additional hardware complexities for the processor. The term “scheduling” generally refers to selecting an order for executing instructions. Typically, the processor attempts to schedule instructions as rapidly as possible to maximize the average instruction execution rate (e.g. by executing instructions out of order to deal with dependencies and hardware availability for various instruction types). These complexities may limit the clock frequency at which the processor may operate. In particular, the dependencies between instructions must be respected by the scheduling hardware. Generally, as used herein, the term “dependency” refers to a relationship between a first instruction and a subsequent second instruction in program order which requires the execution of the first instruction prior to the execution of the second instruction. A variety of dependencies may be defined. For example, an operand dependency occurs if a source operand of the second instruction is the destination operand of the first instruction.
Generally, instructions may have one or more source operands and one or more destination operands. The source operands are input values to be manipulated according to the instruction definition to produce one or more results (which are the destination operands). Source and destination operands may be memory operands stored in a memory location external to the processor, or may be register operands stored in register storage locations included within the processor. The instruction set architecture employed by the processor defines a number of architected registers. These registers are defined to exist by the instruction set architecture, and instructions may be coded to use the architected registers as source and destination operands. An instruction specifies a particular register as a source or destination operand via a register number (or register address) in an operand field of the instruction. The register number uniquely identifies the selected register among the architected registers. A source operand is identified by a source register number and a destination operand is identified by a destination register number.
In addition to operand dependencies, one or more types of ordering dependencies may be enforced by a processor. Ordering dependencies may be used, for example, to simplify the hardware employed or to generate correct program execution. By forcing certain instructions to be executed in order with respect to other instructions, hardware for handling consequences of the out of order execution of the instructions may be omitted. For example, if load memory operations are allowed to be performed out of order with respect to store memory operations, hardware may be required to detect a prior store memory operation which updates the same memory location accessed by a subsequent load memory operation (which may have been performed out of order). Generally, ordering dependencies may vary from microarchitecture to microarchitecture.
Scheduling becomes increasingly difficult to perform at high frequency as larger numbers of instructions are allowed to be “in flight” (i.e. outstanding within the processor). Dependencies between instructions may be more frequent due to the larger number of instructions which have yet to be completed. Furthermore, detecting the dependencies among the large number of instructions may be more difficult, as may be detecting when the dependencies have been satisfied (i.e. when the progress of one instruction has proceeded to the point that the dependency need not prevent the scheduling of another instruction). A scheduling mechanism amendable to high frequency operation is therefore desired.
Additionally, a scheduling mechanism is desired which may handle the large variety of ordering dependencies that may be imposed by the microarchitecture. The ordering dependencies, in addition to the operand dependencies, may result in a particular instruction being dependent upon a relatively large number of prior instructions. Accordingly, a flexible scheduling mechanism allowing for a wide variety of dependencies is desired.
SUMMARY OF THE INVENTION
The problems outlined above are in large part solved by a processor enforcing ordering dependencies of load instruction operations store address instruction operations. The processor divides store operations into store address instruction operations and store data instruction operations. The store address instruction operations generate the address of the store, and the store data instruction operations route the corresponding data to the load/store unit. The processor maintains a store address dependency vector indicating each of the outstanding store addresses and records ordering dependencies upon the store address instruction operations for each load instruction operation. Accordingly, the load instruction operation is not scheduled until each prior store address instruction operation has been scheduled. Advantageously, store addresses are available for dependency checking against the load address upon execution of the load instruction operation. If a memory dependency exists, it may be detected upon execution of the load instruction operation.
Broadly speaking, the present invention contemplates a processor comprising a store address register and a dependency vector generation unit coupled thereto. The store address register is configured to store a store address dependency vector identifying store address instruction operations outstanding within the processor. The dependency vector generation unit is configured to generate a dependency vector for an instruction operation. For load instruction operations, the dependency vector generation unit is configured to include the store address dependency vector in the dependency vector.
The present invention further contemplates a method for performing a load instruction operation in a processor. A store address dependency vector indicative of each store address instruction operation outstanding within the processor is maintained. A dependency vector for the load instruction operation is generated including the store address dependency vector. The load instruction operation is inhibited from scheduling until each instruction operation indicated in the dependency vector is completed.
REFERENCES:
patent: 4521851 (1985-06-01), Trubisky et al.
patent: 4594660 (1986-06-01), Guenthner et al.
patent: 5404470 (1995-04-01), Miyake
patent: 5465336 (1995-11-01), Imai et al.
patent: 5467473 (1995-11-01), Kahle et al.
patent: 5555432 (1996-09-01), Hinton et al.
patent: 5651125 (1997-07-01), Witt et al.
patent: 5655096 (1997-08-01), Branigin
patent: 5710902 (1998-01-01), Sheaffer et al.
patent: 5717883 (1998-02-01), Sager
patent: 5748978 (1998-05-01), Narayan et al.
patent: 5799165 (1998-08-01), Favor et al.
patent: 5835747 (1998-11-01), Trull
patent: 5884059 (1999-03-01), Favor et al.
patent: 5884060 (1999-03-01), Vegesna et al.
patent:
Advanced Micro Devices , Inc.
Chan Eddie
Conley Rose & Tayon PC
Merkel Lawrence J.
Nguyen Dzung C.
LandOfFree
Mechanism for load block on store address generation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Mechanism for load block on store address generation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mechanism for load block on store address generation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2484783