A Heuristic for Partitioning Parallel Computation.
Weizhen Mao, David M. Nicol · Parallel and distributed computing and systems · 1995
Parallel computation can usually be viewed as a weighted undirected graph, where graph nodes typically represent computation, and edges represent communication. One seeks to distribute the total workload (computation and communication) by partitioning the graph into subgraphs and assigning each subgraph to a processor such that every processor has approximately the same amount of workload. In this paper, we prove the intractability of this graph partition problem, present a greedy heuristic, and analyze the performance of the algorithm.