本文關(guān)鍵詞： 互連網(wǎng)絡 地址變換 維鄰接關(guān)系 圓排列 獨立生成樹　出處：《蘇州大學》2014年博士論文　論文類型：學位論文

【摘要】：高性能計算機在國防太空、石油勘探、生物制藥、天氣預報以及基礎理論研究等領(lǐng)域發(fā)揮著日益重要的作用，其性能很大程度上取決于系統(tǒng)中處理器或者處理機之間連接的方式（互連網(wǎng)絡）。在并行處理領(lǐng)域，互連網(wǎng)絡及其性質(zhì)的研究是一個重要課題。一個互連網(wǎng)絡可以用一個簡單圖G=(V(G), E(G))來表示，其中V(G)代表G上的頂點集合，而E(G)代表G上的邊集合。 超立方體是常用的互連網(wǎng)絡之一，其許多優(yōu)越性質(zhì)如低直徑、高連通性、對稱性、遞歸構(gòu)造性等受到眾多研究者的青睞。同時，超立方體具有性能優(yōu)越的變型網(wǎng)絡如交叉立方體、莫比烏斯立方體、扭立方體等。研究者依據(jù)一一對應連接和可遞歸構(gòu)造性質(zhì)，將超立方體及其若干變型歸結(jié)為一類互連網(wǎng)絡——BC網(wǎng)絡。在互連網(wǎng)絡中，獨立生成樹在信息的可靠傳輸、并行傳輸、安全分發(fā)及故障處理器的診斷等方面具有重要的作用。本文采用從特殊到一般的方法研究BC網(wǎng)絡上獨立生成樹（IST）的存在性及其構(gòu)造問題，包括以下內(nèi)容： 1.交叉立方體上以任一頂點為根的獨立生成樹的串行構(gòu)造 （1）證明了n維交叉立方體CQn滿足一個重要的地址變換性質(zhì)，依據(jù)該地址變換性質(zhì)給出了CQ01n1和CQn1上同構(gòu)樹的構(gòu)造方法。 （2）給出了CQn上以任一頂點為根的n棵IST的遞歸構(gòu)造方法，證明了其正確性，并設計了時間復雜度為O(Nlog2N)的構(gòu)造算法，這里N是CQn的頂點個數(shù)。 2.莫比烏斯立方體上以任一頂點為根的獨立生成樹的串行構(gòu)造 與交叉立方體不一樣的是，n維莫比烏斯立方體Mn是由兩個不同構(gòu)的子莫比烏斯立方體M01 n1和Mn1組成，從而交叉立方體上地址變換的方法不再適用于在莫比烏斯立方體上構(gòu)造IST。我們從頂點之間維鄰接關(guān)系的角度進行研究，取得了如下成果： （1）結(jié)合Mn的構(gòu)造規(guī)律，從頂點之間維鄰接關(guān)系的角度提出了適合于在M01n1和Mn1上構(gòu)造同構(gòu)樹的方法。 （2）基于頂點之間的維鄰接關(guān)系，設計了Mn上獨立生成樹的構(gòu)造過程中擴展頂點集合和擴展頂點集合劃分的選擇方法，并引入非負向量來證明其上存在IST的正確性。 （3）設計了時間復雜度為O(NlogN)的遞歸構(gòu)造算法，這里N是Mn的頂點個數(shù)。 其中，Mn上基于頂點之間的維鄰接關(guān)系構(gòu)造M01n1和Mn1中同構(gòu)樹的方法同樣適合在CQ01n1和CQn1中構(gòu)造同構(gòu)樹，是CQn上地址變換方法的改進方法。另外，在Mn上所設計的IST的遞歸構(gòu)造算法的效率比CQn上的高。 3.交叉立方體上獨立生成樹的并行構(gòu)造 從交叉立方體和莫比烏斯立方體上IST的串行構(gòu)造方法來看，其對應算法的時間復雜度高且IST在構(gòu)造過程中存在相互依賴的缺點，如第n棵樹在構(gòu)造過程中依賴于前面n1棵樹，因此，尋找交叉立方體的新的性質(zhì)并基于其設計獨立生成樹的并行構(gòu)造方法以提高相應算法的效率是一個很值得研究的內(nèi)容。在這方面我們?nèi)〉昧巳缦卵芯拷Y(jié)果： （1）證明了交叉立方體上滿足一個重要性質(zhì)——維擴散性質(zhì)。 （2）提出一個具有UUID成員和VALUE成員的樹存儲結(jié)構(gòu)，確保樹中頂點的UUID成員總是具有唯一性。 （3）基于交叉立方體上維擴散性質(zhì)給出了其上IST的并行構(gòu)造算法。 4.莫比烏斯立方體上獨立生成樹的并行構(gòu)造 在對交叉立方體上IST的串行和并行構(gòu)造方法、莫比烏斯立方體上IST的串行構(gòu)造方法總結(jié)的基礎上，我們進一步研究了莫比烏斯立方體上IST的并行構(gòu)造問題，取得了如下研究結(jié)果： （1）從排列組合的角度，將圓排列的概念引入到IST的構(gòu)造方法中。 （2）首先證明了遞減的圓排列能夠用于并行構(gòu)造莫比烏斯立方體上以任一頂點為根的IST。其次，進一步證明了任一圓排列能夠用來并行構(gòu)造莫比烏斯立方體和超立方體上以任一頂點為根的IST。 （3）指出利用不同的圓排列構(gòu)造的多組IST能夠構(gòu)造莫比烏斯立方體上任意兩個頂點之間多組頂點不相交路徑。 （4）探討了基于IST的高效診斷算法。 5. BC網(wǎng)絡上IST的構(gòu)造 特殊BC網(wǎng)絡如超立方體、交叉立方體、局部扭立方體、莫比烏斯立方體中IST的構(gòu)造及其證明依賴于其特有的性質(zhì)。我們研究了基于它們的共性來構(gòu)造其上的IST的一個一般性方法，取得了如下結(jié)果： （1）給出了條件BC網(wǎng)絡的定義，證明了超立方體、交叉立方體、局部扭立方體、莫比烏斯立方體等均屬于條件BC網(wǎng)絡。同時，指出了存在不屬于條件BC網(wǎng)絡的BC網(wǎng)絡。 （2）證明了利用遞增的圓排列能夠在O(N)時間內(nèi)構(gòu)造n維條件BC網(wǎng)絡XCn上以任一頂點為根的n棵同構(gòu)于n-級類二項樹的IST，這里n≥2且N=2n是XCn的頂點個數(shù)。 （3）針對任一BC網(wǎng)絡，提出了維的V排列并證明了V排列能夠用來構(gòu)造任一n維BC網(wǎng)絡Xn上以任一頂點為根的生成樹且證明這些生成樹均同構(gòu)于n級二項樹。同時，指出基于V排列能夠構(gòu)造Xn上多組兩兩獨立的生成樹。 綜上所述，本文首先給出了特殊BC網(wǎng)絡交叉立方體、莫比烏斯立方體上IST的串行構(gòu)造方法。然后，在總結(jié)相關(guān)串行構(gòu)造方法的基礎上，設計了其上IST的并行構(gòu)造方法，，并進一步研究了條件BC網(wǎng)絡和BC網(wǎng)絡上IST的構(gòu)造問題。
[Abstract]:......
【學位授予單位】：蘇州大學
【學位級別】：博士
【學位授予年份】：2014
【分類號】：O157.5;TP393.4

【參考文獻】

相關(guān)期刊論文 前2條

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

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

相關(guān)博士學位論文 前1條

1 董強;幾類規(guī)則互連網(wǎng)絡的嵌入與容錯嵌入研究[D];重慶大學;2010年

本文編號：1515761