OPTIMAL EMULATIONS BY BUTTERFLY-LIKE NETWORKS

The power of butterfly-like networks as multicomputer interconnection networks is studied, by considering how efficiently the butterfly can emulate other networks. Emulations are studied formally via graph embe ddings, so the topic here becomes: How efficiently can one embed the g raph underlying a given interconnection network in the graph underlyin g the butterfly network? Within this framework, the slowdown incurred by an emulation is measured by the sum of the dilation and the congest ion of the corresponding embedding (respectively, the maximum amount t hat the embedding stretches an edge of the guest graph, and the maximu m traffic across any edge of the host graph); the efficiency of resour ce utilization in an emulation is measured by the expansion of the cor responding embedding (the ratio of the sizes of the host to guest grap h). Three main results expose a number of optimal emulations by butter fly networks. Call a family of graphs balanced if complete binary tree s can be embedded in the family with simultaneous dilation, congestion , and expansion O(1). (1) The family of butterfly graphs is balanced. (2) (a) Any graph G from a family of maxdegree-d graphs having a recur sive separator of size S(x) can be embedded in any balanced graph fami ly with simultaneous dilation O(log(d Sigma(i) S(2(-i)\G\))) and expan sion O(1). (b) Any dilation-D embedding of a maxdegree-d graph in a bu tterfly graph can be converted to an embedding having simultaneous dil ation O(D) and congestion O(dD). (3) Any embedding of a planar graph G in a butterfly graph must have dilation Omega(log Sigma(G)/Phi(G)), w here: Sigma(G) is the size of the smallest (1/3, 2/3)-node-separator o f G, and Phi(G) is the size of G's largest interior face. Applications of these results include: (1) The n-node X-tree network can be emulat ed by the butterfly network with slowdown O(log log n) and expansion O (1); no embedding has dilation smaller than Omega(log log n), independ ent of expansion. (2) Every embedding of the n x n mesh in the butterf ly graph has dilation Omega(log n); any expansion-O(1) embedding in th e butterfly graph achieves dilation O(log n). These applications provi de the first examples of networks that can be embedded more efficientl y in hypercubes than in butterflies. We also show that analogues of th ese results hold for networks that are structurally related to the but terfly network. The upper bounds hold for the hypercube and the de Bru ijn networks, possibly with altered constants. The lower bounds hold-a t least in weakened form-for the de Bruijn network.