【摘要】：隨著計算機科學和信息化網(wǎng)絡(luò)技術(shù)的發(fā)展,高性能計算機在社會各個領(lǐng)域發(fā)揮著日益重要的作用。高性能計算機的性能在很大程度上取決于其系統(tǒng)內(nèi)部處理器之間的連接方式(互連網(wǎng)絡(luò))�；ミB網(wǎng)絡(luò)的拓撲結(jié)構(gòu)及其性質(zhì)的研究是并行計算領(lǐng)域的研究重點之一�；ミB網(wǎng)絡(luò)一般可以用一個簡單圖G=(V(G),E(G))來表示,其中V(G)表示圖G中的頂點集合,代表互連網(wǎng)絡(luò)中的處理器,E(G)表示圖G中的邊集合,代表處理器之間的鏈路。隨著互連網(wǎng)絡(luò)規(guī)模的不斷擴大,網(wǎng)絡(luò)中處理器和鏈路的數(shù)目也逐漸增多,處理器或鏈路發(fā)生故障的概率也會隨之增加。在網(wǎng)絡(luò)發(fā)生故障的情況下網(wǎng)絡(luò)中某些特性能否繼續(xù)保持,這就是網(wǎng)絡(luò)的容錯性,它是衡量互連網(wǎng)絡(luò)性能的一項關(guān)鍵指標。超立方體網(wǎng)絡(luò)是多處理器系統(tǒng)中一種常用的互連網(wǎng)絡(luò),它具有很多優(yōu)越的性質(zhì),例如直徑較小、結(jié)構(gòu)對稱、遞歸構(gòu)造、可擴展性強等�；谠摼W(wǎng)絡(luò),研究者們已經(jīng)提出了許多性能優(yōu)越的超立方體變型網(wǎng)絡(luò),例如交叉立方體、扭立方體、莫比烏斯立方體等。因此,超立方體網(wǎng)絡(luò)已成為多處理器系統(tǒng)中最基礎(chǔ)也最重要的網(wǎng)絡(luò)模型之一。本文在結(jié)合理論分析的基礎(chǔ)上,就超立方體網(wǎng)絡(luò)的容錯性提出了新的測量方法,并且在該方法的限制條件下,研究了超立方體網(wǎng)絡(luò)上的條件連通度,容錯單播路由算法以及容錯哈密頓性質(zhì)。主要研究內(nèi)容如下:1.本文提出一種與距離相關(guān)的新的條件(邊)連通度  (g,d,k)-條件(邊)連通度。與其他條件連通度相比,(g,d,k)-條件(邊)連通度的要求更符合實際情況,并且允許存在更多的故障頂點(邊)。它為研究超立方體等網(wǎng)絡(luò)的容錯性提供了新的衡量指標。2.本文研究了超立方體網(wǎng)絡(luò)上某些特定的(g,d,k)-條件(邊)連通度,包括κ1,1,k(Qn),κ1,d,2(Qn),λ1,1,1(Qn)和λ1,d,2(Qn)。這些結(jié)果為后續(xù)研究超立方體網(wǎng)絡(luò)上其他(g,d,k)-條件(邊)連通度提供了參考,也為在超立方體變型網(wǎng)絡(luò)等其他網(wǎng)絡(luò)上研究(g,d,k)-條件(邊)連通度提供了方法上的指導。3.本文在(1,1,1)-條件連通的情況下提出了一種基于局部信息的容錯單播路由算法,該算法通過構(gòu)建長度不超過3的跨越路徑來選擇用于路由的維度。本文分析了該算法的時間復雜度以及空間復雜度,并且和現(xiàn)有的幾種單播路由算法從成功率,運行時間,路徑長度等方面進行了比較。4.本文結(jié)合(g,d,k)-條件邊連通的概念,提出了一種新的條件容錯哈密頓性質(zhì):f-(g,d,k)條件邊容錯哈密頓。本文證明,當n≥4時,n維超立方體是(4n-13)-(3,0,0)條件邊容錯哈密頓的,并且這一結(jié)果是最優(yōu)的。最后,對本文工作進行了總結(jié),并對后續(xù)的研究工作進行了展望。
[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