Abstract
The 3-ary n-cube, denoted as \( {Q}_n^3 \), is an important interconnection network topology proposed for parallel computers, owing to its many desirable properties such as regular and symmetrical structure, and strong scalability, among others. In this paper, we first obtain an exact formula for the minimum wirelength to embed \( {Q}_n^3 \) into grids. We then propose a load balancing algorithm for embedding \( {Q}_n^3 \) into a square grid with minimum dilation and congestion. Finally, we derive an O(N2) algorithm for embedding \( {Q}_n^3 \) into a gird with balanced communication, where N is the number of nodes in \( {Q}_n^3 \). Simulation experiments are performed to verify the total wirelength and evaluate the network cost of our proposed embedding algorithm.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Hsu L H, Lin C K. Graph Theory and Interconnection Networks (1st edition). CRC, 2008.
Gu M M, Hao R X. 3-extra connectivity of 3-ary n-cube networks. Information Processing Letters, 2014, 114(9): 486-491.
Yang Y, Wang S. A note on Hamiltonian paths and cycles with prescribed edges in the 3-ary n-cube. Information Sciences, 2015, 296(c): 42-45.
Hsieh S Y, Lin T J, Huang H L. Panconnectivity and edge-pancyclicity of 3-ary N-cubes. The Journal of Supercomputing, 2007, 42(2): 225-233.
Dong Q, Yang X, Wang D. Embedding paths and cycles in 3-ary n-cubes with faulty nodes and links. Information Sciences, 2010, 180(1): 198-208.
Lv Y, Lin C K, Fan J, Jia X. Hamiltonian cycle and path embeddings in 3-ary n-cubes based on K 1,3-structure faults. Journal of Parallel and Distributed Computing. 2018, 120: 148-158.
Yuan J, Liu A, Qin X, Zhang J, Li J. g-Good-neighbor conditional diagnosability measures for 3-ary n-cube networks. Theoretical Computer Science, 2016, 626: 144-162.
Bauer D W, Carothers C D. Scalable RF propagation modeling on the IBM Blue Gene/L and Cray XT5 supercomputers. In Proc. the 2009 Winter Simulation Conference, December 2009, pp.779-787.
Abu-Libdeh H, Costa P, Rowstron A, O’Shea G, Donnelly A. Symbiotic routing in future data centers. ACM SIGCOMM Computer Communication Review, 2010, 40(4): 51-62.
Wang T, Su Z Y, Xia Y, Qin B, Hamdi M. NovaCube: A low latency Torus-based network architecture for data centers. In Proc. the 2004 IEEE Global Communications Conference, December 2014, pp.2252-2257.
Bezrukov S L, Chavez J D, Harper L H, Röttger M, Schroeder U P. Embedding of hypercubes into grids. In Proc. the 23rd Int. Symposium on Mathematical Foundations of Computer Science, August 1998, pp.693-701.
Cheng B, Fan J, Jia X, Jia J. Parallel construction of independent spanning trees and an application in diagnosis on Möbius cubes. The Journal of Supercomputing, 2013, 65(3): 1279-1301.
Wang X, Fan J, Jia X, Zhang S, Yu J. Embedding meshes into twisted-cubes. Information Sciences, 2011, 181(14): 3085-3099.
Wang D. Hamiltonian embedding in crossed cubes with failed links. IEEE Trans. Parallel and Distributed Systems, 2012, 23(11): 2117-2124.
Wang S, Li J, Wang R. Hamiltonian paths and cycles with prescribed edges in the 3-ary n-cube. Information Sciences, 2011, 181(14): 3054-3065.
Fan J, Jia X, Lin X. Complete path embeddings in crossed cubes. Information Sciences, 2006, 176(22): 3332-3346.
Fan J, Jia X, Lin X. Embedding of cycles in twisted cubes with edge-pancyclic. Algorithmica, 2008, 51(3): 264-282.
Han Y, Fan J, Zhang S et al. Embedding meshes into locally twisted cubes. Information Sciences, 2010, 180(19): 3794-3805.
Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness (1st edition). W. H. Freeman, 1979.
Nakano K. Linear layout of generalized hypercubes. International Journal of Foundations of Computer Science, 2003, 14(1): 137-156.
Fan W, Fan J, Lin C K, Wang G J, Cheng B, Wang R. An efficient algorithm for embedding exchanged hypercubes into grids. The Journal of Supercomputing. doi:org/10.1007/s11227-018-2612-2. (to be appeared)
Miller M, Rajan R S, Parthiban N, Rajasingh I. Minimum linear arrangement of incomplete hypercubes. The Computer Journal, 2015, 58(2): 331-337.
Chen Y, Shen H. Routing and wavelength assignment for hypercube in array-based WDM optical networks. Journal of Parallel and Distributed Computing, 2010, 70(1): 59-68.
Yu C, Yang X, Yang L X, Zhang J. Routing and wavelength assignment for 3-ary n-cube in array-based optical network. Information Processing Letters, 2012, 112(6): 252-256.
Liu Y L. Routing and wavelength assignment for exchanged hypercubes in linear array optical networks. Information Processing Letters, 2015, 115(2): 203-208.
Wang Z, Gu H, Yang Y, Zhang H, Chen Y. An adaptive partition-based multicast routing scheme for mesh-based networks-on-chip. Computers and Electrical Engineering, 2016, 51: 235-251
Xiang D, Chakrabarty K, Fujiwara H. Multicast-based testing and thermal-aware test scheduling for 3D ICs with a stacked network-on-chip. IEEE Trans. Computers, 2016, 65(9): 2767-2779.
Xiang D, Liu X. Deadlock-free broadcast routing in dragonfly networks without virtual channels. IEEE Trans. Parallel and Distributed Systems, 2016, 27(9): 2520-2532.
Xiang D, Zhang Y, Pan Y. Practical deadlock-free fault-tolerant routing in meshes based on the planar network fault model. IEEE Trans. Computers, 2009, 58(5): 620-633.
Xiang D, Luo W. An efficient adaptive deadlock-free routing algorithm for torus networks. IEEE Trans. Parallel and Distributed Systems, 2012, 23(5): 800-808.
Lan H, Liu L, Yu X, Gu H, Gao Y. A novel multi-controller flow schedule scheme for fat-tree architecture. In Proc. the 15th International Conf. Optical Communications and Networks, Sept. 2016, Article No. 113.
Bezrukov S L, Chavez J D, Harper L H, Röttger M, Schroeder U P. The congestion of n-cube layout on a rectangular grid. Discrete Mathematics, 2000, 213(1/2/3): 13-19.
Heckmann R, Klasing R, Monien B, Unger W. Optimal embedding of complete binary trees into lines and grids. Journal of Parallel and Distributed Computing, 1991, 18(49): 40-56.
Manuela P, Rajasinghb I, Rajanb B, Mercy H. Exact wirelength of hypercubes on a grid. Discrete Applied Mathematics, 2009, 157(7): 1486-1495.
Wei W, Gu H, Wang K, Yu X, Liu X. Improving cloud-based IoT services through virtual network embedding in elastic optical inter-DC networks. IEEE Internet of Things Journal. doi:https://doi.org/10.1109/JIOT.2018.2866504.
Chen C, Agrawal D P. dBCube: A new class of hierarchical multiprocessor interconnection networks with area efficient layout. IEEE Trans. Parallel and Distributed Systems, 1993, 4(12): 1332-1344.
Bezrukov S L, Das S K, Elsässer R. An edge-isoperimetric problem for powers of the Petersen graph. Annals of Combinatorics, 2000, 4(2): 153-169.
Yu C, Yang X, He L, Zhang J. Optimal wavelength assignment in the implementation of parallel algorithms with ternary n-cube communication pattern on mesh optical network. Theoretical Computer Science, 2014, 524: 68-77.
Rajan R S, Manuel P, Rajasingh I, Parthiban N, Miller M. A lower bound for dilation of an embedding. The Computer Journal, 2015, 58(12): 3271-3278.
Massie M L, Chun B N, Culler D E. The ganglia distributed monitoring system: Design, implementation, and experience. Parallel Computing, 2004, 30(7): 817-840.
Acknowledgment
We would like to express our sincerest appreciation to Prof. Guo-Liang Chen of University of Science and Technology of China for his constructive suggestions.
Author information
Authors and Affiliations
Corresponding author
Electronic supplementary material
ESM 1
(PDF 299 kb)
Rights and permissions
About this article
Cite this article
Fan, WB., Fan, JX., Lin, CK. et al. Optimally Embedding 3-Ary n-Cubes into Grids. J. Comput. Sci. Technol. 34, 372–387 (2019). https://doi.org/10.1007/s11390-019-1893-0
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11390-019-1893-0