Independent net task identification for efficient partition and distribution

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.

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.