Net zeroing for efficient partition and distribution

Abstract

The present invention is 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 ones of the multiple computers are attached to the communication graph. Independent nets may be separated out of the communication graph. For each net, non-terminal nodes adjacent to all of terminal nodes on the net and connected to the net by non-zero weighted edges are identified For each identified non-terminal node, the smallest weight for any terminal edge is identified and the weight of each terminal edge is reduced by the value of that smallest weight, the weight of terminal edges having the smallest weight being reduced to zero. After reducing weights on any terminal edges, The min cut solution is obtained from the reduced graph and 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.