Optimal Simulations by Butterfly Networks
Abstract
The power of Butterfly-type networks relative to other proposed multicomputer interconnection networks is studied, by considering how efficiently the Butterfly can simulate the other networks. Simulation is represented formally via graph embeddings, so the topic here becomes: How efficiently can one embed the graph underlying a given network in the graph underlying the Butterfly network? The efficiency of an embedding of a graph G in a graph H is measured in terms of: the dilation, or, the maximum amount that any edge of G is stretched by the embedding; the expansion, or, the ratio of the number of vertices of H to the number vertices of G. These results, which extend to Butterfly-like graphs such as the Cube-Connected Cycles and Benes networks, supply the first examples of graphs that can be embedded more efficiently in the Hypercube than in the Butterfly. Keywords: Computer networks; Computer systems; Butterfly networks.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1988
- Accession Number
- ADA200780
Entities
People
- Arnold L. Rosenberg
- F. T. Leighton
- Fan R. Chung
- Jia-wei Hong
- Sandeep N. Bhatt
Organizations
- Massachusetts Institute of Technology