并行計(jì)算系統(tǒng)的性能很大程度上取決于相應(yīng)互連網(wǎng)絡(luò)的有效性。人們通常用圖來表示互連網(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)該繼續(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)要介紹,并給出互連網(wǎng)絡(luò)和圖嵌入相關(guān)的圖論基礎(chǔ)知識(shí)。 (2)第二章主要研究蜂窩環(huán)網(wǎng)絡(luò)的容錯(cuò)哈密爾頓性問題。蜂窩環(huán)網(wǎng)絡(luò)是一類很有前景的并行計(jì)算機(jī)互連網(wǎng)絡(luò),它的結(jié)點(diǎn)度是傳統(tǒng)...

【文章頁(yè)數(shù)】：106 頁(yè)

【學(xué)位級(jí)別】：博士

【部分圖文】：

圖1.2三個(gè)笛卡爾乘積圖

數(shù)的圈稱為偶圈,長(zhǎng)度為k的圈稱為k-圈。phic)：兩個(gè)圖G和H是同構(gòu)的，記為G),使得(x,y)∈E(G)(θ(x),θ(y))∈E(Htransitive)：如果對(duì)于圖G中任意兩個(gè)結(jié)點(diǎn)θ(x)=y....

圖2.2兩個(gè)廣義蜂窩環(huán)Fig.2.2Twogeneralizedhoneycombtori

圖2.2兩個(gè)廣義蜂窩環(huán)Fig.2.2Twogeneralizedhoneycombtori下面我們引入一些符號(hào)，以幫助我們標(biāo)記廣義蜂窩環(huán)中的路徑和圈。給定廣義蜂窩環(huán)GHT(m,n,d)的兩個(gè)相鄰結(jié)點(diǎn)(i,j)和(k,l)，我們用(i,j)→來表示路徑(....

圖2.3遞歸構(gòu)造的無(wú)故障哈密爾頓圈

圖2.3遞歸構(gòu)造的無(wú)故障哈密爾頓圈.3Fault-freehamiltoniancyclesproducedbyrecursiveco窩環(huán)的容錯(cuò)哈密爾頓性們假設(shè)六角形蜂窩環(huán)中某個(gè)6-圈上距離為3，我們稱這個(gè)6-圈為故障6-圈。我們的任務(wù)就造無(wú)故障哈密爾頓....

圖2.11GHT(2,12,8)–{(0,0),(1,0)}中的無(wú)故障哈密爾頓圈

hamiltoniancycleofGHT≤k≤2d1,2≤h≤2(2,k+h1)的路徑+h1)→(1,k+h1),kh+1)的路徑h+1)→(1,kh+1)窩環(huán)G....

本文編號(hào)：3931149