Efficient embeddings and simulations for hypercubic networks
Eric J. Schwabe, Frank Thomson Leighton · 1991
Part I of this thesis studies the relative computational strengths of the shuffle-exchange graph and the butterfly network, the most common representatives of the two main classes of hypercube-derived networks, demonstrating new structural similarities and establishing the computational equivalence of the two networks. The butterfly network can simulate a certain class of structured hypercube algorithms as efficiently as the shuffle-exchange graph can. We show that each network is able to efficiently simulate an arbitrary computation on the other. In terms of what a network with a given number of nodes can compute in a given number of steps, all of these networks are equivalent up to constant factors. The simulation does not involve a direct embedding of either network into the other; it does not lead to the immediate translation of results that deal with the combinatorial structures of the two networks rather than with algorithmic issues. However, many structural results for one of the networks do in fact have analogues for the other. We give an improved lower bound on dilation for embeddings of the X-tree network into the shuffle-exchange graph, bringing it nearer to the optimal result known for the butterfly network. We consider recent results in the VLSI packaging of deBruijn graph networks, and show that a recently developed packaging scheme can be made to yield the same optimal behavior in terms of the number of off-chip connections needed that is easily achievable for the butterfly network. In Part II, we study the problems of dynamic tree embedding and dynamic allocation of distributed memory resources. For either the butterfly network or the hypercube, we give algorithms that achieve small constant dilation and maximum load O(M/N + log N) with high probability. We also give an improved algorithm for the hypercube that achieves constant dilation and maximum load O(M/N + 1) with high probability. Finally, we prove a lower bound of $\Omega$($\sqrt{\log N}$) on dilation for deterministic embedding algorithms. We consider the problem of dynamic allocation of distributed memory resources. We give a fully on-line algorithm for this distributed dynamic allocation problem that guarantees 100% usage of the available space while achieving slowdown O(M/N + 1). (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.) (Abstract shortened with permission of school.)