Journal of Computer Science and Technology ›› 2019, Vol. 34 ›› Issue (2): 372-387.doi: 10.1007/s11390-019-1893-0

Special Issue: Surveys; Data Management and Data Mining; Computer Networks and Distributed Computing

• Computer Networks and Distributed Computing • Previous Articles     Next Articles

Optimally Embedding 3-Ary n-Cubes into Grids

Wei-Bei Fan1,2, Member, CCF, Jian-Xi Fan1,2,*, Member, CCF, Cheng-Kuan Lin3, Member, CCF, Yan Wang1, Yue-Juan Han1, Ru-Chuan Wang2   

  1. 1 School of Computer Science and Technology, Soochow University, Suzhou 215006, China;
    2 Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks, Nanjing 210003, China;
    3 College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China
  • Received:2018-08-08 Revised:2018-11-13 Online:2019-03-05 Published:2019-03-16
  • Contact: Jian-Xi Fan E-mail:jxfan@suda.edu.cn
  • About author:Wei-Bei Fan received his B.S. degree in computer science from Henan University of Urban Construction, Pingdingshan, in 2011, and received his M.S. degree in Henan University, Kaifeng, in 2014. He is currently a Ph.D. candidate in computer science at Soochow University, Suzhou. His research interests include parallel and distributed systems, algorithms, and interconnection architectures.
  • Supported by:
    This work is supported by the National Key Research and Development Program of China under Grant No. 2018YFB1003201, the National Natural Science Foundation of China under Grant Nos. 61572337, 61602261, 61672296, and 61872257, Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks Foundation under Grant No. WSNLBKF201701, the Scientific & Technological Support Project of Jiangsu Province of China under Grant Nos. BE2016777, BE2016185, and BE2017166, China Postdoctoral Science Foundation under Grant No. 172985, the Natural Science Foundation of the Jiangsu Higher Education Institutions of China under Grant No. 17KJB520036, and Jiangsu Planned Projects for Postdoctoral Research Funds under Grant No. 1701172B.

PDF

720

Supplement

1

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.

Key words: 3-ary n-cube; embedding algorithm; grid; interconnection network;

[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 edgepancyclicity 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 faulttolerant 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 cloudbased 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.
[1] Xi Wang, Jian-Xi Fan, Cheng-Kuan Lin, Jing-Ya Zhou, Zhao Liu. BCDC: A High-Performance, Server-Centric Data Center Network [J]. , 2018, 33(2): 400-416.
[2] Dong-Fang Zhou, Jian-Xi Fan, Cheng-Kuan Lin, Bao-Lei Cheng, Jing-Ya Zhou, Zhao Liu. Optimal Path Embedding in the Exchanged Crossed Cube [J]. , 2017, 32(3): 618-629.
[3] Wen-Tao Bao, Bin-Zhang Fu, Ming-Yu Chen, Li-Xin Zhang. A High-Performance and Cost-Effcient Interconnection Network for High-Density Servers [J]. , 2014, 29(2): 281-292.
[4] Amineh Amini, Teh Ying Wah, and Hadi Saboohi. On Density-Based Data Streams Clustering Algorithms：A Survey [J]. , 2014, 29(1): 116-141.
[5] Jie Yan, Guang-Ming Tan, and Ning-Hui Sun. Optimizing Parallel Sn Sweeps on Unstructured Grids for Multi-Core Clusters [J]. , 2013, 28(4): 657-670.
[6] Jun-Wei Cao, (曹军威), Member, CCF, ACM, Senior Member, IEEE, Fan Zhang (张帆), Student Member, IEEE, Ke Xu (许可), Lian-Chen Liu (刘连臣) and Cheng Wu (吴澄). Formal Verification of Temporal Properties for Reduced Overhead in Grid Scientific Workflows [J]. , 2011, 26(6): 1017-1030.
[7] Sarbani Roy and Nandini Mukherjee, Member, IEEE. Adaptive Execution of Jobs in Computational Grid Environment [J]. , 2009, 24(5): 925-938.
[8] Huanyu Zhao, Student Member, IEEE, and Xiaolin Li, Member, ACM, IEEE. H-Trust: A Group Trust Management System for Peer-to-Peer Desktop Grid [J]. , 2009, 24(5): 833-843.
[9] Tiziana Calamoneri, Saverio Caminiti, and Rossella Petreschi. A General Approach to {\it\bfseries L$($h,k$)$}-Label Interconnection Networks [J]. , 2008, 23(4 ): 652-659 .
[10] Zhen-Hua Huang, Jian-Kui Guo, Sheng-Li Sun, and Wei Wang. Efficient Optimization of Multiple Subspace Skyline Queries [J]. , 2008, 23(1): 103-111 .
[11] Qiang Zhou, Yi-Ci Cai, Duo Li, and Xian-Long Hong. A Yield-Driven Gridless Router [J]. , 2007, 22(5): 653-660 .
[12] Youcef Derbal. A model of grid service capacity [J]. , 2007, 22(4): 505-514 .
[13] Zhi-Wei Xu, Hao-Jie Zhou, and Guo-Jie Li. Usability Issues of Grid System Software [J]. , 2006, 21(5): 641-647 .
[14] Dan Feng and Hai Jin. Massive Storage Systems [J]. , 2006, 21(5): 648-664 .
[15] Satoshi Matsuoka, Masayuki Hatanaka, Yasumasa Nakano, Yuji Iguchi, Toshio Ohno, Kazushige Saga, and Hidemoto Nakada. Design and Implementation of NAREGI SuperScheduler Based on the OGSA Architecture [J]. , 2006, 21(4): 521-528 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhang Bo; Zhang Ling;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[10] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

 Home
Editorial Board
Author Guidelines
Subscription		 Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved