胡春雷 陳 鋒 方 杰

(1合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院；2安徽職業(yè)技術(shù)學(xué)院信息工程學(xué)院 安徽合肥 230011)

1研究概述

隨著集成電路制造工藝的不斷發(fā)展，芯片上可集成的晶體管的數(shù)目和芯片的集成度都在不斷增加，這使得單個(gè)芯片上可以集成數(shù)十甚至上百個(gè)IP核。這樣基于總線通訊架構(gòu)的片上系統(tǒng)(system-on-chip，SOC)將面臨可擴(kuò)展性問(wèn)題、通訊效率問(wèn)題、全局時(shí)鐘同步困難等問(wèn)題。為了解決以上問(wèn)題，片上網(wǎng)絡(luò)(network-on-chip，NoC)作為一種全新的互連結(jié)構(gòu)被提了出來(lái)[1]。由于該種架構(gòu)具有很好的擴(kuò)展性、更高的吞吐量以及更小的功耗開(kāi)銷，因此被用于解決復(fù)雜片上系統(tǒng)的核間通信。隨著單平面片上網(wǎng)絡(luò)(2D NoC)中IP核的增加，2D NoC并沒(méi)有在根本上解決縮短物理連線和減小信號(hào)延遲的問(wèn)題。三維集成電路設(shè)計(jì)和片上網(wǎng)絡(luò)多核互連架構(gòu)，在學(xué)術(shù)界已經(jīng)進(jìn)行了多年的研究，三維集成電路設(shè)計(jì)工藝與先進(jìn)的片上網(wǎng)絡(luò)架構(gòu)相結(jié)合而產(chǎn)生的三維片上網(wǎng)絡(luò)(three dimension network on chip，3D NoC)，以其優(yōu)良的性能、良好的可擴(kuò)展性被認(rèn)為是納米工藝下最有前途的多核互連通信架構(gòu)[2]。3D NoC的結(jié)構(gòu)如圖1所示，由資源節(jié)點(diǎn)(IP核)、資源網(wǎng)絡(luò)接口(resource network interface，RNI)、路由器(router)、垂直通信鏈路、水平通信鏈路等幾部分組成，是在2D片上網(wǎng)絡(luò)的基礎(chǔ)上進(jìn)行垂直方向的擴(kuò)展。這種結(jié)構(gòu)大大縮短了IP核之間的平均跳數(shù)，使得片內(nèi)通信效率大大提高。硅通孔(through—silicon-via，TSV)是業(yè)界最常見(jiàn)也被認(rèn)為是最有前途的層間互連技術(shù)，將多個(gè)晶片(die)在垂直方向進(jìn)行堆疊，有效縮短了IP核連線長(zhǎng)度，減少了延時(shí)、降低了功耗，更好的滿足了多核系統(tǒng)對(duì)通信效率的需求。但是隨著芯片特征尺寸的縮小，集成電路密度的增加以及TSV的引入，都將導(dǎo)致芯片的可靠性問(wèn)題[2]。ITRS[3]中預(yù)測(cè)，到2025年集成電路的特征尺寸將達(dá)到10nm，單個(gè)芯片將集成更多的晶體管，從而引起芯片內(nèi)部發(fā)生更多的缺陷。主要體現(xiàn)在：①受制造工藝水平的限制，芯片在生產(chǎn)過(guò)程中將存在更多缺陷。②芯片在使用過(guò)程中，由于電路老化、電子遷移、負(fù)偏壓溫度不穩(wěn)定性、電介質(zhì)擊穿等原因，造成芯片出現(xiàn)故障不斷增多。③芯片在使用過(guò)程中極易受到串?dāng)_、噪聲、α粒子撞擊、電磁干擾、宇宙輻射等因素影響，導(dǎo)致芯片出現(xiàn)瞬時(shí)故障。這些因素都將導(dǎo)致芯片的可靠性問(wèn)題。三維片上網(wǎng)絡(luò)的通訊架構(gòu)出現(xiàn)錯(cuò)誤，將導(dǎo)致芯片通信性能急劇下降甚至系統(tǒng)癱瘓，如何保證三維片上網(wǎng)絡(luò)的通訊架的可靠性成為學(xué)術(shù)界研究的熱點(diǎn)[4]。

圖1 3DNoC結(jié)構(gòu)圖

2擁塞感知的三維片上網(wǎng)絡(luò)容錯(cuò)路由算法

2.1三維片上網(wǎng)絡(luò)路由介紹

圖2顯示了一個(gè)3×3×3的標(biāo)準(zhǔn)的3D Mesh結(jié)構(gòu)三維片上網(wǎng)絡(luò)，為了方便顯示，并未畫出每個(gè)節(jié)點(diǎn)的IP核及NI接口，僅在圖中畫出了各個(gè)節(jié)點(diǎn)的路由器。為了標(biāo)識(shí)路由器，需要為每個(gè)路由器都設(shè)置一個(gè)地址。為了方便路由控制，通常使用該路由器在空間上的坐標(biāo)值(x，y，z)來(lái)表示該路由器的地址，其中z坐標(biāo)代表路由器所處的層，如坐標(biāo)(1，2，3)代表的是處于第3層的x坐標(biāo)為1、y坐標(biāo)為2的路由器節(jié)點(diǎn)。三維片上網(wǎng)絡(luò)通常采用維序路由算法如XYZ路由算法、ZXY路由算法等。下面以XYZ路由算法為例，來(lái)介紹三維片上網(wǎng)絡(luò)的數(shù)據(jù)路由過(guò)程。XYZ路由算法的原理是讓數(shù)據(jù)先沿著X維進(jìn)行傳輸，直到數(shù)據(jù)傳輸?shù)胶湍繕?biāo)節(jié)點(diǎn)處于同一X坐標(biāo)后再讓數(shù)據(jù)沿著Y維進(jìn)行傳輸，直到數(shù)據(jù)傳輸?shù)胶湍繕?biāo)節(jié)點(diǎn)處于同一Y坐標(biāo)后再讓數(shù)據(jù)沿著Z維進(jìn)行傳輸，直到數(shù)據(jù)到達(dá)目標(biāo)節(jié)點(diǎn)。如圖所示，假設(shè)源節(jié)點(diǎn)S(3，3，3)給目標(biāo)節(jié)點(diǎn)D(1，2，1)發(fā)送數(shù)據(jù)，數(shù)據(jù)的傳輸過(guò)程為(3，3，3)→(2，3，3)→(1，3，3)→(1，2，3)→(1，2，2)→(1，2，1)。

圖2 3D MeshNoC通信架構(gòu)圖

2.2擁塞感知容錯(cuò)路由算法

文章提出的容錯(cuò)路由算法能夠感知到路由器或通信鏈路的故障，根據(jù)故障程度和擁塞程度來(lái)為數(shù)據(jù)包選擇合適路徑。同時(shí)，在容錯(cuò)路由算法的設(shè)計(jì)上考慮到溫度對(duì)通信架構(gòu)可靠性的影響。文章假定芯片所用的散熱器安裝在第一層下方，這樣第一層的熱量散失最快，第二層居中，第三層最慢。根據(jù)熱量散失的分布特性，在控制數(shù)據(jù)包路由的時(shí)候可以考慮讓數(shù)據(jù)包在水平方向傳輸所產(chǎn)生的熱量盡可能的在靠近散熱器的底層散失掉。容錯(cuò)路由算法流程如圖3所示。

圖3 路由算法流程圖

由圖3可知，假設(shè)(Cx，Cy，Cz)代表發(fā)送數(shù)據(jù)節(jié)點(diǎn)即源節(jié)點(diǎn)的地址，(Dx，Dy，Dz)代表接收數(shù)據(jù)節(jié)點(diǎn)即目標(biāo)節(jié)點(diǎn)的地址，Cx、Cy、Cz和Dx、Dy、Dz分別代表原節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)X、Y、Z坐標(biāo)對(duì)應(yīng)的值。當(dāng)源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)不在同一平面時(shí)(即Dz!=Cz)，如果目標(biāo)節(jié)點(diǎn)在源節(jié)點(diǎn)的上方(即Dz>Cz)，則讓數(shù)據(jù)包在當(dāng)前平面進(jìn)行XY路由；如果當(dāng)前平面X方向和Y方向都無(wú)故障，則可根據(jù)兩個(gè)方向的通信擁塞程度來(lái)選擇擁塞程度低的方向傳輸；如果當(dāng)前平面的X方向或Y方向存在一個(gè)方向有故障，則選擇無(wú)故障的方向進(jìn)行傳輸；如果XY兩個(gè)方向都存在故障，則選擇使數(shù)據(jù)包沿著Z方向向目標(biāo)節(jié)點(diǎn)前進(jìn)一步，當(dāng)數(shù)據(jù)包到另外一個(gè)平面后還是按照同樣的策略進(jìn)行路由。如果目標(biāo)節(jié)點(diǎn)在源節(jié)點(diǎn)的下方(即Dz

在圖4中，假設(shè)數(shù)據(jù)包從源節(jié)點(diǎn)S(3，3，3)發(fā)送給目標(biāo)節(jié)點(diǎn)D(1，2，1)，根據(jù)文章提出的容錯(cuò)路由算法，目標(biāo)節(jié)點(diǎn)位于下層，則數(shù)據(jù)包先沿Z軸向下傳輸一步到達(dá)節(jié)點(diǎn)(3，3，2)，然后在沿節(jié)點(diǎn)(3，3，2)再向下傳輸。但是此時(shí)節(jié)點(diǎn)(3，3，2)與下層路由相連的鏈路出現(xiàn)了故障，根據(jù)路由算法節(jié)點(diǎn)(3，3，2)將會(huì)從選擇讓數(shù)據(jù)包現(xiàn)在當(dāng)前層沿X軸或者Y軸向目標(biāo)節(jié)點(diǎn)前進(jìn)一步，若節(jié)點(diǎn)(3，3，2)與在Y軸相連的節(jié)點(diǎn)(3，2，2)之間的鏈路也出現(xiàn)了故障，則這時(shí)會(huì)選擇將數(shù)據(jù)包發(fā)送給節(jié)點(diǎn)(2，3，2)，數(shù)據(jù)包到達(dá)(2，3，2)還是優(yōu)先選擇向下傳輸，將數(shù)據(jù)包交給節(jié)點(diǎn)(2，3，1)。此時(shí)數(shù)據(jù)包已經(jīng)到達(dá)目標(biāo)層，但數(shù)據(jù)包在X維和Y維還沒(méi)有達(dá)到目標(biāo)。節(jié)點(diǎn)(2，3，1)到目標(biāo)節(jié)點(diǎn)(1，2，1)有兩條最短路徑，即沿X維傳輸或者沿Y維傳輸，如果這兩條路徑都可用，則根據(jù)兩條路徑的擁塞程度選擇擁塞程度輕的路徑傳輸。假設(shè)節(jié)點(diǎn)(2，3，1)→節(jié)點(diǎn)(1，3，1)的流量小于節(jié)點(diǎn)(2，3，1)→節(jié)點(diǎn)(2，2，1)，則會(huì)選擇將數(shù)據(jù)包傳遞給節(jié)點(diǎn)(1，3，1)，然后再由節(jié)點(diǎn)(1，3，1)將數(shù)據(jù)包傳遞給目標(biāo)節(jié)點(diǎn)(1，2，1)。

圖4 含故障鏈路3D MeshNoC通信架構(gòu)圖

路由算法除了應(yīng)該能夠快速地為數(shù)據(jù)包進(jìn)行路由，還應(yīng)該保證保證路由算法時(shí)無(wú)死鎖的。片上網(wǎng)絡(luò)容錯(cuò)路由算法通常都是采用繞過(guò)故障鏈路或路由器節(jié)點(diǎn)來(lái)達(dá)到容錯(cuò)的目的，在繞的過(guò)程中極易形成環(huán)路而產(chǎn)生死鎖，如果不采用相應(yīng)的方法去避免，將導(dǎo)致數(shù)據(jù)包在網(wǎng)絡(luò)中不斷的兜圈子，浪費(fèi)網(wǎng)絡(luò)的帶寬資源并產(chǎn)生大量的功耗。目前片上網(wǎng)絡(luò)路由算法中主要采用拐彎模型、虛擬通道技術(shù)、維序路由等技術(shù)來(lái)避免死鎖。該研究采用廣泛使用的虛擬通道技術(shù)來(lái)避免死鎖的產(chǎn)生。

3實(shí)驗(yàn)結(jié)果

為評(píng)估文章算法，通過(guò)實(shí)驗(yàn)對(duì)其性能進(jìn)行分析。實(shí)驗(yàn)使用的是Booksim 2.0模擬器，該模擬器是美國(guó)斯坦福大學(xué)CVA小組開(kāi)發(fā)研制的仿真平臺(tái)，是一個(gè)用于NoC路由算法仿真的仿真器。它模塊化了NoC的各個(gè)組成部分，支持多種拓?fù)浣Y(jié)構(gòu)、路由算法、路由器結(jié)構(gòu)、仲裁器結(jié)構(gòu)與算法等。實(shí)驗(yàn)對(duì)象為4×4×4的3D Mesh NoC ，通信方式使用的是均勻隨機(jī)模式，鏈路故障率為10%，通過(guò)對(duì)文獻(xiàn)[5]和[6]以及文章提出的容錯(cuò)路由算法進(jìn)行模擬。下面對(duì)評(píng)價(jià)的重要指標(biāo)做具體說(shuō)明。

(1)數(shù)據(jù)包時(shí)延。是指一個(gè)數(shù)據(jù)包從它的首部進(jìn)入網(wǎng)絡(luò)開(kāi)始計(jì)時(shí)，直到該數(shù)據(jù)包的尾部離開(kāi)網(wǎng)絡(luò)所使用的時(shí)間。

(2)平均延時(shí)。網(wǎng)絡(luò)中傳輸?shù)乃袛?shù)據(jù)包的時(shí)延求平均值。是衡量網(wǎng)絡(luò)通信傳輸性能的重要指標(biāo)。

其中pk_num指接收到的數(shù)據(jù)包總數(shù)。

(3)丟包率。數(shù)據(jù)傳輸過(guò)程中因故障等原因丟失數(shù)據(jù)包的數(shù)目占所發(fā)送數(shù)據(jù)包總數(shù)的百分比,是衡量網(wǎng)絡(luò)可靠性的重要指標(biāo)。

Lossrate=(loss/(receiver+loss))×100%

其中：loss為3DNoC丟棄的數(shù)據(jù)包的總數(shù)目；receiver為3D NoC接收到的數(shù)據(jù)包的數(shù)目。

圖5顯示了在數(shù)據(jù)包注入速率為0.02、0.04、0.06、0.08時(shí)文獻(xiàn)[5]、文獻(xiàn)[6]和文章在鏈路故障率為10%下的數(shù)據(jù)包平均時(shí)延的比較。由實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，相比較文獻(xiàn)[5]、文獻(xiàn)[6]，該方案所提出的容錯(cuò)路由算法能夠在不同注入率都具有較低的數(shù)據(jù)包平均時(shí)延，與文獻(xiàn)[5]相比，平均時(shí)延提升了20%，與文獻(xiàn)[6]相比，平時(shí)時(shí)延提升了約14.6%，得益于該算法具有擁塞感知功能，在網(wǎng)絡(luò)通信量較大時(shí)能夠選擇擁塞程度低的鏈路傳輸，有效地降低數(shù)據(jù)包的平時(shí)時(shí)延。

圖5 故障率為10%時(shí)數(shù)據(jù)包注入率與平均時(shí)延比較

表1顯示了在數(shù)據(jù)包注入率為0.06時(shí)，3DNoC通信架構(gòu)中鏈路故障分別為5%、10%、15%情況下，三種不同路由算法的丟包率情況，可以看到，隨著3D NoC中故障鏈路數(shù)目的增加，文章在丟包率上的優(yōu)勢(shì)越為明顯，這主要是因?yàn)槲恼路桨柑岢龅膿砣兄蒎e(cuò)路由算法更加具有靈活性，在多條路徑中選擇無(wú)故障且擁塞程度輕的路徑傳輸數(shù)據(jù)，而且在傳輸?shù)倪^(guò)程中考慮到熱量對(duì)芯片可靠性的影響，讓數(shù)據(jù)包在水平方向傳輸所產(chǎn)生的熱量盡可能的在靠近散熱器的底層散失掉，大大減少了溫度熱點(diǎn)對(duì)芯片可靠性帶來(lái)的負(fù)面影響。

表1 不同鏈路故障占比下丟包率比較(%)

4小結(jié)

文章根據(jù)3DNoC通信架構(gòu)中故障路由器或者鏈路帶來(lái)的可靠性問(wèn)題，設(shè)計(jì)了一種擁塞感知的容錯(cuò)路由算法。該路由算法能夠指導(dǎo)數(shù)據(jù)包繞過(guò)故障鏈路或者路由器從而達(dá)到一定程度的容錯(cuò)，并且能夠根據(jù)擁塞程度不同選擇合適的路徑傳輸數(shù)據(jù)包。實(shí)驗(yàn)結(jié)果表明，文章所設(shè)計(jì)的容錯(cuò)路由算法在提高3D NoC的通信的可靠性的同時(shí)，能夠有效地降低數(shù)據(jù)包傳輸?shù)钠骄鶗r(shí)延。