Parallelized coherent read and writeback transaction processing system for use in a packet switched cache coherent multiprocessor system

• US 5,581,729 A
• Filed: 03/31/1995
• Issued: 12/03/1996
• Est. Priority Date: 03/31/1995
• Status: Expired due to Fees

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Lee, Sue K., Nishtala, Satyanarayana, Coffin, Louis F. III, Loewenstein, Paul, Van Loo, William C., Ebrahim, Zahir
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): KING, CONLEY BURRELL
• Application Number:
  US08/414,763
• Time in Patent Office: 613 Days
• Field of Search: 395/468, 395/470, 395/471, 395/474, 395/472
• US Class Current: 711/143
• CPC Class Codes: G06F 12/0822 Copy directories local copy tags for implementing a bus snooping protocol G06F12/0831
• CPC Class Codes: G06F 12/0828 with concurrent directory accessing, i.e. handling multiple concurrent coherency transactions

Abstract

A multiprocessor computer system is provided having a multiplicity of sub-systems and a main memory coupled to a system controller. An interconnect module, interconnects the main memory and sub-systems in accordance with interconnect control signals received from the system controller. At least two of the sub-systems are data processors, each having a respective cache memory that stores multiple blocks of data and a respective master cache index. Each master cache index has a set of master cache tags (Etags), including one cache tag for each data block stored by the cache memory. Each data processor includes a master interface having master classes for sending memory transaction requests to the system controller. The system controller includes memory transaction request logic for processing each memory transaction request by a data processor. The system controller maintains a duplicate cache index having a set of duplicate cache tags (Dtags) for each data processor. Each data processor has a writeback buffer for storing the data block previously stored in a victimized cache line until its respective writeback transaction is completed and an Nth+1 Dtag for storing the cache state of a cache line associated with a read transaction which is executed prior to an associated writeback transaction of a read-writeback transaction pair. Accordingly, upon a cache miss, the interconnect may execute the read and writeback transactions in parallel relying on the writeback buffer or Nth+1 Dtag to accommodate any ordering of the transactions.

Claims

1. A computer system, comprising:

a system controller;

a main memory coupled to said system controller;

a data processor having a cache memory having N cache lines for storing N data blocks, where N is an integer greater than 4, N master cache tags (Etags), including one Etag for each said cache line in said cache memory, and a writeback buffer for storing a dirty victim data block displaced from said cache memory until it is written back into said main memory;

said Etag for each cache line storing an address index and an Etag state value that indicates whether said data block stored in said cache line includes data modified by said data processor;

said data processor including a master interface, coupled to said system controller, for sending memory transaction requests to said system controller, said memory transaction requests including read requests and writeback requests;

each memory transaction request specifying an address for an associated data block to be read or written;

said master interface further including cache coherence logic for responding to a cache miss on any cache line in said cache memory by (A) generating a read request, and (B) when said cache miss requires a cache line to be victimized and said victim cache line includes modified data, according to the Etag state value in the corresponding Etag, storing the data block having said modified data in said writeback buffer and generating a writeback request;

said system controller including a set of N duplicate cache tags (Dtags), each Dtag corresponding to one of said Etags and storing a Dtag state value and the same address index as the corresponding Etag;

said Dtag state value indicating whether said data block stored in the corresponding cache line includes data modified by said data processor;

said system controller further including an N+1th Dtag;

said system controller including memory transaction request logic for processing each said memory transaction request by said data processor;

said system controller'"'"'s memory transaction request logic including writeback logic for processing said writeback request by writing the data block in said writeback buffer into said main memory and invalidating the state value in the corresponding Dtag;

said system controller'"'"'s memory transaction request logic including read logic for processing said read request by (A) identifying a victim cache line, if any, in said cache memory and accessing the Dtag corresponding to said victim cache line to determine whether processing said read request will displace from said cache memory a data block that includes modified data, (B) retrieving a data block from said main memory corresponding to said read request and providing it to said data processor for storage in said data processor'"'"'s cache memory, (C) storing a Dtag state value and address tag in the Dtag corresponding to said victim cache line when processing said read request does not displace from said cache memory a modified data block and when said corresponding Dtag'"'"'s state value is invalid, (D) storing said Dtag state value and address tag for said read request in said N+1th Dtag when processing said read request does displace from said cache memory a modified data block and said corresponding Dtag'"'"'s state value is not invalid, and (E) transferring said N+1th Dtag into said Dtag corresponding to said victim cache line when said writeback logic invalidates said Dtag state value in said corresponding Dtag; and

wherein said memory transaction request logic processes said read request and writeback request such that processing of either of said read request and writeback request may be completed prior to the other in accordance with resource availability for processing said requests.

2. The computer system of claim 1,

each said read request including a DVP flag that has a first value when said read request corresponds to a cache fill operation that displaces a modified data block from said cache memory, said data block displacement being represented by said writeback request;

said DVP flag having a second value, distinct from said first value, when said read request corresponds to a cache fill operation that does not displace a modified data block from said cache memory; and

said transaction request logic including logic for storing a Dtag state value and address tag in the Dtag corresponding to said victim cache line when DVP flag in said read request has said second value and when said corresponding Dtag'"'"'s state value is invalid, and storing said Dtag state value and address tag for said read request in said N+1th Dtag when said DVP flag in said read request has said first value and said corresponding Dtag'"'"'s state value is not invalid.

3. The computer system of claim 1,

said Etag state being selected from the set of states consisting essentially of:

Exclusive Modified (M), Shared Modified (O), Exclusive Clean (E), Shared Clean (S), and Invalid (I);

said Dtag state being selected from the set of states consisting essentially of;

Exclusive Modified (M), Shared Modified (O), Shared Clean (S), and Invalid (I); and

wherein said Dtag state stored in said Dtags never indicates said Exclusive Clean (E) state and when each data processor modifies data stored in its cache memory in a cache line whose Etag thereby transitions from said E state to said M state, said data processor does not generate a corresponding transaction request and the corresponding Dtag remains unchanged with a Dtag state equal to said M state.

4. The computer system of claim 1,

wherein said main memory is a reflective memory;

said Etag state being selected from the set of states consisting essentially of;

Exclusive Modified (M), Exclusive Clean (E), Shared Clean (S), and Invalid (I);

said Dtag state being selected from the set of states consisting essentially of;

Exclusive Modified (M), Shared Clean (S), and Invalid (I); and

wherein said Dtag state stored in said Dtags never indicates said Exclusive Clean (E) state and when each data processor modifies data stored in its cache memory in a cache line whose Etag thereby transitions from said E state to said M state, said data processor does not generate a corresponding transaction request and the corresponding Dtag remains unchanged with a Dtag state equal to said M state.

5. A computer system, comprising:

a system controller;

a main memory coupled to said system controller;

a data processor having a cache memory having N cache lines for storing N data blocks, where N is an integer greater than 4, N master cache tags (Etags), including one Etag for each said cache line in said cache memory, and a writeback buffer for storing a dirty victim data block displaced from said cache memory until it is written back into said main memory;

said Etag for each cache line storing an address index and an Etag state value that indicates whether said data block stored in said cache line includes data modified by said data processor;

said data processor including a master interface, coupled to said system controller, for sending memory transaction requests to said system controller, said master interface including at least two parallel outgoing request queues for storing memory transaction requests to be sent to said system controller;

said memory transaction requests including read requests and writeback requests;

each memory transaction request specifying an address for an associated data block to be read or written;

said master interface further including cache coherence logic for responding to a cache miss on any cache line in said cache memory by (A) storing a read request in a first one of said outgoing request queues, and (B) when said cache miss requires a cache line to be victimized and said victim cache line, according to the Etag state value in the corresponding Etag, includes modified data, storing the data block having said modified data in said writeback buffer and storing a writeback request in a second one of said outgoing request queues;

said system controller including a set of N duplicate cache tags (Dtags), each Dtag corresponding to one of said Etags and storing a Dtag state value and the same address index as the corresponding Etag;

said Dtag state value indicating whether said data block stored in the corresponding cache line includes data modified by said data processor;

said system controller further including an N+1th Dtag;

said system controller including memory transaction request logic for processing each said memory transaction request by said data processor;

said system controller'"'"'s memory transaction request logic including writeback logic for processing said writeback request by writing the data block in said writeback buffer into said main memory and invalidating said state value in the corresponding Dtag;

said system controller'"'"'s memory transaction request logic including read logic for processing said read request by (A) identifying a victim cache line in said cache memory, if any, and accessing the Dtag corresponding to said victim cache line to determine whether processing said read request will displace from said cache memory a data block that includes modified data, (B) retrieving a data block from said main memory corresponding to said read request and providing it to said data processor for storage in said data processor'"'"'s cache memory, (C) storing a Dtag state value and address tag in the Dtag corresponding to said victim cache line when processing said read request does not displace from said cache memory a modified data block and when the Dtag state value corresponding to the victim cache line is invalid, (D) storing said Dtag state value and address tag for said retrieved data block in said N+1th Dtag when processing said read request does displace from said cache memory a modified data block and said corresponding Dtag'"'"'s state value is not invalid, and (E) transferring said N+1th Dtag into said Dtag corresponding to said victim cache line when said writeback logic invalidates said Dtag state value in said corresponding Dtag;

wherein said memory transaction request logic processes said read request and writeback request such that processing of either of said read request and writeback request may be completed prior to the other in accordance with resource availability for processing said requests.

6. The computer system of claim 5,

each said read request including a DVP flag that has a first value when said read request corresponds to a cache fill operation that displaces a modified data block from said cache memory, said data block displacement being represented by said writeback request;

said DVP flag having a second value, distinct from said first value, when said read request corresponds to a cache fill operation that does not displace a modified data block from said cache memory; and

said transaction request logic including logic for storing a Dtag state value and address tag in the Dtag corresponding to said victim cache line when DVP flag in said read request has said second value and when said corresponding Dtag'"'"'s state value is invalid, and storing said Dtag state value and address tag for said read request in said N+1th Dtag when said DVP flag in said read request has said first value and said corresponding Dtag'"'"'s state value is not invalid.

7. The computer system of claim 5,

said Etag state being selected from the set of states consisting essentially of:

Exclusive Modified (M), Shared Modified (O), Exclusive Clean (E), Shared Clean (S), and Invalid (I);

said Dtag state being selected from the set of states consisting essentially of;

Exclusive Modified (M), Shared Modified (O), Shared Clean (S), and Invalid (I); and

wherein said Dtag state stored in said Dtags never indicates said Exclusive Clean (E) state and when each data processor modifies data stored in its cache memory in a cache line whose Etag thereby transitions from said E state to said M state, said data processor does not generate a corresponding transaction request and the corresponding Dtag remains unchanged with a Dtag state equal to said M state.

8. The computer system of claim 5,

wherein said main memory is a reflective memory;

said Etag state being selected from the set of states consisting essentially of;

Exclusive Modified (M), Exclusive Clean (E), Shared Clean (S), and Invalid (I);

said Dtag state being selected from the set of states consisting essentially of;

Exclusive Modified (M), Shared Clean (S), and Invalid (I); and

wherein said Dtag state stored in said Dtags never indicates said Exclusive Clean (E) state and when each data processor modifies data stored in its cache memory in a cache line whose Etag thereby transitions from said E state to said M state, said data processor does not generate a corresponding transaction request and the corresponding Dtag remains unchanged with a Dtag state equal to said M state.

9. A method for parallelizing writeback and read transactions in a packet switched cache coherent multiprocessor system having a system controller coupled to a main memory and to a data processor having a cache memory comprising the steps of:

storing master cache tags (Etags) in said data processor, including one Etag for each cache line in said cache memory, said Etag for each cache line storing an address index and an Etag state value that indicates whether a data block stored in said cache line includes data modified by said data processor;

storing in a writeback buffer of said data processor a dirty victim data block displaced from said cache memory until it is written back into said main memory;

storing a set of N duplicate tags (Dtags) for said cache memory in said system controller, each Dtag corresponding to one of said Etags including a Dtag state value and the same address index as the corresponding Etag;

said Dtag state value indicating whether said data block stored in the corresponding cache line includes data modified by said data processor;

sending memory transaction requests from said data processor to said system controller, said memory transaction requests including read requests and writeback requests;

responding to a cache miss in said cache memory by (A) generating a read request, and (B) when said cache miss requires victimizing a data block that, according to the Etag state value in a corresponding Etag, includes modified data, storing the data block having said modified data in a writeback buffer and generating a writeback request;

processing writeback requests by writing the data block in said writeback buffer into said main memory and invalidating the state value in the corresponding Dtag; and

processing said read request by;

(A) identifying a victim cache line in said cache memory, if any, and accessing the Dtag corresponding to said victim cache line to determine whether processing said read request will displace from said cache memory a data block that includes modified data;

(B) retrieving a data block from said main memory corresponding to said read request and providing it to said data processor for storage in said data processor'"'"'s cache memory at said victim cache line;

(C) storing a Dtag state value and address tag in the Dtag corresponding to said victim cache line when processing said read request does not displace from said cache memory a modified data block and when said corresponding Dtag'"'"'s state value is invalid;

(D) storing said Dtag state value and address tag for said retrieved data block in a N+1th Dtag when processing said read request does displace from said cache memory a modified data block and said corresponding Dtag'"'"'s state value is not invalid; and

(E) transferring said N+1th Dtag into said Dtag corresponding to said victim cache line when said writeback processing step invalidates said Dtag state value in said corresponding Dtag;

wherein memory transaction request logic processes said read request and writeback request such that processing of either of said read request and writeback request may be completed prior to the other in accordance with resource availability for processing said requests.

10. The method of claim 9,

each said read request including a DVP flag that has a first value when said read request corresponds to a cache fill operation that displaces a modified data block from said cache memory, said data block displacement being represented by said writeback request;

said DVP flag having a second value, distinct from said first value, when said read request corresponds to a cache fill operation that does not displace a modified data block from said cache memory; and

read request processing step including storing a Dtag state value and address tag in the Dtag corresponding to said victim cache line when DVP flag in said read request has said second value and when said corresponding Dtag'"'"'s state value is invalid, and storing said Dtag state value and address tag for said read request in said N+1th Dtag when said DVP flag in said read request has said first value and said corresponding Dtag'"'"'s state value is not invalid.

11. The method of claim 9,

said Etag state being selected from the set of states consisting essentially of:

Exclusive Modified (M), Shared Modified (O), Exclusive Clean (E), Shared Clean (S), and Invalid (I);

said Dtag state being selected from the set of states consisting essentially of;

Exclusive Modified (M), Shared Modified (O), Shared Clean (S), and Invalid (I); and

wherein said Dtag state stored in said Dtags never indicates said Exclusive Clean (E) state and when each data processor modifies data stored in its cache memory in a cache line whose Etag thereby transitions from said E state to said M state, said data processor does not generate a corresponding transaction request and the corresponding Dtag remains unchanged with a Dtag state equal to said M state.

12. The method system of claim 9,

wherein said main memory is a reflective memory;

said Etag state being selected from the set of states consisting essentially of;

Exclusive Modified (M), Exclusive Clean (E), Shared Clean (S), and Invalid (I);

said Dtag state being selected from the set of states consisting essentially of;

Exclusive Modified (M), Shared Clean (S), and Invalid (I); and

wherein said Dtag state stored in said Dtags never indicates said Exclusive Clean (E) state and when each data processor modifies data stored in its cache memory in a cache line whose Etag thereby transitions from said E state to said M state, said data processor does not generate a corresponding transaction request and the corresponding Dtag remains unchanged with a Dtag state equal to said M state.

13. A method for parallelizing writeback and read transactions in a packet switched cache coherent multiprocessor system having a system controller coupled to a main memory and to a data processor having a cache memory comprising the steps of:

storing master cache tags (Etags) in said data processor, including N Etags, one Etag for each cache line in said cache memory, said Etag for each cache line storing an address index and an Etag state value that indicates whether a data block stored in said cache line includes data modified by said data processor;

storing in a writeback buffer of said data processor a dirty victim data block displaced from said cache memory until it is written back into said main memory;

storing duplicate tags (Dtags) for said cache memory in said system controller;

responding to a cache miss in said cache memory by (A) generating a read request, and (B) when said cache miss requires victimizing a cache line containing a data block that, according to the Etag state value in the corresponding Etag, includes modified data, storing said data block having said modified data in a writeback buffer and generating a writeback request;

processing said writeback requests by writing the data block in said writeback buffer into said main memory and invalidating the state value in the corresponding Dtag; and

processing said read request by;

(A) identifying a victim cache line in said cache memory, if any, and accessing the Dtag corresponding to said victim cache line to determine whether processing said read request will displace from said cache memory a data block that includes modified data;

(B) retrieving a data block from said main memory corresponding to said read request and providing it to said data processor for storage in said data processor'"'"'s cache memory;

(C) storing a Dtag state value and address tag in the Dtag corresponding to said victim cache line when processing said read request does not displace from said cache memory a modified data block and when said corresponding Dtag'"'"'s state value is invalid;

(D) storing said Dtag state value and address tag for said retrieved data block in a N+1th Dtag when processing said read request does displace from said cache memory a modified data block and said corresponding Dtag'"'"'s state value is not invalid; and

(E) transferring said N+1th Dtag into said Dtag corresponding to said victim cache line when said writeback processing step invalidates said Dtag state value in said corresponding Dtag;

wherein memory transaction request logic processes said read request and writeback request such that processing of either of said read request and writeback request may be completed prior to the other in accordance with resource availability for processing said requests.

14. The method of claim 13,

each said read request including a DVP flag that has a first value when said read request corresponds to a cache fill operation that displaces a modified data block from said cache memory, said data block displacement being represented by said writeback request;

said DVP flag having a second value, distinct from said first value, when said read request corresponds to a cache fill operation that does not displace a modified data block from said cache memory; and

read request processing step including storing a Dtag state value and address tag in the Dtag corresponding to said victim cache line when DVP flag in said read request has said second value and when said corresponding Dtag'"'"'s state value is invalid, and storing said Dtag state value and address tag for said read request in said N+1th Dtag when said DVP flag in said read request has said first value and said corresponding Dtag'"'"'s state value is not invalid.

15. The method of claim 13,

said Etag state being selected from the set of states consisting essentially of:

Exclusive Modified (M), Shared Modified (O), Exclusive Clean (E), Shared Clean (S), and Invalid (I);

said Dtag state being selected from the set of states consisting essentially of;

Exclusive Modified (M), Shared Modified (O), Shared Clean (S), and Invalid (I); and

wherein said Dtag state stored in said Dtags never indicates said Exclusive Clean (E) state and when each data processor modifies data stored in its cache memory in a cache line whose Etag thereby transitions from said E state to said M state, said data processor does not generate a corresponding transaction request and the corresponding Dtag remains unchanged with a Dtag state equal to said M state.

16. The method of claim 13,

wherein said main memory is a reflective memory;

said Etag state being selected from the set of states consisting essentially of;

Exclusive Modified (M), Exclusive Clean (E), Shared Clean (S), and Invalid (I);

said Dtag state being selected from the set of states consisting essentially of;

Exclusive Modified (M), Shared Clean (S), and Invalid (I); and

wherein said Dtag state stored in said Dtags never indicates said Exclusive Clean (E) state and when each data processor modifies data stored in its cache memory in a cache line whose Etag thereby transitions from said E state to said M state, said data processor does not generate a corresponding transaction request and the corresponding Dtag remains unchanged with a Dtag state equal to said M state.