蜻蜓网络上完全独立生成树的构造算法

doi:10.11896/jsjkx.211000037

计算机科学 ›› 2022, Vol. 49 ›› Issue (11): 284-292.doi: 10.11896/jsjkx.211000037

蜻蜓网络上完全独立生成树的构造算法

卞庆荣^1,2, 程宝雷^1,2, 樊建席¹, 潘志勇^1,2

1 苏州大学计算机科学与技术学院江苏苏州 215006
2 苏州大学江苏省计算机信息处理技术重点实验室江苏苏州 215006

收稿日期:2021-10-08 修回日期:2022-03-19 出版日期:2022-11-15 发布日期:2022-11-03
通讯作者: 程宝雷(chengbaolei@suda.edu.cn)
作者简介:(20195227075@stu.suda.edu.cn)
基金资助:
国家自然科学基金(62172291,U1905211);江苏高校优势学科建设工程;江苏省教育厅未来网络科研基金(FNSRFP-2021-YB-39).

Construction Algorithm of Completely Independent Spanning Tree in Dragonfly Network

BIAN Qing-rong^1,2, CHENG Bao-lei^1,2, FAN Jian-xi¹, PAN Zhi-yong^1,2

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).

摘要/Abstract

摘要： 蜻蜓网络(Dragonfly network)是由Kim等提出的一种适用于高性能计算系统的拓扑结构。在蜻蜓网络中,网络被组织成两级架构,计算节点与交换机连接,交换机被分为成多个组。在每一组内部的每个交换机之间互相有一条边相连,任意两组之间有一条边相连接。完全独立生成树在信息的可靠传输、信息的并行传输和安全分发以及并行故障服务器诊断算法中具有非常重要的应用。在实际应用中,随着网络规模的不断增大,信息传输的效率以及安全性等要求越来越高。因此,研究网络的完全独立生成树具有重要意义。目前,有许多关于网络中完全独立生成树的研究,但是缺乏蜻蜓网络上的完全独立生成树的研究成果。文中提出了蜻蜓网络全局链路分别以相对链接、绝对链接以及循环链接下的完全独立生成树划分的构造算法,并在此划分的基础上给出了完全独立生成树边集合的构造算法,并对以上算法的正确性进行了证明。最后分析了算法的时间复杂度。

关键词: 蜻蜓网络, 拓扑, 完全独立生成树, 算法

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

中图分类号:

TP393.0

卞庆荣, 程宝雷, 樊建席, 潘志勇. 蜻蜓网络上完全独立生成树的构造算法[J]. 计算机科学, 2022, 49(11): 284-292. https://doi.org/10.11896/jsjkx.211000037

BIAN Qing-rong, CHENG Bao-lei, FAN Jian-xi, PAN Zhi-yong. Construction Algorithm of Completely Independent Spanning Tree in Dragonfly Network[J]. Computer Science, 2022, 49(11): 284-292. https://doi.org/10.11896/jsjkx.211000037

参考文献

[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.

相关文章 15

[1]	柴慧敏, 张勇, 方敏. 基于特征相似度聚类的空中目标分群方法 Aerial Target Grouping Method Based on Feature Similarity Clustering 计算机科学, 2022, 49(9): 70-75. https://doi.org/10.11896/jsjkx.210800203
[2]	刘鑫, 王珺, 宋巧凤, 刘家豪. 一种基于AAE的协同多播主动缓存方案 Collaborative Multicast Proactive Caching Scheme Based on AAE 计算机科学, 2022, 49(9): 260-267. https://doi.org/10.11896/jsjkx.210800019
[3]	宁晗阳, 马苗, 杨波, 刘士昌. 密码学智能化研究进展与分析 Research Progress and Analysis on Intelligent Cryptology 计算机科学, 2022, 49(9): 288-296. https://doi.org/10.11896/jsjkx.220300053
[4]	姜洋洋, 宋丽华, 邢长友, 张国敏, 曾庆伟. 蜜罐博弈中信念驱动的攻防策略优化机制 Belief Driven Attack and Defense Policy Optimization Mechanism in Honeypot Game 计算机科学, 2022, 49(9): 333-339. https://doi.org/10.11896/jsjkx.220400011
[5]	陈俊, 何庆, 李守玉. 基于自适应反馈调节因子的阿基米德优化算法 Archimedes Optimization Algorithm Based on Adaptive Feedback Adjustment Factor 计算机科学, 2022, 49(8): 237-246. https://doi.org/10.11896/jsjkx.210700150
[6]	刘卫明, 安冉, 毛伊敏. 基于聚类和WOA的并行支持向量机算法 Parallel Support Vector Machine Algorithm Based on Clustering and WOA 计算机科学, 2022, 49(7): 64-72. https://doi.org/10.11896/jsjkx.210500040
[7]	唐枫, 冯翔, 虞慧群. 基于自适应知识迁移与资源分配的多任务协同优化算法 Multi-task Cooperative Optimization Algorithm Based on Adaptive Knowledge Transfer andResource Allocation 计算机科学, 2022, 49(7): 254-262. https://doi.org/10.11896/jsjkx.210600184
[8]	张翀宇, 陈彦明, 李炜. 边缘计算中面向数据流的实时任务调度算法 Task Offloading Online Algorithm for Data Stream Edge Computing 计算机科学, 2022, 49(7): 263-270. https://doi.org/10.11896/jsjkx.210300195
[9]	常炳国, 石华龙, 常雨馨. 基于深度学习的黑色素瘤智能诊断多模型算法 Multi Model Algorithm for Intelligent Diagnosis of Melanoma Based on Deep Learning 计算机科学, 2022, 49(6A): 22-26. https://doi.org/10.11896/jsjkx.210500197
[10]	康雁, 王海宁, 陶柳, 杨海潇, 杨学昆, 王飞, 李浩. 混合改进的花授粉算法与灰狼算法用于特征选择 Hybrid Improved Flower Pollination Algorithm and Gray Wolf Algorithm for Feature Selection 计算机科学, 2022, 49(6A): 125-132. https://doi.org/10.11896/jsjkx.210600135
[11]	许思雨, 秦克云. 基于剩余格的模糊粗糙集的拓扑性质 Topological Properties of Fuzzy Rough Sets Based on Residuated Lattices 计算机科学, 2022, 49(6A): 140-143. https://doi.org/10.11896/jsjkx.210200123
[12]	黄国兴, 杨泽铭, 卢为党, 彭宏, 王静文. 利用粒子滤波方法求解数据包络分析问题 Solve Data Envelopment Analysis Problems with Particle Filter 计算机科学, 2022, 49(6A): 159-164. https://doi.org/10.11896/jsjkx.210600110
[13]	杨浩雄, 高晶, 邵恩露. 考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题 Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery 计算机科学, 2022, 49(6A): 191-198. https://doi.org/10.11896/jsjkx.210400005
[14]	单晓英, 任迎春. 基于改进麻雀搜索优化支持向量机的渔船捕捞方式识别 Fishing Type Identification of Marine Fishing Vessels Based on Support Vector Machine Optimized by Improved Sparrow Search Algorithm 计算机科学, 2022, 49(6A): 211-216. https://doi.org/10.11896/jsjkx.220300216
[15]	李丹丹, 吴宇翔, 朱聪聪, 李仲康. 基于多种改进策略的改进麻雀搜索算法 Improved Sparrow Search Algorithm Based on A Variety of Improved Strategies 计算机科学, 2022, 49(6A): 217-222. https://doi.org/10.11896/jsjkx.210700032

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

蜻蜓网络上完全独立生成树的构造算法

Construction Algorithm of Completely Independent Spanning Tree in Dragonfly Network

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0