Patent US5893149A successfully refreshed from Google Patents.
US5893149A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Flushing of cache memory in a computer system
Assignee: Oracle America Inc
•
Filing: 1996-07-01
•
Granted: 1999-04-06
•
Expires: 2016-07-01
Abstract
Abstract An efficient streamlined cache coherent protocol for replacing data is provided in a multiprocessor distributed-memory computer system. In one implementation, the computer system includes a plurality of subsystems, each subsystem includes at least one processor and an associated cache and directory. The subsystems are coupled to a global interconnect via global interfaces. In one embodiment, when data is replaced from a requesting subsystem, an asynchronous flush operation is initiated. In this implementation, the flush operation includes a pair of decoupled local flush instruction and corresponding global flush instruction. By decoupling the local flush instructions from the global flush instructions, once the requesting processor in the requesting subsystem is done issuing the local flush instruction, the requesting processor does not have to wait for a corresponding response from home location associated with the data being replaced. Instead, the requesting processor is freed up quickly since there is no need to wait for an acknowledgment from the home location (home subsystem) over the global interconnect. The home subsystem responds with an appropriate ACK message. The requesting subsystem reissues a read-to-own (RTO) transaction on its local interconnect thereby retrieving and invalidating any copy(s) of the data in the requesting subsystem. A Completion message is sent to the home subsystem together with the dirty data. Subsequently, a confirmation of the completion of the flush operation can be implemented using a "synchronization" mechanism to verify that all previously valid cache lines associated with a page have been successfully replaced with respect to their home location and the replaced cache lines are now marked "invalid" at the home subsystem.
Inventors
- 👤 Erik E. Hagersten
- 👤 Aleksandr Guzovskiy
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 14:26
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0806; G06F12/0813; G06F12/0808; G06F2212/00; G06F2212/25; G06F2212/254; G06F2212/2542
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
270 words
A method for replacing data while maintaining coherency of said data within a computer system having at least a first subsystem and a second subsystem coupled to each other via an interconnect, wherein said first subsystem and said second subsystem each include a local interconnect, a global interface, at least one processor, and at least one cache, and wherein said first subsystem is a home of said data, the method comprising: selecting a page of data in said at least one cache of said second subsystem, wherein said page of data contains a plurality of data lines; freezing all accesses of said second subsystem to said page of data; identifying at least one data line of said plurality of data lines of said page of data, wherein said at least one data line contains data that requires flushing; flushing said at least one data line of said plurality of data lines of said page of data, wherein said flushing includes issuing of a local flush instruction and a global flush instruction, said local flush instruction is issued by said at least one processor of said second subsystem to said global interface of said second subsystem, and said global flush instruction is issued by said at least one processor of said second subsystem to said first subsystem in response to said local flush instruction, and wherein said global flush instruction is performed asynchronously from said local flush instruction; and maintaining a coherency between said at least one data line of said plurality of data lines of said page of data flushed in said second subsystem and data in said first subsystem.
Claim 2
Independent Claim
270 words
A method for replacing data while maintaining coherency of said data within a computer system having at least a first subsystem and a second subsystem coupled to each other via an interconnect, wherein said first subsystem and said second subsystem each include a local interconnect, a global interface, at least one processor, and at least one cache, and wherein said first subsystem is a home of said data, the method comprising: selecting a page of data in said at least one cache of said second subsystem, wherein said page of data contains a plurality of data lines; freezing all accesses of said second subsystem to said page of data; identifying at least one data line of said plurality of data lines of said page of data, wherein said at least one data line contains data that requires flushing; flushing said at least one data line of said plurality of data lines of said page of data, wherein said flushing includes issuing of a local flush instruction and a global flush instruction, said local flush instruction is issued by said at least one processor of said second subsystem to said global interface of said second subsystem, and said global flush instruction is issued by said at least one processor of said second subsystem to said first subsystem in response to said local flush instruction, and wherein said global flush instruction is performed asynchronously from said local flush instruction; and maintaining a coherency between said at least one data line of said plurality of data lines of said page of data flushed in said second subsystem and data in said first subsystem.
Claim 3
Dependent Claim
39 words
The method as recited in claim 1 wherein said selecting a page of data in said at least one cache of said second subsystem includes a criterion suitable to select said page of data that is suitable for replacement.
Claim 4
Dependent Claim
16 words
The method as recited in claim 2 wherein said criterion includes a least recently used criterion.
Claim 5
Dependent Claim
36 words
The method as recited in claim 1 wherein said freezing all accesses of said second subsystem to said page of data includes denying local accesses initiated by said at least one processor of said second subsystem.
Claim 6
Dependent Claim
36 words
The method as recited in claim 1 wherein said identifying at least one data line of said plurality of data lines of said page of data includes determining if said data line is in valid status.
Claim 7
Dependent Claim
58 words
The method as recited in claim 5 wherein said valid status of said data line includes either an owned state or a modified state, wherein said owned said indicates that said second subsystem has a cached copy of said data line and said modified state indicates that said second subsystem is the sole owner of said data line.
Claim 8
Dependent Claim
31 words
The method as recited in claim 6 wherein a subsystem that has said owned state of said data line is configured to perform a write-back upon replacement of said data line.
Claim 9
Dependent Claim
67 words
The method as recited in claim 1 wherein said flushing said at least one data line of said plurality of data lines of said page of data is executed when said data line is in said valid status, and said flushing is not executed if said data line is in an invalid status, wherein said invalid status indicates that said second subsystem can discard said data line.
Claim 10
Dependent Claim
59 words
The method as recited in claim 8 wherein said invalid status of said data line includes either an invalid state or a shared state, wherein said invalid state indicates that said second subsystem has no cached copy of said data line, and said shared state indicates that said second subsystem has a shared cached copy of said data line.
Claim 11
Dependent Claim
74 words
The method as recited in claim 1 wherein said maintaining said coherency comprises: sending a synchronization request from said second subsystem to said first subsystem; verifying that said data is now coherent between said first subsystem and said second subsystem; and sending an acknowledgment from said first subsystem to said second subsystem in response to said synchronization request, said acknowledgment indicating that said data is now coherent between said second and said first subsystem.
Claim 12
Dependent Claim
78 words
The method as recited in claim 10 wherein said acknowledgement by said first system to said second subsystem comprises either a first message, a second message, or a third message; wherein said first message is indicative of either said owned state or said modified state of said data line, said second message is indicative of said shared cached copy of said data line, and said third message is indicative of said no cached copy of said data line.
Claim 13
Independent Claim
298 words
A method for flushing a selected page of data in a cache memory in a requesting subsystem while maintaining coherency of said data with a home subsystem within a computer system, wherein said selected page of data comprises a plurality of data lines, said requesting subsystem is coupled to said home subsystem via an interconnect, said requesting subsystem and said home subsystem each include a local interconnect, a global interface, at least one processor, and at least one said cache memory, wherein said computer system comprises at least said home subsystem and requesting subsystem, the method comprising: issuing a local flush instruction for each data line of said plurality of data lines within said selected page in said cache memory of said requesting subsystem by said at least one processor, wherein said data line is identified for replacement; issuing a global flush instruction by said at least one processor of said requesting subsystem to said home subsystem in response to said local flush instruction, wherein said issuing of said global flush instruction is performed asynchronously from said local flush instruction; sending an acknowledgment message by said home subsystem to said requesting subsystem in response to said global flush instruction issued by said requesting subsystem, wherein said acknowledgement message is indicative of a status of said data line; issuing of a read-to-own transaction by said requesting subsystem on said local interconnect of said requesting subsystem in response to said acknowledgment message indicative of at least one of said status of said data line; sending a completion message by said requesting subsystem to said home subsystem; and updating a directory in said home subsystem by said home subsystem in response to said completion message, wherein said directory comprises at least one entry indicative of said status of said data line.
Claim 14
Independent Claim
298 words
A method for flushing a selected page of data in a cache memory in a requesting subsystem while maintaining coherency of said data with a home subsystem within a computer system, wherein said selected page of data comprises a plurality of data lines, said requesting subsystem is coupled to said home subsystem via an interconnect, said requesting subsystem and said home subsystem each include a local interconnect, a global interface, at least one processor, and at least one said cache memory, wherein said computer system comprises at least said home subsystem and requesting subsystem, the method comprising: issuing a local flush instruction for each data line of said plurality of data lines within said selected page in said cache memory of said requesting subsystem by said at least one processor, wherein said data line is identified for replacement; issuing a global flush instruction by said at least one processor of said requesting subsystem to said home subsystem in response to said local flush instruction, wherein said issuing of said global flush instruction is performed asynchronously from said local flush instruction; sending an acknowledgment message by said home subsystem to said requesting subsystem in response to said global flush instruction issued by said requesting subsystem, wherein said acknowledgement message is indicative of a status of said data line; issuing of a read-to-own transaction by said requesting subsystem on said local interconnect of said requesting subsystem in response to said acknowledgment message indicative of at least one of said status of said data line; sending a completion message by said requesting subsystem to said home subsystem; and updating a directory in said home subsystem by said home subsystem in response to said completion message, wherein said directory comprises at least one entry indicative of said status of said data line.
Claim 15
Dependent Claim
100 words
The method as recited in claim 12 wherein said status of said data line comprises one of either an owned state, a modified state, a shared state, or an invalid state of said data line, wherein said owned state indicates at least said home subsystem has a cached copy of said data line, said modified state indicates said home subsystem is the sole owner of said data line, said shared state indicates at least said home subsystem has a shared copy of said data line, and said invalid state indicates said home subsystem has no copy of said data line.
Claim 16
Dependent Claim
75 words
The method as recited in claim 13 wherein said sending said acknowledgment message by said home subsystem comprises either a first message, a second message, or a third message; wherein said first message is indicative of either said owned state or said modified state of said data line, said second message is indicative of said shared state of said data line, and said third message is indicative of said invalid state of said data line.
Claim 17
Dependent Claim
36 words
The method as recited in claim 14 wherein either said second message or said third message sent by said home subsystem to said requesting subsystem further indicates that said requesting subsystem can discard said data line.
Claim 18
Dependent Claim
49 words
The method as recited in claim 12 wherein said flushing is further comprises synchronization of all identified data lines in said page of data of said requesting subsystem wherein said synchronization results in every line of said all identified data lines having said invalid state in said home subsystem.
Claim 19
Independent Claim
284 words
A system for replacing a selected page of data in a cache memory in a requesting subsystem while maintaining coherency of said data with a home subsystem within a computer system, wherein said selected page of data comprises a plurality of data lines, said requesting subsystem is coupled to said home subsystem via an interconnect, said requesting subsystem and home subsystem each includes a local interconnect, a global interface, at least one processor, and at least one said cache memory, wherein said computer system comprises at least said home subsystem and requesting subsystem, the mechanism comprises: a detector configured to detect a need to replace said data in said cache memory of said requesting subsystem; an identifier configured to identify said selected page of data in said cache memory and to identify at least one data line of said plurality of data lines in said selected page of data in said requesting subsystem; an asynchronous flusher configured to flush all identified data lines in said selected page in said cache memory of said requesting subsystem, wherein said asynchronous flusher is further configured to: issue a local flush instruction for each identified data line of said plurality of data lines, issue a global flush instruction to said home subsystem in response to said local flush instruction, wherein said global flush instruction is asynchronous to said local flush instruction, receive an acknowledgment message sent by said home subsystem in response to said global flush instruction, wherein said acknowledgement message is indicative of a status of said identified data line, issue a read-to-own transaction on said local interconnect of said requesting subsystem in response to said acknowledgment message, and send a completion message to said home subsystem.
Claim 20
Independent Claim
284 words
A system for replacing a selected page of data in a cache memory in a requesting subsystem while maintaining coherency of said data with a home subsystem within a computer system, wherein said selected page of data comprises a plurality of data lines, said requesting subsystem is coupled to said home subsystem via an interconnect, said requesting subsystem and home subsystem each includes a local interconnect, a global interface, at least one processor, and at least one said cache memory, wherein said computer system comprises at least said home subsystem and requesting subsystem, the mechanism comprises: a detector configured to detect a need to replace said data in said cache memory of said requesting subsystem; an identifier configured to identify said selected page of data in said cache memory and to identify at least one data line of said plurality of data lines in said selected page of data in said requesting subsystem; an asynchronous flusher configured to flush all identified data lines in said selected page in said cache memory of said requesting subsystem, wherein said asynchronous flusher is further configured to: issue a local flush instruction for each identified data line of said plurality of data lines, issue a global flush instruction to said home subsystem in response to said local flush instruction, wherein said global flush instruction is asynchronous to said local flush instruction, receive an acknowledgment message sent by said home subsystem in response to said global flush instruction, wherein said acknowledgement message is indicative of a status of said identified data line, issue a read-to-own transaction on said local interconnect of said requesting subsystem in response to said acknowledgment message, and send a completion message to said home subsystem.
Claim 21
Dependent Claim
40 words
The system as recited in claim 17 said home subsystem updates a directory in said home subsystem in response to said completion message, wherein said directory comprises at least one entry indicative of said status of said identified data line.
Claim 22
Dependent Claim
106 words
The system as recited in claim 17 wherein said status of said identified data line comprises one of either an owned state, a modified state, a shared state, or an invalid state of said identified data line, wherein said owned state indicates at least said home subsystem has a cached copy of said identified data line, said modified state indicates said home subsystem is the sole owner of said identified data line, said shared state indicates at least said home subsystem has a shared copy of said identified data line, and said invalid state indicates said home subsystem has no copy of said identified data line.
Claim 23
Dependent Claim
102 words
The system as recited in claim 17 wherein said receive said acknowledgment message sent by said home subsystem message comprises either a first message, a second message, or a third message; wherein said first message is indicative of either said owned state or said modified state of said selected data line, said second message is indicative of said shared state of said selected data line, and said third message is indicative of said invalid state of said selected data line, and wherein either said second message or said third message further indicates that said requesting subsystem can discard said identified data line.
Claim 24
Dependent Claim
47 words
The system as recited in claim 17 further configured to synchronize said flush of said selected page of data of said cache memory of said requesting subsystem until every said identified data line of said selected page of data has said invalid state in said home subsystem.
References Cited (Backward Citations)
US4833601A
Cited
US5025365A
Cited
US5297269A
Cited
US5611070A
Cited
US5249283A
Cited
US5237673A
Cited
US5303362A
Cited
US5313609A
Cited
US5408636A
Cited
US5634068A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-04-05 | 2002-10-05 | 2003-04-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-04-05 | 2006-10-05 | 2007-04-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-04-05 | 2010-10-05 | 2011-04-06 | $7700.00 | Window Closed / Lapsed |