

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
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)網絡仍
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 交叉立方體及加強交叉立方體互連網絡容錯性質的研究.pdf
- 故障超立方體變形網絡路由算法的研究.pdf
- 局部扭曲立方體路由算法研究.pdf
- 超立方體網絡容錯模型及其路由算法研究.pdf
- 局部紐立方體和交叉立方體容錯性研究.pdf
- 基于負載均衡的超立方體網絡容錯路由算法研究.pdf
- 超立方體圖上的容錯路由算法研究.pdf
- Mobius立方體互連網絡容錯路由選擇算法研究.pdf
- 交換超立方體網絡下的容錯路由研究.pdf
- 超立方體網絡模擬實驗平臺和容錯路由算法研究.pdf
- 交叉扭立方體的建模與分析.pdf
- 加強超立方體容錯圈嵌入問題的研究.pdf
- 超立方體網絡中容錯路由的可靠性研究.pdf
- 超立方體網絡中多播路由優(yōu)化策略研究.pdf
- 46500.超立方體最長圈嵌入問題的研究
- 局部扭曲立方體容錯路由策略研究.pdf
- 具有大量錯誤結點的超立方體網絡容錯模型和容錯路由算法研究.pdf
- 交叉立方體容錯路徑嵌入和容錯邊泛圈性研究.pdf
- 交叉立方體里有條件邊錯誤的容錯圈嵌入.pdf
- 邊故障的超立方體中圈嵌入問題之研究.pdf
評論
0/150
提交評論