Optimal Simulations by Butterfly Networks
- 1 March 1988
- report
- Published by Defense Technical Information Center (DTIC)
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.Keywords
This publication has 0 references indexed in Scilit: