Patent ID: 6021442
Filing Date: 2000-02-01
Classification: G06F

Abstract:
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform the method steps for the partitioning of an interconnection medium, the interconnection medium for providing interconnections between nodes in a plurality of disjoint sets of nodes, wherein the interconnection medium comprises a plurality of groups, each including one or more node coupling elements and one or more link coupling elements, the node coupling elements each coupled to one or more of the nodes and capable of being coupled within each of the groups to the link coupling elements, each of the link coupling elements within one of the groups capable of being coupled to the link coupling elements in the other groups to interconnect the node coupling elements in different groups, and wherein a partition is defined by exclusively assigning one or more of the node coupling elements and the link coupling elements required to interconnect the assigned node coupling elements to one of the disjoint sets of nodes to permit the interconnection of the nodes therein and to isolate the nodes therein form the nodes in any other of the disjoint sets of nodes, the method steps comprising:(a) defining a partition interconnecting the largest connected disjoint set of nodes;(b) if any group having a node coupling element in any of the defined partitions includes another node coupling element coupled to an unconnected disjoint set of nodes, defining a new partition interconnecting the nodes within the unconnected disjoint set of nodes to which the other node coupling element in such a group is coupled;(c) repeating step b until no group having a node coupling element in any of the defined partitions also includes another node coupling element coupled to an unconnected disjoint set of nodes; and(d) repeating steps a-c until there are no remaining unconnected disjoint sets of nodes.