發(fā)布時間：2017-12-11 08:12

  本文關鍵詞：幾種BC網(wǎng)絡上完全二叉樹的嵌入研究

  更多相關文章： 互連網(wǎng)絡 圖嵌入 完全二叉樹 莫比烏斯立方體 奇偶立方體 局部扭立方體

【摘要】：并行計算在教育、科研、石油、生物、氣象等相關領域發(fā)揮著日益重要的作用。多處理器互連網(wǎng)絡(簡稱互連網(wǎng)絡)在很大程度上決定了并行計算系統(tǒng)的性能。因此,互連網(wǎng)絡及其性質(zhì)的研究是并行處理領域中的一個重要課題�；ミB網(wǎng)絡可以表示為一個簡單圖,其中頂點代表處理器,邊代表處理器之間的通信鏈路。在互連網(wǎng)絡的設計和分析中,圖嵌入能力是衡量一個互連網(wǎng)絡性能優(yōu)劣的重要指標。給定兩個圖G和H,由G到H的一個嵌入定義為由G到H的一個單射。圖G和圖H分別稱為嵌入的客圖和主圖。理想的互連網(wǎng)絡(主圖)應該擁有優(yōu)秀的圖嵌入能力,使得擁有規(guī)則任務圖(客圖)的并行算法能夠在該網(wǎng)絡上高效的執(zhí)行。擴張、膨脹、擁塞和負載是衡量圖嵌入性能的常用指標,圖嵌入的最優(yōu)性能求解問題是NP難問題。由于完全二叉樹具有優(yōu)越性能和廣泛應用,因此將其作為客圖嵌入互連網(wǎng)絡具有十分重要的研究意義。盡管完全二叉樹到一般互連網(wǎng)絡以最優(yōu)性能嵌入的求解問題是NP難問題,但在一些特殊互連網(wǎng)絡中以最優(yōu)性能嵌入完全二叉樹已經(jīng)得到解決。迄今為止,關于將完全二叉樹嵌入多種互連網(wǎng)絡如網(wǎng)孔、星圖、網(wǎng)格、蝶網(wǎng)等的研究已經(jīng)取得了較多成果。超立方體作為一種常用的互連網(wǎng)絡得到了眾多研究者的青睞,其具有許多優(yōu)越性質(zhì)比如低直徑、高連通性、對稱性、遞歸構(gòu)造性等。然而,完全二叉樹不能以最優(yōu)性能嵌入超立方體,卻能以最優(yōu)性能嵌入某些超立方體變型,如交叉立方體和折疊立方體。超立方體及其若干變型均具有一一對應連接和可遞歸構(gòu)造性質(zhì),研究者依據(jù)這兩個性質(zhì)將它們歸結(jié)為一類互連網(wǎng)絡——BC網(wǎng)絡。然而,關于將完全二叉樹嵌入BC網(wǎng)絡的研究成果相對較少。本文中,我們主要研究幾種BC網(wǎng)絡——莫比烏斯立方體、奇偶立方體和局部扭立方體上完全二叉樹的嵌入問題。我們證明了完全二叉樹能以最優(yōu)性能嵌入莫比烏斯立方體和奇偶立方體,以及以較優(yōu)性能嵌入和容錯嵌入局部扭立方體。具體包括以下內(nèi)容:1.n維莫比烏斯立方體(M_n)上完全二叉樹的嵌入與交叉立方體不同的是,M_n是由兩個不同構(gòu)的子莫比烏斯立方體組成(n≥5)。因此,在M_n上嵌入完全二叉樹將面對更復雜的情形。我們研究了M_n上完全二叉樹以最優(yōu)性能嵌入的問題,取得了如下研究結(jié)果:(1)證明了莫比烏斯立方體中滿足的一個重要性質(zhì)——由不相交子立方體構(gòu)成的立方體對同構(gòu)于子莫比烏斯立方體。(2)基于M_n上存在同構(gòu)立方體對的性質(zhì),提出了一種對M_n上的完全二叉樹嵌入進行類型劃分的構(gòu)造方法。(3)證明了完全二叉樹能以擴張1、負載1、擁塞1和膨脹趨近于1嵌入M_n。2.n維奇偶立方體(PQ_n)上完全二叉樹的嵌入與M_n上完全二叉樹的嵌入方法不同,我們給出了PQ_n上完全二叉樹以最優(yōu)性能嵌入的證明方法。進一步,我們還設計了相應的嵌入算法和模擬實驗,取得了如下研究結(jié)果:(1)證明了完全二叉樹能以擴張1、負載1、擁塞1和膨脹趨近于1嵌入PQ_n。(2)給出了時間復雜度為O(Nlog N)的完全二叉樹嵌入算法,其中N為PQ_n的頂點個數(shù),并給出了算法的正確性證明。(3)設計了在PQ_n上嵌入完全二叉樹的模擬實驗。3.n維局部扭立方體(LT Q_n)上完全二叉樹的容錯嵌入隨著互連網(wǎng)絡規(guī)模的不斷增大,處理器和通信鏈路將不可避免地出現(xiàn)故障。因此,我們有必要去評估互連網(wǎng)絡的容錯嵌入能力。我們研究了LTQ_n上完全二叉樹的嵌入以及容錯嵌入問題,取得了如下研究結(jié)果:(1)證明了以任意頂點為根的完全二叉樹能以擴張2、負載1、擁塞1和膨脹1嵌入LTQ_n。(2)證明了當LTQ_n上的任意一個頂點發(fā)生故障時,LTQ_n上嵌入的完全二叉樹能以擴張2和擁塞2動態(tài)重建。(3)證明了當LTQ_n上的任意兩個頂點發(fā)生故障時,LTQ_n上嵌入的完全二叉樹能以擴張3和擁塞3動態(tài)重建。(4)證明了當LTQ_n上的故障頂點數(shù)超過兩個時,在給定的限制條件下LTQ_n上嵌入的完全二叉樹能以擴張3和擁塞3動態(tài)重建。
【學位授予單位】：蘇州大學
【學位級別】：博士
【學位授予年份】：2016
【分類號】：O157.5

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前9條

1 王琦;;順序二叉樹和右(左)完全二叉樹的一些性質(zhì)[J];河北工學院學報;1986年03期

2 宋麗華,張福增,趙永升;完全二叉樹的實時判別方法[J];煙臺師范學院學報(自然科學版);2004年01期

3 朱濤;;基于遍歷二叉樹的方法判斷完全二叉樹[J];紅河學院學報;2005年06期

4 白亞蘭;師海忠;;完全二叉樹到星連通圈網(wǎng)絡的嵌入[J];甘肅科學學報;2014年03期

5 陳磊,沈復興;完全二叉樹理論的模型及性質(zhì)[J];北京師范大學學報(自然科學版);2004年02期

6 師海忠;牛攀峰;喬韻璇;;完全二叉樹到冒泡排序網(wǎng)絡的嵌入[J];工程數(shù)學學報;2012年03期

7 王世琪;;完全二叉樹理論的可數(shù)模型及其胞腔性[J];南京大學學報數(shù)學半年刊;2007年02期

8 李志敏;羅里波;李祥;;完全二叉樹理論的計算復雜度[J];數(shù)學學報;2008年02期

9 ;[J];;年期

中國重要報紙全文數(shù)據(jù)庫 前1條

1 ;系統(tǒng)設計師考試《數(shù)據(jù)結(jié)構(gòu)》試題分析（上）[N];中國電腦教育報;2004年

中國博士學位論文全文數(shù)據(jù)庫 前1條

1 劉釗;幾種BC網(wǎng)絡上完全二叉樹的嵌入研究[D];蘇州大學;2016年

中國碩士學位論文全文數(shù)據(jù)庫 前4條

1 楊帆;BO-AUC多類分類評估方法的研究[D];安徽工業(yè)大學;2011年

2 范廣臣;基于完全二叉樹SVM燒結(jié)工況多類識別的研究與實現(xiàn)[D];東北大學;2009年

3 羅玉;基于XML數(shù)據(jù)庫查詢優(yōu)化技術的研究[D];西南交通大學;2014年

4 劉舒眉;Narayana數(shù)的組合解釋，，對稱性及其推廣[D];華東師范大學;2014年

本文編號：1277717