版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、并行計(jì)算系統(tǒng)的性能很大程度上取決于相應(yīng)互連網(wǎng)絡(luò)的有效性。人們通常用圖來(lái)表示互連網(wǎng)絡(luò),圖中的結(jié)點(diǎn)代表并行計(jì)算系統(tǒng)中的處理器,圖中的邊代表處理器之間的通信鏈接。在互連網(wǎng)絡(luò)的設(shè)計(jì)和分析中,圖嵌入能力是一個(gè)重要的性能指標(biāo)。理想的互連網(wǎng)絡(luò)(主圖)應(yīng)該擁有優(yōu)秀的圖嵌入能力,使得擁有規(guī)則任務(wù)圖(客圖)的并行算法能夠在這個(gè)網(wǎng)絡(luò)上高效的執(zhí)行。
隨著并行計(jì)算系統(tǒng)的規(guī)模不斷增大,系統(tǒng)中將不可避免地出現(xiàn)故障處理器和故障通信鏈接。理想情況下,系統(tǒng)應(yīng)
2、該繼續(xù)運(yùn)行而不致崩潰,當(dāng)然系統(tǒng)性能會(huì)有所下降。因此,我們非常有必要去評(píng)估互連網(wǎng)絡(luò)的容錯(cuò)能力。尤其需要指出的是,互連網(wǎng)絡(luò)的容錯(cuò)圖嵌入能力是并行計(jì)算中一個(gè)很重要的研究課題。
前人關(guān)于圖嵌入的研究工作通常把圈、路徑、樹、網(wǎng)孔和環(huán)繞等作為客圖,因?yàn)樗鼈兇砹嗽S多并行算法的任務(wù)圖結(jié)構(gòu)。本文中,我們研究將這些常見客圖嵌入或者容錯(cuò)嵌入到一些著名互連網(wǎng)絡(luò)中,其主要內(nèi)容安排如下。
(1)第一章對(duì)并行計(jì)算機(jī)互連網(wǎng)絡(luò)領(lǐng)域進(jìn)行簡(jiǎn)要介
3、紹,并給出互連網(wǎng)絡(luò)和圖嵌入相關(guān)的圖論基礎(chǔ)知識(shí)。 4、奇數(shù),那么廣義蜂窩環(huán)GHT(m,2d,d)包含無(wú)故障哈密爾頓圈。結(jié)果表明在蜂窩環(huán)網(wǎng)絡(luò)上能容錯(cuò)地、高效率地運(yùn)行環(huán)形并行算法。 5、以被嵌入到2k+2維交叉立方體(包含22k+2個(gè)結(jié)點(diǎn))中,其中延展率為1,膨脹率大約為4/3;③當(dāng)n≥5并且f≤2n-7時(shí),包含f個(gè)故障結(jié)點(diǎn)的n維交叉立方體中存在長(zhǎng)度至少為2n-f-(n-5)的無(wú)故障圈。結(jié)果表明在交叉立方體上能高效率地運(yùn)行3維網(wǎng)孔并行算法、網(wǎng)孔樹并行算法和容錯(cuò)環(huán)形并行算法。 6、:①當(dāng)n≥3是奇數(shù)并且0≤m≤(n-3)/2時(shí),2m個(gè)結(jié)點(diǎn)不相交的k維2t1×2t2×…×2tk網(wǎng)孔可以被嵌入到n維扭曲立方體中,其中延展率為1,∑ki=1ti=n-m,max1≤i≤k{ti}≥n-2m-1;②當(dāng)n≥5是奇數(shù),f≤n-4并且l≤2n-2-f時(shí),二維2×2l網(wǎng)孔(環(huán)繞)可以被嵌入到包含f個(gè)故障結(jié)點(diǎn)和故障邊的n維扭曲立方體中,并且延展率和擁塞度均為1(2)。結(jié)果表明在扭曲立方體上能容錯(cuò)地、高效率地運(yùn)行網(wǎng)孔并行算法。 7、 (5)第五章主要研究3元n維立方體的容錯(cuò)圈/路徑嵌入性質(zhì)。k元n維立方體是超立方體的一個(gè)重要推廣,具有理論和實(shí)用價(jià)值。假設(shè)當(dāng)n≥2時(shí),3元n維立方體包含fv個(gè)故障結(jié)點(diǎn)和fe條故障邊。我們證明,當(dāng)fv+fe≤2n-2時(shí),故障3元n維立方體中存在從3到3n-fv任意長(zhǎng)度的無(wú)故障圈;當(dāng)fv=fe≤2n-3時(shí),故障3元n維立方體中任意兩個(gè)無(wú)故障結(jié)點(diǎn)之間存在從2n-1到3n-fv-1任意長(zhǎng)度的無(wú)故障路徑。結(jié)果表明在3元n維立方體上能容錯(cuò)地 8、、高效率地運(yùn)行環(huán)形和陣列并行算法。
(2)第二章主要研究蜂窩環(huán)網(wǎng)絡(luò)的容錯(cuò)哈密爾頓性問(wèn)題。蜂窩環(huán)網(wǎng)絡(luò)是一類很有前景的并行計(jì)算機(jī)互連網(wǎng)絡(luò),它的結(jié)點(diǎn)度是傳統(tǒng)環(huán)繞網(wǎng)絡(luò)的四分之三。①我們發(fā)現(xiàn),在長(zhǎng)度為6的圈上距離為3的兩個(gè)結(jié)點(diǎn)發(fā)生故障的情況下,六角形蜂窩環(huán)是容錯(cuò)哈密爾頓圖。②假設(shè)m≥2與d≥8奇偶性相同,廣義蜂窩環(huán)GHT(n,2d,d)中包含兩個(gè)故障結(jié)點(diǎn)(w,y)和(x,y)。我們證明如果w
(3)第三章主要研究交叉立方體的圖嵌入和容錯(cuò)圖嵌入能力。交叉立方體是重要的超立方體變形,具有潛在的應(yīng)用價(jià)值。我們證明:①兩個(gè)(四個(gè))結(jié)點(diǎn)不相交的三維2×2×2n-3(4×2×2n-5)網(wǎng)孔可以被嵌入到n維交叉立方體中,其中延展率為1;②當(dāng)k為奇數(shù)時(shí),2k×2k網(wǎng)孔樹(包含3×22k-2k+1個(gè)結(jié)點(diǎn))可
(4)第四章主要研究扭曲立方體的網(wǎng)孔嵌入和容錯(cuò)網(wǎng)孔/環(huán)繞嵌入能力。扭曲立方體是超立方體的另一個(gè)重要變形,具有潛在的應(yīng)用價(jià)值。我們證明
(6)第六章主要研究廣義匹配網(wǎng)絡(luò)的容錯(cuò)哈密爾頓性問(wèn)題。廣義匹配網(wǎng)絡(luò)是由楊小帆教授等人提出的一類新型類屬互連網(wǎng)絡(luò),它包括超立方體、超立方體變形、星圖、煎餅圖以及許多其他的網(wǎng)絡(luò)結(jié)構(gòu)。假設(shè)廣義匹配網(wǎng)絡(luò)G包含至少4個(gè)基圖,每個(gè)基圖包含q個(gè)結(jié)點(diǎn)并且都是f-故障哈密爾頓連通圖和(f+1)-故障哈密爾頓圖。我們證明如果f+5≤q(n-1),并且同一個(gè)基圖中距離小于等于2的任意兩個(gè)結(jié)點(diǎn)的外部相鄰結(jié)點(diǎn)不在
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 互連網(wǎng)絡(luò)的條件嵌入與容錯(cuò).pdf
- 幾類互連網(wǎng)絡(luò)的容錯(cuò)性研究.pdf
- 互連網(wǎng)絡(luò)的圈嵌入研究.pdf
- 幾種互連網(wǎng)絡(luò)上圖嵌入的研究.pdf
- 若干互連網(wǎng)絡(luò)的圈嵌入和路嵌入.pdf
- 幾類光互連網(wǎng)絡(luò)的診斷性與容錯(cuò)性.pdf
- 幾類互連網(wǎng)絡(luò)的容錯(cuò)哈密頓性.pdf
- 互連網(wǎng)絡(luò)容錯(cuò)性研究.pdf
- 互連網(wǎng)絡(luò)的容錯(cuò)性.pdf
- 某些互連網(wǎng)絡(luò)的容錯(cuò)導(dǎo)出直徑
- 某些互連網(wǎng)絡(luò)的容錯(cuò)導(dǎo)出直徑.pdf
- 基于應(yīng)用驅(qū)動(dòng)的容錯(cuò)多級(jí)互連網(wǎng)絡(luò)研究.pdf
- 幾類互連網(wǎng)絡(luò)性能的組合分析.pdf
- 兩類互連網(wǎng)絡(luò)的邊容錯(cuò)直徑.pdf
- 一類互連網(wǎng)絡(luò)的邊容錯(cuò)直徑.pdf
- 互連網(wǎng)絡(luò)的容錯(cuò)性和可診斷性研究.pdf
- 互連網(wǎng)絡(luò)的可診斷性及容錯(cuò)性.pdf
- 某些容錯(cuò)網(wǎng)絡(luò)的嵌入研究.pdf
- 片上互連網(wǎng)絡(luò)容錯(cuò)關(guān)鍵技術(shù)研究.pdf
- 互連網(wǎng)絡(luò)的容錯(cuò)性和泛連通性.pdf
評(píng)論
0/150
提交評(píng)論