US5625835A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for reordering memory operations in a superscalar or very long instruction word processor
Assignee: International Business Machines Corp
•
Filing: 1995-05-10
•
Granted: 1997-04-29
•
Expires: 2015-05-10
Abstract
Abstract A method and apparatus for reordering memory operations in superscalar or very long instruction word (VLIW) processors is described, incorporating a mechanism that allows for arbitrary distance between reading from memory and using data loaded out-of-order, and that allows for moving load operations earlier in the execution stream. This mechanism tolerates ambiguous memory references. The mechanism executes only one additional instruction for disambiguation purposes, thus producing good performance, and integrates memory disambiguation with speculative execution of instructions. The overhead introduced is only one instruction, and the load operation can be arbitrarily moved earlier in the instruction stream. The mechanism can cope with conflicts that occur as a result of an unexpected combination of store/load instructions, can be used in a coherent multiprocessor context, and combines speculative execution with reordering of memory operations in a way which requires simple hardware support.
Inventors
- 👤 Mahmut K. Ebcioglu
- 👤 David A. Luick
- 👤 Jaime H. Moreno
- 👤 Gabriel M. Silberman
- 👤 Philip B. Winterfield
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 14:23
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3824; G06F9/383; G06F9/30003; G06F9/3004; G06F9/30043; G06F9/30181; G06F9/30185; G06F9/3834; G06F9/3836; G06F9/3842; G06F9/3861; G06F9/3863; G06F9/3865
Claims Analysis
Total Claims: 5
Claim 1
Independent Claim
242 words
A method of reordering memory operations in superscalar or very long instruction word (VLIW) processors even for arbitrarily separated and ambiguous memory references comprising the steps of: decoding instructions issued by a processor; determining if a decoded instruction is an out-of-order load instruction and, if so, determining if the out-of-order load instruction generates an exception; setting a delayed exception bit associated with a target register of the load instruction for an out-of-order load instruction which generates an exception; saving a memory address of an out-of-order load instruction which does not generate an exception in an address comparator and setting a valid bit for the saved memory address in the address comparator; determining if a decoded instruction is a store operation; comparing a range of memory addresses referenced by a decoded store instruction with all entries in the address comparator; for each match of an entry in the address comparator, setting the valid bit of the corresponding entry to invalid; determining if a decoded instruction is a commit operation; checking the valid bit of the address comparator entry associated with a target register of the decoded commit operation and generating a delayed exception if the valid bit is set to invalid and, at the same time, checking the delayed exception bit of a source register of the commit operation and, if the delayed exception bit is set, generating a delayed exception; and aborting an excepting instruction and transferring control to an exception handler.
Claim 2
Independent Claim
242 words
A method of reordering memory operations in superscalar or very long instruction word (VLIW) processors even for arbitrarily separated and ambiguous memory references comprising the steps of: decoding instructions issued by a processor; determining if a decoded instruction is an out-of-order load instruction and, if so, determining if the out-of-order load instruction generates an exception; setting a delayed exception bit associated with a target register of the load instruction for an out-of-order load instruction which generates an exception; saving a memory address of an out-of-order load instruction which does not generate an exception in an address comparator and setting a valid bit for the saved memory address in the address comparator; determining if a decoded instruction is a store operation; comparing a range of memory addresses referenced by a decoded store instruction with all entries in the address comparator; for each match of an entry in the address comparator, setting the valid bit of the corresponding entry to invalid; determining if a decoded instruction is a commit operation; checking the valid bit of the address comparator entry associated with a target register of the decoded commit operation and generating a delayed exception if the valid bit is set to invalid and, at the same time, checking the delayed exception bit of a source register of the commit operation and, if the delayed exception bit is set, generating a delayed exception; and aborting an excepting instruction and transferring control to an exception handler.
Claim 3
Dependent Claim
71 words
The method of reordering memory operations in superscalar or very long instruction word (VLIW) processors recited in claim 1 further comprising the steps of: determining if the decoded instruction is other than an out-of-order load, a store or a commit instruction; and checking the delayed exception bit for all source registers used by the instruction and if any delayed exception bits are set, setting corresponding delayed exception bits in target registers.
Claim 4
Dependent Claim
278 words
A superscalar or very long instruction word (VLIW) processor capable of reordering memory operations even for arbitrarily separated and ambiguous memory references comprising: a decoder for decoding instructions issued by the processor; a plurality of registers each having delayed exception bits accessible as special purpose registers; functional means for determining if a decoded instruction is an out-of-order load instruction and, if so, determining if the out-of-order load instruction generates an exception, said functional means setting a delayed exception bit associated with a target register of the load instruction for an out-of-order load instruction which generates an exception; an address comparator for saving a memory address of an out-of-order load instruction which does not generate an exception, said address comparator having a valid bit which is set for the saved memory address; said functional means determining if a decoded instruction is a store operation; said address comparator comparing a range of memory addresses referenced by a decoded store instruction with all entries in the address comparator and, for each match of an entry in the address comparator, setting the valid bit of the corresponding entry to invalid; said functional means determining if a decoded instruction is a commit operation, checking the valid bit of the address comparator entry associated with a source register of the decoded commit operation and generating a delayed exception if the valid bit is set to invalid and, at the same time, checking the delayed exception bit of a source register of the commit operation and, if the delayed exception bit is set, generating a delayed exception and aborting the excepting instruction; and an exception handler executing recovery code when an excepting instruction is aborted.
Claim 5
Dependent Claim
278 words
A superscalar or very long instruction word (VLIW) processor capable of reordering memory operations even for arbitrarily separated and ambiguous memory references comprising: a decoder for decoding instructions issued by the processor; a plurality of registers each having delayed exception bits accessible as special purpose registers; functional means for determining if a decoded instruction is an out-of-order load instruction and, if so, determining if the out-of-order load instruction generates an exception, said functional means setting a delayed exception bit associated with a target register of the load instruction for an out-of-order load instruction which generates an exception; an address comparator for saving a memory address of an out-of-order load instruction which does not generate an exception, said address comparator having a valid bit which is set for the saved memory address; said functional means determining if a decoded instruction is a store operation; said address comparator comparing a range of memory addresses referenced by a decoded store instruction with all entries in the address comparator and, for each match of an entry in the address comparator, setting the valid bit of the corresponding entry to invalid; said functional means determining if a decoded instruction is a commit operation, checking the valid bit of the address comparator entry associated with a source register of the decoded commit operation and generating a delayed exception if the valid bit is set to invalid and, at the same time, checking the delayed exception bit of a source register of the commit operation and, if the delayed exception bit is set, generating a delayed exception and aborting the excepting instruction; and an exception handler executing recovery code when an excepting instruction is aborted.
References Cited (Backward Citations)
US4903264A
Cited
US5526499A
Cited
US5542075A
Cited
US5557763A
Cited
US5450560A
Cited
US5463745A
Cited
US5537559A
Cited
US5546599A
Cited
US5548738A
Cited
US5559976A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-04-28 | 2000-10-28 | 2001-04-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-04-28 | 2004-10-28 | 2005-04-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-04-28 | 2008-10-28 | 2009-04-29 | $7700.00 | Window Closed / Lapsed |