Scalable multiprocessor system and cache coherence method incorporating invalid-to-dirty requests

• US 6,640,287 B2
• Filed: 01/07/2002
• Issued: 10/28/2003
• Est. Priority Date: 06/10/2000
• Status: Expired due to Fees

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Barroso, Luiz Andre, Scales, Daniel J., Stets, Robert J., Gharachorloo, Kourosh, Ravishankar, Mosur Kumaraswamy
• Primary Examiner(s): Sparks, Donald
• Assistant Examiner(s): CHACE, CHRISTIAN
• Application Number:
  US10/042,009
• Publication Number:
  US 20020083274A1
• Time in Patent Office: 659 Days
• Field of Search: 707/8, 707/10, 707/201, 709/101, 709/213, 709/248, 711/141, 711/151, 711/152
• US Class Current: 711/141
• CPC Class Codes: G06F 12/0826 Limited pointers directories; State-only directories without pointers
• CPC Class Codes: G06F 12/0828 with concurrent directory accessing, i.e. handling multiple concurrent coherency transactions
• CPC Class Codes: G06F 2212/621 Coherency control relating to peripheral accessing, e.g. from DMA or I/O device

Abstract

An invalid-to-dirty request permits a transition from an invalid memory state to a dirty state without requiring an up-to-date copy of the memory. The present invention is a system for supporting invalid-to-dirty memory transactions in an aggressive cache coherence protocol that minimizes directory entry locking. The nodes of a multiprocessor system each include a protocol engine that is configured to implement a distinct invalidation request that corresponds to an invalid-to-dirty memory transaction. If node O receives this distinct invalidation request while waiting for a response to an outstanding request for exclusive ownership, the protocol engine of node O is configured to treat the distinct invalidation request as applying to the memory line of information that is the subject of the outstanding request for exclusive ownership. Furthermore, if the node O receives a normal invalidation request, while it has an outstanding exclusive request, the invalidation request applies to a previous copy of the memory line of information held by the node N and therefore the protocol engine of node O is configured to ignore the normal invalidation request in this circumstance.

Claims

1. A multiprocessor computer system including a plurality of nodes, each node including

an interface to a local memory subsystem, the local memory subsystem storing a multiplicity of memory lines of information and a directory;

a memory cache for caching a multiplicity of memory lines of information, including memory lines of information stored in a remote memory subsystem that is local to another node;

a protocol engine implementing a negative acknowledgment free cache coherence protocol, the protocol engine including

a memory transaction array for storing an entry related to a memory transaction, the entry including a memory transaction state, the memory transaction concerning a memory line of information; and

logic for processing the memory transaction, including advancing the memory transaction when predefined criteria are satisfied and storing a state of the memory transaction in the memory transaction array;

the protocol engine of a requesting node being configured to support memory transactions concerning a request for exclusive ownership of an identified memory line of information having a home address located in the remote memory subsystem that is local to another node, wherein the entire identified memory line of information is to be overwritten by the requesting node after exclusive ownership of the memory line of information is granted and an up-to-date copy of the memory line of information is not required in a response to the request for exclusive ownership of the identified memory line of information.

2. The system of claim 1, wherein

the protocol engine of the requesting node is configured to process the memory transaction concerning the request for exclusive ownership of the memory line of information by

sending a first protocol message to a first node in the plurality of nodes; and

storing in the memory transaction array a state of the memory transaction, the state indicating a second protocol message that will advance the memory transaction to a next state, receipt of the second protocol message being a predefined criterion for advancing the memory transaction to the next state.

3. The system of claim 2, wherein

the first protocol message is an invalid-to-dirty request for a memory line of information stored in the local memory subsystem at the first node;

and

the second protocol message is a invalid-to-dirty invalidation reply.

4. The system of claim 2, wherein

a protocol engine included in the first node is configured to respond to the first protocol message by

determining if a directory entry, in the directory in the memory subsystem local to the first node, indicates that a second node in the plurality of nodes is exclusive owner of the memory line of information;

modifying said directory entry to indicate that the requesting node is exclusive owner of the memory line of information; and

sending an invalid-to-dirty invalidation request to the second node.

5. The system of claim 4, wherein

the protocol engine included in the second node is configured to respond to the invalid-to-dirty invalidation request by sending the invalid-to-dirty invalidation reply to the requesting node.

6. The system of claim 4, wherein

the protocol engine included in the second node is configured to respond to the invalid-to-dirty invalidation request by invalidating a local copy of the identified memory line of information.

7. The system of claim 4, wherein

the protocol engine included in the second node is configured to execute a delay in completing a response to the invalid-to-dirty invalidation request until the protocol engine included in the second node receives a response to an outstanding memory transaction related to the identified memory line of information.

8. The system of claim 7, wherein the outstanding memory transaction related to the identified memory line of information is a request for exclusive ownership of the identified memory line of information.

9. The system of claim 7, wherein the protocol engine included in the second node is configured to execute the delay by updating an entry relating to the invalid-to-dirty invalidation request in the memory transaction array, wherein the protocol engine included in the second node subsequently accesses said entry to complete the response to the invalid-to-dirty invalidation request.

10. The system of claim 1, wherein

the protocol engine of the requesting node is configured to process the memory transaction concerning the request for exclusive ownership of the memory line of information by

sending a first protocol message to a first node in the plurality of nodes;

and

storing in the memory transaction array a state of the memory transaction, the state indicating a set of one or more second protocol messages required to advance the memory transaction to a next state.

11. The system of claim 10, wherein

the first protocol message is an invalid-to-dirty request for a memory line of information having a home address located in the memory subsystem local to the first node;

and

the one or more second protocol messages include an exclusive reply and zero or more invalidation acknowledgments.

12. The system of claim 10, wherein

the protocol engine in the first node is configured to respond to the first protocol message by

determining if a directory entry, in the directory in the memory subsystem local to the first node, indicates that one or more of the plurality of nodes, excluding the first node and the requesting node, have a shared copy of the memory line of information;

sending an invalidation request to the one or more of the plurality of nodes;

sending an exclusive reply to the requesting node, the exclusive reply including a count of the one or more of the plurality of nodes; and

modifying said directory entry to indicate that the requesting node is exclusive owner of the memory line of information.

13. The system of claim 12, wherein

the protocol engine included in each of the one or more of the plurality of nodes is configured to respond to the invalidation request by

invalidating a local copy of the memory line of information;

and

sending an invalidation acknowledgment to the requesting node.

14. The system of claim 1, wherein the logic for processing the memory transaction includes a mechanism for determining whether the request for exclusive ownership of the identified memory line of information is to result in the entire memory line of information being overwritten after exclusive ownership of the memory line of information is granted.

15. The system of claim 14, wherein the mechanism reads a message type included in the request for exclusive ownership of the identified memory line of information to determine whether the entire memory line of information is to be overwritten.

16. The system of claim 14, wherein the logic is configured to send an invalid-to-dirty request to a first node, said first node storing the identified memory line of information in a memory subsystem that is local to the first node, if the logic determines that the request for exclusive ownership is to result in the entire memory line of information being overwritten after exclusive ownership of the memory line of information is granted.

17. The system of claim 14, wherein the logic is configured to send a read-exclusive request to a first node, said first node storing the identified memory line of information in a memory subsystem that is local to the first node, if the logic determines that the request for exclusive ownership is not to result in the entire memory line of information being overwritten after exclusive ownership of the memory line of information is granted.

18. The system of claim 1, wherein an entire identified memory line of information includes each byte of memory associated with a single, unique memory line of information address.

19. A multiprocessor computer system including a plurality of nodes, each node including

an interface to a local memory subsystem, the local memory subsystem storing a multiplicity of memory lines of information and a directory;

a memory cache for caching a multiplicity of memory lines of information, including memory lines of information stored in a remote memory subsystem that is local to another node;

a protocol engine implementing a negative acknowledgment free cache coherence protocol, the protocol engine including

a memory transaction array for storing an entry related to a memory transaction, the entry including a memory transaction state, the memory transaction concerning a memory line;

logic for processing the memory transaction, including advancing the memory transaction when predefined criteria are satisfied and storing a state of the memory transaction in the memory transaction array;

the protocol engine configured to support an invalid-to-dirty memory transaction, wherein

the protocol engine included in a first node from the plurality of nodes is configured to sends an invalid-to-dirty request to a second node from the plurality of nodes, said invalid-to-dirty request identifying a memory line of information stored in the remote memory subsystem that is local to the second node;

the protocol engine included in the second node is configured to send an invalid-to-dirty invalidation request to a third node from the plurality of nodes in response to the invalid-to-dirty request if the third node has previously been designated as exclusive owner of the memory line;

the protocol engine included in the second node is configured to designate the first node as exclusive owner of the memory line of information in response to the invalid-to-dirty request;

the protocol engine included in the third node is configured to respond to the invalid-to dirty invalidation request by invalidating a copy of the memory line of information cached in the memory cache in response to the invalid-to-dirty invalidation request and sending an invalid-to-dirty invalidation reply to the first node.

20. The system of claim 19, wherein

the protocol engine included in the first node determines that the memory line of information is to be entirely overwritten, so that an up-to-date copy of the memory line of information is not required by the first node, before sending the invalid-to-dirty request.

21. The system of claim 20, wherein

the protocol engine included in the first node is configured to send an exclusive request to the second node if the first node determines that the memory line of information is not to be entirely overwritten and that the first node has a valid copy of the memory line of information cached in the memory cache.

22. The system of claim 20, wherein

the protocol engine included in the first node is configured to send a read-exclusive request to the second node if the first node determines that the memory line of information is to be entirely overwritten and that the first node does not have a valid copy of the memory line of information cached in the memory cache.

23. The system of claim 19, wherein

the protocol engine included in the second node is configured to determine that the third node is exclusive owner of the memory line of information by reference to the directory before sending the invalid-to-dirty invalidation request, said directory including status information for the multiplicity of memory lines of information.

24. The system of claim 23, wherein

the protocol engine included in the second node is configured to send an exclusive reply to the first node and an invalidation request to zero or more other nodes from the plurality of nodes if the first node determines that no node is designated as exclusive owner of the memory line and at least one of said other nodes is caching a copy of the memory line of information.

25. The system of claim 19, wherein

the protocol engine included in the third node is configured to determine that the third node is not waiting to process a response to an outstanding request concerning the memory line of information before sending an invalid-to-dirty invalidation reply to the first node and invalidating a copy of the memory line of information cached in the memory cache.

26. The system of claim 25, wherein

the protocol engine included in the third node is configured to update an entry of the memory transaction array relating to the invalid-to-dirty invalidation request if the third node determines that the third node is waiting to process the response to the outstanding request, said entry indicating that the response to the outstanding request must be processed before the invalid-to-dirty memory transaction is advanced.

27. The system of claim 26, wherein

the protocol engine included in the third node is configured to access said entry of the memory transaction array to advance the invalid-to-dirty memory transaction after processing the outstanding request.

28. The system of claim 26, wherein

advancing the invalid-to-dirty memory transaction includes sending an invalid-to-dirty invalidation reply to the first node and invalidating a copy of the memory line of information cached in the memory cache.

29. The system of claim 26, wherein

the outstanding request includes a request for exclusive ownership of the memory line.

30. The system of claim 29, wherein

the response to the outstanding request comprises a read-exclusive reply and zero or more invalidation acknowledgments.

31. The system of claim 29, wherein

the response to the outstanding request comprises an exclusive reply and zero or more invalidation acknowledgments.

32. The system of claim 30, wherein

the response to the outstanding request comprises an invalid-to-dirty invalidation reply.

33. The system of claim 26, wherein

the protocol engine included in the third node is configured to add an entry relating to the invalid-to-dirty invalidation request to the memory transaction array after receiving the invalid-to-dirty invalidation request.

34. The system of claim 33, wherein

the protocol engine included in the third node is configured to remove the entry from the memory transaction array after sending an invalid-to-dirty invalidation reply to the first node and invalidating a copy of the memory line of information cached in the memory cache.

35. The system of claim 19, wherein

the invalid-to-dirty memory transaction is triggered by a write request from a processor included in the first node, said request being routed to the protocol engine included in the first node;

and

the protocol engine sends a notification to the processor after the first node receives the invalid-to-dirty reply, said notification indicating that the processor may write the memory line.

36. The system of claim 35, wherein

the protocol engine included in the first node is configured to add an entry relating to the write request to the memory transaction array after receiving the write request.

37. The system of claim 36, wherein

the protocol engine included in the first node is configured to update said entry of the memory transaction array after the first node determines that the memory line of information is to be entirely overwritten, such that the entry identifies one or more responses relating to the write request that will advance the invalid-to-dirty memory transaction.

38. The system of claim 37, wherein

the one or more responses include a response selected from the set consisting of an invalid-to-dirty invalidation reply, an exclusive reply, and zero or more invalidation acknowledgments.

39. The system of claim 36, wherein

the protocol engine included in the first node is configured to remove the entry from the memory transaction array after receiving the invalid-to-dirty invalidation reply.

40. The system of claim 19, wherein

the protocol engine included in the second node is configured to add an entry relating to the invalid-to-dirty request to the memory transaction array after receiving the invalid-to-dirty request.

41. The system of claim 40, wherein

the protocol engine included in the second node is configured to remove said entry from the memory transaction array after sending the invalid-to-dirty invalidation request to the third node and designating the first node as exclusive owner of the memory line.