Simulation of Large Networks of Processors by Smaller Ones.
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1984
- Accession Number
- ADA143529
Entities
People
- A. Y. Wu
- Azriel Rosenfeld
- S. K. Bhaskar
Organizations
- University of Maryland