US4977498A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data processing system having a data memory interlock coherency scheme
Assignee: Hewlett Packard Development Co LP
•
Filing: 1988-04-01
•
Granted: 1990-12-11
•
Expires: 2008-04-01
Abstract
Abstract This invention is directed to a memory system that determines which blocks of a set of associative blocks in cache memory are unavailable for replacement. This is accomplished by operating the memory system to maintain a duplicate set of tags which track block ownership for this cache pursuant to a "snoopy" protocol. In addition, the cache system maintains a bit associated with each memory address to indicate whether any data blocks resident in it have been locked. The interlock status of the data blocks in the cache is not communicated to the memory system. Once a block is locked, it cannot be allocated for replacement until it is unlocked. When the cache system encounters a locked block, it skips over that block and allocates the next block of the associative blocks. From this, the memory system infers, by means of a replacement algorithm, that block is being locked and, therefore, cannot be replaced. This enables the memory system to implement an irregular replacement policy for this cache when the block to be replaced is owned and locked.
Inventors
- 👤 Joseph Rastegar
- 👤 Anne S. Valiton
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 17:34
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0806; G06F12/0815; G06F12/0817; G06F12/0822; G06F12/12; G06F12/121; G06F12/126
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
335 words
A method of operating a device having a set-associative cache memory structure and a first pointer system to track set locations in said set-associate cache memory structure that are available for replacement, the device being coupled to a memory controller, the memory controller having a second pointer system to independently track said set locations available for replacement in said set-associative cache memory structure, comprising the steps of: (a) operating said device to assert a data lock condition for a preselected set location of said set-associative cache memory structure; (b) utilizing the first pointer system to locate a next available set location for replacement in said set-associative cache memory structure; (c) utilizing the second pointer system to locate said next available set location; (d) incrementing said first pointer system to point to another next available set location of said set-associative cache memory structure when said next available set location pointed to by said first pointer system is said preselected set location; (e) independently incrementing said second pointer system in said memory controller from said next available set location to said another next available set location, subsequent to said incrementing of said first pointer system by: (i) issuing a data transfer command including a memory address to a data block stored in said another next available set location of said set-associative cache memory structure, the data transfer command being issued from said device to said memory controller, (ii) operating said memory controller to store a corresponding memory address for each respective data block stored in each respective set location in said set-associative cache memory structure, (iii) operating said memory controller to compare said memory address in said command, and an address stored in said memory controller in respect of said next available set location to determine a mismatch; and (iv) incrementing said second pointer system to said another next available set location when said comparing step indicates a mismatch, whereby said memory controller remotely and independently tracks the location of data within said set-associative cache memory structure.
Claim 2
Independent Claim
335 words
A method of operating a device having a set-associative cache memory structure and a first pointer system to track set locations in said set-associate cache memory structure that are available for replacement, the device being coupled to a memory controller, the memory controller having a second pointer system to independently track said set locations available for replacement in said set-associative cache memory structure, comprising the steps of: (a) operating said device to assert a data lock condition for a preselected set location of said set-associative cache memory structure; (b) utilizing the first pointer system to locate a next available set location for replacement in said set-associative cache memory structure; (c) utilizing the second pointer system to locate said next available set location; (d) incrementing said first pointer system to point to another next available set location of said set-associative cache memory structure when said next available set location pointed to by said first pointer system is said preselected set location; (e) independently incrementing said second pointer system in said memory controller from said next available set location to said another next available set location, subsequent to said incrementing of said first pointer system by: (i) issuing a data transfer command including a memory address to a data block stored in said another next available set location of said set-associative cache memory structure, the data transfer command being issued from said device to said memory controller, (ii) operating said memory controller to store a corresponding memory address for each respective data block stored in each respective set location in said set-associative cache memory structure, (iii) operating said memory controller to compare said memory address in said command, and an address stored in said memory controller in respect of said next available set location to determine a mismatch; and (iv) incrementing said second pointer system to said another next available set location when said comparing step indicates a mismatch, whereby said memory controller remotely and independently tracks the location of data within said set-associative cache memory structure.
Claim 3
Dependent Claim
14 words
A method according to claim 1, wherein said device comprises an I/O adapter module.
Claim 4
Dependent Claim
18 words
A method according to claim 2, wherein said I/O adapter is coupled to at least one operating device.
Claim 5
Dependent Claim
33 words
A method according to claim 1, further comprising the step of initializing said first pointer system and said second pointer system to a commonly designated starting set within said set associative cache structure.
Claim 6
Dependent Claim
37 words
A method according to claim 1 comprising the further step of repeating (e) (i) through (e) (iv) until a match is found between said memory address in said command and said address stored in said memory controller.
Claim 7
Dependent Claim
80 words
A method according to claim 1, comprising the further steps of: (a) prior to said step of asserting a data lock condition, operating each of said device and said memory controller to set an ownership status indicator to indicate owned status of said preselected set location; and (b) performing said comparing step in said memory controller when and only when said address stored in respect of said next available set location has said ownership status indicator set to owned status.
Claim 8
Dependent Claim
298 words
A data processing system comprising: (a) a device having a set-associative cache memory structure and a first pointer system to track set locations in said set-associative cache memory structure that are available for replacement, said first pointer system indicating a next available set location; (b) a memory controller coupled to said device and having a second pointer system to independently track said set locations available for replacement in said set-associative cache memory structure, the second pointer system pointing to said next available set location; (c) said device including means for indicating a lock status for a preselected set location within said set-associative cache memory structure; (d) said device including means for incrementing said first pointer system to another next available set location within said set-associative cache memory structure when said next available set location pointed to by said first pointer system is said first preselected set location; (e) said memory controller including means for incrementing said second pointer system to said another next available set location within said memory controller, subsequent to said incrementing of said first pointer system, the means comprising: (i) means for receiving a data transfer command from said device, said data transfer command including a memory address to a data block stored in said another next available set location; (ii) a tag store in said memory controller for storing a corresponding memory address for a respective data block stored in each set location in said set-associative cache memory structure; (iii) means for comparing said memory address in said data transfer command and a memory address in said tag store corresponding to said next available set location; and (iv) means for incrementing said second pointer system to said another next available set location within said memory controller when said means for comparing indicates a mismatch.
Claim 9
Dependent Claim
298 words
A data processing system comprising: (a) a device having a set-associative cache memory structure and a first pointer system to track set locations in said set-associative cache memory structure that are available for replacement, said first pointer system indicating a next available set location; (b) a memory controller coupled to said device and having a second pointer system to independently track said set locations available for replacement in said set-associative cache memory structure, the second pointer system pointing to said next available set location; (c) said device including means for indicating a lock status for a preselected set location within said set-associative cache memory structure; (d) said device including means for incrementing said first pointer system to another next available set location within said set-associative cache memory structure when said next available set location pointed to by said first pointer system is said first preselected set location; (e) said memory controller including means for incrementing said second pointer system to said another next available set location within said memory controller, subsequent to said incrementing of said first pointer system, the means comprising: (i) means for receiving a data transfer command from said device, said data transfer command including a memory address to a data block stored in said another next available set location; (ii) a tag store in said memory controller for storing a corresponding memory address for a respective data block stored in each set location in said set-associative cache memory structure; (iii) means for comparing said memory address in said data transfer command and a memory address in said tag store corresponding to said next available set location; and (iv) means for incrementing said second pointer system to said another next available set location within said memory controller when said means for comparing indicates a mismatch.
Claim 10
Dependent Claim
34 words
The data processing system of claim 7 wherein said device includes a tag store, including a plurality of tag entries in said tag store and an interlock bit in each of said tag entries.
Claim 11
Dependent Claim
96 words
The data processing system of claim 8 wherein the means for incrementing the location of said first pointer system comprises: (a) a tag entry comprises of a memory address to be written to, said memory address having an interlock bit as one of a plurality of bits; (b) means for determining if said interlock bit is set in said tag entry of said memory address to be written to; and (c) means for incrementing said first pointer system to said another next available memory set in said set associative cache when said interlock bit is set.
Claim 12
Dependent Claim
15 words
The data processing system of claim 8 wherein said device comprises an I/O adapter module.
Claim 13
Dependent Claim
19 words
The data processing system of claim 10 wherein said I/O adapter is coupled to at least one operating device.
Claim 14
Dependent Claim
109 words
The data processing system of claim 11 wherein the I/O adapter further comprises: (a) a memory cache comprising an odd bank and an even bank, the odd bank and even bank further divided into a low block and a high block; and (b) means for directing data blocks to preselected sets in said set-associative cache memory, the means comprising: (i) said first pointer system, said first pointer system having four, three-bit pointers, (ii) a plurality of bits in each first tag entry, and (iii) a bit detection means for determining the bank and block selection within said preselected within said preselected memory set of said set-associative cache memory structure.
Claim 15
Dependent Claim
276 words
A data processing system comprising: (a) a device having a set-associative cache memory structure and a first pointer system to track set locations in said set-associative cache memory structure that are available for replacement, said first pointer system indicating a next available set location; (b) a memory controller coupled to said device and having a second pointer system to independently track said set locations available for replacement in said set-associative cache memory structure, the second pointer system pointing to said next available set location; (c) said device including means for incrementing said first pointer system to another next available location within said set associative cache memory structure when a preselected event precludes the replacement of a data block stored in said available set location; (d) said memory controller including means for incrementing said second pointer system to said another next available set location within said memory controller, subsequent to said incrementing of said first pointer system, the means comprising: (i) means for receiving a data transfer command from said device, said data transfer command including a memory address to a data block stored in said another next available set location; (ii) a tag store in said memory controller for storing a corresponding memory address for a respective data block stored in each set location in said set associative cache memory structure; (iii) means for comparing said memory address in said data transfer command and a memory address in said tag store corresponding to said next available set location; and (iv) means for incrementing said second pointer system to said another next available set location within said memory controller when said means for comparing indicates a mismatch.
Claim 16
Dependent Claim
276 words
A data processing system comprising: (a) a device having a set-associative cache memory structure and a first pointer system to track set locations in said set-associative cache memory structure that are available for replacement, said first pointer system indicating a next available set location; (b) a memory controller coupled to said device and having a second pointer system to independently track said set locations available for replacement in said set-associative cache memory structure, the second pointer system pointing to said next available set location; (c) said device including means for incrementing said first pointer system to another next available location within said set associative cache memory structure when a preselected event precludes the replacement of a data block stored in said available set location; (d) said memory controller including means for incrementing said second pointer system to said another next available set location within said memory controller, subsequent to said incrementing of said first pointer system, the means comprising: (i) means for receiving a data transfer command from said device, said data transfer command including a memory address to a data block stored in said another next available set location; (ii) a tag store in said memory controller for storing a corresponding memory address for a respective data block stored in each set location in said set associative cache memory structure; (iii) means for comparing said memory address in said data transfer command and a memory address in said tag store corresponding to said next available set location; and (iv) means for incrementing said second pointer system to said another next available set location within said memory controller when said means for comparing indicates a mismatch.
References Cited (Backward Citations)
US4513367A
Cited
US4622631A
Cited
US4622631B1
Cited
US4775955A
Cited
US4885680A
Cited
US4912630A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-12-10 | 1994-06-11 | 1994-12-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-12-10 | 1998-06-11 | 1998-12-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-12-10 | 2002-06-11 | 2002-12-11 | $7700.00 | Window Closed / Lapsed |