Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or... – Scoreboarding – reservation station – or aliasing
Reexamination Certificate
1999-04-22
2001-07-24
Pan, Daniel H. (Department: 2783)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
Scoreboarding, reservation station, or aliasing
C712S220000, C712S245000, C712S248000, C710S054000, C711S125000, C711S135000
Reexamination Certificate
active
06266767
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The invention relates to computer processors and, more particularly, to a queue arrangement for storing information to facilitate out-of-order execution of load instructions.
BACKGROUND OF THE INVENTION
Processors used in computers and other devices execute instructions to perform logical operations, load and store operations, and other operations. Processor performance may be increased by providing several execution units which may execute instructions simultaneously. Processors which include multiple, concurrently operating execution units are referred to as superscalar processors.
Instructions to be executed by a processor are written in a certain order referred to as program order. For example, two different load instructions may load data into two different register locations in a processor, and then the next instruction in program order may perform an operation using the data in these two locations and write the result of the operation to another register location. Finally, a store instruction may store the results from the operation to a location in main memory associated with the processor. The first instructions in program order may be thought of as older than the later instructions in program order. In the example above, the initial load instructions are considered older than the store instruction and, conversely, the store instruction is considered to be younger than the load instructions.
A superscalar processor may increase overall processing speed by executing instructions out of program order. For example, a load instruction may be executed ahead of a store instruction in program order. That is, a younger load instruction may be executed ahead of an older store instruction. A load instruction executed ahead of a store instruction in program order is referred to as a preload.
Problems arise in executing instructions out of program order when one instruction depends upon data supplied by another instruction. For example, a store instruction may store data to an address in memory and a load instruction later in program order may load data from that address. In this example, if the load instruction is executed as a preload ahead of the store instruction, it will load incorrect data, causing an error in program execution. Because the preload instruction specifies the same address as the older store instruction, the preload conflicts with the later executed store instruction.
SUMMARY OF THE INVENTION
It is an object of the invention to provide an apparatus and method for detecting a conflict between preload and store instructions, and for enabling the processor to take corrective action to prevent an error from occurring due to the conflict. By detecting store/preload conflicts, the apparatus and method according to the invention help facilitate the out-of-order execution of load instructions in the processor.
An apparatus according to the invention includes a preload queue including a plurality of queue locations for storing a plurality of preload entries. Each preload entry includes an identifier for a preload instruction and further includes address information defined by the respective preload instruction. The identifier includes means for identifying the instruction associated with the preload entry and means for indicating the relative age of the instruction.
As store instructions are executed, a comparison unit associated with the preload queue uses information in each preload entry and information regarding the store instruction being executed to identify each conflicting preload entry. A conflicting preload entry is an entry which defines an address which matches, that is, overlaps, the address of the store instruction being executed, and is associated with a preload instruction which is younger than the store instruction. Thus, the preload queue and comparison unit cooperate to detect preload instructions which have executed despite being dependent on an older store instruction, and therefore, have executed improperly.
The apparatus according to the invention also includes a flush signal arrangement for producing a flush signal. This flush signal identifies a target preload which comprises the oldest improperly executed, or conflicting, preload. The flush signal allows the processor to take corrective action to avoid the error which would otherwise occur due to the conflict between the store and preload instructions. As used in this disclosure and the following claims the target preload is defined as the oldest preload associated with a conflicting preload entry which has been identified by the comparison unit.
The corrective action which the processor takes in response to the flush signal and the apparatus for taking the corrective action are not part of the present invention, and are therefore not discussed in detail in this disclosure. Those skilled in the art will appreciate that the corrective action may commonly involve flushing the target preload and all instructions which have been fully executed after the target preload, and then restoring the state of the processor to the state immediately before the target preload was executed. The target preload and other instructions which have been flushed are then re-fetched and executed. Any flushing, restoring, and re-fetching arrangement may be employed with the preload queue arrangement according to the invention.
According to the invention, a preload identifying arrangement and preload queue routing arrangement assist in loading the preload queue with the required preload entries. The preload identifying arrangement is associated with each execution unit in the processor which executes load instructions, and includes logic for identifying each load instruction which represents a preload. The preload queue routing arrangement is also associated with each execution unit which executes load instructions, and serves to transfer the address information defined by each respective preload to the preload queue along with the identifier associated with the respective preload.
In the preferred form of the invention, the comparison unit comprises an address comparator and an identifier comparator for each queue location. Each address comparator compares the address information of a store instruction being executed with the address information included in the preload entry stored in the respective queue location to determine whether there is a match between the addresses. Each identifier comparator compares the identifier of the store instruction being executed with the identifier included in the preload entry stored in the respective queue location. This comparison determines the relative age between the preload associated with the respective preload entry and the store instruction being executed. Conflict control logic included in a controller associated with the comparison unit receives the address and identifier comparator outputs. When the address and identifier comparator outputs indicate an address match between a preload and an older store instruction being executed, the conflict control logic directs the flush signal arrangement to produce the flush signal.
As used in this disclosure and the following claims, a “match” between the addresses means that the memory locations defined by the addresses and the respective data at least partially overlap. Thus, the address information required by each address comparator includes the actual address specified by the respective instruction and the byte count. This information together defines the memory location implicated by the respective instruction.
Any number of address comparator arrangements may be employed in the preload queue arrangement within the scope of the invention. For example, U.S. patent application Ser. No. 08/927,889, filed Sep. 11, 1997, and entitled “Method and Apparatus for Detecting an Overlap Condition Between a Storage Reference Instruction and a Previously Executed Storage Reference Instruction,” now U.S. Pat. No. 6,070,238, discloses a preferred address comparator arrangement for use with the present preload
Feiste Kurt Alan
Muhich John Stephen
White Steven Wayne
Culbertson Russell D.
England Anthony V. S.
International Business Machines - Corporation
Pan Daniel H.
Shaffer & Culbertson LLP
LandOfFree
Apparatus and method for facilitating out-of-order execution... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for facilitating out-of-order execution..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for facilitating out-of-order execution... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2511409