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

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

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

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

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

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