US 6,148,394 A · Apparatus and method for tracking out of order load instructions to avoid data coherency violations in a processor

Abstract

The present invention is directed towards a means to detect and reorder out of order instructions that may violate data coherency. The invention comprises a mis-queue table for holding entries of instruction data, each entry corresponding to an instruction in a computer microprocesor. The instruction data in each entry comprises: i) address information for the instruction; ii) ordering information for the instruction, indicating the order of the instruction relative to other instructions in the mis-queue table; iii) data modification information for the instruction, for indicating a possibility of modified data; and iv) out of order information, for indicating that a newer instruction has completed before the corresponding older instruction to the entry. The invention also comprises an out of order comparator for comparing an address of a completed instruction to any address information entries in the miss queue. If a completed instruction accesses the same address as another instruction, as indicated in the address information in the mis-queue table, and the completed instruction is newer than the matched instruction, the out of order field is marked indicating this condition exists. The invention comprises a modification comparator. This compares addresses from data altering events to those addresses in the entries in the mis-queue table. On a match, the modification field of the corresponding entry is marked to indicate this condition exists. When an instruction entry indicates that the corresponding instruction's data is modified, and that the instruction is out of order, all subsequent instructions are canceled.

Claims7

Dependent claims

An apparatus for out of order execution of instructions, the apparatus comprising:

(a) a mis-queue table for holding entries of instruction data, each entry corresponding to an instruction in a computer microprocessor, the instruction data comprising:
(i) address information for the instruction, the address information being held in an address information field of the respective entry;
(ii) order information for the instruction, the order information being held in an order information field of the respective entry for indicating the order of the corresponding instruction in relation to other instructions;
(iii) out of order information, the out of order information being held in an out of order information field of the respective entry for indicating that a newer instruction using data at the address corresponding to the address information field has completed before the current entry;
(iv) data modification information for the instruction, for indicating a possibility of modified data at the address corresponding to the address information field;
(b) an out of order comparator for setting the out of order information field of an entry in the mis-queue table upon the completion of a completing instruction, the out of order information field of a compared entry being set if the completing instruction comprises a newer instruction which uses data at the address corresponding to the address information field in the compared entry;
(c) a modification comparator for comparing address information in the address information field in an entry in the mis-queue table to a possibly modified address, wherein the modification field in the entry is marked to indicate modified data at the address if the possibly modified address is comparable to the address information in the instruction entry being compared.

4 more elements

A method for detecting out of order instructions which may cause a data coherency violation in a microprocessor, the method comprising:

(a) preparing a new instruction to execute on the microprocessor, the new instruction having a data address;
(b) upon completion of the new instruction
(i) comparing the data address of the instruction to existing entries in a mis-queue table, the instruction entries corresponding to previous instructions, the instruction entries containing address information, instruction order information, an out of order indicator, and a modified data indicator;
(ii) if the data address of the new instruction is comparable to address information of an entry in the mis-queue table, marking the comparable entry in the mis-queue table as an out of order instruction;
(c) if the new instruction is presently unable to be completed, creating an entry for the new instruction in the mis-queue table, whereby the data address of the new instruction is put in the address information of the new instruction entry, and information on the order of the instruction is put in the ordering information of the new instruction entry.

2 more elements

Dependencies are inferred from the claim text.

Apparatus and method for tracking out of order load instructions to avoid data coherency violations in a processor

Life of this patent

Apparatus and method for tracking out of order load instructions to avoid data coherency violations in a processor

Life of this patent

Abstract

Claims7