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

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

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

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

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

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