超立方体网络上与距离相关的容错性研究
发布时间：2018-11-05 13:56
【摘要】：随着计算机科学和信息化网络技术的发展,高性能计算机在社会各个领域发挥着日益重要的作用。高性能计算机的性能在很大程度上取决于其系统内部处理器之间的连接方式(互连网络)。互连网络的拓扑结构及其性质的研究是并行计算领域的研究重点之一。互连网络一般可以用一个简单图G=(V(G),E(G))来表示,其中V(G)表示图G中的顶点集合,代表互连网络中的处理器,E(G)表示图G中的边集合,代表处理器之间的链路。随着互连网络规模的不断扩大,网络中处理器和链路的数目也逐渐增多,处理器或链路发生故障的概率也会随之增加。在网络发生故障的情况下网络中某些特性能否继续保持,这就是网络的容错性,它是衡量互连网络性能的一项关键指标。超立方体网络是多处理器系统中一种常用的互连网络,它具有很多优越的性质,例如直径较小、结构对称、递归构造、可扩展性强等。基于该网络,研究者们已经提出了许多性能优越的超立方体变型网络,例如交叉立方体、扭立方体、莫比乌斯立方体等。因此,超立方体网络已成为多处理器系统中最基础也最重要的网络模型之一。本文在结合理论分析的基础上,就超立方体网络的容错性提出了新的测量方法,并且在该方法的限制条件下,研究了超立方体网络上的条件连通度,容错单播路由算法以及容错哈密顿性质。主要研究内容如下:1.本文提出一种与距离相关的新的条件(边)连通度 (g,d,k)-条件(边)连通度。与其他条件连通度相比,(g,d,k)-条件(边)连通度的要求更符合实际情况,并且允许存在更多的故障顶点(边)。它为研究超立方体等网络的容错性提供了新的衡量指标。2.本文研究了超立方体网络上某些特定的(g,d,k)-条件(边)连通度,包括κ1,1,k(Qn),κ1,d,2(Qn),λ1,1,1(Qn)和λ1,d,2(Qn)。这些结果为后续研究超立方体网络上其他(g,d,k)-条件(边)连通度提供了参考,也为在超立方体变型网络等其他网络上研究(g,d,k)-条件(边)连通度提供了方法上的指导。3.本文在(1,1,1)-条件连通的情况下提出了一种基于局部信息的容错单播路由算法,该算法通过构建长度不超过3的跨越路径来选择用于路由的维度。本文分析了该算法的时间复杂度以及空间复杂度,并且和现有的几种单播路由算法从成功率,运行时间,路径长度等方面进行了比较。4.本文结合(g,d,k)-条件边连通的概念,提出了一种新的条件容错哈密顿性质:f-(g,d,k)条件边容错哈密顿。本文证明,当n≥4时,n维超立方体是(4n-13)-(3,0,0)条件边容错哈密顿的,并且这一结果是最优的。最后,对本文工作进行了总结,并对后续的研究工作进行了展望。
[Abstract]:With the development of computer science and information network technology, high performance computer plays an increasingly important role in all fields of society. The performance of high-performance computers depends to a large extent on the way in which processors are connected within their systems (interconnection networks). The study of the topology and properties of interconnection networks is one of the focuses in the field of parallel computing. Interconnection networks can generally be represented by a simple graph G = (V (G), E (G), where V (G) represents the set of vertices in graph G, and the processor, E (G) in the network represents the set of edges in graph G. Represents links between processors. With the expansion of interconnection network, the number of processors and links in the network is increasing, and the probability of processor or link failure will also increase. Whether some characteristics of the network can be maintained in the event of network failure is the fault tolerance of the network. It is a key index to measure the performance of the interconnection network. Hypercube network is a commonly used interconnection network in multiprocessor systems. It has many excellent properties, such as small diameter, symmetrical structure, recursive construction, strong expansibility and so on. Based on this network, researchers have proposed many superior hypercube networks, such as cross cubes, twisted cubes, Mobius cubes and so on. Therefore, hypercube network has become one of the most basic and important network models in multiprocessor systems. On the basis of theoretical analysis, a new measurement method for fault tolerance of hypercube network is proposed in this paper, and the conditional connectivity of hypercube network is studied under the limitation of this method. Fault-tolerant unicast routing algorithm and fault-tolerant Hamiltonian. The main contents are as follows: 1. In this paper, a new distance-dependent condition (edge) -condition (edge) connectivity is proposed. Compared with other conditional connectivity, the requirement of (GG) -conditional (edge) connectivity is more in line with the actual situation, and more fault vertices (edges) are allowed. It provides a new measure of fault tolerance for networks such as hypercubes. 2. 2. In this paper, we study some special (Gndnk) -condition (edge) connectivity of hypercube networks, including 魏 1 (Qn), k 1 (Qn), 1 (Qn) and 位 1 DX 2 (Qn). These results provide a reference for the further study of the connectivity of other (gdnk)-conditional (edge) networks on hypercube networks, and also for the study of other networks such as hypercube networks. K)-conditional (edge) connectivity provides methodological guidance. 3. In this paper, a fault-tolerant unicast routing algorithm based on local information is proposed in the case of (1 / 1 / 1)-conditional connectivity. The algorithm selects the dimension for routing by constructing spanning paths of less than 3 in length. In this paper, the time complexity and space complexity of the algorithm are analyzed, and compared with the existing unicast routing algorithms in terms of success rate, running time, path length and so on. 4. In this paper, a new conditional fault-tolerant Hamiltonian property, f- (gdnk) -conditional edge fault-tolerant Hamiltonian, is proposed. In this paper, we prove that when n 鈮，
本文编号：2312289
[Abstract]:With the development of computer science and information network technology, high performance computer plays an increasingly important role in all fields of society. The performance of high-performance computers depends to a large extent on the way in which processors are connected within their systems (interconnection networks). The study of the topology and properties of interconnection networks is one of the focuses in the field of parallel computing. Interconnection networks can generally be represented by a simple graph G = (V (G), E (G), where V (G) represents the set of vertices in graph G, and the processor, E (G) in the network represents the set of edges in graph G. Represents links between processors. With the expansion of interconnection network, the number of processors and links in the network is increasing, and the probability of processor or link failure will also increase. Whether some characteristics of the network can be maintained in the event of network failure is the fault tolerance of the network. It is a key index to measure the performance of the interconnection network. Hypercube network is a commonly used interconnection network in multiprocessor systems. It has many excellent properties, such as small diameter, symmetrical structure, recursive construction, strong expansibility and so on. Based on this network, researchers have proposed many superior hypercube networks, such as cross cubes, twisted cubes, Mobius cubes and so on. Therefore, hypercube network has become one of the most basic and important network models in multiprocessor systems. On the basis of theoretical analysis, a new measurement method for fault tolerance of hypercube network is proposed in this paper, and the conditional connectivity of hypercube network is studied under the limitation of this method. Fault-tolerant unicast routing algorithm and fault-tolerant Hamiltonian. The main contents are as follows: 1. In this paper, a new distance-dependent condition (edge) -condition (edge) connectivity is proposed. Compared with other conditional connectivity, the requirement of (GG) -conditional (edge) connectivity is more in line with the actual situation, and more fault vertices (edges) are allowed. It provides a new measure of fault tolerance for networks such as hypercubes. 2. 2. In this paper, we study some special (Gndnk) -condition (edge) connectivity of hypercube networks, including 魏 1 (Qn), k 1 (Qn), 1 (Qn) and 位 1 DX 2 (Qn). These results provide a reference for the further study of the connectivity of other (gdnk)-conditional (edge) networks on hypercube networks, and also for the study of other networks such as hypercube networks. K)-conditional (edge) connectivity provides methodological guidance. 3. In this paper, a fault-tolerant unicast routing algorithm based on local information is proposed in the case of (1 / 1 / 1)-conditional connectivity. The algorithm selects the dimension for routing by constructing spanning paths of less than 3 in length. In this paper, the time complexity and space complexity of the algorithm are analyzed, and compared with the existing unicast routing algorithms in terms of success rate, running time, path length and so on. 4. In this paper, a new conditional fault-tolerant Hamiltonian property, f- (gdnk) -conditional edge fault-tolerant Hamiltonian, is proposed. In this paper, we prove that when n 鈮，
本文编号：2312289
本文链接：https://www.wllwen.com/guanlilunwen/ydhl/2312289.html
