Computer Science

Computer Science ›› 2022, Vol. 49 ›› Issue (11): 284-292.doi: 10.11896/jsjkx.211000037

• Computer Network • Previous Articles     Next Articles

Construction Algorithm of Completely Independent Spanning Tree in Dragonfly Network

BIAN Qing-rong1,2, CHENG Bao-lei1,2, FAN Jian-xi1, PAN Zhi-yong1,2   

  1. 1 School of Computer Science and Technology,Soochow University,Suzhou,Jiangsu 215006,China
    2 Jiangsu Provincial Key Laboratory for Computer Information Processing Technology,Soochow University,Suzhou,Jiangsu 215006,China
  • Received:2021-10-08 Revised:2022-03-19 Online:2022-11-15 Published:2022-11-03
  • About author:BIAN Qing-rong,born in 1993,postgraduate.His main research interests include parallel and distributed systems,and graph algorithms.
    CHENG Bao-lei,born in 1979,Ph.D,associate professor,Ph.D supervisor.His main research interests include parallel and distributed systems,computer networks and graph algorithms.
  • Supported by:
    National Natural Science Foundation of China(62172291,U1905211),Priority Academic Program Development of Jiangsu Higher Education Institutions and Jiangsu Province Department of Education Future Network Research Fund Project(FNSRFP-2021-YB-39).

PDF (PC)

383

Abstract: Dragonfly network,proposed by Kim et al.,is a topology for high-performance computer systems.In dragonfly network,compute nodes are attached to switches,the switches are organized into groups,and the network is organized as a two-level clique.There is a link between any two nodes in a group,and there is a global link between different groups.Completely independent spanning trees(CISTs) play important roles in reliable information transmission,parallel transmission and safe distribution of information.In practical application,with the continuous increase of network scale,the requirements for information transmission efficiency and security are becoming higher and higher.Therefore,it is meaningful to study the construction of completely independent spanning trees in dragonfly network.At present,there are many results on completely independent spanning trees in networks,but completely independent spanning trees in dragonfly network have not been studied.In this paper,construction algorithm for the global link of dragonfly network is proposed,which is divided into completely independent spanning tree under re-lative link,absolute link and circulant link.Based on this division,a construction algorithm for the edge set of completely independent spanning tree is given,and the correctness of the above algorithms is proved.Finally,the time complexity of these algorithms is analyzed.

Key words: Dragonfly network, Topology, Completely independent spanning tree, Algorithm

CLC Number: 

  • TP393.0
[1]JACK D.The international exascale software project roadmap[J].The International Journal of High Performance Computing Applications,2011,25(1):3-60.
[2]DENNIS A,MICHAEL R M,PHILIP M,et al.Energy proportional datacenter networks[J].ACM SIGARCH Computer Architecture News,2010,38(3):338-347.
[3]BESTA M,HO T.Slim Fly:A cost effective low-diameter network topology[J].Networking,Storage and Analysis,2014,4(4):348-359.
[4]WILDE T,AUWETER A,SHOUKOURIAN H.The 4 pillar framework for energy efficient HPC data centers[J].Computer Science－Research and Development,2014,29(3/4):241-251.
[5]CURTSINGER R,BUNDE D.Shortest paths in dragonfly systems[C]//International Workshop of High-Perfomance Interconnection Networks in the Exascale and Big-Data Era.IEEE,2019:1-8.
[6]GAHVARI H,GROPP W,JORDAN K E,et al.Algebraic multigrid on a dragonfly network:first experiences on a Cray XC30[C]//IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing.IEEE,2015:3-21.
[7]FAANES G,BATAINEH A,ROWETH D,et al.Cray Cascade:A scalable HPC system based on a dragonfly network[C]//2012 International Conference for High Performance Computing,Networking,Storage and Analysis.IEEE,2012:1-9.
[8]ARIMILLI L B,ARIMILLI R,CHUNG V,et al.The PERCS high-performance interconnect[C]//18th IEEE Annual Symposium on High Performance Interconnects.IEEE,2010:75-82.
[9]WANG X,FAN J X,LIN C K,et al.BCDC:A high-perfor-mance,server-centric data center network[J].Journal of Compu-ter Science and Technology,2018,33(2):400-416.
[10]FUENTES P,VALLEJO E,CAMARERO C,et al.Throughput unfairness in dragonfly networks under realistic traffic patterns[C]//1st IEEE International Workshop on High-Performance Interconnection Networks Towards the Exascale and Big-Data Era(HiPINEB).IEEE,2015:801-808.
[11]YEBENES P,ESCUDERO-SAHUQUILLO J,GARCIA P J,et al.Straightforward solutions to reduce HoL blocking in different Dragonfly fully-connected interconnection patterns[J].Journal of Supercomputing,2016,72(12):1-23.
[12]YEBENES P,GARCIA P J,QUILES F J,et al.Straightforward modeling of fully-connected dragonfly topologies in HPC-system simulators[C]//2015 International Conference on High Performance Computing & Simulation (HPCS).IEEE,2015:172-178.
[13]CHAKARAVARTHY V T,KATTA N,KEDIA M,et al.Mapping Strategies for the PERCS Architecture[C]//2012 19th International Conference on High Performance Computing.IEEE,2012:1-10.
[14]PRISACARI B,RODRIGUEZ G,HEIDELBERGERP,et al.Efficient task placement and routing of nearest neighbor exchanges in dragonfly networks[C]//High-performance Parallel and Distributed Computing.2014.
[15]HASUNUMA T.Completely independent spanning trees inmaximal planar graphs[C]//Revised Papers from the International Workshop on Graph-theoretic Concepts in Computer Science.Cham:Springer,2002:235-245.
[16]QIAN Y,CHENG B L,FAN J X,et al.A general construction method of vertex independent spanning tree in a kind of data center network[J].Computer Application Research,2021,38(7):2130-2134.
[17]PAI K J,CHANG J M.Constructing two completely indepen-dent spanning trees in hypercube-variant networks[J].Theo-retical Computer Science,2016,652(1):28-37.
[18]YANG M C.Constructing edge-disjointspanning trees in twisted cubes[J].Information Sciences,2010,180(20):4075-4083.
[19]CHENG B L,WANG D J,FAN J X.Constructing completelyindependent spanning trees in crossed cubes[J].Discrete Applied Mathematics,2017,219:100-109.
[20]LINC K,ZHAO Y,FAN J X,et al.Research on completely independent spanning tree based on vertex degree[J].Computer Science,2017(6):93-96.
[21]MAN L J.Some sufficient conditions for the existence of two completely independent spanning trees[D].Urumqi:Xinjiang University,2016.
[22]QIN X W,HAO R X,PAI K J,et al.Comments on A Hamilton sufficient condition for completely independent spanning tree[J].Discrete Applied Mathematics,2020,283(3):33-38.
[23]PETERFALVI.Two counterexamples on completely indepen-dent spanning trees[J].DISCRETE MATH,2012,312(4):808-810.
[24]HASTINGS E,RINCON-CRUZ D,SPEHLMANN M,et al.Comparing global link arrangements for dragonfly networks[C]//IEEE International Conference on Cluster Computing.IEEE,2015:361-370.
[25]BELKA M,DOUBET M,MEYERS S,et al.New link arrangements for dragonfly networks[C]//2017 IEEE 3rd International Workshop on High-Performance Interconnection Networks in the Exascale and Big-Data Era (HiPINEB).IEEE,2017:325-334.
[26]ARAKI T.Dirac’s condition for completely independent spanning trees[J].Journal of Graph Theory,2014,77(3):171-177.
[27]KIM J,DALLY W,SCOTT S,et al.Technology-Driven,Highly-Scalable Dragonfly Topology[J].Acm Sigarch Computer Architecture News,2008,36(3):77-88.
[1] CHAI Hui-min, ZHANG Yong, FANG Min. Aerial Target Grouping Method Based on Feature Similarity Clustering [J]. Computer Science, 2022, 49(9): 70-75.
[2] LIU Xin, WANG Jun, SONG Qiao-feng, LIU Jia-hao. Collaborative Multicast Proactive Caching Scheme Based on AAE [J]. Computer Science, 2022, 49(9): 260-267.
[3] NING Han-yang, MA Miao, YANG Bo, LIU Shi-chang. Research Progress and Analysis on Intelligent Cryptology [J]. Computer Science, 2022, 49(9): 288-296.
[4] JIANG Yang-yang, SONG Li-hua, XING Chang-you, ZHANG Guo-min, ZENG Qing-wei. Belief Driven Attack and Defense Policy Optimization Mechanism in Honeypot Game [J]. Computer Science, 2022, 49(9): 333-339.
[5] CHEN Jun, HE Qing, LI Shou-yu. Archimedes Optimization Algorithm Based on Adaptive Feedback Adjustment Factor [J]. Computer Science, 2022, 49(8): 237-246.
[6] LIU Wei-ming, AN Ran, MAO Yi-min. Parallel Support Vector Machine Algorithm Based on Clustering and WOA [J]. Computer Science, 2022, 49(7): 64-72.
[7] TANG Feng, FENG Xiang, YU Hui-qun. Multi-task Cooperative Optimization Algorithm Based on Adaptive Knowledge Transfer andResource Allocation [J]. Computer Science, 2022, 49(7): 254-262.
[8] ZHANG Chong-yu, CHEN Yan-ming, LI Wei. Task Offloading Online Algorithm for Data Stream Edge Computing [J]. Computer Science, 2022, 49(7): 263-270.
[9] CHANG Bing-guo, SHI Hua-long, CHANG Yu-xin. Multi Model Algorithm for Intelligent Diagnosis of Melanoma Based on Deep Learning [J]. Computer Science, 2022, 49(6A): 22-26.
[10] XU Si-yu, QIN Ke-yun. Topological Properties of Fuzzy Rough Sets Based on Residuated Lattices [J]. Computer Science, 2022, 49(6A): 140-143.
[11] HUANG Guo-xing, YANG Ze-ming, LU Wei-dang, PENG Hong, WANG Jing-wen. Solve Data Envelopment Analysis Problems with Particle Filter [J]. Computer Science, 2022, 49(6A): 159-164.
[12] YANG Hao-xiong, GAO Jing, SHAO En-lu. Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery [J]. Computer Science, 2022, 49(6A): 191-198.
[13] SHAN Xiao-ying, REN Ying-chun. Fishing Type Identification of Marine Fishing Vessels Based on Support Vector Machine Optimized by Improved Sparrow Search Algorithm [J]. Computer Science, 2022, 49(6A): 211-216.
[14] LI Dan-dan, WU Yu-xiang, ZHU Cong-cong, LI Zhong-kang. Improved Sparrow Search Algorithm Based on A Variety of Improved Strategies [J]. Computer Science, 2022, 49(6A): 217-222.
[15] WANG Wen-qiang, JIA Xing-xing, LI Peng. Adaptive Ensemble Ordering Algorithm [J]. Computer Science, 2022, 49(6A): 242-246.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.