[發明專利]大規模集群系統的數據傳輸網絡及其構建方法

無效

• 申請號: 201010176149.7
• 申請日: 2010-05-13
• 公開（公告）號: CN101883039A
• 公開（公告）日: 2010-11-10
• 發明（設計）人: 胡凱;丁毅;蔣樹;陳陸佳;張新宇
• 申請（專利權）人: 北京航空航天大學
• 主分類號: H04L12/44
• 分類號: H04L12/44
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及一種用于數據傳輸的通信網絡及其構建方法，特別是應用于大規模計算機集群網絡的數據傳輸的通信網絡及其構建方法。

背景技術

傳統的集群網絡監測工具一般采用C/S架構，1對n的通信模型，當計算規模在幾十個節點以下時還可以獲得較好的性能，而當計算規模擴展到幾百甚至幾千、上萬時，這樣的通信模型顯然無法滿足網絡監測工具通信的性能需求。本發明旨在解決這一問題，通過研究傳統模型的通信瓶頸，使用經典的LogP模型對并行計算網絡進行分析，證明了使用基于樹形網絡的層次通信模式的必要性和優越性，并開發出基于樹形的通信網絡，以滿足大規模計算環境下的網絡監測工具的通信需求，并可提供給其他具有相似需求的并行工具或相關平臺使用。

LogP模型是一個比較經典的分析并行計算機網絡通信性能的模型，具有簡單、精確、適用范圍廣等特點，本發明通過對LogP模型分析，證明采用樹形的層次通信模型相比傳統的1對n通信模型更具有合理性和優越性。

LogP模型假設并行系統是一個分布式存儲的、點到點通信的結構，包括數以千計的節點，每個節點具有強大的處理器和內存，使用具有明顯延遲和有限帶寬的網絡進行通信，使用四個主要參數來描述通信網絡，其分別是：

■L(Latency)：網絡延遲的上界，通信中消息從源節點到目的節點的時間；

■o(overhead)：額外開銷，表示處理器發送或接收一條消息所消耗的時間(包含操作系統核心開銷和網絡軟件的開銷)，這期間處理器不能做其他計算；

■g(gap)：間隔，處理器連續發送和接收消息的最小時間間隔，其倒數相應于處理器的通信帶寬；

■P(Processor)：并行系統中的處理器個數或者存儲器模塊數。

LogP模型使用L、o、g和P四個簡單的參數精確的描述了并行系統中的網絡通信特征，同時屏蔽了網絡拓撲、路由算法和通信協議等細節。因為有L和g的限制，這樣的網絡容量是有限的，任何時刻在任何兩個節點之間最多有L/g個消息在傳遞，處理器試圖發送超過這個數目的消息則要等待。盡管網絡拓撲對網絡性能的影響也很大，但是LogP模型中忽略了這一點，因為研究發現包含上千個節點的網絡，不管是超立方體、蝶形或胖樹拓撲結構，其平均的性能差別僅有2倍，所以忽略網絡拓撲不影響對整個網絡的建模。

下面的幾個參數(L、o、g)單位為處理器的CPU周期數，其取值視具體的網絡有所不同，我們采用的方法是，如果網絡帶寬是w，跳數為H，中繼節點的延遲是r，要傳送的消息是M位大小，發送開銷和接收開銷分別為T_send和T_recv，b是處理器對剖寬度，比較合理的選擇是：

o＝(T_send+T_recv)/2??????(1)

L＝H*r+M/w??????????????(2)

g＝M/b??????????????????(3)

下面使用LogP模型簡單分析一下傳統的1對n通信模式和基于樹形的層次通信模式的不同。首先使用LogP研究人員給出的8節點最優廣播樹作為例子說明這兩種模式下通信的流程，并計算一下分別的時間消耗。這里按照上文中給出的值取四個參數分別為P＝8，L＝6，g＝4，o＝2，這樣的分析并不涉及具體的并行系統，參數的取值并不會影響對問題性質的分析。圖1中給出了8個節點時1對n通信模式的拓撲結構和使用LogP模型對其通信過程的詳細分析，容易看出，根節點逐個向每個葉子節點廣播消息，每個節點上的數字代表其收到消息的時間，從開始發送到最后一個節點收到消息總共花費了34個CPU周期。圖2中給出的是二層的樹形通信結構，圖形中各個數值的含義與圖1相同，只不過根節點只向1、2、3、5四個節點發消息，這四個節點再分別把消息發送給自己的子節點，最后消息廣播遍全網的時間是24個CPU周期。

下面把上面的兩種情況做一下推廣，假設網絡中有n個節點，而n剛好等于2^h-1，也就是說這些節點恰巧可以用來組成一顆高度為h的滿二叉樹，根節點需要把一個消息廣播到全網。首先分析1對n的情況，這種情況下一個根節點和其余的n-1個節點直接相連，必須逐個的把消息發送到每一個子節點，整個廣播的完成時間是：

T_flat＝(2^h-3)g+2o+L????(4)

然后設想這n個節點組成了一顆高度為h的滿二叉樹，節點數為n＝2^h-1，第i層的節點個數為2^i-1，根據LogP模型，整個廣播的完成時間是：