本站小編為你精心準備了混合網絡拓撲論文參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

1相關工作

常見的直接網絡拓撲有Mesh／Torus、Flat－tenedButterfly、Dragonfly等。Mesh／Torus網絡拓撲（k－ary，n－cube）（如圖1和圖2所示）是一個n維網格，每一維上有k個節點，相鄰節點之間有通道相連，其節點規模為kn。Mesh／Torus網絡拓撲結構具有較優良的特性。Mesh／Torus網絡拓撲結構十分簡單，具有高度的規則性，易于布局布線，便于實際部署，也具有很好的擴展性。Mesh／To－rus網絡拓撲結構具有廣泛的應用，比如64個節點的Tilera［5］、TRIPS［6］處理器、RAW處理器［7］，還有英特爾Teraflops［8］，都是采用2－DMesh網絡拓撲結構。但是，隨著節點規模的擴大，其劣勢就表現出來了。這主要體現在網絡直徑增大、吞吐率下降等。Mesh／Torus網絡拓撲是早期提出的經典網絡拓撲，由于其結構簡單、性能較好一直沿用至今。為了滿足日益增長的性能要求和節點規模增大的情況，KimJ等人［9］于2007年提出了Flat－tenedButterfly（如圖3所示）網絡拓撲結構，這種結構利用高階（High－radix）路由器［10］將每個路由節點與之同維的所有路由器節點相連，這樣每一維上的跳數就變成了1。一個n維、每一維規模為k的FlattenedButterfly（k－ary，n－cube）網絡拓撲上的數據包的路由跳數最多為n跳。FlattenedBut－terfly網絡中的每個高階路由器能連接多個計算終端（p），整個網絡能夠連接總共p×kn個終端。KimJ的實驗表明，FlattenedButterfly豐富的鏈路特性使得網絡性能得到提升，但是物理開銷的增加也是巨大的。2009年KimJ又相繼提出層次化［11］的Dragonfly（如圖4所示）拓撲結構［12］。Dragonfly網絡拓撲可以分為三層。在最底層，每個路由器節點連接p個計算終端。在中間層，也就是在局部組內，每個路由器與組內a－1個路由器相連。在最高層，每個局部組內總共b×a跳全局通道與其余局部組進行相連。Dragonfly拓撲結構實際上是基于光通信技術的發展提出的。對于鏈路較長的全局通道，采用光纖通信來代替電信號通信，這樣可以大大降低全局通信的延時，局部組內由于距離較短，仍然采用電信號通信。為了更好地進行均衡負載，將參數p和b取同值，將a取為2p或者2b。Dragonfly拓撲結構能夠獲得比較好的性能，如延時相對較低、跳步數較短。但是，同時也可以看到，Dragonfly網絡拓撲具有很差的擴展性，全局通道的延時仍然會較大。實際中應用Dragonfly拓撲結構的系統有Cray［13］和IBM的PERCS［14］。

常見的間接網絡有FatTree［15］、Butterfly等。FatTree（如圖5所示）是一種是應用很廣泛的間接網絡拓撲結構。最早由LeisersonCE于1985年提出，當時提出的FatTree是一個標準的Bina－ryTree結構，樹的每個葉子節點連接p個計算終端，每個葉子節點又有p條鏈路連接其父親節點，越高層的節點所連接的鏈路數就越多，也就顯得越來越“fat”。由于每一路由器節點的開關規模差異較大，不利于實際應用，后來經過不斷發展變化，形成了每級節點開關規模一致的FatTree結構。FatTree網絡拓撲結構中間路由器較多，鏈路非常豐富，能夠使網絡獲得比較好的性能，其缺點是開銷較大、成本較高。Butterfly（如圖6所示）網絡拓撲結構是一種經典間接網絡結構，對于確定的終端數N和開關度為2k的Butterfly具有最短的網絡直徑logkN＋1，雖然有此優點，但是其缺點也是很明顯的。首先Butterfly網絡具有很差的路徑多樣性，對于每一個從源節點到目的節點的數據包，其路由路徑是唯一的；其次Butterfly級與級之間的鏈路較長，這會增加電信號傳送鏈路的延時。對于第一個缺點，可以對Butterfly網絡拓撲結構做一些改變，比如增加級數來解決這一問題。在間接拓撲網絡中使用Butterfly的有BBNButterfly［16］等。為了應對節點規模擴大的情況，要對網絡拓撲的結構做一些調整。對于直接網絡，擴展的方式有兩種方式。第一種方式是擴展每一維上的路由節點規模。第二種方式是擴展網絡拓撲的維數。第一種方式簡單，每個路由器節點的端口數不會改變，易于部署，但是其缺點是隨著跳數的增大，吞吐率等性能會急劇下降，在節點數較大的情況下一般不采用這種擴展方式。第二種擴展網絡維數的方法是一個可行的方法，它會使網絡拓撲節點的基數增大，但數據包在網絡中的跳數增加緩慢。通過實驗發現，在相同節點規模下，維數較大的網絡拓撲的性能要優于低維的網絡拓撲性能。比如To－fu結構就是采用6－D的Mesh來解決這一問題的。但是，增加維數會給實際部署帶來較大難度，維數越大，難度也變得越大。對于間接網絡拓撲結構，其擴展的方法是增加間接網絡拓撲的級數，這種方式能夠給系統帶來比較好的性能，具有廣泛的應用，比如Tianhe－2就是采用FatTree這種間接網絡結構來實現的。但是，間接網絡的弊端是物理開銷太大。隨著終端規模的增大，級數會變大，中間路由節點會急劇增多。RobertoP等人［4］在2012年提出了一種新型混合拓撲結構，這種新型的混合拓撲結構（Hybridtopology，后續內容的圖表中將這種拓撲結構簡稱為“HD”）是結合了直接網絡和間接網絡的優點而提出的。本文將這種新型混合網絡拓撲結構的參數表示為（k－ary，n－direct，m－indirect，p－c）。k代表每一維的節點數，n代表網絡的維數，m代表間接網絡的級數，p代表每個路由節點所連接的終端數，若網絡節點所連接的終端數為1，則該參數可缺省。如圖7所示為這種新型混合拓撲結構。每一維上的節點布局類似于Mesh／Torus網絡，只是相鄰節點之間并沒有鏈路相連，而是通過每一維所在的間接網絡進行相連。每個間接網絡的級數m視每一維的節點規模而定，比如k值較小，間接網絡的級數可以小到僅僅為1，也就是說每一維上的間接網絡就是一個Crossbar。如果k值較大，間接網絡可以為m級的FatTree網絡。每個直接網絡的節點可以連接多于一個的計算終端。計算終端連接數為p的混合拓撲結構網絡所連接的終端規模為p×kn。這種新型混合拓撲結構有一些比較好的靜態特性。相對于直接網絡，新型混合拓撲結構的直徑要比普通直接網絡的直徑小很多。在網絡拓撲規模比較小的情況下，間接網絡可以為一個交叉開關Crossbar，其網絡直徑僅為2n（n表示網絡拓撲維數），而普通直接網絡拓撲結構，比如Torus，其網絡直徑為k／2×logkN。同等節點規模下網絡直徑的減小能夠減小網絡的延時，提升吞吐率。另外一方面，規模比較小的間接網絡（FatTree），其層數要比同等節點規模的FatTree要小很多，整個混合網絡拓撲的路由節點數、鏈路數要比完全間接網絡小很多，因此其開銷會比完全間接網絡小。文獻［4］對這種新型的混合網絡拓撲與傳統的直接網絡、間接網絡性能進行了比較，得出的結果是新型混合拓撲結構的吞吐率性能要優于Mesh／Torus、FatTree等網絡，但比FlattenedButterfly要差。

2新型混合拓撲結構的優化

新型混合拓撲結構Hybrid的每一維上均由以FatTree為代表的間接網絡相連接，這實際上可以將規模為（k－ary，n－direct，m－indirect，p－c）的混合拓撲結構看成由規模為（k1／m－ary，m×logkp＋m×n－tree）的FatTree網絡分解為n×kn－1個規模為（k1／m－ary，m－tree）的FatTree，然后將這些FatTree的葉節點組成直接網絡。這樣做的好處是可以降低FatTree的級數，減小數據包路由的跳數。但是，當每一維上的節點規模增大時，間接網絡（FatTree）的級數仍然較高。本文提出一種解決的方法，就是每一維上的節點由多個間接網絡相連接。本文提出的改進優化的混合拓撲結構（Hy－brid－Ytopology，后續內容的圖表中將簡稱為“HY”）是將Hybrid網絡每一維上的間接網絡由原來的單個間接網絡改造成多個間接網絡。這些間接網絡的葉節點的鏈路相間地與Hybrid網絡同一維上的節點相連接，Hybrid網絡同一維上的節點若連接著不同的間接網絡，則將這些節點用鏈路連接起來。

2.1Hybrid－Y拓撲結構描述Hybrid－Y拓撲網絡結構每一維上的間接網絡和Hybrid拓撲網絡結構的間接網絡一樣，可以是一個簡單的Crossbar或者多級FatTree。Hy－brid－Y拓撲網絡結構和Hybrid拓撲網絡結構的差異體現在兩個方面：（1）間接網絡與每一維節點的連接方式不同。Hybrid網絡拓撲結構的間接網絡葉節點（或者Crossbar）的鏈路依次分別與同維直接網絡的節點相連接。Hybrid－Y拓撲網絡結構的s個間接網絡的葉節點的鏈路相互交替地與同維直接網絡的節點相連接。（2）直接網絡中節點之間的連接方式不同。Hybrid網絡拓撲結構的直接網絡節點之間沒有鏈路連接，Hybrid－Y網絡拓撲結構直接網絡某一維中的節點若連接著不同的間接網絡，就將這些節點用鏈路連接起來。下面引入如表1的參數來描述這個改進優化的混合拓撲結構。描述拓撲結構表達式的參數之間需要滿足一定的條件。對于某一維上的直接網絡連接的間接網絡，參數k和參數s、m需要滿足這樣的條件：s×lm＝k，其中l代表間接網絡，也就是FatTree每個葉節點所連接的終端數。對于給定的k值，參數s、m都是可以發生相應改變的。即便是參數s指定了，也就是每一維上的間接網絡的個數確定了，間接網絡的級數m也可能會有變化。若m取值為1，那么間接網絡是一個規模為（k／s）×（k／s）的Crossbar；若m取大于1的值，則間接網絡是一個FatTree，這個FatTree網絡在m值給定后也就確定了。如圖8是這種改進拓撲結構的一個實例。這個圖中的直接網絡每一維上由兩個間接網絡相連接。直接網絡上的節點00連接間接網絡00－0，節點01連接間接網絡00－1，節點00與節點01連接著不同的間接網絡，因此有一條鏈路連接節點00與節點01。同樣，節點02也有一條鏈路與節點03相連。注意，節點01與節點02雖然連接著不同的間接網絡，但是這兩個節點之間并不用鏈路連接，這是因為這兩個節點已經與它們相鄰的連接著不同間接網絡的節點相連了。

2.2Hybrid－Y網絡路由策略在Hybrid－Y拓撲結構上主要采用了兩種路由算法：維序路由和自適應路由。為了突出Hy－brid－Y拓撲結構的分析研究，本文將不對間接網絡內部的路由進行分析，在后續所講的維序路由和自適應路由，其間接網絡都是文獻［18］中使用的針對FatTree的基本自適應路由算法。Hybrid－Y網絡拓撲的維序路由算法可以分為兩個階段。第一個階段為跨維。在n維的Hy－brid－Y網絡上執行維序路由算法首先要從數據包的源節點所在的維路由到目的節點所在的維。為了更好地描述這一過程，我們將數據包從某一維路由到另外一維這兩維所決定的平面依據節點序號的遞增方向劃分為x軸方向和y軸方向。維序路由算法在執行跨維路由計算時統一執行先x軸方向后y軸方向或者先y軸方向后x軸方向。執行的x軸或者y軸方向確定后，具體沿著哪一條路徑從一維跨到另外一維取決于直接網絡每一維上的路由策略了，也就是第二階段了。第二階段為維內路由。簡單來說，維內路由就是數據包如何從同一維上的一個節點路由到另外一個節點，這個過程是Hybrid－Y網絡拓撲維序路由算法的關鍵步驟，它決定著網絡的數據包路由跳數和延時。本文在實現這一過程時采用下面的策略。源節點和目的節點只有可能是直接網絡中的節點，消息包所在的當前節點有可能是直接網絡中的節點也有可能是間接網絡中的節點。情景1源節點、當前節點s和目的節點d均是直接網絡中的節點。（1）若當前節點s和目的節點d相鄰且有鏈路連接，則數據包直接從當前節點路由到目的節點，如圖9a所示；（2）如當前節點s和目的節點d不相鄰，但是當前節點s和目的節點d連接著相同的間接網絡，則數據包從當前節點s路由到其所連接的間接網絡，如圖9b所示；（3）若當前節點s和目的節點d不相鄰，且連接著不同的間接網絡，則數據包從當前節點s路由到與節點s有鏈路相連并且連接著與目的節點d相同間接網絡的節點，如圖9c所示。路由算法執行上面三個步驟就可以將數據包在同一維上從當前節點路由到目的節點。策略（3）的做法能夠保證網絡的流量相對均衡，不至于都去爭搶直接網絡中相鄰節點之間的鏈路而導致直接網絡節點之間鏈路的擁塞。（1）數據包從當前節點在間接網絡內執行基本自適應路由算法朝著目的節點d的方向路由。情景2只有一種策略情形，這是因為情景2是依賴于情景1的，情景1中策略（3）的執行能夠保證情景2只有唯一一種路由策略。至于間接網絡內部的路由，這里不加以分析。對于Hybrid－Y網絡拓撲的自適應路由算法，其路由執行過程也可以分為與維序路由算法類似的兩個階段：跨維階段和維內路由階段，但是每個階段有所不同。在跨維階段，自適應路由算法的不同點在于能夠動態選擇x軸方向或者y軸方向，其判斷的依據是x軸方向和y軸方向鏈路通道的擁塞情況。路由算法將數據包沿著x和y方向鏈路通道中擁塞狀況較好的方向路由。在維內路由階段，其不同點體現在情景1中的策略（3）。維序路由算法中策略（3）的做法是為了保證網絡流量的相對均衡，減小擁塞情況，但自適應路由算法將依據直接網絡相鄰節點鏈路擁塞情況與所連接的間接網絡鏈路通道擁塞情況相比較，選擇擁塞情況較小的鏈路通道路由，從而能夠考慮到網絡中鏈路通道的實際擁塞情況，避開擁塞較嚴重的鏈路通道，從而能夠改善網絡性能。對于自適應路由可能存在的死鎖問題，根據路由路徑的選擇，可從兩個方面分析：（1）路由路徑經過間接網絡。在這種情況下，由于間接網絡是FatTree，所以不會發生死鎖。（2）路由路徑不經過間接網絡。出現這種可能的唯一情形如圖10a所示，節點a、b、c和d分別有鏈路相連接。當這些節點之間的數據包路由路徑構成相關環時，就有可能發生死鎖。為了避免這種情形的發生，使用虛通道的分配來避免死鎖。如圖10b所示，節點a、b、c和d之間的物理通道被劃分為兩個虛通道，分別標記為虛通道0和虛通道1。為了打破相關環路，當節點a、b、c和d之間的數據包的原地址編號和目的地址編號是升序時，使用虛通道0，當數據包的原地址編號和目的地址編號是降序時，使用虛通道1。分配虛通道后，圖10a中的路徑相關環就不存在了，也就避免了死鎖的發生。

3性能評估

本文將改進的混合拓撲結構（Hybrid－Y）與新型混合拓撲結構（Hybrid）、FatTree、Mesh、To－rus、FlattenedButterfly進行比較。我們的模擬工具是時鐘精確模擬器Booksim2．0［19］，混合拓撲結構的間接網絡都是基于FatTree的網絡。模擬的時候，數據包packet的尺寸都取10個flit，模擬的流量模式為均衡模式uniform，路由算法采用維序路由，網絡維數均為2－D。此外，在節點規模較大的情況下（本文指節點數為1024），對FatTree網絡和混合拓撲結構以及改進優化的混合拓撲結構在worst－case流量模式下進行性能的比較。

3.1模擬實驗結果分析圖11是在均衡流量模式下，64個節點規模的網絡吞吐率模擬結果。從這個圖中可以看出，FlattenedButterfly取得了最低的延時和最高的吞吐率，然后依次是改進的混合拓撲結構Hybrid－Y和新型混合拓撲結構Hybrid，結果顯示最差的是Torus和Mesh。當網絡節點規模增加到256個時，如圖12a所示，結果顯示FlattenedButterfly仍然能夠獲得最低的延時和最高的吞吐率，但這些都是建立在較高的開銷基礎之上的。改進的混合拓撲結構Hybrid－Y（間接網絡級數大于1）獲得了次之的吞吐率。同時注意到，間接網絡級數大于1的混合拓撲結構Hybrid－Y的基本延時要比新型混合拓撲結構Hybrid（這里指間接網絡級數小于4）高，從圖12b的模擬跳步數可以看出，間接網絡級數為3的混合拓撲結構Hybrid－Y的跳步數是10．5，新型混合拓撲結構Hybrid的平均跳步數分別為4．75和7．75。混合拓撲結構Hybrid－Y（間接網絡級數大于1的情況）的基本延時要比新型混合拓撲結構Hybrid（這里指間接網絡級數小于4）高的原因是線頭阻塞效應（Head－Of－LineBloc－king）［20］。Mesh和Torus仍舊是表現最差的網絡拓撲，這也說明了Mesh和Torus的2－D結構不適合作為大規模互連網絡的拓撲結構。將節點規模增加到1024，如圖13所示，能夠得到類似的結論。FatTree網絡在大規模節點的巨型機系統具有廣泛的應用。如圖14所示，在流量模式為worst－case的情況下，混合拓撲結構和改進優化的混合拓撲結構均獲得了比FatTree更好的吞吐率。對于新型混合拓撲結構Hybrid與改進優化混合拓撲結構Hybrid－Y，在間接網絡級數相近的情況下（圖示中Hybrid的間接網絡級數為5，Hy－brid－Y間接網絡級數為4），改進優化的Hybrid－Y網絡擁有更好的網絡性能。對于維數高于2－D的情形能夠得到類似的結果。

3.2性能開銷比的比較和分析比較不同拓撲結構網絡的指標有很多，比如平均和最大跳步數、對分帶寬［21］、網絡鏈路數量和交叉開關規模等。為了更好地將改進的混合拓撲結構Hybrid－Y和新型混合拓撲結構Hybrid進行比較，這里采用文獻［1］中提出的網絡開銷評價指標，即鏈路（Links）數量、交叉開關（Switches）數量和交叉開關單元（SwitchingElements）規模。網絡拓撲的硬件開銷比較將采用交叉開關單元規模作為指標。網絡的性能評價指標采用基本延時和吞吐率。基本延時和交叉開關單元規模的乘積越低，表示網絡拓撲性能就越好；吞吐率和交叉開關單元規模的比值越高，表示網絡拓撲的性能就越好。表2列出了這兩種混合拓撲結構的鏈路數、開關單元規模、交叉開關數的計算式。表3列出了Hybrid－Y網絡拓撲和Hybrid網絡拓撲模擬實驗的相關參數，包括基本延時（也稱為0負載延時）、吞吐率（Throughput）、鏈路數、開關單元、交叉開關（Switches），以及性能比較的參數“吞吐率／開關單元”、“基本延時×開關單元”。當節點規模為64時，間接網絡為Crossbar（間接網絡級數為1）的新型混合拓撲結構Hybrid的基本延時要比間接網絡同為Crossbar的改進的混合拓撲結構Hybrid－Y的基本延時要小，這是因為改進的混合拓撲結構Hybrid－Y的直接網絡中每一維上有兩個Crossbar，而新型混合拓撲結構Hy－brid只有一個Crossbar，因此Hybrid－Y網絡中數據包的平均跳步數（Hop）要比Hybrid網絡的大。但是，Hybrid－Y網絡的吞吐率要比Hybrid網絡的高，其原因是其線頭阻塞（Head－Of－LineBlocking）效應較之要弱。對于間接網絡級數大于1（即多級FatTree）的情形，Hybrid－Y網絡與Hybrid網絡的“吞吐率／開關單元”性能指標幾乎持平，但是Hybrid－Y網絡“基本延時×開關單元”性能指標要優于Hybrid。當節點規模增大到256時，間接網絡為Cross－bar的Hybrid－Y網絡的上述兩項性能指標要明顯優于Hybrid，分別提升了92％和37．8％。同時注意到，間接網絡級數為3的Hybrid－Y網絡的上述兩項性能指標介于間接網絡分別為2和4的Hy－brid網絡。若繼續將節點規模增大，達到1024時，從表3中可以觀察到，間接網絡為Crossbar或者多級FatTree的Hybrid－Y網絡拓撲的兩項性能指標比Hybrid網絡拓撲的均要好。從上述的模擬結果分析可以得出這樣的結論，Hybrid－Y網絡的性能與物理開銷和Hybrid網絡相比，特別是在較大規模情況下，Hybrid－Y網絡的性能與物理開銷要優于Hybrid網絡。在實際應用的時候，可以根據應用的需求尋求合適的參數配置，使得Hybrid－Y網絡的優勢更加突出。

4結束語

本文通過對新型混合拓撲結構Hybrid的分析發現，網絡規模較大時，間接網絡的級數會隨著網絡規模的增加而增大，從而增加網絡延遲。對于這些問題，提出將混合拓撲結構Hybrid每一維上單個間接網絡改進為多個間接網絡，再按照一定的規則將直接網絡中對應的節點用鏈路通道連接起來的改進混合拓撲結構Hybrid－Y。模擬實驗結果表明，在網絡規模較大時，改進后的混合拓撲結構Hybrid－Y的性能指標“吞吐率／開關單元”和“基本延時×開關單元”要優于Hybrid的。在實際應用中，可以根據實際應用情況調整Hybrid－Y網絡的參數配置，以便獲得更優的性能。

作者：楊明英雷斐董德尊沈勝宇龐征斌單位：國防科學技術大學計算機學院