《拓撲網絡_折疊式Clos拓撲在片上網絡中的應用》由會員分享，可在線閱讀，更多相關《拓撲網絡_折疊式Clos拓撲在片上網絡中的應用（11頁珍藏版）》請在裝配圖網上搜索。
1、拓撲網絡_折疊式Clos拓撲在片上網絡中的應用
摘要:隨著半導體與集成電路技術的進步,網絡中用于連接芯片的路由設備得到了很大的發(fā)展。通過引入新的技術,路由的“度”數(shù)得到了增加,即單個路由可連接的芯片數(shù)目變得越來越多,這種路由被稱為“高度數(shù)”路由。該種路由結構可以顯著降低網絡延遲和開銷,必將在以后得到大量應用。本文將淺析使用該種路由的折疊式Clos拓撲結構在片上網絡中的應用,比較該拓撲結構與其他拓撲性能的優(yōu)劣,介紹幾種針對自適應路由算法的中間級模塊分配策略。 關鍵詞:片上網絡;折疊式克勞斯網絡;拓撲結構 The Application of The Folded-Clos
2、Topology on Chip GUO Bin, WANG Changshan (School of Computer Xidian University) Abstract: As the advancement of semiconductor technics and integrated circuits, the routing device which is used to connect chips in the network has great development. Through the introduction of new technolo
3、gy, the degree of routing which is named ‘high radix’ routing has increased and the number of cores connected on one routing has increased. The high-radix routers will be widely used in future, as it can effectively reduce latency and cost of the network. This paper introduces the application of the
4、 folded-clos network, which can take advantage of high-radix routers. We compare the performance of the folded-clos network and other topologies and introduce some allocation strategies of mid-stage models, which fit for adaptive routing algorithm in this paper. Key words: NoC; the folded-clos net
5、work; topology 1引言 片上網絡(NoC)于20世紀末期被提出,作為一種新型的技術,國際國內對它的研究都還處于初級階段。提出的初衷是為解決片上系統(tǒng)(SoC)在可擴展性、能耗、時鐘統(tǒng)一性、重用性以及服務質量等方面的局限性。其核心思想是將計算機網絡技術移植到芯片設計中來,用網絡結構來取代傳統(tǒng)的總線結構,通過使用可控電參數(shù),使得通信與計算分離,從而提供良好的通信與處理能力。片上網絡拓撲結構定義了片上網絡中的通信節(jié)點是如何在芯片中分布和連接的。作為網絡非常重要的一個特性,它對整個網絡的性能有很重要的影響。 隨著集成電路中信號處理速度的加快,出現(xiàn)了高帶寬的路由片。
6、對于傳統(tǒng)的低度數(shù)拓撲結構,并不能充分發(fā)揮高度數(shù)路由的優(yōu)勢?；谡郫B式Clos拓撲結構的網絡則可以通過運用該種技術提供比傳統(tǒng)網絡更低的延遲,獲得更高的吞吐。 本文主要介紹了折疊式Clos網絡在片上網絡中的應用,分析其使用的路由算法,并通過仿真來驗證其性能的好壞。 2拓撲結構介紹 Charles Clos 在1953 年提出了后來以他名字命名的Clos拓撲結構。最常見的Clos拓撲網絡是3級Clos網絡V(m,n,r),如圖1所示,它擁有n個輸入輸出級模塊。每個Clos網絡都如同是兩個蝴蝶網絡疊加起來,其中一個的輸出級與另一個的輸入級疊加。Clos網絡中每個交換模塊內部結
7、構都是一個crossbar結構,按照crossbar原理模式進行工作。 Clos網絡可以通過使用較小的交換單元來構建較大容量的交叉矩陣。由于其任意輸入輸出對之間都有多種路由可選擇,故它的可靠性很好。并且通過交換模塊的橫向增加,很容易完成對網絡的擴充,其可擴展性很好。 Clos網絡的路由過程為由輸入級輸入,經由任意一個中間級交換單元后再從輸出級輸出。由于Clos網絡的級數(shù)總為奇數(shù)個,我們可以以最中間的那一級為中軸,將Clos網絡折疊起來,形成折疊式Clos網絡。圖2即為圖1所示Clos網絡所對應形成的折疊式Clos網絡。與傳統(tǒng)的Clos網絡使用單向鏈路不同,折疊式Clos網絡使用雙
8、向鏈路進行通信。與傳統(tǒng)的Clos網絡不同,該網絡的路由過程并不需要通過所有的中間級路由模塊來完成。由于折疊式Clos拓撲結構可以充分地發(fā)揮高度數(shù)路由的優(yōu)勢,它已經被應用于很多網絡當中。 3路由算法分析 3.1 路由算法介紹 對于一個片上網絡,合適的路由算法可以降低網絡延遲,保證網絡負載平衡。按照算法是否具有自適應性分類,可以分為無關路由和自適應路由。無關路由又可分為確定性路由和隨機路由。無關路由算法不考慮網絡流量及擁塞狀況,其中確定性路由算法是基于網絡拓撲和平均分組時延要求,以某一固定的準則來選擇分組的路徑;而隨機路由是隨機決定分組路徑。自適應路由基于某個在時間上不
9、固定的準則來選擇在某一段時間內有效的路徑。 對于Clos網絡,數(shù)據包在路由過程中必然要經過所有的中間級交換單元。但折疊式Clos網絡并不需要,數(shù)據包由輸入端口進入網絡之后所要做的就是找一個合適的“交匯點”。該“交匯點”到輸入端口與輸出端口都存在可使用的空閑路徑。一旦數(shù)據包到達該點,即可直接發(fā)送往輸出端口,而無需經過所有的中間級。 在路由過程中,首先在最低級的中間級模塊中查找看是否有鏈路存在可以完成路由請求。若有則直接建立鏈接完成通信請求;若沒有,則將請求傳向高一級中間模塊,使用該級中間模塊來完成路由請求。 在折疊式Clos網絡中,確定性路由算法與自適應路由算法均可使用。確定性
10、路由算法由于其分組路徑的選擇方式已確定,故實現(xiàn)起來比較簡單,但靈活性不高,容易造成擁塞。而自適應路由算法則相對比較復雜,它需要根據當時的網絡狀況來為每個數(shù)據包選擇中間級交換單元,但它具有路徑多樣性,靈活度比較高,可以很好的降低網絡擁塞發(fā)生的概率。故總體性能來講,自適應路由算法要優(yōu)于確定性路由算法。 一般在實現(xiàn)過程中,由輸入端路由到“交匯點”時使用自適應算法,由“交匯點”到輸出端的過程使用確定性路由算法。 3.2 自適應路由算法的中間模塊分配策略 當輸入節(jié)點與輸出節(jié)點并沒有連接在同一路由模塊上時,完成它們間的路由就需要使用中間級的路由模塊,這樣便涉及到中間級路由模塊的分配問題。
11、 以下是幾種中間級路由模塊分配策略的介紹: (1) 隨機分配策略(random):使用隨機函數(shù),為每一個連接請求在其可用的中間模塊集中隨機分配一個中間模塊,如果該集合為空則建立失敗。 (2) 順序分配策略(sequential):為每個請求分配模塊時從第k個中間模塊開始順序分配,在仿真部分中我們按照從左到右的順序選擇最左邊的中間模塊為開始模塊來進行仿真分析。 (3) 輪循分配策略(round-robin):與順序分配類似,如果上一次請求占用了第n個中間模塊,那么下一個請求就從第n+1個中間模塊開始。 (4) 最多空閑端口優(yōu)先策略:優(yōu)先分配空閑端口
12、最多的中間模塊,如果不成功再分配負載較輕的中間模塊。如果幾個中間模塊的空閑端口數(shù)量相同,則排除上次路由請求使用過的模塊之后,在剩余的模塊中隨機選擇一個進行路由。 隨機分配策略未考慮中間級模塊的空閑端口狀態(tài),使用隨機方法選取模塊。由于順序分配策略均勻地選取中間級模塊,它造成的網絡延遲要比隨機分配策略低。最多空閑端口優(yōu)先策略則考慮到了中間級模塊的網絡狀態(tài),它的性能要優(yōu)于以上幾種策略,網絡延遲最低。 3.3 重排算法介紹 當網絡中沒有空閑中間模塊可以分配給新到的請求時則發(fā)生網絡阻塞,可以通過對網絡中已有的鏈路進行重排,以釋放出可用的中間模塊,從而滿足新到的請求。 每當有新的路由
13、請求到達時,就將已經建立的請求和新到來的請求進行一次統(tǒng)一的處理,完成全網的輸入輸出匹配,該種調整方法稱為一次統(tǒng)一調整算法。由于該算法每次都要對整個網絡進行調整,需要調整的鏈路數(shù)量較多,工作量比較大。 如果對于一個新來的鏈路請求,先在第一級中間級交換模塊中查找有無空閑模塊可以完成路徑建立,若無則對網絡中部分鏈路進行調整,以完成鏈路請求。如果調整后仍無法完成路徑建立,則對第二級中間模塊進行調整來完成鏈路請求。該種算法被稱為逐條調整算法。 使用重排算法雖然可以滿足更多的鏈路請求,降低網絡的延遲,但是會引入額外的鏈路調整開銷。如果重排引入的鏈路調整數(shù)量高于降低的鏈路阻塞數(shù)量,反而會使整個網絡的
14、性能降低。 4仿真與分析 本文使用OPNET仿真軟件來完成對折疊式Clos網絡拓撲結構和算法進行了仿真,以此來評估折疊式Clos網絡的性能,同時我們使用相同的網絡設置來對其他幾種常見的拓撲結構進行了仿真比較。 4.1 仿真參數(shù)設定 1) 網絡拓撲結構規(guī)模:各個拓撲結構都采用16節(jié)點的模型。節(jié)點注入率設定:仿真中注入率使用bitscycle的網絡發(fā)送一個數(shù)據包需要32個cycles。 2) 數(shù)據包結構設定:仿真中數(shù)據包的長度可以變化,最小值為32bits。其中包的ID號占15bits,包的源節(jié)點與目標節(jié)點橫縱坐標各占4個bits。 3) 結點模型的設
15、定:使用source-sink對來完成包的產生和銷毀。開始由source模塊生成并發(fā)送數(shù)據包,結束時到達sink模塊,由它來完成數(shù)據量的統(tǒng)計,并對各種類型的包進行銷毀。 4) 網絡規(guī)模的設定:仿真所用的所有拓撲結構均采用16個結點的規(guī)模,即由這16個結點來發(fā)送并接受數(shù)據包,期間的路由過程由其他路由結點來完成。 4.2 仿真結果分析 1) 圖3是不同注入率下各種拓撲結構的端到端時延與吞吐率的比較。 從圖中可以看出,由于折疊式Clos網絡豐富的路徑多樣性,提供了多條可選路徑,使得該拓撲結構具有自適應性,向上路由時擁塞情況很少,端到端延遲和吞吐率方面都有很好的表現(xiàn)。在ETE-
16、delay性能圖中,折疊式Clos網絡一直保持著很低的延遲,直到注入率(offered load)增至0.4時才有了顯著的上升。而其他兩種拓撲結構則在0.2 - 0.3處延遲即有了明顯的增高。在吞吐性能圖中,同樣直到注入率增至0.4時折疊式Clos網絡的吞吐才逐漸保持水平不變,吞吐性能相比其他兩種拓撲提高了近30%左右。當?shù)竭_0.4時,折疊式Clos網絡的吞吐量到達其飽和點,隨著注入率的增加,性能基本保持不變。 2) 圖4是不同注入率下不同中間級模塊分配策略的性能比較。 從圖中可以看出,由于最多空閑端口優(yōu)先策略在選取中間級模塊過程中考慮到了該模塊的實時狀態(tài),優(yōu)先選擇空閑端口多的
17、模塊,可以明顯減少網絡擁塞 ,減低網絡延遲,因此在時延與吞吐率方面都有良好的表現(xiàn)。 隨機策略由于都會使中間級模塊負載達到基本均衡,相比于其他幾種策略延遲和吞吐都不是很理想。順序選擇策略與輪詢策略可以保證每個中間模塊被等概率的選到,將網絡請求均勻地分布到各個中間模塊,其性能要優(yōu)于隨機策略。 5結論 折疊式Clos拓撲結構可以充分發(fā)揮高度數(shù)路由的優(yōu)勢,可以顯著降低網絡的延遲與開銷。本文分析比較了用于折疊式Clos網絡中的路由分配算法。由于自適應路由算法在路由過程中會考慮到當時的網絡狀態(tài),并根據此做出路由選擇,因此相比于確定性路由算法,合適的自適應路由算法可以更好地提高路由
18、網絡的性能,降低網絡延遲。 對于自適應路由算法,我們提供了幾種中間級模塊分配策略,介紹了模塊重排的思想。選擇空閑端口最多的模塊來發(fā)送這種策略充分考慮到了路由的狀態(tài),避免多個請求擁擠到同一路由,從而造成排隊等待而增加了路由延遲,它的性能最佳。隨機策略與輪循策略無視了網絡與路由器的狀態(tài),它們的性能較差,但實現(xiàn)起來比較簡單。 隨著路由的發(fā)展,折疊式Clos拓撲結構會被更多的應用。雖然折疊式Clos網絡在時延與吞吐率方面表現(xiàn)良好,但由于其結構比較復雜,路由過程中的跳數(shù)比較多,從而造成了較高的開銷,在芯片上布線時困難比較大。針對折疊式Clos網絡的這些缺點,如何改善它們是下一步研究的重點。
19、 參考文獻 [1] Kim, J., W.J. Dally and D. Abts.Adaptive routing in high-radix Clos network [R]. x ACM/IEEE Conference on Supercomputing, SC"06, November 11,x - November 17,x. x. Tampa, FL, United states: Association for Computing Machinery. [2] H.Kariniemi, J.Nurmi. Arbitration and Routing Schem
20、es for On-chip Packet Networks [C]. Interconnect-Centric Design for Advanced SoC and NoC,. Kluwer Academic Publishers. x. 253-282. [3] H.Kariniemi, J.Nurmi. Arbitration and Routing Schemes for On-chip Packet Networks. Interconnect-Centric Design for Advanced SoC and NoC [C]. Kluwer Academic Publis
21、hers.x.253 - 282. [4] F. H. Chang, J. Y. Guo, F. K.Wang. Wide-sense nonblocking for symmetric or asymmetric 3-stage Clos networks under various routing strategies [C]. ISSN: 0304 ? 3975. x. 375 - 386. [5] Wenqing Dou, Enyu Yao. On rearrangeable multirate three-stage Clos networks [C]
22、.x. 103-107. [6] Frank K. Hwang, Sheng ? Chyang Liaw. On nonblocking multicast three-stage Clos networks [C].2000. pp. 535-539. [7] P Jose R. Correa, PMichel X. Gomemans. Improved Bounds on Nonblocking 3-Stage Clos Networks [C]. x. pp. 870-894. [8] Phi-Hung Pham, Kumar, Y.,Chulwoo Kim. High
23、Performance and Area-Efficient Circuit-Switched Network on Chip Design [J], Computer and Information Technology, x. CIT "06. The Sixth IEEE International Conference on Sept. x . Page(s):243 - 243 [9] P. Guerrier and A. Greiner. A generic architecture for on-chip packet-switched interconnections [R
24、]. Design, Automaion and Test in Euiope Conference and Exhibition 2000. March,2000. pp.250-256. [10] P. P. Pande, C. Grecu, A. Ivanov and R. Saleh. Design of a switch for network on chip applications [J]. May,2003. Vol.4 pp.1 - 5. (下轉第89頁) [11] Kim, J., et al. Microarchitecture of a high-radix
25、 router[R]. In 32nd Interntional Symposium on Computer Architecture, ISCA x, June 04,x - June 08,x. x. Madison, WI, United states: Institute of Electrical and Electronics Engineers Inc. [12] Hung Q.Ngo. A new routing algorithm for multirate rearrangeable Clos networks [C]. ISSN: 0304-3975. 2003.
26、Page: 2157 - 2167. [13] Tomohiro Morimura, Keisuke Iwai, Hideharu Amano. Hierarchical multistage interconnection network R-Clos[C]. Electronics and Communication in Japan. No.11.x. Part 3, Vol.89. 作者簡介 郭彬,碩士研究生,主要研究領域為片上網絡拓撲結構。 王長山,副教授,碩士研究生導師,主要研究領域為軟件理論與應用和計算機網絡。
拓撲網絡_折疊式Clos拓撲在片上網絡中的應用
