Accession Number : ADA195168


Title :   Optimal Simulations by Butterfly Networks: Extended Abstract,


Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE


Personal Author(s) : Bhatt, Sandeep N ; Chung, Fan R ; Hong, Jia-Wei ; Leighton, F T ; Rosenberg, Arnold


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a195168.pdf


Report Date : Nov 1987


Pagination or Media Count : 13


Abstract : We investigate the power of the Butterfly network (which is the FFT network with inputs and outputs identified) relative to other proposed multicomputer interconnection networks, by considering how efficiently the Butterfly can simulate the other networks: Formally we ask, How efficiently can one embed the graph underlying the other network in the graph underlying the Butterfly? We measure the efficiency of an embedding of a graph G in a graph H 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 of vertices of G. We present three simulations that are optimal, to within constant factors: (1) Any complete binary tree can be embedded in a Butterfly graph, with simultaneous dilation O(1) and expansion O(1). (2) The n-vertex X-tree can be embedded in a Butterfly graph with simultaneous dilation O(log log n) and expansion O(1); no embedding has better dilation, independent of expansion. (3) Any embedding of the n x n mesh in the Butterfly graph must have dilation (log n), independent of expansion; any embedding of the mesh in the Butterfly graph achieves this dilation. Thus, we have simulations of complete-binary-tree machines, X-tree machines, and mesh computers on Butterfly machines, that are optimal in resource utilization (expansion) and delay (dilation), to within constant factors.


Descriptors :   *CIRCUIT INTERCONNECTIONS , *COMPUTERS , *EMBEDDING , *GRAPHS , *MESH , *NETWORKS , ABSTRACTS , EXPANSION , OPTIMIZATION , RATIOS , RESOURCES , SIMULATION , UTILIZATION


Subject Categories : Command, Control and Communications Systems


Distribution Statement : APPROVED FOR PUBLIC RELEASE