Accession Number : ADA139847

Title :   Embedding of Networks of Processors into Hypercubes.

Descriptive Note : Technical rept.,

Corporate Author : MARYLAND UNIV COLLEGE PARK CENTER FOR AUTOMATION RESEARCH

Personal Author(s) : Wu,A Y

PDF Url : ADA139847

Report Date : Dec 1983

Pagination or Media Count : 24

Abstract : In the study of parallel computing, networks of processors are often organized into various configurations such as trees, pyramids, and mesh arrays. These configurations can be represented as graphs. Using the properties and structures of the underlying graph effectively, the computation and communication speeds can often be improved. The hypercube is a good host graph for the embedding of networks of processors because of its low degree and low diameter. Graphs such as trees and arrays can be embedded into a hypercube with small dilation and expansion costs, but there are classes of graphs which can be embedded into a hypercube only with large expansion cost or large dilation cost.

Descriptors :   *GRAPHS, *EMBEDDING, *PARALLEL PROCESSORS, *NETWORKS, CONFIGURATIONS, BINARY ARITHMETIC, COMPUTATIONS, HAMILTONIAN FUNCTIONS, TREES, NODES

Subject Categories : Theoretical Mathematics
      Computer Hardware
      Computer Systems

Distribution Statement : APPROVED FOR PUBLIC RELEASE