Scalable multiprocessor system and cache coherence method implementing store-conditional memory transactions while an associated directory entry is encoded as a coarse bit vector
First Claim
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;
wherein the protocol engine is configured to support a store-conditional memory transaction initiated by a requesting node for exclusive ownership of an identified memory line of information stored in the remote memory subsystem that is local to a first node in the plurality of nodes, and wherein the store-conditional memory transaction succeeds if the directory in the memory subsystem local to the first node unambiguously indicates that the requesting node is exclusive owner of the memory line of information;
the store-conditional memory transaction succeeds if the directory in the memory subsystem local to the first node unambiguously indicates that the requesting node is sharing the memory line of information;
the store-conditional memory transaction succeeds if the directory in the memory subsystem local to the first node ambiguously indicates that the requesting node is sharing the memory line of information and the requesting node is in fact sharing the memory line of information; and
the store-conditional memory transaction fails if the directory in the memory subsystem local to the first node unambiguously indicates that the requesting node is not sharing the memory line of information.
3 Assignments
0 Petitions
Accused Products
Abstract
A system including a plurality of processor nodes is configured to execute a cache coherence protocol that avoids the use of negative acknowledgments and ordering requirements on the underlying transaction-message interconnect/network, and implements store-conditional memory transactions. A store-conditional memory transaction succeeds if a directory tracking the state of a memory line of information unambiguously indicates that the requesting node is the exclusive owner of the memory line, if the directory ambiguously indicates that the requesting node is sharing the memory line and the requesting node is in fact sharing the memory line, or if the directory unambiguously indicates that the requesting node is sharing the memory line. The store-conditional memory transaction fails if the directory unambiguously indicates that the requesting node is not sharing the memory line, or if the directory ambiguously indicates that the requesting node may be sharing the memory line and the requesting node is in fact not sharing the memory line.
-
Citations
49 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;
wherein the protocol engine is configured to support a store-conditional memory transaction initiated by a requesting node for exclusive ownership of an identified memory line of information stored in the remote memory subsystem that is local to a first node in the plurality of nodes, and wherein the store-conditional memory transaction succeeds if the directory in the memory subsystem local to the first node unambiguously indicates that the requesting node is exclusive owner of the memory line of information;
the store-conditional memory transaction succeeds if the directory in the memory subsystem local to the first node unambiguously indicates that the requesting node is sharing the memory line of information;
the store-conditional memory transaction succeeds if the directory in the memory subsystem local to the first node ambiguously indicates that the requesting node is sharing the memory line of information and the requesting node is in fact sharing the memory line of information; and
the store-conditional memory transaction fails if the directory in the memory subsystem local to the first node unambiguously indicates that the requesting node is not sharing the memory line of information. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
the protocol engine in the requesting node is configured to process the store-conditional memory transaction by sending a first protocol message to the first node; - and
storing in the memory transaction array a state of the store-conditional memory transaction, the state indicating a second protocol message that will advance the store-conditional memory transaction to a next state, receipt of the second protocol message being a predefined criterion for advancing the store-conditional memory transaction to the next state.
-
-
3. The system of claim 2, wherein
the first protocol message is a store-conditional request; - and
the second protocol message is a may-succeed reply, said may-succeed reply indicating that the store-conditional memory transaction will succeed if the requesting node is sharing the memory line of information.
- and
-
4. The system of claim 3, wherein
the may-succeed reply includes a count of one or more other nodes in the plurality of nodes sharing the memory line of information. -
5. The system of claim 3, wherein
the second protocol message is an invalidation request concerning the memory line of information, said invalidation request indicating that the requesting node is no longer sharing the memory line of information. -
6. The system of claim 3, wherein
the protocol engine in the requesting node is configured to respond to a may-succeed reply by: -
determining whether the requesting node is sharing the memory line of information; and
upon determining that the requesting node is sharing the memory line of information, sending a responsive protocol message to the first node, said responsive protocol message indicating that the requesting node has received the may-succeed reply and is sharing the memory line of information.
-
-
7. The system of claim 6, wherein
the protocol engine in the first node is configured to respond to the responsive protocol message by sending an invalidation request to a set of nodes in the plurality of nodes that the directory in the memory subsystem local to the first node indicates are sharing the memory line of information, said set of nodes not including the requesting node; - and
modifying the directory in the memory subsystem local to the first node to indicate that the requesting node is exclusive owner of the memory line of information.
- and
-
8. The system of claim 7, wherein
the protocol engine included in each node in the set 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.
- and
-
9. The system of claim 3, wherein
the protocol engine included in the requesting node is configured to respond to a may-succeed reply by updating the state of the store-conditional memory transaction stored in the memory transaction array, the state subsequently indicating that a third protocol message will advance the store-conditional memory transaction to a next state, receipt of the third protocol message being a predefined criterion for advancing the store-conditional memory transaction to the next state. -
10. The system of claim 9, wherein
the third protocol message is an invalidation acknowledgment concerning the memory line of information, said invalidation acknowledgment indicating-that a third node in the plurality of nodes is no longer sharing the memory line of information. -
11. The system of claim 9, wherein
the protocol engine included in the requesting node is configured to include in the state of the store-conditional memory transaction a count of one or more other nodes in the plurality of nodes sharing the memory line of information, said count having been included in a may-succeed reply received in response to a store-conditional request. -
12. The system of claim 11, wherein
the store-conditional memory transaction is complete after the requesting node receives a number of invalidation acknowledgments equal to the count of the one or more other nodes in the plurality of nodes sharing the memory line of information. -
13. The system of claim 11, wherein
the protocol engine included in the requesting node is configured to remove from the memory transaction array an entry concerning the store-conditional memory transaction after receiving a number of invalidation acknowledgments equal to the count of the one or more other nodes in the plurality of nodes sharing the memory line of information. -
14. The system of claim 9, wherein
the protocol engine included in the first node is configured to include in the may-succeed reply an identifier of a node, other than the requesting node, that the directory in the memory subsystem local to the first node indicates is sharing the memory line of information; the protocol engine included in the requesting node is further configured to respond to the may-succeed reply by sending an invalidation request to the node, other than the requesting node, that the directory in the memory subsystem local to the first node indicates is sharing the memory line of information.
-
15. The system of claim 14, wherein
the protocol engine included in the node, other than the requesting node, that the directory in the memory subsystem local to the first node indicates is sharing the memory line of information 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.
- and
-
16. The system of claim 3, wherein
the protocol engine included in the first node is configured to respond to the first protocol message by determining whether the directory in the memory subsystem local to the first node unambiguously indicates that the requesting node is exclusive owner of the memory line of information; - and
upon determining that the directory in the memory subsystem local to the first node unambiguously indicates that the requesting node is exclusive owner of the memory line of information, sending a success reply to the requesting node, said success reply being the second protocol message.
- and
-
17. The system of claim 3, wherein
the protocol engine included in the first node is configured to respond to the first protocol message by determining whether the directory in the memory subsystem local to the first node unambiguously indicates that the requesting node is not sharing the memory line of information; - and
upon determining that the directory in the memory subsystem local to the first node unambiguously indicates that the requesting node is not sharing the memory line of information, sending a failure reply to the requesting node, said failure reply being the second protocol message.
- and
-
18. The system of claim 3, wherein
the protocol engine included in the first node is configured to respond to the first protocol message by determining whether the directory in the memory subsystem local to the first node unambiguously indicates that the requesting node is sharing the memory line of information; - and
upon determining that the directory in the memory subsystem local to the first node unambiguously indicates that the requesting node is sharing the memory line of information, sending a success reply to the requesting node, said success reply being the second protocol message.
- and
-
19. The system of claim 3, wherein
the protocol engine included in the first node is configured to respond to the first protocol message by determining whether the directory in the memory subsystem local to the first node ambiguously indicates that the requesting node is sharing the memory line of information; - and
upon determining that the directory in the memory subsystem local to the first node ambiguously indicates that the requesting node is sharing the memory line of information, sending a may-succeed reply to the requesting node, said may-succeed reply being the second protocol message.
- and
-
20. The system of claim 3, wherein
the protocol engine included in the requesting node is configured to respond to a may-succeed reply by determining that the requesting node is not sharing the memory line of information; - and
sending a responsive protocol message to the first node, said responsive protocol message indicating that the requesting node has received the may-succeed reply but that the requesting node is not sharing the memory line of information.
- and
-
21. The system of claim 2, wherein
the first protocol message is a store-conditional request; - and
the second protocol message is a success reply, said success reply indicating that the store-conditional memory transaction is successful and that the requesting node is exclusive owner of the memory line of information.
- and
-
22. The system of claim 2, wherein
the first protocol message is a store-conditional request; - and
the second protocol message is a failure reply, said failure reply indicating that the store-conditional memory transaction is unsuccessful such that the requesting node is not sharing the memory line of information.
- and
-
23. The system of claim 1, wherein
the directory ambiguously indicates that the requesting node is sharing the memory line of information when an indicator included in the directory and associated with a set of nodes including the requesting node and one or more other nodes in the plurality of nodes indicates that an unidentified node included in the set of nodes is sharing the memory line of information. -
24. The system of claim 1, wherein
the directory unambiguously indicates that the requesting node is sharing the memory line of information when an indicator included in the directory is set to indicate that the requesting node is sharing the memory line of information, said indicator associated with only the requesting node.
-
25. 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 a store-conditional memory transaction, wherein the protocol engine included in a requesting node from the plurality of nodes sends a store-conditional request to a first node from the plurality of nodes, said store-conditional request identifying a memory line of information stored in the remote memory subsystem that is local to the first node;
the protocol engine included in the first node sends a may-succeed reply to the requesting node in response to the store-conditional request if the directory in the memory subsystem local to the first node ambiguously indicates that the requesting node is sharing the memory line of information;
the protocol engine included in the requesting node sends a first responsive protocol message to the first node in response to the may-succeed reply if the requesting node is sharing the memory line of information; and
the protocol engine included in the first node modifies a directory entry, in the directory in the memory subsystem local to the first node, corresponding to the memory line of information to indicate that the requesting node is exclusive owner of the memory line of information in response to the first responsive protocol message. - View Dependent Claims (26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49)
the protocol engine included in the requesting node adds an entry relating to the store-conditional memory transaction to the memory transaction array, said entry including a state of the store-conditional memory transaction, said state indicating that a second protocol message will advance the store-conditional memory transaction to a next state. -
27. The system of claim 26, wherein
the second protocol message is a may-succeed reply, said may-succeed reply indicating that the store-conditional memory transaction will succeed if the requesting node is sharing the memory line of information. -
28. The system of claim 26, wherein
the second protocol message is an invalidation request concerning the memory line of information, said invalidation request indicating that the requesting node is no longer sharing the memory line of information. -
29. The system of claim 26, wherein
the protocol engine included in the requesting node is configured to respond to a may-succeed reply by updating the state of the store-conditional memory transaction stored in the memory transaction array, the state subsequently indicating that a third protocol message will advance the store-conditional memory transaction to a next state. -
30. The system of claim 29, wherein
the third protocol message is an invalidation acknowledgment concerning the memory line of information, said invalidation acknowledgment indicating that a third node in the plurality of nodes is no longer sharing the memory line of information. -
31. The system of claim 26, wherein
the second protocol message is a success reply, said success reply indicating that the store-conditional memory transaction is successful and that the requesting node is exclusive owner of the memory line of information. -
32. The system of claim 26, wherein
the second protocol message is a failure reply, said failure reply indicating that the store-conditional memory transaction is unsuccessful and that the requesting node is not sharing the memory line of information. -
33. The system of claim 25, wherein
the protocol engine included in the requesting node is configured to respond to a may-succeed reply by determining whether the requesting node is sharing the memory line of information; - and
upon determining that the requesting node is not sharing the memory line of information, sending a second responsive protocol message to the first node, said responsive protocol message indicating that the requesting node has received the may-succeed reply but that the requesting node is not sharing the memory line of information.
- and
-
34. The system of claim 25, wherein
the protocol engine included in the first node is configured to respond to the store-conditional request by determining whether the directory in the memory subsystem local to the first node unambiguously indicates that the requesting node is exclusive owner of the memory line of information; - and
upon determining that the directory in the memory subsystem local to the first node unambiguously indicates that the requesting node is exclusive owner of the memory line of information, sending a success reply to the requesting node.
- and
-
35. The system of claim 25, wherein
the protocol engine included in the first node is configured to respond to the store-conditional request by determining whether the directory in the memory subsystem local to the first node unambiguously indicates that the requesting node is not sharing the memory line of information; - and
upon determining that the directory in the memory subsystem local to the first node unambiguously indicates that the requesting node is not sharing the memory line of information, sending a failure reply to the requesting node.
- and
-
36. The system of claim 25, wherein
the protocol engine included in the first node is configured to respond to the store- conditional request by determining whether the directory in the memory subsystem local to the first node unambiguously indicates that the requesting node is sharing the memory line of information; - and
upon determining that the directory in the memory subsystem local to the first node unambiguously indicates that the requesting node is sharing the memory line of information, sending a success reply to the requesting node, said success reply indicating that the requesting node is exclusive owner of the memory line of information.
- and
-
37. The system of claim 25, wherein
the store-conditional memory transaction is triggered by a request to modify a shared copy of the memory line of information from a processor included in the requesting node, said request being routed to the protocol engine included in the requesting node. -
38. The system of claim 37, wherein
the protocol engine included in the requesting node sends a notification to the processor upon receiving the may-succeed reply. -
39. The system of claim 38, wherein
the notification indicates that the request is granted if the requesting node is sharing the memory line of information. -
40. The system of claim 38, wherein
the notification indicates that the request is granted if the requesting node is exclusive owner of the memory line of information. -
41. The system of claim 37, wherein
the protocol engine included in the requesting node is configured to add an entry relating to the request upon receiving said write request. -
42. The system of claim 41, wherein
the protocol engine included in the requesting node is configured to update the memory transaction array entry after receiving a protocol message responsive to the store-conditional request, such that the memory transaction array entry identifies one or more additional protocol messages that will advance the store-conditional memory transaction. -
43. The system of claim 42, wherein
the one or more additional protocol messages that will advance the store-conditional memory transaction includes an invalidation acknowledgment. -
44. The system of claim 25, wherein
the protocol engine included in the first node is configured to send an invalidation request to one or more nodes, if any, in the plurality of nodes sharing the memory line of information in response to the first responsive protocol message, said one or more nodes not including the requesting node. -
45. The system of claim 25, wherein
the protocol engine included in the first node is configured to include in the may-succeed reply an identifier of one or more nodes, if any, in the plurality of nodes sharing the memory line of information; - and
the protocol engine included in the requesting node is configured to send an invalidation request to the one or more nodes, if any, in the plurality of nodes sharing the memory line of information by reference to the identifier in response to the may-succeed reply if the requesting node is sharing the memory line of information.
- and
-
46. The system of claim 25, wherein
the protocol engine included in a node in the plurality of nodes is configured to respond to an invalidation request by invalidating a local copy of the memory line of information; - and
sending an invalidation acknowledgment to the requesting node.
- and
-
47. The system of claim 25, wherein
the protocol engine included in the requesting node is configured to remove from the memory transaction array the entry concerning the store-conditional memory transaction after receiving an invalidation acknowledgment from-each node, if any, receiving an invalidation request in connection with the store-conditional memory transaction. -
48. The system of claim 47, wherein
the may-succeed reply includes a count of the each node, if any, receiving an invalidation request in connection with the store-conditional memory transaction. -
49. The system of claim 25, wherein
the directory in the memory subsystem local to the first node ambiguously indicates that the requesting node is sharing the memory line of information when an indicator included in the directory and associated with a set of nodes including the requesting node and one or more other nodes in the plurality of nodes indicates that an unidentified node included in the set of nodes is sharing the memory line of information.
-
Specification