0 引言

    目前對(duì)路由器故障的檢測(cè)與容忍研究是片上網(wǎng)絡(luò)相關(guān)研究的一個(gè)重要方面。其解決辦法主要有以下兩類：(1)通過(guò)容錯(cuò)路由算法繞開故障節(jié)點(diǎn)，如文獻(xiàn)[1]和文獻(xiàn)[2]。但是這些方法容錯(cuò)粒度較大，一旦發(fā)現(xiàn)故障節(jié)點(diǎn)就選擇繞開或者丟棄，極大地浪費(fèi)了片上緩存等資源；(2)通過(guò)修改路由器微結(jié)構(gòu)進(jìn)行容錯(cuò)，如文獻(xiàn)[3]和文獻(xiàn)[5]，但是根據(jù)文獻(xiàn)[4]，在FIFO深度為32的路由器中，F(xiàn)IFO占用了94%以上的面積，發(fā)生故障的概率也最大，文獻(xiàn)[3]未對(duì)FIFO提出容錯(cuò)方案，這顯然對(duì)于設(shè)計(jì)容錯(cuò)路由器是不夠的。文獻(xiàn)[5]的檢錯(cuò)粒度大，且其采用的故障通道隔離技術(shù)浪費(fèi)了片上一些仍然可用的資源。文獻(xiàn)[4]提出了一種可靠的容錯(cuò)路由器架構(gòu)Vicis，但是文中提出的故障診斷是線下的，降低了路由器的工作效率。文獻(xiàn)[6]提出了一種在線的FIFO硬故障檢查方法，能夠在線對(duì)FIFO故障進(jìn)行檢測(cè)，但是故障覆蓋率不高，也未對(duì)最關(guān)鍵的FIFO控制部分進(jìn)行故障檢測(cè)，而且在對(duì)故障檢測(cè)后也未提出合適的容錯(cuò)方案。

    綜合以上研究，本文針對(duì)于片上網(wǎng)絡(luò)FIFO提出了一種故障實(shí)時(shí)容忍設(shè)計(jì)方案，首先針對(duì)于片上網(wǎng)絡(luò)FIFO中易發(fā)生的故障建立故障模型；然后提出一種針對(duì)于片上網(wǎng)絡(luò)路由器FIFO的實(shí)時(shí)故障檢測(cè)算法，最后提出了有效的容錯(cuò)機(jī)制容忍FIFO故障。

1 FIFO功能模型及故障模型

    本文選用的路由器是基本的蟲孔路由器，采用蟲孔交換機(jī)制，輸入通道中利用FIFO作為數(shù)據(jù)包緩存。

1.1 FIFO功能模型

    本文討論的是異步雙端口RAM型FIFO，其功能模型如圖1所示。

    FIFO相關(guān)控制信號(hào)作用如下：

    FF：FIFO滿信號(hào)，為1表示滿，為0表示不滿；

    EF：FIFO空信號(hào)，為1表示空，為0表示不空；

    RS：復(fù)位信號(hào)，將讀寫地址恢復(fù)到初始地址（Initial Address,IA），即（RAR）:=IA||（WAR）:=IA||FF:=0||EF:=1，||代表操作同時(shí)獨(dú)立發(fā)生；

    WE：寫使能，WE=1時(shí)允許寫操作；

    RE：讀使能，RE=1時(shí)允許讀操作；

    WClk：寫時(shí)鐘；

    RClk：讀時(shí)鐘。

1.2 FIFO故障模型

    本文結(jié)合RAM型FIFO中尋址故障和功能故障發(fā)生相似性，將片上網(wǎng)絡(luò)FIFO故障分為存儲(chǔ)單元陣列故障和FIFO控制邏輯故障兩大類。存儲(chǔ)單元陣列故障模型包括：固定型故障(Stuck-At Fault，SAF)、開路故障(Stuck-Open Fault，SOF)、地址譯碼器故障(Address Decoder Fault，ADF)、跳變故障(Transition Fault，TF)、耦合故障（Coupling Fault，CF)(包括倒置耦合故障CFin，固化耦合故障CFid，狀態(tài)耦合故障CFst)、數(shù)據(jù)延時(shí)故障(Data Retention Fault，DRF)和多端口故障(Multi-Port Fault，MPF)。FIFO控制邏輯故障模型主要有以下5種：

    FF=0,while(WAR)=(RAR) and (LO)=WO；

    FF=1,while(WAR)≠(RAR) or (LO)≠WO；

    EF=0,while(WAR=RAR) and (LO=RO)；

    EF=1,while(WAR)≠(RAR) or (LO)≠RO；

    RS:(WAR)≠IA or (RAR)≠IA or (LO)≠RO。

2 容錯(cuò)設(shè)計(jì)

2.1 實(shí)時(shí)故障檢測(cè)算法描述

    i=test_address；//FIFO地址指針

    j=0；//j代表單地址測(cè)試周期

    while(j≤2) do

        if(j == 1||j == 2)

        delay；//發(fā)現(xiàn)DRF故障

        temp1=read(i)；

        if(j == 0)

            if(0 < i < n-1) check(FF == 0&EF == 0);

            if(i = n-1)   check(FF == 0&EF == 1);

            original = temp1;

            write(i,!temp1) & temp2 = read(i);

        result = compare(temp1,temp2); 

    else if(j == 1)

        result = compare(temp1,original);

        write(i,!temp1) & temp2 = read(i);

        result = compare(temp1,temp2); 

    if(0 < i < n-1) check(FF == 0&EF == 0);

    if(i = n-1)    check(FF == 1&EF == 0);

            else

        result = compare(temp1,original);

        end if

        j = j+1;

    endwhile

    算法中i代表FIFO的測(cè)試地址，每次測(cè)試分為3個(gè)階段，由j來(lái)控制，當(dāng)j為0時(shí)執(zhí)行算法的第一個(gè)階段，讀出測(cè)試地址test_address的值，保存在一個(gè)臨時(shí)寄存器temp1中，并通過(guò)判斷是否是FIFO最后一個(gè)地址來(lái)檢查空標(biāo)志EF的狀態(tài)，隨后將temp1的值保存在一個(gè)寄存器original中，然后對(duì)temp1取反，將取反值寫到測(cè)試地址上，與此同時(shí)，讀出測(cè)試地址上的值與temp1做比較；當(dāng)j為1時(shí)，進(jìn)入第二個(gè)測(cè)試階段，先經(jīng)過(guò)一段時(shí)間的延遲，然后讀出測(cè)試地址上的值存在temp1中，與original值作比較，并將temp1值取反寫回到測(cè)試地址上，與此同時(shí)，讀出測(cè)試地址上的值，與temp1值作比較，并通過(guò)判斷是否是FIFO最后一個(gè)地址來(lái)檢查滿標(biāo)志FF的狀態(tài)；當(dāng)j為2時(shí)，同樣經(jīng)過(guò)一段延時(shí)，然后讀出測(cè)試地址上的值，最后一個(gè)階段的讀操作保證了對(duì)前兩個(gè)階段未發(fā)現(xiàn)的故障再次進(jìn)行檢測(cè)，有效增強(qiáng)了故障檢測(cè)能力。

2.2 故障覆蓋率分析

    針對(duì)前文描述的不同故障類型，本文對(duì)提出的測(cè)試算法能達(dá)到的故障覆蓋率分析如下。

    耦合故障(CF)： 算法對(duì)FIFO每個(gè)地址的值都采取了翻轉(zhuǎn)和讀寫交替操作，但是地址只遞增遍歷一次，對(duì)于侵略單元地址大于受害單元地址的故障不能檢出，因此只能覆蓋50%的耦合故障。

    數(shù)據(jù)延時(shí)故障(DRF)：算法描述中的Del代表了一定的延時(shí)操作，可覆蓋DRF。

    控制邏輯故障：可對(duì)空滿信號(hào)FF/EF故障進(jìn)行檢測(cè)，但是因?yàn)樗惴◤?qiáng)調(diào)實(shí)時(shí)性和無(wú)損性，所以對(duì)復(fù)位信號(hào)RS故障無(wú)法檢測(cè)。

2.3 FIFO重定向機(jī)制

    本文引入FIFO讀寫指針重定向表（Redirection Table），提出一種FIFO故障檢測(cè)與重定向機(jī)制。讀寫地址生成器生成的讀寫指針輸入到重定向表中，產(chǎn)生輸入到FIFO緩存的讀寫指針，其原理圖如圖3所示，深色方塊代表故障槽。在未檢測(cè)到故障時(shí)，重定向表與FIFO中地址一一順序?qū)?yīng)；當(dāng)檢測(cè)到故障后，測(cè)試電路產(chǎn)生地址更新信號(hào)address_update對(duì)重定向表進(jìn)行更新，有效避開了故障并充分節(jié)省了片上資源。

3 功能比較及實(shí)驗(yàn)結(jié)果

3.1 功能比較

    本文提出的路由器FIFO檢錯(cuò)容錯(cuò)方法與文獻(xiàn)[4]、文獻(xiàn)[6]提出的方法在故障覆蓋率、測(cè)試在線性和是否有容錯(cuò)機(jī)制分析比較如表1所示?？梢园l(fā)現(xiàn)本文方案故障覆蓋率較高，具有實(shí)時(shí)測(cè)試性，且包含容錯(cuò)機(jī)制。

3.2 仿真實(shí)驗(yàn)

    本文采用修改的開源片上網(wǎng)絡(luò)仿真器作為仿真實(shí)驗(yàn)平臺(tái)，使用systemC作為硬件描述語(yǔ)言，搭建的拓?fù)浣Y(jié)構(gòu)為4×4的mesh結(jié)構(gòu)，F(xiàn)IFO深度為6個(gè)微片，路由算法采用XY維序路由方式。根據(jù)提出的算法設(shè)計(jì)相應(yīng)的FIFO故障測(cè)試電路，并通過(guò)設(shè)置故障測(cè)試電路不同的時(shí)鐘周期觀察網(wǎng)絡(luò)的延時(shí)和吞吐率。

    圖4所示的是在不同的測(cè)試周期下網(wǎng)絡(luò)的吞吐率變化圖。隨著測(cè)試周期的不斷增加，吞吐率增長(zhǎng)越來(lái)越緩慢，逐漸接近一個(gè)固定值，這是因?yàn)楫?dāng)測(cè)試周期增加，對(duì)FIFO測(cè)試的頻率減少，測(cè)試過(guò)程對(duì)片上網(wǎng)絡(luò)正常工作模式的影響越來(lái)越小。

    圖5所示為不同測(cè)試周期下的網(wǎng)絡(luò)延時(shí)變化圖，隨著測(cè)試周期的不斷增加，平均網(wǎng)絡(luò)延時(shí)逐漸接近一個(gè)固定值。

    為測(cè)試本文容錯(cuò)機(jī)制對(duì)故障容忍的效果，在FIFO注入相同故障的情況下，比較基準(zhǔn)蟲孔路由器和本文提出的路由器在不同數(shù)據(jù)包注入率下的吞吐率和延時(shí)。圖6所示為吞吐率對(duì)比圖，隨著注入率增大，采用基準(zhǔn)路由器和本文路由器的網(wǎng)絡(luò)的吞吐率都逐漸接近飽和值，但是因?yàn)楸疚穆酚善鞑扇×巳蒎e(cuò)措施，吞吐率改善約為17.89%。

    圖7所示為延時(shí)對(duì)比圖，可以看出本文的路由器隨數(shù)據(jù)包注入率增加，延時(shí)均小于基準(zhǔn)路由器，這是因?yàn)榛鶞?zhǔn)路由器未設(shè)計(jì)合適的容錯(cuò)機(jī)制，隨注入率增加，基準(zhǔn)路由器的堵塞和丟包現(xiàn)象越來(lái)越嚴(yán)重。與基準(zhǔn)蟲孔路由器相比，本文路由器延時(shí)改善約25.67%。

4 結(jié)論

    本文根據(jù)FIFO讀寫特性，提出了一種可對(duì)片上網(wǎng)絡(luò)路由器FIFO故障實(shí)時(shí)檢測(cè)并對(duì)故障容忍的方法。實(shí)驗(yàn)結(jié)果表明，在故障條件下，能有效提高片上網(wǎng)絡(luò)吞吐率，并且降低了網(wǎng)絡(luò)延時(shí)。

參考文獻(xiàn)

[1] 姚磊，蔡覺平，李贊，等.基于內(nèi)建自測(cè)技術(shù)的Mesh結(jié)構(gòu)NoC無(wú)虛通道容錯(cuò)路由算法[J].電子學(xué)報(bào)，2012，40(5)：983-989.

[2] Liu Junxiu，Jim Harkin，Li Yuhua，et al.Fault-tolerant networks-on-chip routing with coarse and fine-grained look-ahead[J].IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems，2016，35(2)：260-273.

[3] Pavan Poluri，Ahmed Louri.Shield：a reliable network-on-chip router architecture for chip multiprocessors[J].IEEE Transactions on Parallel and Distributed Systems，2016.

[4] Andrew DeOrio，David Fick，Valeria Bertacco，et al.A reli-able routing architecture and algorithm for NoCs[J].IEEE Transactions on Computer-aided design of Integrated Circuits and Systems.2012，31(5)：726-739.

[5] 歐陽(yáng)一鳴，陳義軍，梁華國(guó)，等.一種故障通道隔離的低開銷容錯(cuò)路由器設(shè)計(jì)[J].電子學(xué)報(bào)，2014，42(11)：2142-2149.

[6] Bibhas Ghoshal，Kanchan Manna，Santanu Chattopadhyay et al.In-field test for permanent faults in FIFO buffers of NoC routers[J].IEEE Transactions on Very Large Scale Integration Systems.2016，24(1)：393-397.

[7] SEBASTIAN W，JAVIER N，MIKEL L.A survey on design approaches to circumvent permanent faults in networks-on-chip[J].ACM Computing Surveys.2016，48(4)：5920-5936.

作者信息:

杭彥希，徐金甫，陳松濤，郭朋飛

（解放軍信息工程大學(xué)，河南 鄭州450001）