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

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

【參考文獻(xiàn)】

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

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

2 喻昕;吳敏;王國(guó)軍;;一種新的交叉立方體最短路徑路由算法[J];計(jì)算機(jī)學(xué)報(bào);2007年04期

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

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

本文編號(hào)：1515761