交叉立方體網(wǎng)絡(luò)路由算法與圖嵌入問題的研究.pdf

1、并行計(jì)算機(jī)互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)一直是國(guó)際上的研究熱點(diǎn)。人們已提出了多種互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，其中超立方體是最流行的互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)之一而且已被廣泛用于商業(yè)并行計(jì)算機(jī)系統(tǒng)。但它并不是各方面拓?fù)湫再|(zhì)最好的互連網(wǎng)絡(luò)，于是人們開展了對(duì)超立方體的一類變型，即交叉立方體及其性質(zhì)的研究。研究表明，交叉立方體的某些性質(zhì)優(yōu)于超立方體，尤其是它的直徑幾乎是超立方體的一半，因此是一種值得人們研究并推廣應(yīng)用的互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。本文對(duì)交叉立方體網(wǎng)絡(luò)的最短路徑路由、并行

2、路由、廣播路由、無(wú)死鎖路由、結(jié)點(diǎn)不相交路徑長(zhǎng)度以及交叉立方體環(huán)網(wǎng)絡(luò)的嵌入問題展開了研究。本文的主要研究工作和貢獻(xiàn)如下： (1)針對(duì)已有的交叉立方體網(wǎng)絡(luò)最短路徑路由算法只能將部分最短路徑作為候選路徑進(jìn)行輸出且不具有根據(jù)結(jié)點(diǎn)的繁忙程度進(jìn)行選擇路徑能力的缺點(diǎn)，給出了結(jié)點(diǎn)各邊可進(jìn)行最短路徑路由的充要條件，提出了一種可根據(jù)結(jié)點(diǎn)的繁忙程度進(jìn)行擇路時(shí)間復(fù)雜度為D(n2)的完全自適應(yīng)最短路徑路由算法，其中n為交叉立方體網(wǎng)絡(luò)的維數(shù)。算法在進(jìn)行路由

3、的每一步，都從所有可進(jìn)行最短路徑路由的鄰邊中選擇繁忙程度最低的計(jì)算機(jī)結(jié)點(diǎn)對(duì)應(yīng)的邊進(jìn)行路由，因此是將全部最短路徑作為候選路徑，從而可輸出任意一條最短路徑。仿真實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性。 (2)對(duì)交叉立方體的頂點(diǎn)不相交路徑進(jìn)行了研究，證明了以下結(jié)論：在n維交叉立方體CQn中任意兩頂點(diǎn)間存在n條頂點(diǎn)不相交的路徑，并且滿足①最短路徑的長(zhǎng)度=兩頂點(diǎn)間的距離，②所有路徑中最長(zhǎng)路徑的長(zhǎng)度≤兩頂點(diǎn)間的距離+4。這說(shuō)明交叉立方體互連網(wǎng)絡(luò)具有很好

4、的并行通信性能和容錯(cuò)性能。同時(shí)提出了一種時(shí)間復(fù)雜度為O(n2)的n維交叉立方體網(wǎng)絡(luò)并行路由算法，可輸出源結(jié)點(diǎn)到目的結(jié)點(diǎn)的三條結(jié)點(diǎn)不相交路徑P0，P1，P2，并且滿足①|(zhì)P0|=源結(jié)點(diǎn)到目的結(jié)點(diǎn)的距離，②|Pi|≤源結(jié)點(diǎn)到目的結(jié)點(diǎn)的距離+3(i=1，2)。 (3)在全端口蟲洞模型下，利用遞歸方法將交叉立方體網(wǎng)絡(luò)分解為互不相交的子交叉立方體網(wǎng)絡(luò)，提出了n維交叉立方體網(wǎng)絡(luò)的廣播路由算法，其所需路由步數(shù)為O(n/log2(n+1))，在

5、常數(shù)乘積因子范圍內(nèi)是優(yōu)化的。仿真實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性。 (4)證明了在不使用虛通道的情況下n(n≥3)維交叉立方體網(wǎng)絡(luò)中不存在無(wú)死鎖的最短路徑路由算法，通過(guò)將一個(gè)物理通道分成三個(gè)虛通道提出了一種時(shí)間復(fù)雜度為O(n)的無(wú)死鎖最短路徑蟲洞路由算法。理論分析和仿真實(shí)驗(yàn)結(jié)果表明了算法的有效性。 (5)交叉立方體網(wǎng)絡(luò)具有規(guī)模難以擴(kuò)展(不易升級(jí))的性質(zhì)，而交叉立方體環(huán)網(wǎng)絡(luò)可以有效克服升級(jí)困難的缺點(diǎn)。本文證明了交叉立方體環(huán)網(wǎng)絡(luò)仍