System for minimizing directory information in scalable multiprocessor systems with logically independent input/output nodes

• US 6,738,868 B2
• Filed: 01/07/2002
• Issued: 05/18/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., Barroso, Luiz Andre, Gharachorloo, Kourosh
• Primary Examiner(s): Sparks, Donald
• Assistant Examiner(s): CHACE, CHRISTIAN
• Application Number:
  US10/042,035
• Publication Number:
  US 20020087807A1
• Time in Patent Office: 862 Days
• Field of Search: 707/10, 707/201, 709/201, 709/213, 709/217, 711/117, 711/148, 711/151, 711/156, 711/159
• 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

A system of scalable shared-memory multiprocessors includes processor nodes and I/O nodes. The I/O nodes connect I/O devices directly to an interconnection network of a system of scalable shared-memory multiprocessors. Each node of the system includes an interface to a local memory subsystem, a memory cache and a protocol engine. The local memory subsystem stores memory lines of information and a directory. Each entry in the directory stores sharing information concerning a memory line of information stored in the local memory subsystem. The protocol engine in each I/O node is configured to limit to a predefined period of time any sharing of a memory line of information from the memory subsystem of any other node. The protocol engine in the home node of the memory line is configured to identify only nodes other than I/O nodes that are sharing the memory line of information. In one embodiment, I/O nodes that share the memory line of information are not identified in the directory entry of the memory line, and instead are represented by a count field, which indicates how many I/O nodes share the memory line of information.

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, said directory configured to store sharing information concerning a memory line of information stored in the local memory subsystem;

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;

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;

a first subset of nodes comprising one or more nodes from said plurality of nodes, each node in said first subset including an interface to one or more I/O devices;

the protocol engine included in each node from said first subset of nodes is configured to limit to a predefined period of time, any sharing of a memory line of information stored in the remote memory subsystem that is local to a home node from said plurality of nodes; and

the protocol engine included in the home node is configured to identify only nodes other than nodes in the first subset that are sharing the memory line of information.

2. The system of claim 1, wherein

the protocol engine included in the home node is further configured to maintain a count of the nodes in the first subset that are sharing the memory line of information.

3. The system of claim 2, wherein

the protocol engine included in the home node is further configured to place a request for exclusive ownership of the memory line of information in a pending state if the count indicates that at least one node in the first subset is sharing the memory line of information.

4. The system of claim 3, wherein

the protocol engine included in the home node is further configured to remove from the pending state the request for exclusive ownership of the memory line of information when the count subsequently indicates that none of the nodes in the first subset are sharing the memory line of information.

5. The system of claim 3, wherein

the protocol engine included in the home node is further configured to place in a pending state a request to share the memory line of information from a requesting node of the first subset of nodes if the request for the exclusive ownership is in a pending state.

6. The system of claim 5, wherein

the protocol engine included in the home node is further configured to remove from the pending state the request to share the memory line of information from the requesting node after the request for exclusive ownership of the memory line of information is removed from the pending state.

7. The system of claim 2, wherein

the protocol engine included in the home node is further configured to increment the count in response to a request to share the memory line of information from a requesting node of the first subset of nodes.

8. The system of claim 2, wherein

the count is maintained in an entry of the directory, said entry being associated with the memory line of information.

9. The system of claim 2, wherein

the protocol engine included in the home node is further configured to reduce the count in response to a notice of invalidation from a requesting node of said first subset of nodes, said notice of invalidation indicating that the requesting node is no longer sharing the memory line of information.

10. The system of claim 1, wherein

the protocol engine included in each node in said first subset of nodes is configured to store information in the memory transaction array to facilitate monitoring of the predefined period of time.

11. The system of claim 10, wherein

modifying the memory transaction array includes encoding a time at which the predefined period of time expires, said time subsequently being compared to a current time.

12. The system of claim 10, wherein

modifying the memory transaction array includes encoding a numerical value, said numerical value subsequently being reduced a predefined number times such that the predefined period of time expires approximately when the numerical value is reduced to a predefined value.

13. The system of claim 10, wherein

the sharing of the memory line of information begins when a requesting node of said first subset of nodes receives an affirmative response to a request to share the memory line of information.

14. The system of claim 10, wherein

the protocol engine included in each node in said first subset of nodes is configured to scan the memory transaction array to determine whether the predefined period of time has expired.

15. The system of claim 14, wherein

the protocol engine included in each node of said first subset of nodes is configured to terminate the sharing of the memory line of information if the predefined period of time has expired.

16. The system of claim 15, wherein

terminating the sharing of the memory line of information includes invalidating a copy of the memory line of information stored in the memory cache.

17. The system of claim 15, wherein

terminating the sharing of the memory line of information includes sending an invalidation notice to the home node.

18. The system of claim 1, wherein

the protocol engine included in the home node is further configured to send an invalidation acknowledgment to a node of the plurality of nodes requesting exclusive ownership of the memory line of information after each node of the first subset of nodes that was sharing the memory line of information terminates the sharing of the memory line of information, said node from the plurality of nodes requesting exclusive ownership of the memory line of information being prevented from completing a memory transaction associated with the request for exclusive ownership until after each node of the first subset of nodes that was sharing the memory line of information terminates the sharing of the memory line of information.

19. The system of claim 1, where

the protocol engine included in the home node is further configured to limit the sharing of the memory line of information by the one or more requesting nodes to a predefined period of time.

20. The system of claim 19, wherein

the protocol engine included in the home node is further configured to set a time field associated with the memory line of information in the memory transaction array to monitor the predefined period of time.

21. The system of claim 19, wherein

the protocol engine included in each node in said first subset of nodes is configured to scan the memory transaction array to determine whether the predefine period of time has expired.

22. The system of claim 19, wherein

the protocol engine included in each node in said first subset of nodes is configured to terminate the sharing of the memory line of information if the predefine period of time has expired.

23. 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, said directory configured to store sharing information concerning a memory line of information stored in the local memory subsystem;

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;

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;

a first subset of nodes comprising one or more nodes from said plurality of nodes, each node in said first subset including an interface to one or more I/O devices;

the protocol engine included in a requesting node from said first subset of nodes configured to send to a home node from said plurality of nodes a request to share a memory line of information stored in the remote memory subsystem that is local to the home node;

the protocol engine included in the home node further configured to generate a reply in response to the request to share the memory line of information such that the requesting node receives a copy of the memory line of information;

the protocol engine included in the home node further configured to update a count maintained in a directory entry associated with the memory line of information in response to the request to share the memory line of information, said count subsequently indicating that an unidentified node from said first subset of nodes is sharing the memory line of information;

the protocol engine included in the requesting node further configured to send a notice of invalidation after a predetermined amount of time sharing the memory line of information; and

the protocol engine included in the home node further configured to update said count in response to the notice of invalidation, said count subsequently indicating that the unidentified node from said first subset of nodes is not sharing the memory line of information.

24. The system of claim 23, wherein

the protocol engine included in the requesting node is further configured to invalidate the copy of the memory line of information after the predetermined amount of time sharing the memory line of information.

25. The system of claim 23, wherein

the protocol engine included in the home node is further configured to place a request for exclusive ownership of the memory line of information in a pending state if the count indicates that at least one unidentified node is sharing the memory line of information.

26. The system of claim 25, wherein

the protocol engine included in the home node is further configured to remove from the pending state the request for exclusive ownership of the memory line of information after the count indicates that no unidentified nodes are sharing the memory line of information.

27. The system of claim 25, wherein

the protocol engine included in the home node is further configured to place a request by a node from the first subset of nodes to share the memory line of information in a pending state if the request for exclusive ownership of the memory line of information is in a pending state.

28. The system of claim 27, wherein

the protocol engine included in the home node is further configured to remove from the pending state the request by the node from the first subset of nodes to share the memory line of information after the request for exclusive ownership of the memory line of information is removed from the pending state.

29. 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, said directory configured to store sharing information concerning a memory line of information stored in the local memory subsystem;

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;

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;

a first subset of nodes comprising one or more nodes from said plurality of nodes, each node in said first subset including an interface to one or more I/O devices;

the protocol engine included in a requesting node from said first subset of nodes is configured to send to a home node from said plurality of nodes a request to share a memory line of information stored in the remote memory subsystem that is local to the home node;

the protocol engine included in the home node further configured to generate a response to the request to share the memory line of information such that the requesting node receives a copy of the memory line of information, wherein the home node is configured to retain sharer information identifying only nodes other than nodes in the first subset that are sharing the memory line of information;

the protocol engine included in the home node further configured to set of field of a directory entry associated with the memory line of information in response to the request to share the memory line of information, said field subsequently indicating that an unidentified node from said first subset of nodes is sharing the memory line of information;

the protocol engine included in the home node further configured to update the field of the directory entry after a first predetermined period of time such that the field no longer indicates that the unidentified node is sharing the memory line of information; and

the protocol engine included in the requesting node further configured to invalidate the copy of the memory line of information after a second predetermined amount of time, the second predetermined amount of time corresponding to the first predetermined amount of time.

30. The system of claim 29, wherein

the protocol engine included in the home node is further configured to place a request for exclusive ownership of the memory line of information in a pending state if the field of the directory entry indicates that at least one unidentified node is sharing the memory line of information.

31. The system of claim 30, wherein

the protocol engine included in the home node is further configured to remove from the pending state the request for exclusive ownership of the memory line of information after the field of the directory entry indicates that no unidentified nodes are sharing the memory line of information.

32. The system of claim 31, wherein

the requesting node is a first requesting node;

and

the protocol engine included in the home node is further configured to place a request to share the memory line of information from a second requesting node from the first subset of nodes in a pending state if the request for exclusive ownership of the memory line of information is in a pending state.

33. The system of claim 32, wherein

the protocol engine included in the home node is further configured to remove from the pending state the request to share the memory line of information by the second requesting node after the request for exclusive ownership of the memory line of information is removed from the pending state.

34. The system of claim 29, wherein

the protocol engine included in the home node is further configured to update the field of the directory entry each time a request is received from a node from the first subset of nodes to share the memory line of information while the field of the directory entry indicates that at least one unidentified node is sharing the memory line of information.

35. 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;

a first subset of nodes comprising one or more nodes from said plurality of nodes, each node in said first subset including an interface to one or more I/O devices;

the protocol engine included in each node in said first subset of nodes configured to treat requests initiated by said one or more I/O devices for a shared copy of a memory line of information maintained in a memory subsystem that is local to another node as a request for an exclusive copy of the memory line of information.

36. The system of claim 35, wherein

each node in said first subset of nodes does not include a processor core.

37. The system of claim 35, wherein

the protocol engine included in each node in said first subset of nodes is configured to treat a read request as a read-exclusive request.