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

Claim 2

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.

Claim 3

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.

Claim 4

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.

Claim 5

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.

Claim 6

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.

Claim 7

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.

Claim 8

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.

Claim 9

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.

Claim 10

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.

Claim 13

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.

Claim 14

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.

Claim 15

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.

Claim 18

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.

Claim 19

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.

Claim 20

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.