Accession Number:

ADA143529

Title:

Simulation of Large Networks of Processors by Smaller Ones.

Descriptive Note:

Technical rept.,

Corporate Author:

MARYLAND UNIV COLLEGE PARK CENTER FOR AUTOMATION RESEARCH

Personal Author(s):

Report Date:

1984-05-01

Pagination or Media Count:

24.0

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

Subject Categories:

  • Theoretical Mathematics
  • Computer Hardware
  • Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE