Independent net task identification for efficient partition and distribution

• US 7,010,789 B1
• Filed: 09/29/2000
• Issued: 03/07/2006
• Est. Priority Date: 09/29/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rajan, Vadakkedathu T., Wegman, Mark N., Roth, Tova, Hogstedt, Karin, Kimelman, Douglas N.
• Primary Examiner(s): An, Meng-Al T.
• Assistant Examiner(s): Ali, Syed J
• Application Number:
  US09/676,422
• Time in Patent Office: 1,985 Days
• Field of Search: 718/100, 718/102, 718/106, 718/105, 718/104, 709/200, 709201-203, 709217-219, 719/310
• US Class Current: 718/100
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

A task management system, method and computer program product for determining optimal placement of task components on multiple machines for task execution, particularly for placing program components on multiple computers for distributed processing. First, a communication graph is generated representative of the computer program with each program unit (e.g., an object) represented as a node in the graph. Nodes are connected to other nodes by edges representative of communication between connected nodes. A weight is applied to each edge, the weight being a measure of the level of communication between the connected edges. Terminal nodes representative of the multiple computers are attached to the communication graph. Then, the communication graph is divided into independent nets and a min cut is found for each independent net. The min cut for the communication graph is the combination of the min cuts for all of the independent nets. Finally, program components which may be a single program unit or an aggregate of units are placed on computers according to the communication min cut.

Claims

1. A task management method for determining optimal placement of task components, said method comprising:

a) generating a communication graph representative of a task;

b) identifying independent nets in said communication graph comprising steps of;

i) selecting a seed node for an independent net,

ii) identifying nodes adjacent to said seed node as perimeter nodes belonging to said independent net, perimeter nodes being an outer perimeter of nodes identified as belonging to said independent net,

iii) identifying nodes adjacent to said perimeter nodes as belonging to said independent net, said identified adjacent nodes being identified as perimeter nodes; and

iv) repeating step (iii) until all perimeter nodes are terminal nodes;

c) determining a min cut for each independent net; and

d) placing said task components responsive to said min cut determined for each independent net.

2. A task management method as in claim 1, wherein the communication graph generated in step (a) comprises:

task components represented as said nodes of said communication graph; and

edges connecting ones of said nodes representing communication between connected nodes.

3. A task management method as in claim 2, after the step (a) of generating a communication graph, further comprising the steps of:

a1) weighting edges, said edges being weighted proportional to communication between connected nodes; and

a2) assigning terminal nodes, task components being placed on said terminal nodes in the task placing step (d).

4. A task management method as in claim 3, wherein before the step (i) of selecting a seed node, all nodes not being terminal nodes are marked as unvisited nodes.

5. A task management method as in claim 4, wherein in step (i) the seed node is marked as visited and perimeter nodes are marked as visited in steps (ii) and (iii).

6. A task management method as in claim 5, wherein all nodes marked as visited in steps (i)–

(iv) identify an independent net, said method further comprising the steps of;

v) checking said communication graph for unvisited nodes; and

,

vi) repeating steps (i)–

(v) whenever unvisited nodes remain in said communication graph.

7. A task management method as in claim 3, wherein the step (c) of determining a min cut comprises the steps of:

i) listing all independent nets as subgraphs in a subgraph list;

ii) selecting a subgraph from said subgraph list;

iii) applying a linear complexity method to said subgraph, if said linear complexity method divides said subgraph into two or more smaller independent nets, listing said smaller independent nets in said sub graph list and returning to step (i);

iv) checking whether said subgraph includes two or more smaller independnet nets, if said subgraph includes two or more smaller independent nets, identifying and listing said smaller independent nets in said subgraph list and returning to step (i);

v) applying a higher complexity method to said subgraph, said higher complexity method being more complex than said linear complexity method and, if said higher complexity method divides said subgraph into two or more smaller independent nets, listing said smaller independent nets in said subgraph list and returning to step (i);

vi) selectively collapsing an edge to reduce said subgraph, if collapsing said edge divides said subgraph into two or more smaller independent nets, listing said smaller independent nets in said subgraph list and returning to step (i); and

vii) checking whether said subgraph list is empty.

8. A task management method as in claim 3, wherein each said task component is a unit of the computer program.

9. A task management method as in claim 8, wherein said each computer program unit is an instance of an object in an object oriented program.

10. A task management method as in claim 8, wherein in step (d) computer program units are placed on computers, computer program units being placed on a common computer being combined into a single component.

11. A distributed processing system for determining optimal placement of computer program components on multiple computers, said distributed processing system comprising:

means for generating a communication graph representative of a computer program;

means for identifying independent nets in said communication graph comprising;

means for selecting a seed node amongst nodes of said communication graph, and

means for branching out from said seed node and identifying perimeter nodes adjacent until all perimeter nodes are terminal nodes;

means for determining a min cut for each independent net; and

means for placing program components on ones of multiple independent computers responsive to said min cut determined for each independent net;

said computer program being executed by said multiple independent computers.

12. A distributed processing system as in claim 11, wherein the communication graph comprises:

a plurality of said nodes, each of said plurality of nodes representing one of said program components; and

a plurality of edges connecting ones of said nodes, each of said edges representing communication between connected nodes.

13. A distributed processing system as in claim 12, further comprising:

weighting means for weighting said edges proportional to communication between connected said nodes and the communication graph further comprises terminal nodes, task components being placed on said terminal nodes.

14. A distributed processing system as in claim 13 further comprising means for marking nodes as unvisited nodes or as visited nodes.

15. A distributed processing system as in claim 14, wherein the marking means marks each perimeter node as visited, when all nodes in said communication graph are marked as visited all independent nets have been identified in said communication graph.

16. A distributed processing system as in claim 15, wherein the means for determining a min cut comprises:

means for maintaining a list of all independent nets;

linear complexity reduction means for selectively reducing listed independent nets;

higher complexity reduction means for selectively reducing listed independent nets using a method having higher complexity than used by said linear complexity means;

means for selectively collapsing independent net edges to reduce said listed independent nets;

means for checking whether any reduced independent net includes two or more smaller independent nets; and

means for checking whether said list is empty.

17. A distributed processing system as in claim 16, wherein each said program component is a unit of the computer program.

18. A distributed processing system as in claim 17, wherein said each program unit is an instance of an object in an object oriented program.

19. A computer program product for partitioning a graph, said computer program product comprising a computer usable medium having computer readable program code thereon, said computer readable program code comprising:

computer readable program code means for identifying independent nets in a graph of a plurality of nodes connected together by a plurality of edges each of said edges being between a pair of adjacent said nodes, a plurality of said nodes being terminal nodes, said computer readable program code means for identifying independent nets comprising;

computer readable program code means for selecting a seed node;

computer readable program code means for identifying nodes adjacent to said independent net as perimeter nodes beginning at said seed node;

computer readable program code means for determining a min cut for each independent net; and

computer readable program code means for assigning nodes to ones of said terminal nodes responsive to said min cut determined for each independent net.

20. A computer program product for partitioning a graph as in claim 19, wherein each of said plurality of edges includes a weight, said min cut for said each independent net being a cut of said independent net wherein the sum of weights of edges in said cut is minimum for said independent net.

21. A computer program product for partitioning a graph as in claim 20 wherein the computer readable program code means for identifying independent nets further comprises:

computer readable program code means for marking nodes as visited or unvisited nodes, said seed node and said perimeter nodes being marked as visited.

22. A computer program product for partitioning a graph as in claim 21, wherein the computer readable program code means for identifying independent nets further comprises:

computer readable program code means for checking for unvisited nodes.

23. A computer program product for partitioning a graph as in claim 20, wherein the computer readable program code means for determining a min cut comprises:

computer readable program code means for listing all independent nets as subgraphs in a subgraph list;

computer readable program code means for selecting a subgraph from said subgraph list;

computer readable program code means for applying a linear complexity method to selectively reduce said subgraph;

computer readable program code means for applying a higher complexity method to selectively reduce said subgraph said higher complexity method being more complex than said linear complexity method;

computer readable program code means for selectively collapsing an edge to reduce said subgraph;

computer readable program code means for checking whether said subgraph includes two or more smaller independnet nets, if said subgraph includes two or more smaller independent nets, identifying and listing said smaller independent nets in said subgraph list; and

computer readable program code means for checking whether said subgraph list is empty.

24. A computer program product for partitioning a graph as in claim 20, wherein each said terminal node represents a computer, each of the remaining ones of said plurality of nodes is a unit of the computer program and each of said edges represents communication between connected computer program units.

25. A computer program product for partitioning a graph as in claim 24, wherein each computer program unit is an instance of an object in an object oriented program.