Scalable multiprocessor system and cache coherence method implementing store-conditional memory transactions while an associated directory entry is encoded as a coarse bit vector

• US 6,748,498 B2
• Filed: 01/07/2002
• Issued: 06/08/2004
• 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: Stets, Robert J., Barroso, Luiz Andre, Scales, Daniel J., Ravishankar, Mosur K., Gharachorloo, Kourosh
• Primary Examiner(s): Bragdon, Reginald G.
• Assistant Examiner(s): CHACE, CHRISTIAN
• Application Number:
  US10/042,053
• Publication Number:
  US 20020124144A1
• Time in Patent Office: 883 Days
• Field of Search: 707/10, 707/201, 709/213, 709/217, 711/120, 711/122, 711/130, 711/141, 711/148, 711/156, 711/165
• 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
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

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.

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.

2. The system of claim 1, wherein

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

26. The system of claim 25, wherein

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.

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.

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.

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.

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.

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.

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.