US5313609A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Optimum write-back strategy for directory-based cache coherence protocols
Assignee: International Business Machines Corp
•
Filing: 1991-05-23
•
Granted: 1994-05-17
•
Expires: 2011-05-23
Abstract
Abstract A directory-based protocol is provided for maintaining data coherency in a multiprocessing (MP) system having a number of processors with associated write-back caches, a multistage interconnection network (MIN) leading to a shared memory, and a global directory associated with the main memory to keep track of state and control information of cache lines. Upon a request by a requesting cache for a cache line which has been exclusively modified by a source cache, two buffers are situated in the global directory to collectively intercept modified data words of the modified cache line during the write-back to memory. A modified word buffer is used to capture modified words within the modified cache line. Moreover, a line buffer stores an old cache line transferred from the memory, during the write back operation. Finally, the line buffer and the modified word buffer, together, provide the entire modified line to a requesting cache.
Inventors
- 👤 Sandra J. Baylor
- 👤 Kevin P. McAuliffe
- 👤 Bharat D. Rathi
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 04:57
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0806; G06F12/0815; G06F12/0817; G06F12/082
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
164 words
A system for optimizing the performance of a multiprocessor system having write-back caches and a multistage interconnection network connected to a shared memory, by allowing concurrent line transfer and write-back operations, comprising: a modified word buffer configured to store any modified words within a modified cache line when said modified words are written back from a cache; a line buffer configured to store an old cache line transferred from said memory, said old cache line corresponding in address identity with said modified cache line; and a global directory associated with said modified word buffer and said line buffer, said global directory configured to store state and control information pertaining to cache lines, said global directory configured to request a write-back of said modified words from said cache and concurrently request said old cache line from said memory, and said global directory configured to cause said modified word buffer and said line buffer to write, in combination, said modified cache line to a requesting cache.
Claim 2
Independent Claim
164 words
A system for optimizing the performance of a multiprocessor system having write-back caches and a multistage interconnection network connected to a shared memory, by allowing concurrent line transfer and write-back operations, comprising: a modified word buffer configured to store any modified words within a modified cache line when said modified words are written back from a cache; a line buffer configured to store an old cache line transferred from said memory, said old cache line corresponding in address identity with said modified cache line; and a global directory associated with said modified word buffer and said line buffer, said global directory configured to store state and control information pertaining to cache lines, said global directory configured to request a write-back of said modified words from said cache and concurrently request said old cache line from said memory, and said global directory configured to cause said modified word buffer and said line buffer to write, in combination, said modified cache line to a requesting cache.
Claim 3
Dependent Claim
71 words
The system of claim 1, further comprising state lines available to said global directory corresponding to each cache line of the system, each of said state lines specifies a particular cache line, a global state, one or more processors owning the cache line, a wait event indicator indicating whether the state line is waiting for a write-back, and a request event indicator identifying the event which caused any write-back to occur.
Claim 4
Dependent Claim
39 words
The system of claim 1, further comprising a multistage interconnection network having three stages with four switches within each of said stages, said switches having two inputs and two outputs and configured to switch any input to any output.
Claim 5
Independent Claim
128 words
A system for optimizing the performance of a multiprocessor system having write-back caches and a multistage interconnection network connected to a shared memory by allowing concurrent line transfer and write-back operations, comprising: control means for receiving requests for a modified cache line from a requesting cache, for requesting a write-back of modified words in said modified cache line from a source cache and concurrently requesting a transfer of an old cache line from the memory, said old cache line corresponding in address identity with said modified cache line, and for transferring said modified cache line to said requesting cache; and buffer means, connected to said control means, for capturing said modified words written back from said source cache and concurrently storing said old cache line from the memory.
Claim 6
Independent Claim
128 words
A system for optimizing the performance of a multiprocessor system having write-back caches and a multistage interconnection network connected to a shared memory by allowing concurrent line transfer and write-back operations, comprising: control means for receiving requests for a modified cache line from a requesting cache, for requesting a write-back of modified words in said modified cache line from a source cache and concurrently requesting a transfer of an old cache line from the memory, said old cache line corresponding in address identity with said modified cache line, and for transferring said modified cache line to said requesting cache; and buffer means, connected to said control means, for capturing said modified words written back from said source cache and concurrently storing said old cache line from the memory.
Claim 7
Dependent Claim
30 words
The system of claim 4, further wherein and buffer means comprises a modified word buffer configured to store words and a line buffer configured to store said old cache line.
Claim 8
Dependent Claim
71 words
The system of claim 4, further comprising state lines available to said control means corresponding to each cache line of the system, each of said state lines specifies a particular cache line, a global state, one or more processors owning the cache line, a wait event indicator indicating whether the state line is waiting for a write-back, and a request event indicator identifying the event which caused any write-back to occur.
Claim 9
Dependent Claim
39 words
The system of claim 4, further comprising a multistage interconnection network having three stages with four switches within each of said stages, said switches having two inputs and two outputs and configured to switch any input to any output.
Claim 10
Independent Claim
134 words
A method for controlling the performance of a multiprocessor system having write-back caches and a multistage interconnection network connected to a shared memory monitored by a global directory, the method for allowing concurrent line transfer and write-back operations, comprising the steps of: (a) requesting the global directory for a modified cache line; (b) requesting a write-back of modified words in said modified cache line from a source cache and concurrently requesting a transfer of an old cache line from the memory, said old cache line corresponding in address identity with said modified cache line; (c) capturing in said global directory said modified words written back from said source cache and concurrently storing in said global directory said old cache line from said memory; and (d) transferring from said global directory said modified cache line.
Claim 11
Independent Claim
134 words
A method for controlling the performance of a multiprocessor system having write-back caches and a multistage interconnection network connected to a shared memory monitored by a global directory, the method for allowing concurrent line transfer and write-back operations, comprising the steps of: (a) requesting the global directory for a modified cache line; (b) requesting a write-back of modified words in said modified cache line from a source cache and concurrently requesting a transfer of an old cache line from the memory, said old cache line corresponding in address identity with said modified cache line; (c) capturing in said global directory said modified words written back from said source cache and concurrently storing in said global directory said old cache line from said memory; and (d) transferring from said global directory said modified cache line.
Claim 12
Dependent Claim
21 words
The method of claim 8, further including the step of identifying modified words by using a bit vector in a header.
Claim 13
Dependent Claim
33 words
The method of claim 8, further comprising the steps of determining at said global directory that data has been modified in said modified data line and determining the identity of said source cache.
Claim 14
Dependent Claim
21 words
The method of claim 8, further comprising the step of allocating a state line for each cache line of the system.
Claim 15
Dependent Claim
19 words
The method of claim 11, further comprising the step of specifying in said state line a particular cache line.
Claim 16
Dependent Claim
18 words
The method of claim 11, further comprising the step of specifying in said state line a global state.
Claim 17
Dependent Claim
23 words
The method of claim 11, further comprising the step of specifying in said state line one or more processors owning the cache line.
Claim 18
Dependent Claim
26 words
The method of claim 11, further comprising the step of providing a wait event indicator for indicating whether the state line is waiting for a write-back.
Claim 19
Dependent Claim
25 words
The method of claim 11, further comprising the step of providing a request event indicator for identifying the event which caused any write-back to occur.
Claim 20
Dependent Claim
23 words
The method of claim 8, further including the step of transferring said modified words simultaneously to both the memory and the global directory.
References Cited (Backward Citations)
US4471429A
Cited
US4426681A
Cited
US4445174A
Cited
US4484267A
Cited
US4622631A
Cited
US4622631B1
Cited
US4747043A
Cited
US4847804A
Cited
US4755930A
Cited
US4768148A
Cited
US4785395A
Cited
US5119485A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-05-16 | 1997-11-15 | 1998-05-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-05-16 | 2001-11-15 | 2002-05-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-05-16 | 2005-11-15 | 2006-05-17 | $7700.00 | Window Closed / Lapsed |