【摘要】：互連網(wǎng)絡(luò)(Interconnection Network)融合了計算機科學(xué)、信息化技術(shù)、通信工程、數(shù)學(xué)等多學(xué)科多領(lǐng)域的知識,是高性能并行計算機的主要研究課題之一�；ミB網(wǎng)絡(luò)的結(jié)構(gòu)多種多樣,超立方體(Hypercube)就是該領(lǐng)域里較早提出的優(yōu)秀網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)之一。它高度的對稱性、正則性、短直徑性、強容錯性、可靠性、可嵌入性、可擴展性以及網(wǎng)絡(luò)良好的通信能力等優(yōu)點,深受學(xué)者們和業(yè)內(nèi)人士的喜歡,引起了國內(nèi)外專家學(xué)者們的長期關(guān)注,成為近些年來國際研究的熱點之一本文針對n維超立方體Qn的拓?fù)浣Y(jié)構(gòu),基于其節(jié)點編碼的特點,得到了求超立方體Qn中指定條件下的最短路算法,并且利用避圈法,依據(jù)廣度優(yōu)先策略,給出了在超立方體Qn中找一棵生成樹的算法,最后在理論分析的基礎(chǔ)上,得到關(guān)于超立方體Qn中邊不交生成樹棵數(shù)上界和下界的兩個定理。具體的研究結(jié)果如下：1.給出了求超立方體Qn中從始點s到達終點t的一條最短路徑算法；2.給出了求超立方體Qn中從始點s到達終點t且邊不交的最優(yōu)路徑算法；3.給出了求超立方體Qn中從始點s到達終點t且經(jīng)過指定節(jié)點υ1,ν2,…,νk(kn)的最短路徑算法；4.給出了超立方體Qn中尋找一棵最小生成樹的算法；5.給出了超立方體Qn中邊不交的生成樹棵樹的上界和下界：(1)Qn中邊不交的生成樹最多有「n·2n-1/2n-1」棵，，即Г(Qn)|≤「n·2n-1/2n-1」；(2)當(dāng)n＞4時，Qn中至少存在2棵邊不交的生成樹,即|Γ(Qn)|≥2.在每個重要算法給出之前,文中都交代了其算法思想,并且給出了算法框圖、算法步驟,之后還有算法復(fù)雜度分析和實例驗證過程。研究結(jié)果表明,這些算法均屬多項式時間算法,不僅針對性強,而且效率非常高。文章中給出的所有算法以及對邊不交生成樹數(shù)量上界和下界的研究,為設(shè)計超立方體互連網(wǎng)絡(luò)中單播和并行廣播路由算法提供了強有力的理論支撐。
[Abstract]:Interconnect network (Interconnection Network) is one of the main research topics of high performance parallel computers, which integrates the knowledge of computer science, information technology, communication engineering, mathematics and so on. Hypercube (Hypercube) is one of the excellent network topologies proposed in this field. It has the advantages of high symmetry, regularity, short diameters, strong fault tolerance, reliability, embeddedness, extensibility and good communication ability of the network. It has attracted the attention of experts and scholars at home and abroad for a long time, and has become one of the international research hotspots in recent years. According to the topological structure of n-dimensional hypercube QN, based on the characteristics of node coding, In this paper, the shortest path algorithm under specified conditions in hypercube Qn is obtained, and the algorithm of finding a spanning tree in hypercube Qn is given by using the method of cycle avoidance, according to the breadth-first strategy. Finally, on the basis of theoretical analysis, the algorithm of finding a spanning tree in the hypercube Qn is given. Two theorems about the upper bound and lower bound of the spanning tree of edge disjoint in hypercube Qn are obtained. The specific findings are as follows: 1: 1. A shortest path algorithm is given for finding the shortest path from the beginning point s to the end point t in the hypercube Qn. In this paper, an optimal path algorithm for finding the optimal path from the beginning point s to the end point t and edge disjoint in the hypercube Qn is presented. In this paper, we give the solution of the hypercube Qn from the beginning point s to the end point t and pass through the specified nodes v 1, v 2, 鈥

本文編號：2179851