Electrical computers and digital processing systems: processing – Architecture based instruction processing – Multiprocessor instruction
Reexamination Certificate
2000-09-29
2004-01-20
Treat, William M. (Department: 2183)
Electrical computers and digital processing systems: processing
Architecture based instruction processing
Multiprocessor instruction
C712S207000, C712S216000, C712S225000, C712S228000
Reexamination Certificate
active
06681317
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of processors and more particularly to a technique for providing ordering when utilizing an advanced load instruction.
2. Description of the Related Art
Processor instruction sets for a computer system may incorporate the use of advanced loads to improve processing performance. When a processor instruction set utilizes an advanced load feature, a specialized instruction or instructions is/are utilized to boost the ordinary load instruction to be performed at a earlier time than originally scheduled. As a typical example, when an advanced load is executed, it allocates an entry in a structure called the advanced load address table (ALAT) and the load instruction is boosted to occur at a earlier time in the instruction sequence. At the location of the original load instruction, some form of load checking instruction is inserted to confirm that the entry of the advanced load is still valid. That is, the original load instruction is replaced by an advanced load instruction, which occurs earlier in the instruction sequence, and a separate checking instruction is inserted at the original location of the load instruction to check or confirm that the entry of the advanced load instruction is still valid at the location where the original load instruction was scheduled. Advanced load instructions are available in various forms, including integer advanced loads, floating point advanced loads and floating point pair advanced loads.
When an advanced load instruction is executed, it allocates an entry (typically, an address tag) in the ALAT. Later, when a corresponding check instruction is executed to check the validity of the advanced load entry, the presence of the tag entry in the ALAT indicates that the data speculation of the advanced load has succeeded. Otherwise, the advanced load has failed and a predetermined type of recovery is performed in order to retrieve (load) the appropriate valid data (or value). Data obtained by the advanced load instruction may not be the correct value (i.e. it differs from the value that would have been obtained), had it been executed as a load at the original position. For example, after an advanced load instruction loads a data from a selected memory location, an intervening store instruction may store a different data to the same memory location. In this instance, memory location corresponding to the loaded data of the advanced load is modified by the subsequent store to that memory location and if the load had been executed at the original position, the modified data would have been obtained. In order to keep track of such changes to memory locations, an ALAT is used to maintain a list of advanced load locations and a subsequent corresponding check instruction checks the ALAT to determine if a location specified by the advanced load entry may have been modified.
Thus, when the advanced load instruction is executed, an entry is placed in the ALAT to identify the location of the advanced load access. The subsequent advanced load checking operation looks for an entry in the ALAT and if the entry is present, then the advanced load operation is still deemed to be valid. However, if an intervening instruction which could modify the memory location, such as an intervening store instruction, to the same corresponding memory location occurs, then the entry is removed from the ALAT. When the subsequent checking is performed for the advanced load entry in the ALAT, the absence of the entry signifies that the data of the memory location may have been changed. The system then responds based on the particular checking instruction utilized.
For example, a check load instruction can be used for reloading the data. The check load searches the ALAT for a matching entry and, if found, the speculative operation of the advanced load is determined to be successful and the check load instruction is ignored. If a matching entry is not found, the speculation is deemed to be unsuccessful and the check load loads the data from the memory location, as though the advanced load instruction never existed.
Another checking instruction is an advanced load check instruction, which is used as a speculation check. If the speculation of the advanced load is successful, the execution continues and no recovery is necessary. However if the speculation was unsuccessful, in that the matching entry in the ALAT is found, the advanced load check instruction causes a branch to a recovery routine. The recovery routine contains instructions to respond to the failure of the advanced load.
Although a variety of advanced load and ALAT schemes are known, none are known to operate with processor ordering semantics. Current ALAT schemes are utilized in a single processing environment in which a set of instructions operate on a single processor. The advanced load instruction, is a speculative operation performed out of order from the original load instruction location, but it is still constrained by the instruction sequencing constraints imposed on the system. However, when system ordering constraints are imposed, such as when multiple processors are present in a system, the ALAT should also conform to such ordering constraints. For example, when multiple processors have access to a shared memory location, certain ordering constraints are imposed on the processors to ensure ordering.
Ordering constraints are used to guarantee that single and multiple processor systems will operate with predictable results when executing dependent accesses to possibly similar locations. For example, for two processors executing a code sequence where processor
0
was executing a store to memory location A followed by a store to memory location B (ensured by ordering constraints) and processor
1
was executing a load from memory location B followed by a load from memory location A (ensured by ordering constraints), then it would follow that if the load from B returned the data stored to B, the load from A should return the data stored to A. Since advanced loads perform a load operation on a memory location, the advanced loads should also take into consideration these dependencies.
Accordingly, in order to abide by the access ordering semantics, the advanced load and ALAT operations should abide by the access ordering semantics. The present invention provides for ALAT ordering.
REFERENCES:
patent: 5420990 (1995-05-01), McKeen et al.
patent: 5420991 (1995-05-01), Konigsfeld et al.
patent: 5542075 (1996-07-01), Ebcioglu et al.
patent: 5634023 (1997-05-01), Adler et al.
patent: 5758051 (1998-05-01), Moreno et al.
patent: 5848256 (1998-12-01), Call et al.
patent: 5931957 (1999-08-01), Konigsburg et al.
patent: 5961636 (1999-10-01), Brooks et al.
patent: 6370632 (2002-04-01), Kikuta et al.
patent: 6484254 (2002-11-01), Chowdhury et al.
patent: 6505296 (2003-01-01), Morris et al.
patent: 6542988 (2003-04-01), Tremblay et al.
patent: 6598156 (2003-07-01), Arora
patent: 1 150 202 (2001-10-01), None
patent: WO 01/67239 (2001-09-01), None
Blakely , Sokoloff, Taylor & Zafman LLP
Intel Corporation
Treat William M.
LandOfFree
Method and apparatus to provide advanced load ordering does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus to provide advanced load ordering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus to provide advanced load ordering will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3222008