Simulation of Large Networks of Processors by Smaller Ones.
MARYLAND UNIV COLLEGE PARK CENTER FOR AUTOMATION RESEARCH
Pagination or Media Count:
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
- Theoretical Mathematics
- Computer Hardware
- Computer Systems