Simulation of Large Networks of Processors by Smaller Ones.
S. K. Bhaskar, Azriel Rosenfeld, Angela Y. Wu · 1984
This paper considers the problem of simulating a large network N of processors using a small set of p processors. The approach taken is to partition the nodes of N into p subsets N sub 1 N sub P and to assign each subset to a processor for simulation. In order to equalize the workloads of the processors, the sizes of N sub 1, N sub P should be as equal as possible; and in order to minimize (and equalize) the amount of message passing between the processors, the number of pairs of nodes that are neighbors in N but belong to different subsets should be as small (and as equal) as possible. The authors discuss the general problem of partitioning a graph N so as to satisfy these criteria, and also consider the particular case of partitioning a tree. (Author)