Scalable multiprocessor system and cache coherence method

• US 6,751,710 B2
• Filed: 06/11/2001
• Issued: 06/15/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: Scales, Daniel J., Stets, Robert J. Jr., Ravishankar, Mosur K., Gharachorloo, Kourosh, Barroso, Luiz A.
• Primary Examiner(s): Sparks, Donald
• Assistant Examiner(s): TAKEGUCHI, KATHY K
• Application Number:
  US09/878,982
• Publication Number:
  US 20020007443A1
• Time in Patent Office: 1,100 Days
• Field of Search: 711/141, 711/144, 711/146, 711/145, 711/147, 711/150, 711/143
• 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

The present invention relates generally to multiprocessor computer system, and particularly to a multiprocessor system designed to be highly scalable, using efficient cache coherence logic and methodologies. More specifically, the present invention is a system and method including a plurality of processor nodes configured to execute a cache coherence protocol that avoids the use of negative acknowledgment messages (NAKs) and ordering requirements on the underlying transaction-message interconnect/network and services most 3-hop transactions with only a single visit to the home node.

Claims

1. A multiprocessor computer system, comprising:

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 add an entry related to a memory transaction in the memory transaction array in response to receipt by the protocol engine of a protocol message related to the memory transaction.

2. The system of claim 1, wherein

each node includes a central processing unit configured to initiate the protocol message, the memory transaction concerning a memory line of information stored in the local memory subsystem and exclusively cached in the memory cache of another node of the plurality of nodes.

3. The system of claim 1, wherein

the protocol message is received from another node of the plurality of nodes and is related to a memory line of information stored in the local memory subsystem.

4. The system of claim 1, wherein

the protocol engine comprises a remote protocol engine and a home protocol engine, the home protocol engine limited to a memory transaction related to a memory line of information stored in the local memory subsystem, the remote protocol engine limited to a memory transaction related to a memory line of information stored in a memory subsystem that is local to another node.

5. A multiprocessor computer system, comprising:

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 of a requesting node is configured to process a memory transaction 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.

6. The system of claim 5, wherein the protocol engine included in the first node is configured to add an entry related to the memory transaction in the memory transaction array included in the first node in response to receipt by the protocol engine included in the first node of the first protocol message.

7. The system of claim 5, wherein

the first protocol message is a read request for a memory line maintained at the first node; and

the second protocol message is a read reply or a read-exclusively reply.

8. The system of claim 7, wherein

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

determining if a directory maintained in the local memory subsystem of the first node does not indicate that a second node in the plurality of nodes is exclusive owner of the memory line;

sending the read reply to the requesting node, said read reply including the memory line; and

modifying the directory in the local memory subsystem of the first node to indicate that the requesting node is sharing the memory line.

9. The system of claim 7, wherein

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

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

modifying the directory to indicate the memory line is in a pending state; and

sending a read-forward to the second node.

10. The system of claim 9, wherein

the protocol engine included in the first node is further configured to set a state of the memory transaction in the memory transaction array to indicate that a share write-back is a protocol message that will advance the memory transaction to a next state.

11. The system of claim 9, wherein

the protocol engine included in the second node is configured to respond to the read-forward by

sending a share write-back to the first node, said share write-back including the memory line;

and

sending the read reply to the requesting node, said read reply including the memory line.

12. The system of claim 11, wherein

the protocol engine included in the first node is configured to respond to the share write-back by

modifying the directory to indicate that the memory line is being shared by the requesting node and the second node;

and

updating a local copy of the memory line.

13. The system of claim 12, wherein

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

determining if a directory maintained in the memory subsystem local to the first node indicates an invalid state for the memory line;

sending the read-exclusive reply to the requesting node, said read-exclusive reply including the memory line; and

modifying the directory to indicate that the requesting nodes is exclusive owner of the memory line.

14. The system of claim 5, wherein

the first protocol message is a write-back request, said write-back request including a copy of a memory line;

and

the second protocol message is a write-back acknowledgment.

15. The system of claim 14, wherein

a protocol engine included in the first node is configured to respond to the write-back request by

updating a directory maintained in a memory subsystem accessible from the first node to indicate that the memory line is not shared by another node;

updating a local copy of the memory line; and

sending the write-back acknowledgement to the requesting node.

16. The system of claim 14, wherein

a protocol engine included in the first node is configured to respond to the write-back request by

determining if a directory maintained in a memory subsystem accessible from the first node indicates that the requesting node is not exclusive owner or the memory line;

updating a local copy of the memory line; and

sending the write-back acknowledgment to the requesting node, the write-back acknowledgment indicating that a read-forward request was sent to the node that sent write-back request before receipt of the write-back request, the read-forward request being sent in response to receipt of a read request from a second node.

17. The system of claim 14, wherein

the protocol engine included in the requesting node is configured to

maintain a copy of the memory line;

and

forward a copy of the memory line in response to receiving a read-forward request for the memory line before receiving the write-back acknowledgment.

18. The system of claim 17, wherein

the protocol engine included in the requesting node is configured to then invalidate the copy of the memory line upon receiving the write-back acknowledgment.

19. The system of claim 14, wherein

the protocol engine included in the requesting node is further configured to maintain the copy of the memory line after receiving the write-back acknowledgement if the write-back acknowledgment indicates that a read-forward request for the memory line was sent to the requesting node by the first node before receiving the write-back request.

20. The system of claim 19, wherein

the protocol engine included in the requesting node is configured to then

forward a copy of the memory line in response to receiving a read-forward request for the memory line;

and then

invalidate the copy of the memory line.

21. A multiprocessor computer system, comprising:

a plurality or 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 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 of a requesting node is configured to process a memory transaction 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;

the first protocol message is a read-exclusive request for a memory line maintained at the first node; and

the one or more second protocol messages include a read-exclusive reply and a determined number of invalidation acknowledgments.

22. The system of claim 21, wherein

the protocol engine included in the first node is configured to respond the read-exclusive request by

determining if the directory maintained in the memory subsystem local to the first node indicates that none of the plurality of nodes has a copy of the memory line;

sending the read-exclusive reply to the requesting node, said read reply including the memory line; and

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

23. The system of claim 21, wherein

the protocol engine included in the first node is configured to respond to the read-exclusive request by

determining if the directory maintained 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;

sending a read-exclusive forward to the second node; and

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

24. The system of claim 23, wherein

the protocol engine included in the second node is configured to respond to the read-exclusive forward by

invalidating a local copy of the memory line;

and

sending the read-exclusive reply to the request node, said read-exclusive reply including the memory line and an indication that the determined number of invalidation acknowledgments is zero.

25. The system of claim 21, wherein

the protocol engine included in the first node is configured to respond to the read-exclusive request by

determining if the directory maintained in the memory subsystem local to the first node indicates that a subset of the plurality of nodes have copies of the memory line, the subset comprising a number of the nodes equal to the determined number;

sending an invalidation request to the determined number of nodes; and

sending the read-exclusive reply to the requesting nodes, the read-exclusive reply including the memory line and indicating the determined number of nodes in the plurality of nodes that have a copy of the memory line.

26. The system of claim 25, wherein

the protocol engine included in each of the subset of nodes is configured to respond to the invalidation request by

invalidating a local copy of the memory line;

and

sending an invalidation acknowledgment to the requesting node.

27. The system of claim 26, wherein

the protocol engine included in the requesting node is configured to delay completion of received requests concerning the memory line until the determined number of invalidation acknowledgments are processed by the requesting node.

28. A multiprocessor computer system, comprising:

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 tray for storing an entry related to a memory transaction, the entry including 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 of a requesting nodes is configured to process a memory transaction 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;

the first protocol message is an exclusive request for a memory line maintained at the first node and the requesting node; and

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

29. The system of claim 28, wherein

the protocol engine in the first node is configured to respond to the exclusive request by

determining if a directory maintained in the memory subsystem local to the first node indicates that a subset of the plurality of nodes have a shared copy of the memory line;

sending an invalidation request to the subset of the plurality of nodes;

sending the exclusive reply to the requesting node, the exclusive reply including a count of the subset of the plurality of nodes; and

modifying the directory to indicate that the requesting nodes is an exclusive owner of the memory line.

30. The system of claim 29, wherein

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

invalidating a local copy of the memory line;

and

sending an invalidation acknowledgment to the requesting node.

31. The system of claim 28, wherein

the protocol engine in the first node is configured to respond to the exclusive request by

determining if the directory maintained in the memory subsystem local to the first node indicates that only the requesting node has a copy of the memory line;

sending the exclusive reply to the requesting node, the exclusive reply indicating that only the requesting node has a copy of the memory line; and

modifying the directory to indicate that the requesting node is an exclusive owner of the memory line.

32. The system of claim 28, wherein

the protocol engine in the first node is configured to respond to the exclusive request by

determining if a directory maintained in the memory subsystem local to the first node indicates that the requesting node has a shared copy of the memory line;

declining further processing of the exclusive request.

33. A multiprocessor computer system, comprising:

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 of a requesting node is configured to process a memory transaction 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 first set of one or more protocol message required to advance the memory transaction to a next state; and

updating the state of the memory transaction in response to receipt of a protocol message included in the first set of one or more protocol messages to indicate a second set of one ore more protocol messages required to advance the state of the memory transaction.

34. The system of claim 33, wherein

the first set of one or more protocol messages includes a reply to a request, the reply specifying a determined number of invalidation acknowledgments, the invalidation acknowledgments composing a portion of the first set of one or more protocol messages.

35. The system of claim 34, wherein

the protocol engine is configured to update the state of the memory transaction to reflect invalidation acknowledgments received.

36. The system of claim 34, wherein

the state of the memory transaction includes a counter, the counter used to track receipt of the determined number of invalidation acknowledgments.

37. The system of claim 33, wherein the state comprises a number of separate fields within the memory transaction array.

38. A multiprocessor computer system, comprising:

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 process a memory transaction by removing from the memory transaction array an entry for the memory transaction upon processing a final protocol message.

39. The system of claim 38, wherein

each node is configured to maintain in the directory an entry for a memory line of information stored in the local memory subsystem, the entry indicating a state of the memory line of information.

40. The system of claim 39, wherein

each node is configured to

set the state of the memory line to an invalid state to indicate that a memory cache included in another node is not caching the memory line;

set the state of the memory line to a shared state to indicate that the memory cache included in the another node is caching a shared copy of the memory line; and

set the state of the memory line to an exclusive state to indicate that the memory cache included in the another node is caching an exclusive copy of the memory line.

41. A multiprocessor computer system, comprising:

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 each node is configured to maintain in the directory an entry for a memory line of information stored in the local memory subsystem, the entry indicating a state of the memory line of information;

wherein each node is configured to

set the state or the memory line to an invalid state to indicate that a memory cache included in another node is not caching the memory line;

set the state of the memory line to a shared state to indicate that the memory cache included in the another node is caching a shared copy of the memory line;

set the state of the memory line to an exclusive state to indicate that the memory cache included in the another node is caching an exclusive copy of the memory line;

maintain in the entry an identifier of the another node caching a shared copy of the memory line; and

maintain in the entry an identifier of the another node caching an exclusive copy of the memory line.

42. The system of claim 41, wherein

each node includes a central processing unit, the central processing unit configured to initiate a protocol message concerning a memory line of information stored in the local memory subsystem; and

each node is configured to route the message to the protocol engine if an entry for the memory line in the directory indicates that another node is caching an exclusive copy of the memory line.

43. The system of claim 41, wherein

each node includes a central processing unit, the central processing unit configured to initiate a protocol message concerning a memory line of information stored in the local memory subsystem;

and

each node is configured to not route the protocol message to the protocol engine if an entry for the memory line in the directory indicates that no other node is caching a copy of the memory line.

44. The system of claim 41, wherein

each node includes a central processing unit, the central processing unit configured to initiate a protocol message concerning a memory line of information stored in the local memory subsystem;

and

each node is configured to not route the protocol message to the protocol engine if an entry for the memory line in the directory indicates that another node is caching a copy of the memory line.

45. A multiprocessor computer system, comprising:

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 plurality of nodes are interconnected by a network; and

each node is configured to select a priority for a protocol message routed across the network, the priority determining an allocation of resources to the protocol message by each node.

46. The system of claim 45, wherein

a first priority is selected for the protocol message directed to an input/output device;

a second priority is selected for the protocol message concerning a memory line of information stored in the memory subsystem that is local to a first node and being sent to or received by the first node;

a third priority is selected for the protocol message concerning a memory line of information stored in the memory subsystem that is local to a first node and being sent by or received from the first node; and

a fourth priority is selected for the protocol message concerning a memory line of information stored in the memory subsystem that is local to a first node and being sent by a second node to a third node or received by the third node from the second node.

47. The system of claim 46, wherein

node resources are allocated to a memory transaction including protocol messages for which the second priority is selected until the memory transaction is complete.

48. The system or claim 46, wherein

the third priority is selected for a write-back request through said write-back request is a protocol message concerning a memory line of information stored in the memory subsystem that is local to a first node and being sent to the first node.

49. A multiprocessor computer system, comprising:

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 includes logic required to manage a race condition, the race condition occurring in a first node waiting for a reply to a first protocol message sent by the first node to a second node related to a memory line maintained in a memory subsystem local to the second node receives a second protocol message from the second node related to the memory line before receiving the reply.

50. The system of claim 49, wherein

the first protocol message is a read-request for the memory line;

the reply is a read reply, the reply including a copy of the memory line;

the second protocol message is a invalidation request;

the protocol engine included in the first node is configured to

send an invalidation acknowledgment in response to receiving the invalidation request; and

not cache the copy of the memory line included in the reply.

51. The system of claim 49, wherein

the first protocol message is one of a set including a read-exclusive request and an exclusive request for the memory line;

the second protocol message is an invalidation request;

the protocol engine included in the first node is configured to

send an invalidation acknowledgment in response to receiving the invalidation request and;

process the reply upon receiving the reply without regard to the invalidation request.

52. The system of claim 49, wherein

the second protocol message is one of a set including a read request and a read-exclusive request;

the protocol engine included in the first node is configured to delay processing of the second protocol message until after the reply is received.

53. The system of claim 52, wherein

an entry in the memory transaction array is added for the second protocol message, the entry indicating that receipt of the reply by the first node is required to advance a state of a memory transaction associated with the second protocol message.

54. The system of claim 53, wherein

the first protocol message is a write-back request.