Granted Patent B2

US 8,407,424 · App. 11/268,164 · Granted Mar 26, 2013

Abstract

Claims (44)

1. A method of maintaining data coherency in a computer system having a plurality of processing nodes, each processing node including at least one computer processor and a local memory, a subset of the processing nodes cooperating on a common task, the method comprising:

grouping the processing nodes into a plurality of node groups, each node group having a level, wherein each node group in a lowest level consists of a single processing node in the subset, and each node group that has a given level other than the lowest level consists of a fixed number of node groups, each node group in the fixed number of node groups having a level that is lower than the given level, there being at least one node group having a level other than the lowest level;

in each node of the subset, storing a data record comprising a memory directory, each memory directory having (1) data indicating a first level and (2) data relating to a plurality of node groups having that level;

receiving, in a given node, a request from a requesting node to obtain a copy of a portion of the local memory of the given node, the given node hereinafter called the home node;

determining whether the memory directory of the home node includes data relating to a node group that is associated with the requesting node; and

when the memory directory does not include such data, setting the memory directory of the home node to have (1) data indicating a second, higher level and (2) data relating to a plurality of node groups at the higher level, wherein one node group of the plurality of node groups at the higher level is associated with the requesting node, and wherein setting the memory directory does not change its size, to save memory space required to store the memory directory.

2. The method as defined by claim 1 wherein each processing node in the subset is a member of at least one node group in each level.

3. The method as defined by claim 1 wherein each node group in the higher level comprises a plurality of node groups in the lower level, each lower level node group being a part of at least one node group in the higher level.

4. The method as defined by claim 1 further comprising determining if the requesting node is a member of a requesting group in the plurality of node groups at the higher level after setting the directory of the home node to have data relating to the plurality of node groups at the higher level.

5. The method as defined by claim 4 further comprising forwarding a coherence message to at least one of the nodes in the requesting group if it is determined that the requesting node is a member of the requesting group, the coherence message having information relating to the state of the requested data.

6. The method as defined by claim 1 wherein the requesting node is a member of a given node group, the given node group being one of the plurality of node groups in the directory of the home node, the method further comprising:

determining if the directory of the home node has data indicating that one of the members of the given node group has access to the data requested from the requesting node; and

modifying the directory of the home node to have data indicating such access if the directory of the home node does not have data indicating such access.

7. The method as defined by claim 1 wherein the directory of the home node has a multi-dimensional data structure for storing information relating to the different node groups.

8. The method as defined by claim 1 further comprising increasing the level of the directory of the home node until it has been determined that the requesting node is a member of at least one group identified by the directory of the home node.

9. A memory controller for maintaining data coherency in a home node of a computer system having a plurality of processing nodes, each processing node including at least one computer processor and a local memory, the memory controller comprising:

a grouping module that groups the plurality of processing nodes into a plurality of node groups, each node group having a level, wherein each node group in a lowest level consists of a single processing node in the subset, and each node group that has a given level other than the lowest level consists of a fixed number of node groups, each node group in the fixed number of node groups having a level that is lower than the given level, there being at least one node group having a level other than the lowest level;

in each node of the subset, a memory controller that maintains a data record comprising a memory directory, the memory directory having (1) data indicating a first level and (2) data relating to a plurality of node groups having that level;

a membership module operatively coupled with the grouping module, the membership module determining, in response to the home node receiving a request from a requesting node to obtain a copy of a portion of the local memory of the home node, whether the memory directory of the home node includes data relating to a node group that is associated with the requesting node; and

a level module operatively coupled with the membership module, the level module setting the memory directory of the home node to have (1) data indicating a second, higher level and (2) data relating to a plurality of node groups at the higher level, wherein one node group of the plurality of node groups at the higher level is associated with the requesting node, and wherein setting the memory directory does not change its size, to save memory space required to store the memory directory,

one or more of the modules being formed at least in part from hardware of the processing node.

10. The memory controller as defined by claim 9 wherein each processing node is a member of at least one node group in each level.

11. The memory controller as defined by claim 9 wherein each node group in the higher level comprises a plurality of node groups in the lower level, each lower level node group being a part of at least one node group in the higher level.

12. The memory controller as defined by claim 9 wherein the membership module determines if the requesting node is a member of a requesting group in the plurality of node groups at the higher level after setting the directory of the home node to have data relating to the plurality of node groups at the higher level.

13. The memory controller as defined by claim 12 further comprising an output for forwarding a coherence message to at least one of the nodes in the requesting group if it is determined that the requesting node is a member of the requesting group, the coherence message having information relating to the state of the requested data.

14. The memory controller as defined by claim 9 wherein the requesting node is a member of a given node group, the given node group being one of the plurality of node groups in the directory of the home node, the memory controller further comprising:

a parser that determines if the directory of the home node has data indicating that one of the members of the given node group has access to the data requested from the requesting node; and

a modifier operatively coupled with the parser, the modifier modifying the directory of the home node to have data indicating such access if the directory of the home node does not have data indicating such access.

15. The memory controller as defined by claim 9 wherein the level module increases the level of the directory of the home node until it has been determined that the requesting node is a member of at least one group identified by the directory of the home node.

16. A computer program product for maintaining data coherency by and in a computer system having a plurality of processing nodes, each processing node including at least one computer processor and a local memory, a subset of the computer nodes cooperating on a common task, the computer program product comprising a non-transitory tangible computer-usable storage medium having computer readable program code thereon, the computer readable program code comprising:

program code for grouping the processing nodes into a plurality of node groups, each node group having a level, wherein each node group in a lowest level consists of a single processing node in the subset, and each node group that has a given level other than the lowest level consists of a fixed number of node groups, each node group in the fixed number of node groups having a level that is lower than the given level, there being at least one node group having a level other than the lowest level;

program code for storing, in each node of the subset, a data record comprising memory directory that maintains a record of other nodes in the subset, each memory directory having (1) data indicating a first level and (2) data relating to a plurality of node groups at that level;

program code for receiving, in a given node, a request from a requesting node to obtain a copy of a portion of the local memory of the given node, the given node hereinafter called the home node;

program code for determining whether the memory directory of the home node includes data relating to a node group that is associated with the requesting node; and

program code for setting the memory directory of the home node, when the memory directory does not include such data, to have (1) data indicating a second, higher level and (2) data relating to a plurality of node groups at the higher level, wherein one node group of the plurality of node groups at the higher level is associated with the requesting node, and wherein setting the memory directory does not change its size, to save memory space required to store the memory directory.

17. The computer program product as defined by claim 16 wherein each processing node in the subset is a member of at least one node group in each level.

18. The computer program product as defined by claim 16 wherein each node group in the higher level comprises a plurality of node groups in the lower level, each lower level node group being a part of at least one node group in the higher level.

19. The computer program product as defined by claim 16 further comprising program code for determining if the requesting node is a member of a requesting group in the plurality of node groups at the higher level after the directory of the home node is set to have data relating to the plurality of node groups at the higher level.

20. The computer program product as defined by claim 19 further comprising program code for forwarding a coherence message to at least one of the nodes in the requesting group if it is determined that the requesting node is a member of the requesting group, the coherence message having information relating to the state of the requested data.

21. The computer program product as defined by claim 16 wherein the requesting node is a member of a given node group, the given node group being one of the plurality of node groups in the directory of the home node, the computer program product further comprising:

program code for determining if the directory of the home node has data indicating that one of the members of the given node group has access to the data requested from the requesting node; and

program code for modifying the directory of the home node to have data indicating such access if the directory of the home node does not have data indicating such access.

22. The computer program product as defined by claim 16 further comprising program code for increasing the level of the directory of the home node until it has been determined that the requesting node is a member of at least one group identified by the directory of the home node.

23. The computer program product as defined by claim 16 wherein each node has a physical location and at least one node that is physically close, the program code for storing a directory of the home node comprising program code for grouping nodes with its relative neighbors.

Assignments (6)