Machine cut task 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. Independent nets may be separated out of the communication graph. A cut is made at each terminal node and the weights of the cut edges are summed. The second heaviest terminal is identified from the cut and edges connected to at least one internal node and not connected to the second heaviest edge are compared against the weight of the second heaviest edge. Any edge found in the comparison to be at least as heavy as the second heaviest terminal node need not be included in the min cut for the communication graph and so, is 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.