Embedding of Networks of Processors into Hypercubes.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1983
- Accession Number
- ADA139847
Entities
People
- A. Y. Wu
Organizations
- University of Maryland