AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Article Link
Collect
Submit Manuscript
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Regular Paper

Optimally Embedding 3-Ary n-Cubes into Grids

School of Computer Science and Technology, Soochow University, Suzhou 215006, China
Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks, Nanjing 210003, China
College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China
Show Author Information

Abstract

The 3-ary n-cube, denoted as Qn3, 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 Qn3 into grids. We then propose a load balancing algorithm for embedding Qn3 into a square grid with minimum dilation and congestion. Finally, we derive an O(N2) algorithm for embedding Qn3 into a gird with balanced communication, where N is the number of nodes in Qn3. Simulation experiments are performed to verify the total wirelength and evaluate the network cost of our proposed embedding algorithm.

Electronic Supplementary Material

Download File(s)
jcst-34-2-372-Highlights.pdf (299.4 KB)

References

[1]

Hsu L H, Lin C K. Graph Theory and Interconnection Networks (1st edition). CRC, 2008.

[2]

Gu M M, Hao R X. 3-extra connectivity of 3-ary n-cube networks. Information Processing Letters, 2014, 114(9): 486-491.

[3]

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.

[4]

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.

[5]

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.

[6]

Lv Y, Lin C K, Fan J, Jia X. Hamiltonian cycle and path embeddings in 3-ary n-cubes based on K1,3-structure faults. Journal of Parallel and Distributed Computing. 2018, 120: 148-158.

[7]

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.

[8]
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.
[9]

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.

[10]
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.
[11]
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.
[12]

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.

[13]

Wang X, Fan J, Jia X, Zhang S, Yu J. Embedding meshes into twisted-cubes. Information Sciences, 2011, 181(14): 3085-3099.

[14]

Wang D. Hamiltonian embedding in crossed cubes with failed links. IEEE Trans. Parallel and Distributed Systems, 2012, 23(11): 2117-2124.

[15]

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.

[16]

Fan J, Jia X, Lin X. Complete path embeddings in crossed cubes. Information Sciences, 2006, 176(22): 3332-3346.

[17]

Fan J, Jia X, Lin X. Embedding of cycles in twisted cubes with edge-pancyclic. Algorithmica, 2008, 51(3): 264-282.

[18]

Han Y, Fan J, Zhang S et al. Embedding meshes into locally twisted cubes. Information Sciences, 2010, 180(19): 3794-3805.

[19]

Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness (1st edition). W. H. Freeman, 1979.

[20]

Nakano K. Linear layout of generalized hypercubes. International Journal of Foundations of Computer Science, 2003, 14(1): 137-156.

[21]
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)
[22]

Miller M, Rajan R S, Parthiban N, Rajasingh I. Minimum linear arrangement of incomplete hypercubes. The Computer Journal, 2015, 58(2): 331-337.

[23]

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.

[24]

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.

[25]

Liu Y L. Routing and wavelength assignment for exchanged hypercubes in linear array optical networks. Information Processing Letters, 2015, 115(2): 203-208.

[26]

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

[27]

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.

[28]

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.

[29]

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.

[30]

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.

[31]
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.
[32]

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.

[33]

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.

[34]

Manuela P, Rajasinghb I, Rajanb B, Mercy H. Exact wirelength of hypercubes on a grid. Discrete Applied Mathematics, 2009, 157(7): 1486-1495.

[35]

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:10.1109/JIOT.2018.2866504.

[36]

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.

[37]

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.

[38]

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.

[39]

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.

[40]

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.

Journal of Computer Science and Technology
Pages 372-387
Cite this article:
Fan W-B, Fan J-X, Lin C-K, et al. Optimally Embedding 3-Ary n-Cubes into Grids. Journal of Computer Science and Technology, 2019, 34(2): 372-387. https://doi.org/10.1007/s11390-019-1893-0

397

Views

32

Crossref

N/A

Web of Science

33

Scopus

3

CSCD

Altmetrics

Received: 08 August 2018
Revised: 13 November 2018
Published: 22 March 2019
©2019 Springer Science + Business Media, LLC & Science Press, China
Return