Abstract
Various permutation interconnection networks have recently been suggested as an alternative to the hypercube. We investigate embeddings of these permutation networks on hypercubes. Our embeddings exhibit a marked trade-off between dilation and expansion and for the n-dimensional star network have the following dilation and expansion bounds:
-
1.
dilation 2 and expansion O(\(2^{n^2 }\) / n n),
-
2.
dilation O(log n) and expansion O((2e) n),
-
3.
dilation O(log n log log n) and expansion O(e n /n),
-
4.
dilation O(log 2 n) and expansion O((e/2) n/\(\sqrt n\)), and
-
5.
dilation n(log n − 2) and expansion n/2.
The embeddings are, in fact, optimum or nearly optimum in both dilation and expansion for small values of n, which are the important cases in practice. We also show that any star network with dimension at least 4 is not a subgraph of a hypercube and that any embedding with O(1) expansion must have dilation Ω(log n).
Partial support from the Louisiana Education and Quality Support Fund (LEQSF) is gratefully acknowledged.
Partial support from a Texas Advanced Research Project Grant is gratefully acknowledged.
This article was processed using the LATEX macro package with LMAMULT style
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
S. Akers, D. Harel, B. Krishnamurthy, ”The Star Graph: an Attractive Alternative to the n-cube”, Proc. of 1987 International Conference on Parallel Processing, pp. 393–400.
Michalek, R., Tarantello, G.: ”Subharmonic solutions with prescribed minimal period for nonautonomous Hamiltonian systems” J. Diff. Eg. 72 (1988) 28–55
S.G. Akl, K. Qiu, adn I. Stojmenovic, ”Data Communication and Comnputational Geometry on the Star and Pancake Interconnection Networks”, in Proceedings of The Third IEEE Symposium on Parallel and Distributed Processing, pp. 415–422, 1991.
S. Bettayeb, Z. Miller, and I. H. Sudborough, ”Embedding Grids into Hypercubes”, Proc. '88 A WOC: VLSI, Algorithms and Architectures Conf. (July, 1988), Spring Verlag's Lecture Notes in Computer Science, vol. 327. to appear in J. Computer and System Sci.
S. Bhatt, F. Chung, F. T. Leighton, and A. Rosenberg, ”Optimal Simulations of Tree Machines”, Proc. of 27th Annual IEEE Foundations of Computer Sci. Conf. (1986), pp. 274–282.
S. Bhatt, F. Chung, J-W. Hong, F. T. Leighton, and A. Rosenberg, ”Optimal Simulations by Butterfly Networks”, Proc. of 23rd Annual ACM Theory of Computer Sci. Conf. (1988), pp. 192–204.
B. Cong, Z. Miller, I. H. Sudborough, ”Optimum Simulation of Meshes by Small Hypercubes”, Proc. of 6th International MYCS (Nov., 1990), Smolenice, Czechoslovakia, Springer-Verlag Lecture Notes in Computer Science, Vol 464, pp. 30–46.
M. Dietzfelbinger, S. Madhavapeddy, and I.H. Sudborough ”Three Disjoint Path Paradigms in Star Networks”, in Proceedings of The Third IEEE Symposium on Parallel and Distributed Processing, pp. 400–406, 1991.
J. Jwo, S. Lakshmivarahan, S. Dhall, ”Embedding of Cycles and Grids in Star Graphs”, Proc. of the 2nd IEEE Parallel and Distributed Proc. Symp. (Dec., 1990), Dallas, TX.
S. MacLane and G. Birkhoff, Algebra, Macmillan, 1967, pp. 91–97.
Z. Miller, D. Pritikin, I. H. Sudborough, ”Small Dilation Embeddings of Hypercubes into Star Networks”, manuscript, University of Texas at Dallas, Richardson, TX 75083.
B. Monien and I. H. Sudborough, ”Simulating Binary Trees on Hypercubes”, Proc. '88 AWOC VLSI Algorithms and Architectures Conf. (July, 1988), in Springer Verlag's Lecture Notes in Computer Science, vol. 319, pp. 170–180.
M. Nigam, S. Sahni, B. Krishnamurthy, ”Embedding Hamiltonians and Hypercubes in Star Interconnection Graphs”, Proc. of International Conference on Parallel Processing 1990.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bettayeb, S., Cong, B., Girou, M., Sudborough, I.H. (1992). Simulating permutation networks on hypercubes. In: Simon, I. (eds) LATIN '92. LATIN 1992. Lecture Notes in Computer Science, vol 583. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0023817
Download citation
DOI: https://doi.org/10.1007/BFb0023817
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55284-0
Online ISBN: 978-3-540-47012-0
eBook Packages: Springer Book Archive