拓?fù)渚W(wǎng)絡(luò)_折疊式Clos拓?fù)湓谄暇W(wǎng)絡(luò)中的應(yīng)用

上傳人:青 文檔編號:17028501 上傳時間:2020-11-06 格式:DOCX 頁數(shù):11 大?。?9.58KB
收藏 版權(quán)申訴 舉報 下載
拓?fù)渚W(wǎng)絡(luò)_折疊式Clos拓?fù)湓谄暇W(wǎng)絡(luò)中的應(yīng)用_第1頁
第1頁 / 共11頁
拓?fù)渚W(wǎng)絡(luò)_折疊式Clos拓?fù)湓谄暇W(wǎng)絡(luò)中的應(yīng)用_第2頁
第2頁 / 共11頁
拓?fù)渚W(wǎng)絡(luò)_折疊式Clos拓?fù)湓谄暇W(wǎng)絡(luò)中的應(yīng)用_第3頁
第3頁 / 共11頁

下載文檔到電腦,查找使用更方便

6 積分

下載資源

還剩頁未讀,繼續(xù)閱讀

資源描述:

《拓?fù)渚W(wǎng)絡(luò)_折疊式Clos拓?fù)湓谄暇W(wǎng)絡(luò)中的應(yīng)用》由會員分享,可在線閱讀,更多相關(guān)《拓?fù)渚W(wǎng)絡(luò)_折疊式Clos拓?fù)湓谄暇W(wǎng)絡(luò)中的應(yīng)用(11頁珍藏版)》請在裝配圖網(wǎng)上搜索。

1、拓?fù)渚W(wǎng)絡(luò)_折疊式Clos拓?fù)湓谄暇W(wǎng)絡(luò)中的應(yīng)用   摘要:隨著半導(dǎo)體與集成電路技術(shù)的進(jìn)步,網(wǎng)絡(luò)中用于連接芯片的路由設(shè)備得到了很大的發(fā)展。通過引入新的技術(shù),路由的“度”數(shù)得到了增加,即單個路由可連接的芯片數(shù)目變得越來越多,這種路由被稱為“高度數(shù)”路由。該種路由結(jié)構(gòu)可以顯著降低網(wǎng)絡(luò)延遲和開銷,必將在以后得到大量應(yīng)用。本文將淺析使用該種路由的折疊式Clos拓?fù)浣Y(jié)構(gòu)在片上網(wǎng)絡(luò)中的應(yīng)用,比較該拓?fù)浣Y(jié)構(gòu)與其他拓?fù)湫阅艿膬?yōu)劣,介紹幾種針對自適應(yīng)路由算法的中間級模塊分配策略。   關(guān)鍵詞:片上網(wǎng)絡(luò);折疊式克勞斯網(wǎng)絡(luò);拓?fù)浣Y(jié)構(gò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引言       片上網(wǎng)絡(luò)(NoC)于20世紀(jì)末期被提出,作為一種新型的技術(shù),國際國內(nèi)對它的研究都還處于初級階段。提出的初衷是為解決片上系統(tǒng)(SoC)在可擴(kuò)展性、能耗、時鐘統(tǒng)一性、重用性以及服務(wù)質(zhì)量等方面的局限性。其核心思想是將計算機(jī)網(wǎng)絡(luò)技術(shù)移植到芯片設(shè)計中來,用網(wǎng)絡(luò)結(jié)構(gòu)來取代傳統(tǒng)的總線結(jié)構(gòu),通過使用可控電參數(shù),使得通信與計算分離,從而提供良好的通信與處理能力。片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)定義了片上網(wǎng)絡(luò)中的通信節(jié)點(diǎn)是如何在芯片中分布和連接的。作為網(wǎng)絡(luò)非常重要的一個特性,它對整個網(wǎng)絡(luò)的性能有很重要的影響。   隨著集成電路中信號處理速度的加快,出現(xiàn)了高帶寬的路由片。

6、對于傳統(tǒng)的低度數(shù)拓?fù)浣Y(jié)構(gòu),并不能充分發(fā)揮高度數(shù)路由的優(yōu)勢?;谡郫B式Clos拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)則可以通過運(yùn)用該種技術(shù)提供比傳統(tǒng)網(wǎng)絡(luò)更低的延遲,獲得更高的吞吐。   本文主要介紹了折疊式Clos網(wǎng)絡(luò)在片上網(wǎng)絡(luò)中的應(yīng)用,分析其使用的路由算法,并通過仿真來驗(yàn)證其性能的好壞。      2拓?fù)浣Y(jié)構(gòu)介紹       Charles Clos 在1953 年提出了后來以他名字命名的Clos拓?fù)浣Y(jié)構(gòu)。最常見的Clos拓?fù)渚W(wǎng)絡(luò)是3級Clos網(wǎng)絡(luò)V(m,n,r),如圖1所示,它擁有n個輸入輸出級模塊。每個Clos網(wǎng)絡(luò)都如同是兩個蝴蝶網(wǎng)絡(luò)疊加起來,其中一個的輸出級與另一個的輸入級疊加。Clos網(wǎng)絡(luò)中每個交換模塊內(nèi)部結(jié)

7、構(gòu)都是一個crossbar結(jié)構(gòu),按照crossbar原理模式進(jìn)行工作。      Clos網(wǎng)絡(luò)可以通過使用較小的交換單元來構(gòu)建較大容量的交叉矩陣。由于其任意輸入輸出對之間都有多種路由可選擇,故它的可靠性很好。并且通過交換模塊的橫向增加,很容易完成對網(wǎng)絡(luò)的擴(kuò)充,其可擴(kuò)展性很好。   Clos網(wǎng)絡(luò)的路由過程為由輸入級輸入,經(jīng)由任意一個中間級交換單元后再從輸出級輸出。由于Clos網(wǎng)絡(luò)的級數(shù)總為奇數(shù)個,我們可以以最中間的那一級為中軸,將Clos網(wǎng)絡(luò)折疊起來,形成折疊式Clos網(wǎng)絡(luò)。圖2即為圖1所示Clos網(wǎng)絡(luò)所對應(yīng)形成的折疊式Clos網(wǎng)絡(luò)。與傳統(tǒng)的Clos網(wǎng)絡(luò)使用單向鏈路不同,折疊式Clos網(wǎng)絡(luò)使用雙

8、向鏈路進(jìn)行通信。與傳統(tǒng)的Clos網(wǎng)絡(luò)不同,該網(wǎng)絡(luò)的路由過程并不需要通過所有的中間級路由模塊來完成。由于折疊式Clos拓?fù)浣Y(jié)構(gòu)可以充分地發(fā)揮高度數(shù)路由的優(yōu)勢,它已經(jīng)被應(yīng)用于很多網(wǎng)絡(luò)當(dāng)中。      3路由算法分析       3.1 路由算法介紹    對于一個片上網(wǎng)絡(luò),合適的路由算法可以降低網(wǎng)絡(luò)延遲,保證網(wǎng)絡(luò)負(fù)載平衡。按照算法是否具有自適應(yīng)性分類,可以分為無關(guān)路由和自適應(yīng)路由。無關(guān)路由又可分為確定性路由和隨機(jī)路由。無關(guān)路由算法不考慮網(wǎng)絡(luò)流量及擁塞狀況,其中確定性路由算法是基于網(wǎng)絡(luò)拓?fù)浜推骄纸M時延要求,以某一固定的準(zhǔn)則來選擇分組的路徑;而隨機(jī)路由是隨機(jī)決定分組路徑。自適應(yīng)路由基于某個在時間上不

9、固定的準(zhǔn)則來選擇在某一段時間內(nèi)有效的路徑。      對于Clos網(wǎng)絡(luò),數(shù)據(jù)包在路由過程中必然要經(jīng)過所有的中間級交換單元。但折疊式Clos網(wǎng)絡(luò)并不需要,數(shù)據(jù)包由輸入端口進(jìn)入網(wǎng)絡(luò)之后所要做的就是找一個合適的“交匯點(diǎn)”。該“交匯點(diǎn)”到輸入端口與輸出端口都存在可使用的空閑路徑。一旦數(shù)據(jù)包到達(dá)該點(diǎn),即可直接發(fā)送往輸出端口,而無需經(jīng)過所有的中間級。   在路由過程中,首先在最低級的中間級模塊中查找看是否有鏈路存在可以完成路由請求。若有則直接建立鏈接完成通信請求;若沒有,則將請求傳向高一級中間模塊,使用該級中間模塊來完成路由請求。   在折疊式Clos網(wǎng)絡(luò)中,確定性路由算法與自適應(yīng)路由算法均可使用。確定性

10、路由算法由于其分組路徑的選擇方式已確定,故實(shí)現(xiàn)起來比較簡單,但靈活性不高,容易造成擁塞。而自適應(yīng)路由算法則相對比較復(fù)雜,它需要根據(jù)當(dāng)時的網(wǎng)絡(luò)狀況來為每個數(shù)據(jù)包選擇中間級交換單元,但它具有路徑多樣性,靈活度比較高,可以很好的降低網(wǎng)絡(luò)擁塞發(fā)生的概率。故總體性能來講,自適應(yīng)路由算法要優(yōu)于確定性路由算法。   一般在實(shí)現(xiàn)過程中,由輸入端路由到“交匯點(diǎn)”時使用自適應(yīng)算法,由“交匯點(diǎn)”到輸出端的過程使用確定性路由算法。    3.2 自適應(yīng)路由算法的中間模塊分配策略   當(dāng)輸入節(jié)點(diǎn)與輸出節(jié)點(diǎn)并沒有連接在同一路由模塊上時,完成它們間的路由就需要使用中間級的路由模塊,這樣便涉及到中間級路由模塊的分配問題。  

11、 以下是幾種中間級路由模塊分配策略的介紹:    (1) 隨機(jī)分配策略(random):使用隨機(jī)函數(shù),為每一個連接請求在其可用的中間模塊集中隨機(jī)分配一個中間模塊,如果該集合為空則建立失敗。    (2) 順序分配策略(sequential):為每個請求分配模塊時從第k個中間模塊開始順序分配,在仿真部分中我們按照從左到右的順序選擇最左邊的中間模塊為開始模塊來進(jìn)行仿真分析。    (3) 輪循分配策略(round-robin):與順序分配類似,如果上一次請求占用了第n個中間模塊,那么下一個請求就從第n+1個中間模塊開始。    (4) 最多空閑端口優(yōu)先策略:優(yōu)先分配空閑端口

12、最多的中間模塊,如果不成功再分配負(fù)載較輕的中間模塊。如果幾個中間模塊的空閑端口數(shù)量相同,則排除上次路由請求使用過的模塊之后,在剩余的模塊中隨機(jī)選擇一個進(jìn)行路由。    隨機(jī)分配策略未考慮中間級模塊的空閑端口狀態(tài),使用隨機(jī)方法選取模塊。由于順序分配策略均勻地選取中間級模塊,它造成的網(wǎng)絡(luò)延遲要比隨機(jī)分配策略低。最多空閑端口優(yōu)先策略則考慮到了中間級模塊的網(wǎng)絡(luò)狀態(tài),它的性能要優(yōu)于以上幾種策略,網(wǎng)絡(luò)延遲最低。    3.3 重排算法介紹    當(dāng)網(wǎng)絡(luò)中沒有空閑中間模塊可以分配給新到的請求時則發(fā)生網(wǎng)絡(luò)阻塞,可以通過對網(wǎng)絡(luò)中已有的鏈路進(jìn)行重排,以釋放出可用的中間模塊,從而滿足新到的請求。   每當(dāng)有新的路由

13、請求到達(dá)時,就將已經(jīng)建立的請求和新到來的請求進(jìn)行一次統(tǒng)一的處理,完成全網(wǎng)的輸入輸出匹配,該種調(diào)整方法稱為一次統(tǒng)一調(diào)整算法。由于該算法每次都要對整個網(wǎng)絡(luò)進(jìn)行調(diào)整,需要調(diào)整的鏈路數(shù)量較多,工作量比較大。   如果對于一個新來的鏈路請求,先在第一級中間級交換模塊中查找有無空閑模塊可以完成路徑建立,若無則對網(wǎng)絡(luò)中部分鏈路進(jìn)行調(diào)整,以完成鏈路請求。如果調(diào)整后仍無法完成路徑建立,則對第二級中間模塊進(jìn)行調(diào)整來完成鏈路請求。該種算法被稱為逐條調(diào)整算法。   使用重排算法雖然可以滿足更多的鏈路請求,降低網(wǎng)絡(luò)的延遲,但是會引入額外的鏈路調(diào)整開銷。如果重排引入的鏈路調(diào)整數(shù)量高于降低的鏈路阻塞數(shù)量,反而會使整個網(wǎng)絡(luò)的

14、性能降低。      4仿真與分析       本文使用OPNET仿真軟件來完成對折疊式Clos網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和算法進(jìn)行了仿真,以此來評估折疊式Clos網(wǎng)絡(luò)的性能,同時我們使用相同的網(wǎng)絡(luò)設(shè)置來對其他幾種常見的拓?fù)浣Y(jié)構(gòu)進(jìn)行了仿真比較。    4.1 仿真參數(shù)設(shè)定    1) 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)規(guī)模:各個拓?fù)浣Y(jié)構(gòu)都采用16節(jié)點(diǎn)的模型。節(jié)點(diǎn)注入率設(shè)定:仿真中注入率使用bitscycle的網(wǎng)絡(luò)發(fā)送一個數(shù)據(jù)包需要32個cycles。    2) 數(shù)據(jù)包結(jié)構(gòu)設(shè)定:仿真中數(shù)據(jù)包的長度可以變化,最小值為32bits。其中包的ID號占15bits,包的源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)橫縱坐標(biāo)各占4個bits。    3) 結(jié)點(diǎn)模型的設(shè)

15、定:使用source-sink對來完成包的產(chǎn)生和銷毀。開始由source模塊生成并發(fā)送數(shù)據(jù)包,結(jié)束時到達(dá)sink模塊,由它來完成數(shù)據(jù)量的統(tǒng)計,并對各種類型的包進(jìn)行銷毀。    4) 網(wǎng)絡(luò)規(guī)模的設(shè)定:仿真所用的所有拓?fù)浣Y(jié)構(gòu)均采用16個結(jié)點(diǎn)的規(guī)模,即由這16個結(jié)點(diǎn)來發(fā)送并接受數(shù)據(jù)包,期間的路由過程由其他路由結(jié)點(diǎn)來完成。    4.2 仿真結(jié)果分析    1) 圖3是不同注入率下各種拓?fù)浣Y(jié)構(gòu)的端到端時延與吞吐率的比較。    從圖中可以看出,由于折疊式Clos網(wǎng)絡(luò)豐富的路徑多樣性,提供了多條可選路徑,使得該拓?fù)浣Y(jié)構(gòu)具有自適應(yīng)性,向上路由時擁塞情況很少,端到端延遲和吞吐率方面都有很好的表現(xiàn)。在ETE-

16、delay性能圖中,折疊式Clos網(wǎng)絡(luò)一直保持著很低的延遲,直到注入率(offered load)增至0.4時才有了顯著的上升。而其他兩種拓?fù)浣Y(jié)構(gòu)則在0.2 - 0.3處延遲即有了明顯的增高。在吞吐性能圖中,同樣直到注入率增至0.4時折疊式Clos網(wǎng)絡(luò)的吞吐才逐漸保持水平不變,吞吐性能相比其他兩種拓?fù)涮岣吡私?0%左右。當(dāng)?shù)竭_(dá)0.4時,折疊式Clos網(wǎng)絡(luò)的吞吐量到達(dá)其飽和點(diǎn),隨著注入率的增加,性能基本保持不變。    2) 圖4是不同注入率下不同中間級模塊分配策略的性能比較。      從圖中可以看出,由于最多空閑端口優(yōu)先策略在選取中間級模塊過程中考慮到了該模塊的實(shí)時狀態(tài),優(yōu)先選擇空閑端口多的

17、模塊,可以明顯減少網(wǎng)絡(luò)擁塞 ,減低網(wǎng)絡(luò)延遲,因此在時延與吞吐率方面都有良好的表現(xiàn)。   隨機(jī)策略由于都會使中間級模塊負(fù)載達(dá)到基本均衡,相比于其他幾種策略延遲和吞吐都不是很理想。順序選擇策略與輪詢策略可以保證每個中間模塊被等概率的選到,將網(wǎng)絡(luò)請求均勻地分布到各個中間模塊,其性能要優(yōu)于隨機(jī)策略。      5結(jié)論       折疊式Clos拓?fù)浣Y(jié)構(gòu)可以充分發(fā)揮高度數(shù)路由的優(yōu)勢,可以顯著降低網(wǎng)絡(luò)的延遲與開銷。本文分析比較了用于折疊式Clos網(wǎng)絡(luò)中的路由分配算法。由于自適應(yīng)路由算法在路由過程中會考慮到當(dāng)時的網(wǎng)絡(luò)狀態(tài),并根據(jù)此做出路由選擇,因此相比于確定性路由算法,合適的自適應(yīng)路由算法可以更好地提高路由

18、網(wǎng)絡(luò)的性能,降低網(wǎng)絡(luò)延遲。      對于自適應(yīng)路由算法,我們提供了幾種中間級模塊分配策略,介紹了模塊重排的思想。選擇空閑端口最多的模塊來發(fā)送這種策略充分考慮到了路由的狀態(tài),避免多個請求擁擠到同一路由,從而造成排隊等待而增加了路由延遲,它的性能最佳。隨機(jī)策略與輪循策略無視了網(wǎng)絡(luò)與路由器的狀態(tài),它們的性能較差,但實(shí)現(xiàn)起來比較簡單。   隨著路由的發(fā)展,折疊式Clos拓?fù)浣Y(jié)構(gòu)會被更多的應(yīng)用。雖然折疊式Clos網(wǎng)絡(luò)在時延與吞吐率方面表現(xiàn)良好,但由于其結(jié)構(gòu)比較復(fù)雜,路由過程中的跳數(shù)比較多,從而造成了較高的開銷,在芯片上布線時困難比較大。針對折疊式Clos網(wǎng)絡(luò)的這些缺點(diǎn),如何改善它們是下一步研究的重點(diǎn)。

19、      參考文獻(xiàn)   [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.   (下轉(zhuǎn)第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.      作者簡介   郭彬,碩士研究生,主要研究領(lǐng)域?yàn)槠暇W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。   王長山,副教授,碩士研究生導(dǎo)師,主要研究領(lǐng)域?yàn)檐浖碚撆c應(yīng)用和計算機(jī)網(wǎng)絡(luò)。

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號:ICP2024067431-1 川公網(wǎng)安備51140202000466號


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng),我們立即給予刪除!