王春華, 孫 琦, 朱新宇, 張多利, 宋宇鯤

(合肥工業(yè)大學(xué) 電子科學(xué)與應(yīng)用物理學(xué)院,安徽 合肥 230601)

近年來,隨著集成電路設(shè)計技術(shù)的飛躍發(fā)展,單個芯片內(nèi)部可能集成了幾百甚至上千個處理器核和通信部件,傳統(tǒng)的基于總線的片上系統(tǒng)(system-on-chip,SoC),已經(jīng)不能高效地處理處理器核心之間快速的數(shù)據(jù)資源交換。片上網(wǎng)絡(luò)(network-on-chip,NoC)由于其集成度高、擴(kuò)展性強(qiáng)、高并行度的通信能力和功耗低等優(yōu)勢,已經(jīng)逐漸取代總線成為新的片上通信的標(biāo)準(zhǔn)。

但是隨著集成電路工藝進(jìn)入納米時代,更小的特征尺寸、更低的工作電壓以及不斷提升的工作頻率,導(dǎo)致片上網(wǎng)絡(luò)很容易受到故障的影響而破壞網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)。尤其是在大氣層外,電子設(shè)備暴露在有大量宇宙射線的強(qiáng)輻射環(huán)境中,這些宇宙射線由電子、質(zhì)子、α粒子等高能帶電粒子構(gòu)成,穿透能力強(qiáng),易對電子元器件產(chǎn)生諸多危害。一旦高能粒子轟擊集成電路,會引發(fā)永久效應(yīng)或瞬時效應(yīng)。高可靠性已成為片上網(wǎng)絡(luò)系統(tǒng)發(fā)展的重要方向[1]。研究結(jié)果表明,計算機(jī)系統(tǒng)中80%～90%的失效都是由瞬時故障引起的[2]。

基于此,本文提出了一種針對數(shù)據(jù)瞬時故障的傳輸機(jī)制,即基于維序路由的NoC容錯方案。該方案通過雙鏈路發(fā)送數(shù)據(jù)配合路由容錯算法提高整個NoC的容錯能力,以達(dá)到減少延時和提高吞吐的目的。

1 相關(guān)研究

為了解決數(shù)據(jù)傳輸中的瞬時故障問題,國內(nèi)外研究者提出了許多具有容錯性能的NoC傳輸機(jī)制方案[3-5],主要分為基于檢錯糾錯碼的請求重傳機(jī)制[6]和基于隨機(jī)通信的路由算法2類[7]。針對NoC的瞬時故障,文獻(xiàn)[8]提出了一種基于XYX路由的方法,有效地提高了網(wǎng)絡(luò)的容錯能力;文獻(xiàn)[9]提出了一種低延時的可靠傳輸算法,利用發(fā)送端主動重傳分組技術(shù)以及端到端的反饋技術(shù),有效地降低了數(shù)據(jù)重傳過程的平均延時;文獻(xiàn)[10]提出了一種混合容錯方案,該方案通過自適應(yīng)編碼來調(diào)節(jié)各路由器之間的容錯能力。隨機(jī)通信算法是路由節(jié)點(diǎn)以一定的概率向相鄰節(jié)點(diǎn)以廣播的形式發(fā)送數(shù)據(jù)包,直到目的節(jié)點(diǎn)收到數(shù)據(jù)包,目的節(jié)點(diǎn)從它相鄰的節(jié)點(diǎn)得到數(shù)據(jù)包的多個備份,從中選取一份正確的數(shù)據(jù)包[11]。文獻(xiàn)[12]提出了一種直接擴(kuò)散與冗余隨機(jī)走動算法,改善了隨機(jī)擴(kuò)散目的端被忽略的缺點(diǎn)。但對于擴(kuò)散算法,不論哪種算法,都需要在網(wǎng)絡(luò)中傳輸大量的冗余包,從而造成很大的開銷。

2 基于維序路由的容錯設(shè)計

2.1 設(shè)計思想

基于維序路由的容錯設(shè)計是一種多徑路由的容錯算法,以2條路徑進(jìn)行數(shù)據(jù)傳輸配合奇偶校驗(yàn)碼,利用雙模數(shù)據(jù)自檢容錯,對瞬時故障進(jìn)行屏蔽。

瞬時故障的產(chǎn)生具有隨機(jī)性和偶然性,可能出現(xiàn)在NoC的控制信號或者傳輸數(shù)據(jù)中,對控制信號采用三模冗余可以很好地屏蔽瞬時故障的干擾。而對于傳輸數(shù)據(jù),無論空間三模冗余或時間三模冗余,對NoC的資源消耗都十分巨大[13]。雙模冗余自校驗(yàn)方案相對于傳統(tǒng)的三模冗余既不會增加太多資源,又可以實(shí)現(xiàn)容錯目的,是當(dāng)前研究的一個重要方向。

奇偶校驗(yàn)碼是一種簡單有效的校驗(yàn)碼,它在源端記錄數(shù)據(jù)包中0的個數(shù)是奇數(shù)還是偶數(shù),在目的端再檢測0的個數(shù)是奇數(shù)還是偶數(shù),僅需要1位即可檢驗(yàn)出數(shù)據(jù)在傳輸過程中是否出現(xiàn)錯誤。奇偶校驗(yàn)碼檢錯性能好、消耗資源少,是一種優(yōu)質(zhì)的檢錯方案,但劣勢在于無法檢驗(yàn)出偶數(shù)個錯誤,因此可以將雙模冗余和奇偶校驗(yàn)結(jié)合起來,完成對瞬時故障的屏蔽。

2.2 故障模型與容錯機(jī)制

瞬時故障引起的單粒子效應(yīng)一般表現(xiàn)為單粒子翻轉(zhuǎn)(single event upset,SEU)和單粒子瞬態(tài)(single event transient,SET),在集成電路中主要為SEU錯誤。在近地軌道電子設(shè)備中每天1 bit產(chǎn)生SEU的概率[9]為10-7。本文研究的目標(biāo)多核系統(tǒng)1次任務(wù)的傳輸量約為106bit。結(jié)合瞬時故障產(chǎn)生的概率,假設(shè)在1次數(shù)據(jù)傳輸過程中,同一個數(shù)據(jù)包中瞬時故障至多發(fā)生1次,因此可以采用基于維序路由的容錯設(shè)計。

對于NoC中的控制信號,均采用三模冗余表決進(jìn)行容錯,對于傳輸數(shù)據(jù)的容錯采用雙模冗余自校驗(yàn)的方式進(jìn)行容錯,雙模冗余自檢容錯。雙模冗余自檢容錯電路如圖1所示。

圖1 雙模冗余自檢容錯電路

雙模容錯真值見表1所列,OUT的初始狀態(tài)為0,單條路徑奇偶校驗(yàn)結(jié)果分別為IN0和IN1。若單條路徑校驗(yàn)結(jié)果正確,則記為0；若校驗(yàn)結(jié)果錯誤,則記為1。由表1可知,當(dāng)1條鏈路中出現(xiàn)了SEU錯誤,不影響OUT的正常輸出；當(dāng)2條鏈路同時出現(xiàn)SEU錯誤,OUT輸出值為1,此時向源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)均反饋重傳信號,進(jìn)行整體重傳,實(shí)現(xiàn)對單粒子錯誤進(jìn)行屏蔽。

表1 雙模容錯真值

2.3 路由器結(jié)構(gòu)

本文以二維網(wǎng)格結(jié)構(gòu)來探討容錯方案的設(shè)計,為了實(shí)現(xiàn)雙路徑傳輸,在傳統(tǒng)的單端口路由器結(jié)構(gòu)下,添加一個本地端口,在源節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸時,可以通過雙端口將雙路徑數(shù)據(jù)同時送入NoC中。數(shù)據(jù)網(wǎng)絡(luò)的網(wǎng)絡(luò)節(jié)點(diǎn)結(jié)構(gòu)如圖2所示。由圖2所知,每個路由節(jié)點(diǎn)包括編碼器、輸入控制器、優(yōu)先級編碼器、路由器、仲裁器、交叉開關(guān)、輸出控制器、緩存器、解碼器。

圖2 數(shù)據(jù)網(wǎng)絡(luò)的網(wǎng)絡(luò)節(jié)點(diǎn)結(jié)構(gòu)

基于維序路由的容錯方案只在源節(jié)點(diǎn)的本地端口進(jìn)行編碼,在目的節(jié)點(diǎn)端口進(jìn)行解碼,網(wǎng)絡(luò)節(jié)點(diǎn)的工作流程如下。

(1) 發(fā)送端。源節(jié)點(diǎn)的運(yùn)算核心將準(zhǔn)備好的運(yùn)算包,通過本地節(jié)點(diǎn)0和本地節(jié)點(diǎn)1送入到網(wǎng)絡(luò)節(jié)點(diǎn)的路由器中,經(jīng)過端口編碼,送入節(jié)點(diǎn)的路由器中進(jìn)行傳輸。雙路數(shù)據(jù)路由中傳輸協(xié)議一致,以發(fā)送頭包的形式先建立鏈路,頭包中采用三模冗余的方案對目標(biāo)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行冗余表決,解析出正確的目的節(jié)點(diǎn)坐標(biāo)；優(yōu)先級編碼器對各端口的請求優(yōu)先級進(jìn)行排序；路由器對優(yōu)先級高的目的節(jié)點(diǎn)分配端口；仲裁器根據(jù)路由結(jié)果對鏈路通道進(jìn)行仲裁,若處于空閑狀態(tài),則分配通道交予當(dāng)前請求,若通道處于占用狀態(tài),則反饋拒絕信號,鏈路建立失敗。交叉開關(guān)根據(jù)交叉開關(guān)將所允許的通道打開,頭包發(fā)送至下一個路由節(jié)點(diǎn)。

需要注意的是,對于本地節(jié)點(diǎn)0輸入的數(shù)據(jù),采用XY路由規(guī)則進(jìn)行傳輸,對于本地節(jié)點(diǎn)1輸入的數(shù)據(jù)采用YX路由規(guī)則進(jìn)行傳輸,保證數(shù)據(jù)鏈路不會互相占用。

(2) 目的端。頭包經(jīng)歷中間路由節(jié)點(diǎn)后發(fā)送至目的節(jié)點(diǎn),目的節(jié)點(diǎn)反饋成功信號將沿途的各網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行鎖定,源節(jié)點(diǎn)接收到反饋信號后發(fā)送數(shù)據(jù)包和尾包,經(jīng)過編碼后由輸入控制器傳輸至數(shù)據(jù)網(wǎng)絡(luò),到達(dá)目的節(jié)點(diǎn)后目的節(jié)點(diǎn)的緩存器將傳輸數(shù)據(jù)進(jìn)行緩存,緩存大小與網(wǎng)絡(luò)規(guī)模有關(guān)。在解碼器中,對數(shù)據(jù)的解碼結(jié)果進(jìn)行對比,對單粒子錯誤屏蔽,對多粒子錯誤反饋重傳信號,重新發(fā)送當(dāng)前事物。

解碼器中奇偶校驗(yàn)的結(jié)果記為奇偶校驗(yàn)值value,通過比較各自鏈路的value來判斷數(shù)據(jù)的正確與否。當(dāng)校驗(yàn)值value為0時,數(shù)據(jù)正確；當(dāng)value為1時,數(shù)據(jù)錯誤。若雙鏈路中的數(shù)據(jù)奇偶校驗(yàn)值value均為0,說明雙鏈路的數(shù)據(jù)均正確,則正確的數(shù)據(jù)會發(fā)送至目的端本地接口0和本地接口1中;若雙鏈路數(shù)據(jù)的校驗(yàn)值value為01(10),說明一條鏈路發(fā)生瞬時故障,選取另一條校驗(yàn)值value為0的數(shù)據(jù),發(fā)送至目的端本地接口0和本地接口1中,屏蔽瞬時故障的影響;若雙鏈路數(shù)據(jù)的value均為1,說明雙鏈路的數(shù)據(jù)均發(fā)生瞬時故障,則解碼器中反饋重傳信號給源節(jié)點(diǎn)與目的節(jié)點(diǎn),同時將緩存器中數(shù)據(jù)清空,進(jìn)行整體重傳。

2.4 路由算法

本文的NoC拓?fù)浣Y(jié)構(gòu)采用2D Mesh結(jié)構(gòu),可以很好地避免死鎖,同時擴(kuò)展性也很高。路由算法采用維序路由確定性路由算法,從源端到目的端采用雙鏈路發(fā)送數(shù)據(jù),路由算法采用雙路徑發(fā)送數(shù)據(jù),對于數(shù)據(jù)的傳輸,按照源節(jié)點(diǎn)和目的節(jié)點(diǎn)傳輸示意圖進(jìn)行傳輸,具體如圖3所示。

在2D-Mesh結(jié)構(gòu)中存在圖3a所示的源節(jié)點(diǎn)與目的節(jié)點(diǎn)的相對位置,對于該相對位置,本文提出的容錯機(jī)制采用一條鏈路沿XY路由方向發(fā)送數(shù)據(jù),另一條鏈路沿YX路由方向發(fā)送數(shù)據(jù),可以同時到達(dá)目的節(jié)點(diǎn)。對于圖3b所示的節(jié)點(diǎn)相對位置,采用一條鏈路沿XY方向發(fā)送數(shù)據(jù),另一條鏈路先傳播到相鄰節(jié)點(diǎn),再沿XY方向發(fā)送數(shù)據(jù),最后傳播到目的節(jié)點(diǎn)。

圖3 源端和目的端傳輸示意圖

由于數(shù)據(jù)包經(jīng)過數(shù)量不同的路由節(jié)點(diǎn),為了保證數(shù)據(jù)能夠同時到達(dá)目的端,在目的端接口增加緩存器對數(shù)據(jù)進(jìn)行緩存。

實(shí)際的網(wǎng)絡(luò)中會出現(xiàn)擁堵情況。若2條鏈路均處于擁堵狀態(tài),則反饋失敗信號,等待再次傳輸；若一條鏈路建立成功,另一條鏈路遇到擁堵,則成功的鏈路反饋信號在緩存器中等待16個周期,若沒有等到另一條鏈路信號,則反饋失敗信號,等待再次傳輸；若2條鏈路建立成功,則反饋成功信號,鎖定鏈路,進(jìn)行數(shù)據(jù)傳輸。

對于圖3b所示的邊界情況條件,有4種邊界傳輸情況,如圖4所示。

圖4 邊界傳輸情況

對于邊界條件下的路由轉(zhuǎn)向,應(yīng)該區(qū)分出來進(jìn)行研究。

對于邊界條件下的源節(jié)點(diǎn)和目的節(jié)點(diǎn)的數(shù)據(jù)傳輸,要采用改進(jìn)的算法進(jìn)行傳輸。

算法基本思想為:頭包進(jìn)入路由器后,路由模塊對數(shù)據(jù)頭包進(jìn)行解析,提取出目的節(jié)點(diǎn)與源節(jié)點(diǎn)坐標(biāo)；利用標(biāo)示位區(qū)分由本地節(jié)點(diǎn)0/1進(jìn)入網(wǎng)絡(luò)的數(shù)據(jù),通過源節(jié)點(diǎn)與目的節(jié)點(diǎn)的坐標(biāo)是否相同來區(qū)分是否存在同軸的情況,從而根據(jù)目的節(jié)點(diǎn)與源節(jié)點(diǎn)的相對位置,確定固定的傳輸路徑。

具體流程如下:從源節(jié)點(diǎn)到目的節(jié)點(diǎn),若頭包標(biāo)示位為0,則按照XY路由傳輸規(guī)則進(jìn)行傳輸,按圖4中實(shí)線路由方向;若頭包標(biāo)示位為1,則按照虛線路由方向進(jìn)行傳輸。若同X軸,從源節(jié)點(diǎn)發(fā)出的路由頭包進(jìn)行輪轉(zhuǎn)選取輸出端口,優(yōu)先方向?yàn)槟媳?微片沿X軸傳遞到目的節(jié)點(diǎn)同維度的X軸上,數(shù)據(jù)包再進(jìn)入目的節(jié)點(diǎn);若同Y軸,頭包微片輪轉(zhuǎn)優(yōu)先方向?yàn)槲鳀|,數(shù)據(jù)沿Y軸傳遞到目的節(jié)點(diǎn)同維度的Y軸上，再進(jìn)入目標(biāo)節(jié)點(diǎn),通過本地端口發(fā)送雙模數(shù)據(jù)進(jìn)入數(shù)據(jù)層網(wǎng)絡(luò)。

對于非邊界條件下的源節(jié)點(diǎn)和目的節(jié)點(diǎn)的數(shù)據(jù)傳輸,在目的節(jié)點(diǎn)和源節(jié)點(diǎn)存在XY路徑與YX路徑2條數(shù)據(jù)傳輸路徑的前提下,標(biāo)示位為0,沿XY路徑進(jìn)行傳輸,標(biāo)示位為1,沿YX路徑進(jìn)行傳輸。

路由算法描述如下,其中邊界條件設(shè)置為4,可以根據(jù)網(wǎng)絡(luò)規(guī)模進(jìn)行調(diào)整。

if(!sign&&DestX>LocalX‖

sign&& DestY=LocalY&&DestX>LocalX‖

sign&&DestY=IntY&&DestX>LocalX

&&!request[east] ‖

sign&&DestX=IntX!=’d4&&IntY=LocalY&&!request[east]

)

dest[east]=1;

if(!sign&&DestX

sign&& DestY=LocalY&&DestX

sign&&DestY=IntY&&

DestX

sign&&DestX=IntX&&IntY=LocalY&&!

request[west]

)

dest[west]=1;

if(!sign&&DestX=LocalX&& DestY>LocalY‖

sign&& DestY>LocalY‖

sign&&DestX=IntX&& DestY>LocalY&& !request[south]‖

sign&&DestY=IntY!=’d4&& IntX=LocalX&& !request[south]

)

dest[south]=1;

if(!sign&&DestX=LocalX&&

DetsY

sign&& DestY

sign&&DestX=IntX&&DestY

&& !request[north]‖

sign&&DestY=IntY&&IntX=LocalX

&& !request[north]

)

dest[south]=1;

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

由于瞬時故障的隨機(jī)性和偶然性,對上述設(shè)計進(jìn)行NoC仿真實(shí)驗(yàn),對比本文方案與傳統(tǒng)的端到端檢錯重傳方案。傳統(tǒng)端到端設(shè)計采用漢明碼編解碼,對瞬時故障也具有糾一檢二的功能,主要討論基于維序路由的容錯算法在容錯性能、網(wǎng)絡(luò)性能和面積開銷3個方面的可靠性效果。

3.1 容錯性能

基于維序路由的檢錯重傳機(jī)制采用對傳輸協(xié)議控制信號三模冗余容錯,對傳輸?shù)臄?shù)據(jù)包采用雙模自校驗(yàn)的方法來實(shí)現(xiàn)容錯,屏蔽單粒子錯誤,由于多粒子翻轉(zhuǎn)故障出現(xiàn)概率極低(約為0),因此基于維序路由的檢錯重傳的容錯性能約為100%。傳統(tǒng)的端到端檢錯重傳對傳輸數(shù)據(jù)進(jìn)行保護(hù),缺乏對控制信號的保護(hù),因此在容錯性能上略遜于基于維序路由的設(shè)計。

3.2 網(wǎng)絡(luò)性能

在NoC中,評價其性能主要有延遲和吞吐2類,因?yàn)樗矔r錯誤的概率太小,并且具有隨機(jī)性和偶然性,所以在實(shí)驗(yàn)仿真時要模擬故障注入。

設(shè)一個數(shù)據(jù)包為1 000個微片,每個微片大小為66 bit,設(shè)置注入率每個周期每個節(jié)點(diǎn)為1微片,因此故障注入率每個周期每個節(jié)點(diǎn)為10-6～10-1。

首先驗(yàn)證高故障注入率10-2的情況下多個任務(wù)對系統(tǒng)傳輸數(shù)據(jù)平均延遲的影響,結(jié)果如圖5a所示,記錄了在高故障率10-2和多個任務(wù)數(shù)的情況下,從源節(jié)點(diǎn)到目的節(jié)點(diǎn)數(shù)據(jù)包到達(dá)目的節(jié)點(diǎn)所需要的平均延遲。由圖5a可知,在低任務(wù)數(shù)下,維序容錯路由與端到端容錯路由的平均延遲周期差距不大,這是由于任務(wù)數(shù)少、瞬時故障概率出現(xiàn)低的原因;但隨著任務(wù)數(shù)的不斷增加,瞬時故障產(chǎn)生增多,端到端平均延遲增大,同時由于任務(wù)數(shù)增多,導(dǎo)致維序路由可用鏈路減少,延遲升高,但從總體延遲性能來看，維序路由的設(shè)計優(yōu)于端對端容錯路由設(shè)計。

同一個任務(wù)在不同的故障注入率情況下,2種算法從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的平均延遲如圖5b所示。由圖5b可知,隨著故障率的不斷提高,端到端容錯易受到瞬時故障的影響,而維序路由算法則更加穩(wěn)定;當(dāng)故障注入率達(dá)到10-1時,基于維序路由檢錯重傳的平均延遲比端到端檢錯重傳延遲低近40%。在故障不斷注入的情況下,基于維序路由檢錯重傳依然能保持較低的傳輸延遲?？梢?基于維序路由的算法明顯優(yōu)于端到端檢錯重傳。

圖5 平均延遲比較

不同故障率的注入會引發(fā)網(wǎng)絡(luò)中吞吐量的變化,而吞吐量的大小可以直觀地說明各個網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)入微片的平均數(shù)量。故障注入率與吞吐量的關(guān)系如圖6所示。

圖6 故障注入率與吞吐量的關(guān)系

由于維序路由具有雙端口,微片可以從本地節(jié)點(diǎn)0與本地節(jié)點(diǎn)1同時進(jìn)入到數(shù)據(jù)網(wǎng)絡(luò)中,這雖然增加了一部分功耗,但是相比于端到端的路由算法,吞吐量有了一定的增長。從圖6可以看出,在低故障率注入的情況下,2種容錯算法的平均吞吐量相差不大,但隨著故障率不斷上升,端到端檢錯重傳算法的劣勢越來越明顯,平均吞吐量開始下降,而基于維序路由的檢錯重傳,在高故障率注入的情況下,吞吐量的變化依然不是很明顯,容錯效果很好;當(dāng)故障注入率達(dá)到10-1時,基于維序路由檢錯重傳的平均吞吐量比端到端檢錯重傳高約33%。由此可見,本文基于維序路由的容錯重傳算法在吞吐量上明顯優(yōu)于端到端路由容錯重傳算法。

3.3 硬件開銷

實(shí)驗(yàn)采用Xilinx公司的軟件Vivado2016.3對本文提出的結(jié)構(gòu)進(jìn)行設(shè)計,采用Verilog語言分別對單端口路由結(jié)構(gòu)、端到端容錯重傳和基于維序路由的容錯方案進(jìn)行建模。各方案硬件開銷見表2所列。

表2 硬件開銷對比

本文方案采用雙端口設(shè)計,在硬件開銷上增加了端口設(shè)計以及緩存單元,因此消耗資源增加。端到端容錯方案數(shù)據(jù)采用漢明碼編碼,在路由中增加了復(fù)雜的編碼和解碼模塊,導(dǎo)致資源消耗增加。兩者相比,基于維序路由的容錯方案對硬件的消耗略小,容錯性能優(yōu)于端到端容錯重傳。

4 結(jié) 論

本文設(shè)計了一種基于維序路由的容錯重傳方案,在2D Mesh結(jié)構(gòu)下通過雙鏈路發(fā)送數(shù)據(jù),將數(shù)據(jù)從源端發(fā)送到目的端,并通過奇偶校驗(yàn)碼雙路徑自檢對瞬時故障進(jìn)行屏蔽；在保證容錯性能的同時,達(dá)到了延遲和吞吐量的優(yōu)化。通過NoC仿真實(shí)驗(yàn),在8×8的網(wǎng)絡(luò)模型下,對容錯機(jī)制進(jìn)行了驗(yàn)證,多組實(shí)驗(yàn)結(jié)果表明,基于維序路由的容錯重傳方案具有良好的容錯性能；在故障注入率為10-1時,傳輸延遲相對于端到端容錯重傳降低了約40%,同時吞吐量提高了約33%,完成了高可靠性的傳輸。