Independent net task identification for efficient partition and distribution
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
25 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
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. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18)
-
-
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. - View Dependent Claims (20, 21, 22, 23, 24, 25)
-
Specification