Abstract
This paper studies network embeddings in the Hamming cubes, a recently designed interconnection topology for multicomputers. The Hamming cube networks are supergraphs of incomplete hypercubes such that the additional edges form an extra binomial spanning tree. The recursively constructible and unit incremental Hamming cubes have better properties than hypercubes, including half of logarithmic diameter and higher fault-tolerance. They also support simple routing and efficient broadcasting schemes. In this paper, we show that Hamiltonian paths and cycles of all lengths, complete binary trees and their several variants are subgraphs of Hamming cubes. Our embeddings have both dilation and expansion equal to one. Furthermore, taking advantage of the enhanced edges in the Hamming cubes, tree machines can be embedded with dilation of one and expansion of 7/6. Thus, Hamming cubes provide embeddings at a lower cost than (incomplete) hypercubes of the same size.
This research is supported by Texas Advanced Technology Program TATP-003594031.
Chapter PDF
Keywords
References
S. N. Bhatt and I. Ipsen. How to embed trees in hypercubes. Tech. rep. rr-443, Department of Computer Science, Yale University, New Heaven, CT, 1985.
H. L. Chen and N. F. Tzeng. An effective approach to the enhancement of incomplete hypercube computers. J. Parallel Distri. Comput., 14:163–174, 1992.
S. K. Das and A. Mao. On enhanced generalized incomplete hypercubes. Tech. Rep. CRPDC-94-3, Dept Comput Sci, Univ North Texas, Denton, Jan 1994.
S. K. Das and A. Mao. Embeddings of Cycles and Tree-Related Networks in the Hamming Cubes. Tech. Rep. CRPDC-95-2, Dept Comput Sci, Univ North Texas, Denton, Jan 1995.
S. K. Das and A. Mao. An interconnection network model and the Hamming cube networks. In Proceedings of the 8th International Parallel Processing Symposium, pages 18–22, Cancun, Mexico, Apr 1994.
S. K. Das and A. Mao. Broadcasting trees in Hamming cubes. Proc. Int. Conf. Parallel and Distri. Comput. Syst., pp 587–592, Las Vegas, Nevada, Oct 1994.
A. El-Amawy and S. Latifi. Properties and performance of folded hypercubes. IEEE Transactions on Parallel and Distributed Systems, 2(1):31–42, Jan 1991.
K. Efe. Embedding mesh of trees in the hypercube. Journal of Parallel and Distributed Computing, 11:222–230, 1991.
K. Efe. The crossed cube architecture for parallel computation. IEEE Transactions on Parallel and Distributed Systems, 3(5):513–524, Sep 1992.
A-H. Esfahanian, L. M. Ni, and B. E. Sagan. The twisted n-cube with application to multiprocessing. Tech. Rep., Michigan State Univ, Dec 1987.
J. R. Goodman and C. H. Sequin. Hypertree: A multiprocessor interconnection topology. IEEE Trans. on Comput., C-30(12):923–933, Dec 1981.
H. P. Katseff. Incomplete hypercubes. IEEE Transactions on Computers, 37(5):604–608, May 1988.
F. T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann Publishers, San Mateo, CA, 1992.
S. Oehring and S. K. Das. Embeddings of tree-related networks in incomplete hypercubes. J. Parallel and Distributed Computing, 26(1):36–47, Apr 1995.
Y. Saad and M. H. Schultz. Topological properties of hypercubes. IEEE Transactions on Computers, 37(7):867–872, 1988.
S. Sur and P. K. Srimani. Incrementally extensible hypercube (IEH) graphs. Proc. Int. Conf. Computers and Communication, pp. 1–7, Phoenix, Apr 1992.
A. Sen, A. Sengupta, and S. Bandyopadhyay. On some topological properties of Hypercubes, Incomplete Hypercube and Supercube. Proc. 7th Int. Parallel Processing Symposium, Newport Beach, California, Apr 1993.
N. F. Tzeng, H. L. Chen, and P. J. Chuang. Embeddings in incomplete hypercubes. Proc. Int. Conf. Parallel Processing, vol III, pp. 335–339, 1990.
J-Y Tien and W-P Yang. Hierarchical spanning trees and distributing on incomplete hypercubes. Parallel Computing, 17:1343–1360, 1991.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Das, S.K., Mao, A. (1995). Optimal embeddings in the Hamming cube networks. In: Haridi, S., Ali, K., Magnusson, P. (eds) EURO-PAR '95 Parallel Processing. Euro-Par 1995. Lecture Notes in Computer Science, vol 966. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0020466
Download citation
DOI: https://doi.org/10.1007/BFb0020466
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60247-7
Online ISBN: 978-3-540-44769-6
eBook Packages: Springer Book Archive