本文選題：并行計算機系統(tǒng)　切入點：互連網(wǎng)絡　出處：《蘇州大學》2013年博士論文　論文類型：學位論文

【摘要】：高性能并行計算機是一個國家綜合科技實力的體現(xiàn),在科研、教育、石油、氣象等相關領域發(fā)揮著日益重要的作用。在并行處理領域,研究并行計算機系統(tǒng)中處理器或者處理機連接的方式(互連網(wǎng)絡)是一個很重要的課題。一個互連網(wǎng)絡可以用一個簡單圖G=(V,E)來表示,其中V代表頂點集合,而E代表邊集�；ミB網(wǎng)絡拓撲結(jié)構(gòu)的性質(zhì)對于并行計算機的性能至關重要。 互連網(wǎng)絡的一個重要性能指標是其它己存在的網(wǎng)絡拓撲結(jié)構(gòu)能否嵌入該網(wǎng)絡。圖嵌入問題描述如下：給定一個主圖G2=(V2,E2)和一個客圖G1=(V1,E1),將客圖G1嵌入到主圖G2中就是找到G1中的每個頂點到G2中一個頂點的一個單射,以及G1中的每條邊到G2中某一條路徑的映射。衡量嵌入效率的兩個重要指標是擴張(Dilation)和膨脹(Expansion)。性能良好的互連網(wǎng)絡作為主圖時應該具有理想的嵌入能力,從而能夠使客圖上的并行算法在其上能夠高效地遷移并運行。 隨著互連網(wǎng)絡規(guī)模的增大,互連網(wǎng)絡中的處理器(處理機)或通信鏈路出現(xiàn)故障的可能性也隨之變大。當故障發(fā)生時,我們需要找到故障并修復它。系統(tǒng)級故障診斷就是識別發(fā)生故障的處理器(處理機)或通信鏈路的過程。系統(tǒng)級故障診斷可以在不增加額外投入的情況下,提高系統(tǒng)的可靠性和可用性。系統(tǒng)級故障診斷按照測試策略可分為非自適應性診斷和自適應性診斷。在自適應性診斷中,測試分配是根據(jù)之前的測試結(jié)果動態(tài)分配的,這種方式比非自適應性診斷增加了診斷的效率,可避免不必要的測試。 圖的直徑是圖中任意兩個頂點之間最短路徑的最大值。直徑是衡量網(wǎng)絡通信性能的一個重要指標,它決定了任意頂點對間最大的通信延遲。根據(jù)圖的直徑的定義,我們可知,當刪除邊或者增加邊時,可能會影響頂點之間的距離,進而影響圖的直徑。其中,刪除邊可以表示邊故障的情形�；ミB網(wǎng)絡直徑的改變可以影響其通信性能,因此研究刪除邊或者增加邊對圖直徑的影響是一個有意義的課題。 超立方體是一種研究較多、總體性質(zhì)較好的互連網(wǎng)絡拓撲結(jié)構(gòu)。局部扭立方體(Locally Twisted Cube)是超立方體的一種重要變型,它是超立方體的強有力的競爭者,其直徑約為超立方體的一半。令LT Qn表示n維局部扭立方體。 本文研究局部扭立方體中的以下幾個內(nèi)容：網(wǎng)孔嵌入性,樹嵌入性,自適應性診斷和刪除邊或增加邊時直徑的改變問題。 1.本文證明了局部扭立方體具有很好的網(wǎng)孔嵌入性質(zhì)： (1)對于任意的整數(shù)n≥1,一個2×2n-1的網(wǎng)孔可以擴張1和膨脹1嵌入LTQn。 (2)對于任意的整數(shù)n≥4,兩個4×2n-3的頂點互不相交網(wǎng)孔可以擴展1和膨脹2嵌入LTQn。 (3)對于任意的整數(shù)n≥3,一個4×(2n-2-1)網(wǎng)孔可以擴張2嵌入LTQn。 前兩個結(jié)果在擴張方面是最優(yōu)的,因為其擴張為1。2×2n-1網(wǎng)孔嵌入的膨脹為1,因此該嵌入在膨脹方面也是最優(yōu)的。此外,對于任意的整數(shù)p≥1和q≥1,本文還給出了局部扭立方體中2p×2q網(wǎng)孔嵌入的分析。 2.本文證明了局部扭立方體具有很好的樹嵌入性質(zhì)： (1)對于任意的整數(shù)n≥2,一棵具有2n-1個頂點的完全二叉樹可以擴張2嵌入LTQn。 (2)對于任意的整數(shù)n≥1,LTQn中以任意頂點為根可以擴張1嵌入k階二項樹Bk(k為整數(shù),且0≤k≤n)。 3.本文研究了局部扭立方體的自適應性診斷： 本文證明對于任意的整數(shù)n≥3,LTQn在至多n個頂點出錯的情況下,可以在至多4輪并行測試中被自適應性診斷。然后,本文給出了LTQn的自適應性診斷算法描述及其分析。 4.本文研究了刪除邊或增加邊時直徑的改變問題,得到了以下3個結(jié)論： (1)對于任意的整數(shù)n≥2,我們找到了使LTQn直徑變大,至少需要刪除的邊數(shù)(用ch-(LTQn)表示)。對于n=2,n=3和任意的奇數(shù)n≥7,ch-(LTQn)=1。對于n=5和n=6,ch-(LTQn)=n-1。對于n=4和任意的偶數(shù)n≥8,ch-(LTQn)=2。 (2)對于任意的整數(shù)n≥2,當使LTQn直徑變大至少需要刪除的邊被刪除時,我們找到了LTQn直徑的增加值(用diam+(LT Qn)表示),diam+(LT Qn)=1。 (3)對于任意的整數(shù)n≥4,使LTQn直徑減小,至少需要增加邊的上界為2n-1。
[Abstract]:High performance parallel computer is the embodiment of a country's comprehensive strength of science and technology in scientific research, education, petroleum, meteorology and other related fields play an increasingly important role. In the field of parallel processing, research on parallel computer system processor or processor connected way (interconnection network) is a very important issue. An interconnection network you can use a simple graph G= (V, E) to said, where V represents the vertex set, and E represents the edge set. Properties of the interconnection network topology is crucial for the performance of parallel computers.
One of the most important performance index of interconnection network is the network topology can be embedded into the other existing networks. Graph embedding problem is described as follows: given a graph G2= (V2, E2) and a guest (V1, E1) G1=, passengers will be embedded into the main figure G1 in figure G2 is found for each vertex in G1 to a single shot of a vertex in G2, and each edge in G1 mapping to a path of G2. Two embedding efficiency is an important index to measure the expansion (Dilation) and expansion (Expansion). The interconnection network with good performance as the main figure should have the ideal block the ability to make the guest parallel algorithm on the graph can efficiently transfer and run on it.
With the increase of network scale, interconnection network processors (processor) or the possibility of communication link failure also increases. When a fault occurs, we need to find fault and repair it. The system level fault diagnosis is to identify faulty processors (processor) process or system level fault communication link. Diagnosis can be additional investment under the condition of not increasing, improve system reliability and availability. The system level fault diagnosis according to the test strategy can be divided into non adaptive diagnosis and adaptive diagnosis. In adaptive diagnosis, test according to the test results before the allocation is dynamically allocated, the non adaptive diagnosis increased the efficiency of diagnosis, to avoid unnecessary testing.
The diameter of a graph is the maximum map between any two vertices of the shortest path. The diameter is an important index to measure the performance of communication network, it determines the communication between any vertex maximum delay. According to the definition, the diameter of the graph we can see, when removing the edges or increase the edge, may affect the vertex the distance between and the diameter of a graph. The deleted edges can express edge fault situation. Change the interconnection network diameter can influence the communication performance, so the research delete edge or increase the impact on the edge of graph diameter is a meaningful topic.
The hypercube is a kind of more general nature better interconnection network topology. The locally twisted cube (Locally Twisted Cube) is an important variant of the hypercube, it is the hypercube strong competitor, its diameter is about half of the hypercube. Let LT Qn denote the n-dimensional locally twisted cube.
This paper studies the following contents in Locally Twisted Cube: mesh embeddedness, tree embeddedness, adaptive diagnosis and edge deletion or increase of edge time diameter.
1. this paper proves that the local twisted cube has good mesh embeddedness properties:
(1) for an arbitrary integer greater than or equal to 1 N, a 2 * 2N-1 mesh can be embedded in LTQn. 1 and 1 expansion expansion
(2) for an arbitrary integer n = 4, two * 4 2n-3 vertex disjoint mesh can be extended 1 and 2 expansion of embedded LTQn.
(3) for an arbitrary integer greater than or equal to 3 N, a 4 x 2 expansion (2n-2-1) mesh can be embedded in LTQn.
The two result is optimal in terms of expansion, because of its expansion is 1.2 * 2N-1 mesh embedding expansion is 1, so the expansion is embedded in the optimal. In addition, for an arbitrary integer P = 1 and q = 1, this paper gives the analysis of the locally twisted cube 2p * 2q mesh embedding.
2. this paper proves that the local twisted cube has good tree embedding properties:
(1) for an arbitrary integer greater than or equal to 2 N, a tree with 2N-1 vertices completely two forks tree can be embedded in LTQn. 2 expansion
(2) for an arbitrary integer n = 1, LTQn to any vertex is the root can be extended 1 embedded k order two tree Bk (k is an integer, and 0 = k = n).
3. in this paper, the adaptive diagnosis of local Twisted Cubes is studied.
We prove that for any integer n = 3, LTQn at least n vertices in case of error, can be up to 4 rounds of parallel testing by adaptive diagnosis. Then, this paper gives LTQn the adaptive diagnosis algorithm description and analysis.
4. this paper studies the problem of changing the diameter of the deleting or increasing edge, and obtains the following 3 conclusions:
(1) for an arbitrary integer greater than or equal to 2 N, we found that the LTQn diameter becomes larger, at least need to delete the number of edges (ch- (LTQn) said.) for n=2, n=3 and any odd number n = 7, ch- (LTQn) =1. for n=5 and n=6, ch- (LTQn) =n-1. for n=4 and any even number n = 8, ch- (LTQn) =2.
(2) for an arbitrary integer greater than or equal to 2 N, when the LTQn of larger diameter at least need to delete the edge is deleted, we found increased LTQn diameter (diam+ (LT Qn) said, diam+) (LT Qn) =1.
(3) for an arbitrary integer n = 4, the decrease of the diameter of LTQn increased the need for at least the upper edge of 2n-1.

【學位授予單位】：蘇州大學
【學位級別】：博士
【學位授予年份】：2013
【分類號】：TP338.6

【參考文獻】

相關期刊論文 前5條

1 樊建席;交叉立方體在兩種策略下的可診斷性[J];計算機學報;1998年05期

2 樊建席,何力勤;BC互連網(wǎng)絡及其性質(zhì)[J];計算機學報;2003年01期

3 喻昕;吳敏;王國軍;;一種新的交叉立方體最短路徑路由算法[J];計算機學報;2007年04期

4 鄧偉;楊小帆;吳中福;;面向系統(tǒng)級故障診斷的高效遺傳算法[J];計算機學報;2007年07期

5 常青彥;馬美杰;徐俊明;;局部紐立方體網(wǎng)絡的容錯泛圈性[J];中國科學技術大學學報;2006年06期

，

本文編號：1584704