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