Dominant edge identification for efficient partition and distribution

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, dominant edges are identified within the communication graph. For any non-terminal node, a connected edge is dominant if it is at least as heavy (its weight is greater than or equal to) as the sum of the remaining non-terminal edges and the heaviest of the remaining terminal edges. The min cut for the communication graph need not include any dominant edges and so, dominant edges are removed from consideration for the final min cut solution. Finally, program components which may be a single program unit or an aggregate of units are placed on computers according to the communication graph min cut solution.