本文關(guān)鍵詞：幾種BC網(wǎng)絡(luò)上完全二叉樹(shù)的嵌入研究

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

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

【相似文獻(xiàn)】

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

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

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

3 朱濤;;基于遍歷二叉樹(shù)的方法判斷完全二叉樹(shù)[J];紅河學(xué)院學(xué)報(bào);2005年06期

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

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

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

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

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

9 ;[J];;年期

中國(guó)重要報(bào)紙全文數(shù)據(jù)庫(kù) 前1條

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

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

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

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

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

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

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

4 劉舒眉;Narayana數(shù)的組合解釋?zhuān)瑢?duì)稱(chēng)性及其推廣[D];華東師范大學(xué);2014年

本文編號(hào)：1277717