[發明專利]一種基于超立方體的可擴展并行計算互連網絡拓撲結構

無效

• 申請號: 200810232462.0
• 申請日: 2008-11-28
• 公開（公告）號: CN101414952A
• 公開（公告）日: 2009-04-22
• 發明（設計）人: 劉有耀;楊曉強;杜慧敏;張麗果;韓俊剛
• 申請（專利權）人: 西安郵電學院
• 主分類號: H04L12/46
• 分類號: H04L12/46;H04L12/56
• 代理公司: 西安文盛專利代理有限公司
• 代理人: 彭冬英

技術領域

本發明屬于并行計算技術領域，特別是一種基于超立方體的可擴展并行計算互連網絡拓撲結構。

背景技術

隨著硬件技術的不斷發展，特別是超大規模集成電路工藝的發展，使得包含成千上萬處理器的大規模多處理器系統成為可能。例如CM(ConnectionMachine)多處理器包含多達2¹⁶個處理器。隨著多處理器系統規模不斷擴大，網絡拓撲結構對如此大規模的多處理器系統的性能具有重要的影響，為了提高并行計算的通信效率，人們一直在研究結構簡單、節點度小、網絡直徑小以及良好可擴展的互連網絡拓撲結構。由于超立方體的拓撲結構具有正規性、對稱性、強容錯性、短直徑、可嵌入性等特殊性質，是一種最為重要和最具吸引力的并行計算機互連網絡拓撲結構。

在超立方體網絡拓撲中節點的編碼極大的方便了路由算法的實現，然而，隨著網絡規模的增大，節點度也隨之增加，使得設計和制造變得更加困難，并且超立方體不具有可擴展性，因此，在實際應用中超立方體互連網絡受到了限制。立方環(Cube?Connected-Cycles)是一個節點度為3的拓撲結構，平衡了網絡直徑和節點度，但是該網絡限制節點度為3降低了它的性能，而且路由算法的實現較超立方體的復雜。許多基于超立方體的互連網絡，都和超立方體相似不具有可擴展性并且它們的路由算法實現較超立方體的復雜，使得它們的應用受到了限制。兩個基于超立方體的可擴展互連網絡被提出，但是它們的路由算法實現較超立方體的復雜。

發明內容

本發明的目的是：針對現有超立方體拓撲結構不可擴展性問題以及一些基于超立方體的路由算法復雜問題，提出一種基于超立方體的可擴展并行計算互連網絡拓撲結構。該網絡節點編碼可以采用格雷編碼和約翰遜編碼，使得基于超立方體拓撲結構的各種算法可以不做任何修改直接應用到該互連網絡拓撲結構中。

本發明的技術解決方案是：一種基于超立方體的可擴展并行計算互連網絡拓撲結構，稱之為雙環超立方體(Double-Ring?Hypercube，DRH(m，d))拓撲結構，該拓撲結構DRH(m，d)由4m×2^d個節點和2^d+1×m×(d+3)條鏈路組成，對于4m×2^d個節點和2^d+1×m×(d+3)條鏈路的DRH(m，d)互連網絡拓撲由下述部分構成：1)首先，2^d個節點連接成d維超立方體網絡拓撲結構，共得到4m個d維超立方體，對每個d維超立方體的節點按照超立方體的定義進行編號；2)將4m個d維超立方體中節點編號相同的節點連接成雙環(Double-Ring，DR(2m))互連網絡拓撲結構，共得到d個DR(2m)，即可得到DRH(m，d)互連網絡拓撲結構，DRH(m，d)拓撲結構是對稱正規互連網絡，任意節點的連接度均為d+3；任意兩個節點間的距離最大值為m+d+1；網絡的等分寬度為m×2^d+1。

所述的DRH(m，d)網絡拓撲結構節點采用如下編碼方法，每個節點編碼由兩部分(A_h，A_d)組成，其中A_d采用m+1位二進制約翰遜碼為每個超立方體的編碼，A_h采用d位二進制格雷碼為超立方體內節點的編碼，對DRH(m，d)互連網絡拓撲中任意兩個節點A(A_m+d，...，A_m+1A_mA_m-1，...，A₁A₀)，B(B_m+d，...，B_m+1B_mB_m-1，...，B₁B₀)，A_i，B_i∈{0，1}，i∈{0，1，...，m+d}，則A，B之間的距離