国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

基于偏折路由的雙環(huán)片上網(wǎng)絡(luò)*

2021-04-06 10:48:18齊星云賴明澈???/span>董德尊
關(guān)鍵詞:雙環(huán)結(jié)點(diǎn)網(wǎng)絡(luò)結(jié)構(gòu)

齊星云,戴 藝,賴明澈,???,董德尊

(國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院,湖南 長(zhǎng)沙 410073)

1 引言

隨著集成電路工藝的不斷進(jìn)步,片上多處理器芯片CMP(Chip-Multi-Processor)中集成了多個(gè)處理器核。為了實(shí)現(xiàn)多個(gè)處理器核之間的高速數(shù)據(jù)通信,片上網(wǎng)絡(luò)NoC(Network on Chip)應(yīng)運(yùn)而生。單個(gè)芯片上集成的處理器核數(shù)目從1個(gè)增長(zhǎng)到數(shù)十甚至數(shù)百個(gè),片上網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)也出現(xiàn)了Mesh、Torus和Crossbar等多種形態(tài),同時(shí)也出現(xiàn)了一些商業(yè)化的片上網(wǎng)絡(luò)結(jié)構(gòu)[1,2]。

然而,隨著網(wǎng)絡(luò)規(guī)模的增大和邏輯設(shè)計(jì)復(fù)雜度的增加,當(dāng)前大規(guī)模片上網(wǎng)絡(luò)設(shè)計(jì)面臨的一個(gè)重要問(wèn)題就是硬件資源消耗過(guò)大,局部布線密度過(guò)高。這是因?yàn)?,在基于Crossbar的片上網(wǎng)絡(luò)中,任意一對(duì)輸入端口和輸出端口之間都具有獨(dú)立的數(shù)據(jù)通路,因此內(nèi)部數(shù)據(jù)通路隨著端口數(shù)目的增加成平方增長(zhǎng);而且一般需要經(jīng)過(guò)多級(jí)交換才能實(shí)現(xiàn)輸入端口到輸出端口的數(shù)據(jù)轉(zhuǎn)發(fā),所以導(dǎo)致大量的數(shù)據(jù)總線和控制總線互相交叉。同時(shí),為了避免各端口之間的競(jìng)爭(zhēng)訪問(wèn),Crossbar中設(shè)計(jì)了大量的數(shù)據(jù)緩存,用來(lái)暫存競(jìng)爭(zhēng)失敗、暫時(shí)不能繼續(xù)傳輸?shù)臄?shù)據(jù)。當(dāng)網(wǎng)絡(luò)端口數(shù)目較多且內(nèi)部數(shù)據(jù)總線較寬時(shí),在芯片內(nèi)部進(jìn)行后端布局布線時(shí),大量的存儲(chǔ)器占用了芯片的硅片面積,而且大量的全局長(zhǎng)線占用了有限的全局布線通道,使得芯片局部出現(xiàn)嚴(yán)重的布線擁塞,影響布線的順利進(jìn)行以及后端時(shí)序的收斂。同時(shí),過(guò)于復(fù)雜的邏輯設(shè)計(jì),使得路由器內(nèi)部報(bào)文處理流水線變長(zhǎng),報(bào)文延時(shí)增大。盡管工藝的進(jìn)步可以在一定程度上提高時(shí)鐘頻率,但隨著工藝尺寸的不斷變小以及摩爾定律的逐漸失效,提高頻率的困難度逐漸增加,對(duì)性能的改進(jìn)也微乎其微。以上問(wèn)題正逐漸成為困擾NoC設(shè)計(jì)的關(guān)鍵因素,已經(jīng)不能簡(jiǎn)單地通過(guò)提高實(shí)現(xiàn)工藝,使用高性能庫(kù)單元來(lái)解決了。

另一方面,我們注意到在實(shí)際的互連網(wǎng)絡(luò)中,特別是在CMP系統(tǒng)中,片上網(wǎng)絡(luò)主要承擔(dān)各處理器核之間的Cache一致性協(xié)議報(bào)文的傳輸,其網(wǎng)絡(luò)流量的特點(diǎn)是報(bào)文粒度較小,網(wǎng)絡(luò)負(fù)載較低,但對(duì)報(bào)文延時(shí)特性要求較高[3]。但是,芯片中除了片上網(wǎng)絡(luò)之外,還有多核處理器會(huì)占用大量的硅片面積,這就要求片上網(wǎng)絡(luò)不能占用太多硬件資源。在這種情況下,研究人員在設(shè)計(jì)CMP系統(tǒng)的片上網(wǎng)絡(luò)時(shí),不需要特別強(qiáng)調(diào)網(wǎng)絡(luò)的高吞吐率,而是需要一種資源占用少、設(shè)計(jì)簡(jiǎn)單、硬件資源消耗少、延時(shí)低的片上網(wǎng)絡(luò)來(lái)滿足要求。這些約束條件要求研究人員給出一種新的片上網(wǎng)絡(luò)設(shè)計(jì)方案,來(lái)從根本上解決這些問(wèn)題。

當(dāng)前的NoC設(shè)計(jì)中使用交叉開關(guān)進(jìn)行多個(gè)端口之間的數(shù)據(jù)交換。當(dāng)多個(gè)輸入端口的報(bào)文在競(jìng)爭(zhēng)同一個(gè)輸出端口時(shí),需要將競(jìng)爭(zhēng)失敗的端口報(bào)文緩存起來(lái),所以在NoC中不可避免地需要大量存儲(chǔ)器,用來(lái)緩存數(shù)據(jù)報(bào)文。經(jīng)統(tǒng)計(jì),NoC大部分芯片面積被存儲(chǔ)器占據(jù),這樣使得后端布線更加困難,而且增加了芯片的功耗和生產(chǎn)成本。

針對(duì)上述問(wèn)題,本文提出了一種基于偏折路由的雙環(huán)片上網(wǎng)絡(luò)結(jié)構(gòu)。其思路是,盡量簡(jiǎn)化路由器邏輯設(shè)計(jì)和網(wǎng)絡(luò)結(jié)點(diǎn)之間的連接,用規(guī)則的環(huán)形布線代替以往的交叉互連來(lái)進(jìn)行路由器之間的互連。同時(shí),為了避免單個(gè)環(huán)網(wǎng)造成的性能低下,本文給出了一種雙環(huán)結(jié)構(gòu),2個(gè)并行的環(huán)網(wǎng)同時(shí)工作,以提高網(wǎng)絡(luò)的帶寬。實(shí)驗(yàn)結(jié)果表明,這種雙環(huán)網(wǎng)絡(luò)結(jié)構(gòu)能夠很好地滿足當(dāng)前中等規(guī)模片上網(wǎng)絡(luò)的通信需求。

2 相關(guān)背景和研究現(xiàn)狀

2.1 片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

自從Dally等[4]在21世紀(jì)初提出了片上網(wǎng)絡(luò)的概念后,片上網(wǎng)絡(luò)技術(shù)得到了迅猛的發(fā)展。在這些片上網(wǎng)絡(luò)中,二維Mesh網(wǎng)絡(luò)[5]是一種典型的結(jié)構(gòu),它通過(guò)將m×n個(gè)結(jié)點(diǎn)組織成m行n列的網(wǎng)格結(jié)構(gòu)來(lái)實(shí)現(xiàn)片上結(jié)點(diǎn)間的數(shù)據(jù)通信。例如,Intel 的單芯片微處理器TeraFLOPS[6]內(nèi)包含80 個(gè)核,通過(guò)一個(gè)8×10 的Mesh結(jié)構(gòu)[7]互連在一起。另外一種典型的片上網(wǎng)絡(luò)結(jié)構(gòu)是Torus[5],與Mesh結(jié)構(gòu)相比,它增加了每一維上頭尾之間的連接,將Mesh中每一維的直線鏈路變成了環(huán)形鏈路。YARC(Yet Another Router Chip)[24]結(jié)構(gòu)也是一種典型的路由器結(jié)構(gòu),它將片上網(wǎng)絡(luò)分解成多個(gè)瓦片(Tile),每個(gè)Tile對(duì)應(yīng)1個(gè)網(wǎng)絡(luò)端口,在布局上,Tile排列成行列結(jié)構(gòu),Tile之間通過(guò)行列總線相連。這種交換結(jié)構(gòu)避免了片內(nèi)交換時(shí)的布線擁塞,當(dāng)網(wǎng)絡(luò)端口數(shù)目較多時(shí)也能實(shí)現(xiàn)無(wú)阻塞的高性能數(shù)據(jù)交換。同時(shí),隨著3D堆疊技術(shù)的成熟,3D NoC結(jié)構(gòu)也迅速發(fā)展[9,10]。在先進(jìn)的制造工藝基礎(chǔ)上,采用TSV(Through Silicon Via)技術(shù)能夠在硅片上制造出具有多層電路的3D芯片[11],從而較為容易地將3D Mesh和3D Torus結(jié)構(gòu)映射到實(shí)際的電路中[9,12]。

報(bào)文在傳統(tǒng)的NoC中路由時(shí),每經(jīng)過(guò)一個(gè)路由結(jié)點(diǎn)都需要進(jìn)行接收、緩存、路由計(jì)算、端口分配和仲裁以及報(bào)文重新發(fā)送等過(guò)程。隨著芯片集成度的不斷提高和CMP中處理器核數(shù)目的增加,芯片密度迅速增大,布線困難大大提升,系統(tǒng)功耗快速增長(zhǎng),采用Mesh、Torus或YARC這種傳統(tǒng)互連結(jié)構(gòu)的片上網(wǎng)絡(luò),逐漸面臨著設(shè)計(jì)復(fù)雜、功耗過(guò)高和硬件資源消耗過(guò)大等問(wèn)題[6,8,10,13]。這迫使研究人員尋求一種低復(fù)雜度的設(shè)計(jì)方案,這時(shí)環(huán)形網(wǎng)絡(luò)結(jié)構(gòu)又一次被提了出來(lái)。

2.2 環(huán)形網(wǎng)絡(luò)

環(huán)形網(wǎng)絡(luò)是一種簡(jiǎn)單的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),環(huán)上的每個(gè)結(jié)點(diǎn)只與其鄰居結(jié)點(diǎn)通信。最開始,由于性能的原因,環(huán)形網(wǎng)絡(luò)結(jié)構(gòu)只用于小規(guī)模處理器之間的簡(jiǎn)單互連和組網(wǎng)。為了解決環(huán)網(wǎng)規(guī)模增大時(shí)網(wǎng)絡(luò)帶寬過(guò)低的問(wèn)題,許多學(xué)者提出了層次式環(huán)網(wǎng)結(jié)構(gòu)[14,15]。在這種層次式環(huán)網(wǎng)中,多個(gè)局部子環(huán)通過(guò)路由結(jié)點(diǎn)連接到全局環(huán)網(wǎng)上,并以這種形式擴(kuò)展出多級(jí)層次結(jié)構(gòu)。這樣的層次式環(huán)形網(wǎng)絡(luò)將局部網(wǎng)絡(luò)流量限制在局部環(huán)網(wǎng)上,減少了網(wǎng)絡(luò)帶寬消耗,提高了網(wǎng)絡(luò)性能。為了進(jìn)一步提高環(huán)形網(wǎng)絡(luò)的性能,一些環(huán)形網(wǎng)絡(luò)的變形結(jié)構(gòu)不斷涌現(xiàn)出來(lái)。Spidergon網(wǎng)絡(luò)結(jié)構(gòu)[16]在環(huán)形網(wǎng)絡(luò)的基礎(chǔ)上增加了環(huán)上對(duì)面結(jié)點(diǎn)之間的直連通路,以較小的硬件代價(jià)縮短了網(wǎng)絡(luò)直徑。Cubic Ring結(jié)構(gòu)[17]則在Torus網(wǎng)絡(luò)某一維度上保留一條完整的環(huán)形鏈路,并去掉該維度上其他所有的環(huán)形鏈路,即刪掉Torus網(wǎng)絡(luò)中某一維上的某些鏈路,只在該維上保留少量鏈路,這樣可以用較小的硬件代價(jià)獲得相對(duì)較好的網(wǎng)絡(luò)性能。隨著光互連技術(shù)和硅基光器件逐漸走向應(yīng)用,片上光互連網(wǎng)絡(luò)中也經(jīng)常采用環(huán)形網(wǎng)絡(luò)結(jié)構(gòu)[18,19]。傳統(tǒng)的環(huán)形網(wǎng)絡(luò)雖然具有結(jié)構(gòu)簡(jiǎn)單的優(yōu)點(diǎn),但是容易產(chǎn)生死鎖,并且在路由過(guò)程中每一個(gè)中間結(jié)點(diǎn)都要消耗一定的輸入緩存,這不僅帶來(lái)排隊(duì)延時(shí)和硬件開銷,而且還增加了網(wǎng)絡(luò)的復(fù)雜度和芯片功耗。

2.3 偏折路由

偏折路由(Deflection Routing)[3,20]是到達(dá)路由器的多個(gè)報(bào)文競(jìng)爭(zhēng)同一個(gè)鏈路資源時(shí)使用的一種沖突解決方法。其思想是在多個(gè)報(bào)文競(jìng)爭(zhēng)使用同一個(gè)輸出端口而發(fā)生沖突時(shí),通過(guò)適當(dāng)?shù)闹俨盟惴?,使得其中一個(gè)報(bào)文競(jìng)爭(zhēng)成功并有權(quán)使用該端口,而其他報(bào)文從路由器的其他端口送出,在網(wǎng)絡(luò)上繞道傳輸,并按照路由算法重新選擇下一條鏈路。采用這種偏折路由,當(dāng)報(bào)文競(jìng)爭(zhēng)端口失敗時(shí),不需要進(jìn)行緩存排隊(duì),而只需要選擇另外一個(gè)端口繼續(xù)在網(wǎng)絡(luò)中傳輸即可。卡內(nèi)基·梅隆大學(xué)的研究者提出的CHIPPER(Cheap-Interconnect Partially Permuting Router)路由器[21,22]就是一個(gè)典型的基于偏折路由算法實(shí)現(xiàn)的片上網(wǎng)絡(luò)路由器,該路由器通過(guò)偏折路由消除了路由器內(nèi)部的數(shù)據(jù)緩存,簡(jiǎn)化了路由器設(shè)計(jì),降低了功耗。文獻(xiàn)[13,23-25]研究了片上網(wǎng)絡(luò)的無(wú)緩存偏折路由問(wèn)題。在文獻(xiàn)[24,25]中,當(dāng)沖突產(chǎn)生時(shí),需要將報(bào)文丟棄,這帶來(lái)了一定的復(fù)雜性。

3 雙環(huán)片上網(wǎng)絡(luò)結(jié)構(gòu)

3.1 拓?fù)浣Y(jié)構(gòu)

本文將偏折路由思想與環(huán)形網(wǎng)絡(luò)結(jié)構(gòu)相結(jié)合,提出了一種基于偏折路由的雙環(huán)片上網(wǎng)絡(luò)結(jié)構(gòu)。在這種結(jié)構(gòu)中,每個(gè)路由器(router)由網(wǎng)絡(luò)接口輸入輸出邏輯(ni_in/ni_out)和路由仲裁單元(router_arb)模塊組成。每個(gè)處理單元PE(Processing Element)通過(guò)ni與一個(gè)路由器相連,多個(gè)路由器之間采用2個(gè)同向的環(huán)形網(wǎng)絡(luò)(ni0/ni1)連接起來(lái)。圖1給出了由4個(gè)結(jié)點(diǎn)組成的雙環(huán)片上網(wǎng)絡(luò)。

Figure 1 4×4 bi-ring NoC

在基于偏折路由的雙環(huán)片上網(wǎng)絡(luò)結(jié)構(gòu)中,網(wǎng)絡(luò)流量劃分成4個(gè)虛通道VC(Virtual Channel),各VC之間相互獨(dú)立,分時(shí)使用實(shí)際的物理鏈路。ni_in中包含一個(gè)4 VC的輸入buffer,用來(lái)緩存由PE送來(lái)的報(bào)文。ni_in按照公平輪轉(zhuǎn)的策略,從4個(gè)VC的數(shù)據(jù)buffer中仲裁出1個(gè)VC的報(bào)文,送給router_arb。router_arb除了與ni_in和ni_out之間的接口之外,還具有另外2個(gè)輸入端口和輸出端口,分別連接到2個(gè)環(huán)形網(wǎng)絡(luò)上。由ni_in送來(lái)的報(bào)文根據(jù)環(huán)網(wǎng)鏈路的狀態(tài),使用路由算法選擇從哪個(gè)網(wǎng)絡(luò)端口發(fā)出報(bào)文。報(bào)文按照0-1-2-3的順序在4個(gè)路由器上依次傳輸。如果報(bào)文到達(dá)目的結(jié)點(diǎn),并且目的結(jié)點(diǎn)的ni_out端口空閑,則被對(duì)應(yīng)的路由器吸收并送到目的PE;否則繼續(xù)在網(wǎng)絡(luò)鏈路上傳輸,直至下一次到達(dá)目的結(jié)點(diǎn)。

當(dāng)有報(bào)文從路由器的某個(gè)輸入端口到達(dá)時(shí),路由器首先判斷報(bào)文的目的結(jié)點(diǎn)是否為本地結(jié)點(diǎn)。如果目的結(jié)點(diǎn)不是本地結(jié)點(diǎn),則沿著報(bào)文在環(huán)網(wǎng)中傳輸?shù)姆较?,從?duì)應(yīng)的輸出端口將報(bào)文送出。如果有且只有1個(gè)輸入端口有報(bào)文到達(dá),其目的結(jié)點(diǎn)為本地結(jié)點(diǎn),并且本地ni_out允許接收?qǐng)?bào)文,則將此報(bào)文通過(guò)ni_out送給本地處理結(jié)點(diǎn);否則,采用偏折路由,使此報(bào)文沿著傳輸方向從路由器的輸出端口上送出,繼續(xù)在網(wǎng)絡(luò)中傳輸,直到下一次到達(dá)目的結(jié)點(diǎn)。如果2個(gè)輸入端口都有報(bào)文到達(dá),且其目的結(jié)點(diǎn)均為本地處理結(jié)點(diǎn),則首先按照路由算法選出某一個(gè)端口的報(bào)文,使其競(jìng)爭(zhēng)端口成功;然后再按照前面的方法,決定是將其通過(guò)ni_out送給處理單元,還是通過(guò)偏折路由使其沿著網(wǎng)絡(luò)繼續(xù)傳輸。

3.2 路由算法

在基于偏折路由的雙環(huán)片上網(wǎng)絡(luò)結(jié)構(gòu)中,每個(gè)路由器各有2個(gè)輸入端口和2個(gè)輸出端口與環(huán)網(wǎng)相連。為了簡(jiǎn)化路由算法,本文規(guī)定在雙環(huán)片上網(wǎng)絡(luò)中,ni0網(wǎng)絡(luò)的優(yōu)先級(jí)高于ni1網(wǎng)絡(luò)的優(yōu)先級(jí);如果網(wǎng)絡(luò)上有報(bào)文到達(dá)目的結(jié)點(diǎn),當(dāng)ni0網(wǎng)絡(luò)中有報(bào)文時(shí),則優(yōu)先將ni0上的報(bào)文送到目的結(jié)點(diǎn)的ni_out端口;當(dāng)ni0網(wǎng)絡(luò)中沒有報(bào)文時(shí),則將ni1網(wǎng)絡(luò)中的報(bào)文送給ni_out。

當(dāng)PE有報(bào)文需要發(fā)送到網(wǎng)絡(luò)中時(shí),路由器首先檢測(cè)2個(gè)輸出端口所對(duì)應(yīng)的網(wǎng)絡(luò)鏈路是否空閑。如果都空閑,或者只有ni0端口空閑,則將報(bào)文送到ni0網(wǎng)絡(luò)中;如果只有ni1端口空閑,則將報(bào)文送到ni1網(wǎng)絡(luò)中;如果所有端口都忙,則PE中的報(bào)文繼續(xù)在結(jié)點(diǎn)中排隊(duì)等待,直到網(wǎng)絡(luò)中有空閑端口出現(xiàn)。

本文采用類似Verilog的語(yǔ)法對(duì)該路由算法進(jìn)行描述,具體的雙環(huán)片上網(wǎng)絡(luò)路由算法如算法1所示。

算法1雙環(huán)片上網(wǎng)絡(luò)路由算法

定義ni0_in_pkt,ni1_in_pkt,ni0_out_pkt,ni1_out_pkt分別為每個(gè)路由器上ni0和ni1端口輸入和輸出的報(bào)文;ni_in_pkt和ni_out_pkt分別為ni_in和ni_out端口上的報(bào)文;vld(pkt)表示報(bào)文pkt是否有效;ad(pkt)表示報(bào)文pkt當(dāng)前到達(dá)的結(jié)點(diǎn)是否為目的結(jié)點(diǎn)。

ifni_outis idle

if(vld(ni0_in_pkt) &ad(ni0_in_pkt))

ni_out_pkt=ni0_in_pkt;

ni0_out_pkt=0;

ni1_out_pkt=ni1_in_pkt;

elseif(vld(ni1_in_pkt) &ad(ni1_in_pkt))

ni_out_pkt=ni1_in_pkt;

ni0_out_pkt=ni0_in_pkt;

ni1_out_pkt=0;

else

ni0_out_pkt=ni0_in_pkt;

ni1_out_pkt=ni1_in_pkt;

else//ni_outis NOT idle

ni0_out_pkt=ni0_in_pkt;

ni1_out_pkt=ni1_in_pkt;

ifvld(ni_in_pkt)

if(~vld(ni0_out_pkt))

ni0_out_pkt=ni_in_pkt;

elseif(~vld(ni1_out_pkt))

ni1_out_pkt=ni_in_pkt;

采用這樣的思路,整個(gè)路由器的設(shè)計(jì)將非常簡(jiǎn)單,只在與處理單元PE的接口處(ni_in)有一個(gè)小的緩存隊(duì)列,用來(lái)暫存由于鏈路忙而無(wú)法及時(shí)發(fā)出的數(shù)據(jù)。報(bào)文在網(wǎng)絡(luò)中路由時(shí),若不能被目的結(jié)點(diǎn)接收,則一直在網(wǎng)絡(luò)中傳輸而不需要進(jìn)行緩存。這樣極大地減少了芯片中的存儲(chǔ)器,去掉了對(duì)報(bào)文緩存排隊(duì)的管理,降低了設(shè)計(jì)復(fù)雜度和硬件開銷。

3.3 路由算法分析

首先,算法1中的路由算法是無(wú)死鎖的。這個(gè)結(jié)論比較明顯。因?yàn)榫W(wǎng)絡(luò)中死鎖形成的條件是有報(bào)文占據(jù)著緩存,同時(shí)又在等待網(wǎng)絡(luò)下一跳鏈路上的緩存,互相等待緩存資源,形成一個(gè)資源相關(guān)的環(huán),就會(huì)發(fā)生死鎖。在本文提出的基于偏折路由的雙環(huán)片上網(wǎng)絡(luò)中,路由器中沒有緩存,報(bào)文不會(huì)在路由器上存儲(chǔ),即不會(huì)形成互相等待緩存資源的情形,報(bào)文在未到達(dá)目的結(jié)點(diǎn)之前將一直在環(huán)形網(wǎng)絡(luò)上持續(xù)傳輸,因此不會(huì)產(chǎn)生死鎖。

其次,該路由算法是無(wú)活鎖的。在處理單元(PE)允許接收到達(dá)的報(bào)文時(shí),如果網(wǎng)絡(luò)發(fā)生活鎖,即意味著有報(bào)文在網(wǎng)絡(luò)中一直傳輸而始終不能到達(dá)目的結(jié)點(diǎn)。而在本文提出的網(wǎng)絡(luò)中不會(huì)存在這種情況。因?yàn)?,?duì)于雙環(huán)片上網(wǎng)絡(luò)中ni0鏈路上的某個(gè)報(bào)文,經(jīng)過(guò)有限跳步數(shù)肯定可以到達(dá)目的結(jié)點(diǎn),此時(shí)如果PE允許接收?qǐng)?bào)文,則該報(bào)文必定會(huì)從ni0鏈路上送給PE,從而空出ni0鏈路;由于雙環(huán)片上網(wǎng)絡(luò)中結(jié)點(diǎn)數(shù)是有限個(gè),則在有限時(shí)間內(nèi),網(wǎng)絡(luò)中所有ni0鏈路上的報(bào)文都會(huì)被PE接收,從而空出ni0鏈路;此時(shí),如果ni1鏈路上有報(bào)文,則在有限時(shí)間內(nèi)也會(huì)被PE接收。即網(wǎng)絡(luò)中某個(gè)報(bào)文,無(wú)論在ni0鏈路上,還是在ni1鏈路上,最終肯定會(huì)在有限時(shí)間內(nèi)被PE接收,因此不存在某個(gè)報(bào)文一直在網(wǎng)絡(luò)中傳輸而不被接收的情形,因此該路由算法是無(wú)活鎖的。

4 性能評(píng)估

為了對(duì)網(wǎng)絡(luò)性能進(jìn)行精確的仿真,本文使用硬件描述語(yǔ)言Verilog對(duì)上述基于偏折路由的雙環(huán)片上網(wǎng)絡(luò)進(jìn)行了RTL建模和實(shí)現(xiàn),并用Cadence的NC Verilog模擬器進(jìn)行功能模擬和周期精確的性能仿真,仿真時(shí)間為10 000 000個(gè)時(shí)鐘周期。作為對(duì)比,基于標(biāo)準(zhǔn)的YARC結(jié)構(gòu)實(shí)現(xiàn)了一個(gè)同樣規(guī)模的片上網(wǎng)絡(luò)結(jié)構(gòu),文獻(xiàn)[8,26]證明了YARC結(jié)構(gòu)在均衡流量模型下可獲得100%吞吐率。在這2種網(wǎng)絡(luò)中,報(bào)文寬度為256 bit,實(shí)現(xiàn)了4個(gè)虛通道,每個(gè)虛通道輸入buffer的深度為32。

4.1 報(bào)文延時(shí)

本文統(tǒng)計(jì)了8×8的環(huán)形結(jié)構(gòu)和YARC結(jié)構(gòu)在不同的網(wǎng)絡(luò)負(fù)載下,報(bào)文從源結(jié)點(diǎn)到達(dá)目的結(jié)點(diǎn)所需要的傳輸延時(shí),如圖2所示。從圖2中可以發(fā)現(xiàn),在網(wǎng)絡(luò)負(fù)載較小的時(shí)候,環(huán)形結(jié)構(gòu)的延時(shí)與YARC結(jié)構(gòu)的延時(shí)相當(dāng);而當(dāng)網(wǎng)絡(luò)負(fù)載逐漸增大時(shí),環(huán)形網(wǎng)絡(luò)的延時(shí)超過(guò)了YARC結(jié)構(gòu)的延時(shí)。這時(shí)因?yàn)椋?dāng)網(wǎng)絡(luò)負(fù)載較小時(shí),網(wǎng)絡(luò)鏈路基本處于空閑狀態(tài),報(bào)文很少由于發(fā)生沖突而進(jìn)行偏折路由。當(dāng)網(wǎng)絡(luò)負(fù)載較大時(shí),環(huán)形網(wǎng)絡(luò)中由于結(jié)點(diǎn)接收帶寬受限,許多報(bào)文因競(jìng)爭(zhēng)端口失敗而發(fā)生偏折路由,導(dǎo)致在網(wǎng)絡(luò)中繞路,造成平均延時(shí)增大。還發(fā)現(xiàn)環(huán)形結(jié)構(gòu)和YARC結(jié)構(gòu)分別在網(wǎng)絡(luò)負(fù)載為0.4和0.9時(shí)產(chǎn)生了一個(gè)拐點(diǎn),這個(gè)拐點(diǎn)后延時(shí)迅速增加。這是因?yàn)楫?dāng)網(wǎng)絡(luò)負(fù)載增大到一定程度之后,由端結(jié)點(diǎn)送來(lái)的報(bào)文會(huì)在輸入緩存中排隊(duì),報(bào)文的傳輸總延時(shí)會(huì)隨著隊(duì)列深度的增加而增大。

Figure 2 Delay comparison of bi-ring NoC and YARC network

4.2 網(wǎng)絡(luò)吞吐率

本文分析了8×8規(guī)模下2個(gè)網(wǎng)絡(luò)所有結(jié)點(diǎn)的平均吞吐率,如圖3所示。對(duì)于YARC結(jié)構(gòu),隨著網(wǎng)絡(luò)負(fù)載的增加,其吞吐率呈線性增長(zhǎng)。這是因?yàn)樵贑rossbar中,各個(gè)端口之間的交換都是無(wú)阻塞的,任意2個(gè)端口之間都有獨(dú)享的數(shù)據(jù)交換通路。而在環(huán)形結(jié)構(gòu)中,當(dāng)網(wǎng)絡(luò)負(fù)載較小時(shí),其吞吐率隨著網(wǎng)絡(luò)負(fù)載的增加而線性增長(zhǎng);而當(dāng)網(wǎng)絡(luò)負(fù)載較大時(shí),其吞吐率幾乎不再增加,進(jìn)入一個(gè)平穩(wěn)狀態(tài)。這是因?yàn)楫?dāng)網(wǎng)絡(luò)負(fù)載增加到一定程度后,網(wǎng)絡(luò)鏈路達(dá)到飽和狀態(tài),持續(xù)增加的報(bào)文只能在輸入緩存中排隊(duì),無(wú)法直接進(jìn)入網(wǎng)絡(luò)。

Figure 3 Throughput comparison of bi-ring NoC and YARC network

4.3 延時(shí)與距離之間的關(guān)系

為了分析報(bào)文在環(huán)形網(wǎng)絡(luò)結(jié)構(gòu)中,由于發(fā)生偏折路對(duì)網(wǎng)絡(luò)延時(shí)造成的影響,本文統(tǒng)計(jì)了在不同網(wǎng)絡(luò)負(fù)載下,報(bào)文的傳輸延時(shí)與環(huán)網(wǎng)中源結(jié)點(diǎn)到目的結(jié)點(diǎn)的距離之間的關(guān)系,如圖4所示。源結(jié)點(diǎn)與目的結(jié)點(diǎn)之間的距離是指在環(huán)網(wǎng)中報(bào)文從源結(jié)點(diǎn)傳輸?shù)侥康慕Y(jié)點(diǎn)所需要最少的跳步數(shù)。本文分析了環(huán)形網(wǎng)絡(luò)在8×8規(guī)模下成功路由的報(bào)文的跳步數(shù)與結(jié)點(diǎn)距離之間的比值,該值基本分布在2~3,這說(shuō)明在環(huán)形網(wǎng)絡(luò)中,報(bào)文的傳輸延時(shí)比理想的最短延時(shí)稍大,這是由于偏折路由造成的。在網(wǎng)絡(luò)負(fù)載較大時(shí),偏折路由會(huì)導(dǎo)致報(bào)文在網(wǎng)絡(luò)里繞路,使得傳輸延遲增加。同時(shí)可以看出,當(dāng)網(wǎng)絡(luò)負(fù)載較小時(shí),該比值隨著負(fù)載的增加而增大;當(dāng)網(wǎng)絡(luò)負(fù)載較大時(shí),該比值基本維持在一個(gè)穩(wěn)定的值。這說(shuō)明隨著網(wǎng)絡(luò)負(fù)載的增大,報(bào)文沖突會(huì)加劇,造成實(shí)際延時(shí)增加。

Figure 4 Relationship of hop count and distance in bi-ring NoC

前文只分析了8×8規(guī)模下網(wǎng)絡(luò)的性能特征,下面將對(duì)不同網(wǎng)絡(luò)規(guī)模下的延時(shí)和吞吐率等網(wǎng)絡(luò)性能進(jìn)行對(duì)比分析。

4.4 不同網(wǎng)絡(luò)規(guī)模下雙環(huán)片上網(wǎng)絡(luò)結(jié)構(gòu)的延時(shí)

本文比較了4×4,8×8和16×16 3種不同網(wǎng)絡(luò)規(guī)模下雙環(huán)片上網(wǎng)絡(luò)結(jié)構(gòu)的報(bào)文平均延時(shí),如圖5所示??梢钥闯觯W(wǎng)絡(luò)規(guī)模越大,報(bào)文平均延時(shí)也越長(zhǎng)。這是容易理解的,因?yàn)榫W(wǎng)絡(luò)規(guī)模越大,意味著源結(jié)點(diǎn)和目的結(jié)點(diǎn)之間的最短距離也將增加,這必然導(dǎo)致延時(shí)增加。同時(shí)也發(fā)現(xiàn)在網(wǎng)絡(luò)負(fù)載增大時(shí),這3種網(wǎng)絡(luò)都存在一個(gè)延時(shí)迅速上升的拐點(diǎn)。如前所述,這是由于從這個(gè)時(shí)刻開始,報(bào)文逐漸在輸入緩存中排隊(duì)造成的。網(wǎng)絡(luò)規(guī)模越大,隨著網(wǎng)絡(luò)負(fù)載的增加,其拐點(diǎn)越早到達(dá)。當(dāng)網(wǎng)絡(luò)規(guī)模為4×4時(shí),網(wǎng)絡(luò)負(fù)載在0.7以下其性能較好;當(dāng)網(wǎng)絡(luò)規(guī)模為16×16時(shí),網(wǎng)絡(luò)負(fù)載增加到0.3時(shí),網(wǎng)絡(luò)就已經(jīng)基本達(dá)到性能極限了。如果還要繼續(xù)提高網(wǎng)絡(luò)負(fù)載,就只有增加網(wǎng)絡(luò)傳輸帶寬才能滿足性能要求。

Figure 5 Delay of bi-ring NoC in different network scales

4.5 不同網(wǎng)絡(luò)規(guī)模下環(huán)形結(jié)構(gòu)的吞吐率

類似地,本文也比較了不同網(wǎng)絡(luò)規(guī)模下雙環(huán)結(jié)構(gòu)上每個(gè)結(jié)點(diǎn)的平均吞吐率,如圖6所示。在網(wǎng)絡(luò)規(guī)模較小時(shí),這3種網(wǎng)絡(luò)中結(jié)點(diǎn)的平均吞吐率都隨著網(wǎng)絡(luò)負(fù)載的增加而增大。當(dāng)網(wǎng)絡(luò)負(fù)載增加到一定程度后,由于受到網(wǎng)絡(luò)總帶寬的限制,其吞吐率進(jìn)入一個(gè)相對(duì)穩(wěn)定的狀態(tài),不再繼續(xù)增加。其中,由于16×16規(guī)模對(duì)網(wǎng)絡(luò)帶寬的需求更大,因此最早達(dá)到拐點(diǎn)而進(jìn)入穩(wěn)定狀態(tài)。4×4規(guī)模對(duì)網(wǎng)絡(luò)帶寬的需求較小,因此最后達(dá)到穩(wěn)定。

Figure 6 Throughput of bi-ring NoC under different network scale

5 硬件開銷

本文分別使用FPGA和ASIC實(shí)現(xiàn)來(lái)對(duì)本文提出的基于偏折路由的雙環(huán)片上網(wǎng)絡(luò)進(jìn)行硬件實(shí)現(xiàn)評(píng)估。為了進(jìn)行對(duì)比,按照同樣的設(shè)置和工藝參數(shù)對(duì)基于YARC結(jié)構(gòu)的Crossbar片上網(wǎng)絡(luò)進(jìn)行了綜合。2種網(wǎng)絡(luò)都使用16×16的網(wǎng)絡(luò)規(guī)模,報(bào)文寬度256 bit,4個(gè)虛通道,每個(gè)虛通道的輸入buffer深度為32。

5.1 FPGA實(shí)現(xiàn)資源評(píng)估

在FPGA評(píng)估實(shí)現(xiàn)時(shí),使用XILINX XC7V2000T- FHG1761-2芯片,采用Vivado 2018.3綜合實(shí)現(xiàn)工具對(duì)2種設(shè)計(jì)分別進(jìn)行了綜合和布局布線,結(jié)果如表1和表2所示。

本文從查找表LUT、觸發(fā)器FF、塊BRAM 3方面對(duì)FPGA實(shí)現(xiàn)資源進(jìn)行評(píng)估。由表1和表2可以看出,采用同樣的FPGA芯片,在同樣網(wǎng)絡(luò)規(guī)模下,本文提出的基于偏折路由的雙環(huán)片上網(wǎng)絡(luò)與標(biāo)準(zhǔn)的YARC網(wǎng)絡(luò)占用的硬件資源差別較大。本文提出的實(shí)現(xiàn)方案所占用的FPGA資源大約是YARC結(jié)構(gòu)實(shí)現(xiàn)方案的11%~13%。

Table 1 Hardware resource evalution of bi-ring NoC based on FPGA

Table 2 Hardware resource evalution of YARC network based on FPGA

5.2 ASIC實(shí)現(xiàn)資源評(píng)估

在ASIC實(shí)現(xiàn)中,本文采用了TSMC 28 nm工藝,頻率為800 MHz,使用Synopsys的Design Compiler H-2013.03-SP4進(jìn)行邏輯綜合。其結(jié)果如表3所示(面積單位為mm2)。

首先,從表3中可以看出,在ASIC實(shí)現(xiàn)方式中,RAM所占的面積(Macro/Black Box Area部分)在總面積中的比例最大,達(dá)到了75%左右。而本文提出的基于偏折路由的雙環(huán)片上網(wǎng)絡(luò),相比YARC等其他片上網(wǎng)絡(luò),最重要的就是減少了路由器內(nèi)部數(shù)據(jù)緩存的使用,因此顯著降低了硬件開銷。

Table 3 Hardware resource evalution based on ASIC

其次,從表3可以看出,雙環(huán)片上網(wǎng)絡(luò)消耗的硬件資源明顯少于YARC結(jié)構(gòu)的。從設(shè)計(jì)所占用的總面積來(lái)看,雙環(huán)結(jié)構(gòu)的面積僅為YARC結(jié)構(gòu)面積的11.6%。這主要是由2方面原因造成的:一是在雙環(huán)片上網(wǎng)絡(luò)中,在每個(gè)端口上只有一個(gè)輸入緩存,而在YARC結(jié)構(gòu)中,報(bào)文在由源端口路由到目的端口時(shí),需要順序經(jīng)過(guò)3個(gè)不同緩存隊(duì)列,這些緩存占用了相當(dāng)一部分芯片面積;二是在YARC結(jié)構(gòu)中,為每一對(duì)輸入和輸出端口之間都設(shè)計(jì)了獨(dú)享的數(shù)據(jù)通路,這雖然提高了高負(fù)載情形下的網(wǎng)絡(luò)傳輸性能,但其代價(jià)是消耗了大量的硬件邏輯。

從表3中還可以看出,雙環(huán)片上網(wǎng)絡(luò)中消耗的連線資源大約是YARC結(jié)構(gòu)中消耗的連線資源的13.3%。在YARC結(jié)構(gòu)中,這些連線資源主要用在瓦片內(nèi)部多個(gè)Crossbar之間的數(shù)據(jù)通路上,而在雙環(huán)結(jié)構(gòu)中,這些連線資源主要集中在路由器之間較為規(guī)則的數(shù)據(jù)通路上。大量的連線資源在占用了芯片面積、增加了設(shè)計(jì)復(fù)雜性的同時(shí),將會(huì)導(dǎo)致后端布線難以完成,給后端實(shí)現(xiàn)增加難度。

6 結(jié)束語(yǔ)

為了簡(jiǎn)化小到中等規(guī)模片上網(wǎng)絡(luò)的設(shè)計(jì),在盡量保持網(wǎng)絡(luò)性能的同時(shí)減少硬件資源消耗,本文提出了一種基于偏折路由的雙環(huán)片上網(wǎng)絡(luò)結(jié)構(gòu)。在這種網(wǎng)絡(luò)結(jié)構(gòu)下,路由器的設(shè)計(jì)非常簡(jiǎn)單,除了在與處理結(jié)點(diǎn)之間有一個(gè)輸入緩存之外,沒有其它緩存隊(duì)列,減少了報(bào)文的緩存排隊(duì)和端口仲裁,對(duì)于端口的競(jìng)爭(zhēng)訪問(wèn)通過(guò)偏折路由來(lái)解決。研究結(jié)果表明,在8×8(16×16)網(wǎng)絡(luò)規(guī)模下,當(dāng)網(wǎng)絡(luò)負(fù)載小于40%(30%)時(shí),這種雙環(huán)片上網(wǎng)絡(luò)結(jié)構(gòu)具有很好的延時(shí)和吞吐率特性。同時(shí),本文提出的這種雙環(huán)片上網(wǎng)絡(luò)的芯片面積只有其他典型片上網(wǎng)絡(luò)結(jié)構(gòu)(YARC)芯片面積的11.6%,而且降低了設(shè)計(jì)復(fù)雜度,提高了芯片實(shí)現(xiàn)效率。即在網(wǎng)絡(luò)負(fù)載較小時(shí),采用本文提出的基于偏折路由的雙環(huán)片上網(wǎng)絡(luò),可以在僅僅消耗大約11.6%的硬件資源的情況下,得到與通常片上網(wǎng)絡(luò)大致相同的通信性能。這為在SoC芯片中節(jié)省面積,降低功耗,并集成更多的計(jì)算和處理單元提供了一種可能的途徑。

猜你喜歡
雙環(huán)結(jié)點(diǎn)網(wǎng)絡(luò)結(jié)構(gòu)
Ladyzhenskaya流體力學(xué)方程組的確定模與確定結(jié)點(diǎn)個(gè)數(shù)估計(jì)
“單環(huán)學(xué)習(xí)”與“雙環(huán)學(xué)習(xí)”
電流雙環(huán)控制的LCL單相并網(wǎng)逆變器逆變研究
基于互信息的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)
知識(shí)網(wǎng)絡(luò)結(jié)構(gòu)維對(duì)于創(chuàng)新績(jī)效的作用機(jī)制——遠(yuǎn)程創(chuàng)新搜尋的中介作用
滬港通下A+ H股票網(wǎng)絡(luò)結(jié)構(gòu)演化的實(shí)證分析
復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)比對(duì)算法研究進(jìn)展
聚丙烯成核劑雙環(huán)[2.2.1]-庚烷-2,3-二羧酸鈉的合成
雙環(huán)法結(jié)合雙“V”形乳腺切除法在乳房肥大整形術(shù)中的應(yīng)用
基于Raspberry PI為結(jié)點(diǎn)的天氣云測(cè)量網(wǎng)絡(luò)實(shí)現(xiàn)
玛曲县| 乡宁县| 宜兴市| 新巴尔虎右旗| 舟山市| 宜君县| 三门县| 嘉义县| 黑龙江省| 江门市| 瑞丽市| 石嘴山市| 临沭县| 安丘市| 亳州市| 桐城市| 通化县| 舒兰市| 凤阳县| 友谊县| 鄂伦春自治旗| 孙吴县| 油尖旺区| 丽江市| 云浮市| 新沂市| 南华县| 雅江县| 东山县| 搜索| 清新县| 河北省| 安徽省| 海南省| 论坛| 武穴市| 定边县| 辛集市| 山西省| 正定县| 格尔木市|