US5699538A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Efficient firm consistency support mechanisms in an out-of-order execution superscaler multiprocessor
Assignee: International Business Machines Corp
•
Filing: 1994-12-09
•
Granted: 1997-12-16
•
Expires: 2014-12-09
Abstract
Abstract Two processor controls for supporting efficient Firm Consistency while allowing out-of-order execution of Load instructions is provided. The Touch control operates when the processor stores a subsequent Store in a pending Store buffer while awaiting any outstanding Loads or Stores. The efficiency of the pending Store is improved by issuing a Touch of the data which pre-loads the line of data in the cache that is the subject of the store. The processor can complete out-of-order execution of a subsequently issued Load relative to a prior Load, but only to its finished state. The subsequently issued Load is not allowed to complete until the prior Load is completed. The Finished Load Cancellation control ensures that Firm Consistency is maintained by canceling any finished Loads, and subsequent instructions, when the subject of the Load is the same as an invalidation request from a multiprocessor.
Inventors
- 👤 Hung Qui Le
- 👤 Kimming So
- 👤 Bao-Binh Truong
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 11:43
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3824; G06F9/383; G06F9/3834
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
183 words
A method of supporting firm consistency and out-of-order instruction execution by a particular processor in a data processing system comprising a plurality of processors, a cache associated with said particular processor, and system memory, each processor issuing memory operations, including store and load, the method comprising the steps of: issuing first and second instructions, wherein said first instruction precedes said second instruction in a consecutive order, and wherein said second instruction is a store instruction requesting that store data be stored in memory; prior to completion of said first instruction, generating a store address for said store instruction; prior to completion of said first instruction, generating a touch command directed to the cache requesting the exclusive status of a block of memory corresponding to the store address; if the block is not held exclusively by the cache, issuing a command to system memory requesting the block be sent to the cache in an exclusive state; and in response to completion of all instructions preceding said store instruction in said consecutive order, writing the store data associated with the store instruction to the cache.
Claim 2
Independent Claim
183 words
A method of supporting firm consistency and out-of-order instruction execution by a particular processor in a data processing system comprising a plurality of processors, a cache associated with said particular processor, and system memory, each processor issuing memory operations, including store and load, the method comprising the steps of: issuing first and second instructions, wherein said first instruction precedes said second instruction in a consecutive order, and wherein said second instruction is a store instruction requesting that store data be stored in memory; prior to completion of said first instruction, generating a store address for said store instruction; prior to completion of said first instruction, generating a touch command directed to the cache requesting the exclusive status of a block of memory corresponding to the store address; if the block is not held exclusively by the cache, issuing a command to system memory requesting the block be sent to the cache in an exclusive state; and in response to completion of all instructions preceding said store instruction in said consecutive order, writing the store data associated with the store instruction to the cache.
Claim 3
Dependent Claim
44 words
A method according to claim 1, wherein each processor further comprises a pending store queue, further comprising the step of storing the store address and store data in a pending store queue, prior to the step of writing the store data to the cache.
Claim 4
Independent Claim
177 words
A method of supporting firm consistency and out-of-order instruction execution by a processor in a data processing system comprising a plurality of processors and system memory, each processor issuing memory operations, including store and load, the method comprising the steps of: consecutively issuing a plurality of instructions including a load and at least one store in an issuing processor, wherein the load can finish execution in the issuing processor non-consecutively with respect to the store; temporarily recording a consecutive order of all of said plurality of instructions in a completion table pending completion; detecting an invalidation request from another processor among said plurality of processors; in response to receipt of an invalidation request from another processor among said plurality of processors at said issuing processor, said invalidation request indicating at least a portion of an address, determining if said at least a portion of an address within said invalidation request matches a corresponding portion of an address associated with a finished load recorded in said completion table; and in response to said determination, canceling the finished load.
Claim 5
Independent Claim
177 words
A method of supporting firm consistency and out-of-order instruction execution by a processor in a data processing system comprising a plurality of processors and system memory, each processor issuing memory operations, including store and load, the method comprising the steps of: consecutively issuing a plurality of instructions including a load and at least one store in an issuing processor, wherein the load can finish execution in the issuing processor non-consecutively with respect to the store; temporarily recording a consecutive order of all of said plurality of instructions in a completion table pending completion; detecting an invalidation request from another processor among said plurality of processors; in response to receipt of an invalidation request from another processor among said plurality of processors at said issuing processor, said invalidation request indicating at least a portion of an address, determining if said at least a portion of an address within said invalidation request matches a corresponding portion of an address associated with a finished load recorded in said completion table; and in response to said determination, canceling the finished load.
Claim 6
Dependent Claim
23 words
A method according to claim 3, wherein the step of canceling the finished load further comprises canceling all instructions following the finished load.
Claim 7
Dependent Claim
184 words
A data processing system comprising: a plurality of processors capable of performing out-of-order execution of instructions, each processor issuing memory operations, including store and load; a separate cache associated with each processor; system memory; means for issuing first and second instructions, wherein said first instruction precedes said second instruction in a consecutive order, and wherein said second instruction is a store instruction requesting that store data be stored in memory; means for generating a store address for said store instruction prior to completion of said first instruction; means for generating a touch command directed to the cache requesting the exclusive status of a block of memory corresponding to the store address, said touch command being generated prior to completion of said first instruction; means, responsive to the block not being held exclusively by the cache, for issuing a command to system memory requesting the block be sent to the cache in an exclusive state; and means for writing the store data associated with the store instruction to the cache in response to completion of all instructions preceding said store instruction in said consecutive order.
Claim 8
Dependent Claim
184 words
A data processing system comprising: a plurality of processors capable of performing out-of-order execution of instructions, each processor issuing memory operations, including store and load; a separate cache associated with each processor; system memory; means for issuing first and second instructions, wherein said first instruction precedes said second instruction in a consecutive order, and wherein said second instruction is a store instruction requesting that store data be stored in memory; means for generating a store address for said store instruction prior to completion of said first instruction; means for generating a touch command directed to the cache requesting the exclusive status of a block of memory corresponding to the store address, said touch command being generated prior to completion of said first instruction; means, responsive to the block not being held exclusively by the cache, for issuing a command to system memory requesting the block be sent to the cache in an exclusive state; and means for writing the store data associated with the store instruction to the cache in response to completion of all instructions preceding said store instruction in said consecutive order.
Claim 9
Dependent Claim
49 words
A data processing system according to claim 5, wherein each processor further comprises a pending store queue for storing the store address and store data, wherein the store data and store address are written to the pending store queue prior to the store data being written to the cache.
Claim 10
Dependent Claim
170 words
A data processing system comprising: a plurality of processors capable of performing out-of-order execution of instructions, each processor issuing memory operations, including store and load; system memory; means for consecutively issuing a plurality of instructions including a load and at least one store in an issuing processor, wherein the load can finish execution in the issuing processor non-consecutively with respect to the store; and a completion table for temporarily recording a consecutive order of all of said plurality of instructions pending completion; means for detecting an invalidation request from another processor among said plurality of processors; means, responsive to receipt of an invalidation request from another processor among said plurality of processors at said issuing processor, said invalidation request indicating at least a portion of an address, for determining if said at least a portion of an address within said invalidation request matches a corresponding portion of an address associated with a finished load recorded in said completion table; and means, responsive to said determination, for canceling the finished load.
Claim 11
Dependent Claim
170 words
A data processing system comprising: a plurality of processors capable of performing out-of-order execution of instructions, each processor issuing memory operations, including store and load; system memory; means for consecutively issuing a plurality of instructions including a load and at least one store in an issuing processor, wherein the load can finish execution in the issuing processor non-consecutively with respect to the store; and a completion table for temporarily recording a consecutive order of all of said plurality of instructions pending completion; means for detecting an invalidation request from another processor among said plurality of processors; means, responsive to receipt of an invalidation request from another processor among said plurality of processors at said issuing processor, said invalidation request indicating at least a portion of an address, for determining if said at least a portion of an address within said invalidation request matches a corresponding portion of an address associated with a finished load recorded in said completion table; and means, responsive to said determination, for canceling the finished load.
Claim 12
Dependent Claim
19 words
A data processing system according to claim 7, further comprising means for canceling all instructions following the finished load.
Claim 13
Dependent Claim
59 words
The method of claim 3, wherein said step of canceling the finished load is performed only if said invalidation request is received by said issuing processor subsequent to said issuing processor finishing said finished load and prior to said issuing processor completing a second load among said plurality of instructions that precedes said finished load in said consecutive order.
Claim 14
Dependent Claim
62 words
The data processing system of claim 7, wherein said means for canceling the finished load performs said cancellation only if said invalidation request is received by said issuing processor subsequent to said issuing processor finishing said finished load and prior to said issuing processor completing a second load among said plurality of instructions that precedes said finished load in said consecutive order.
References Cited (Backward Citations)
US4794521A
Cited
US4991090A
Cited
US4985827A
Cited
US5148536A
Cited
US5016168A
Cited
US5201041A
Cited
US5185871A
Cited
US5208914A
Cited
US5197130A
Cited
US5191649A
Cited
US5261109A
Cited
US5265233A
Cited
US5428761A
Cited
US5467473A
Cited
US5420991A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-12-15 | 2001-06-16 | 2001-12-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-12-15 | 2005-06-16 | 2005-12-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-12-15 | 2009-06-16 | 2009-12-16 | $7700.00 | Window Closed / Lapsed |