0 引言

    目前對(duì)路由器故障的檢測(cè)與容忍研究是片上網(wǎng)絡(luò)相關(guān)研究的一個(gè)重要方面,。其解決辦法主要有以下兩類(lèi)：(1)通過(guò)容錯(cuò)路由算法繞開(kāi)故障節(jié)點(diǎn)，如文獻(xiàn)[1]和文獻(xiàn)[2],。但是這些方法容錯(cuò)粒度較大,，一旦發(fā)現(xiàn)故障節(jié)點(diǎn)就選擇繞開(kāi)或者丟棄，極大地浪費(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功能模型及故障模型

    本文選用的路由器是基本的蟲(chóng)孔路由器,，采用蟲(chóng)孔交換機(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)，將讀寫(xiě)地址恢復(fù)到初始地址（Initial Address,IA）,，即（RAR）:=IA||（WAR）:=IA||FF:=0||EF:=1,，||代表操作同時(shí)獨(dú)立發(fā)生；

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

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

    WClk：寫(xiě)時(shí)鐘,；

    RClk：讀時(shí)鐘。

1.2 FIFO故障模型

    本文結(jié)合RAM型FIFO中尋址故障和功能故障發(fā)生相似性,，將片上網(wǎng)絡(luò)FIFO故障分為存儲(chǔ)單元陣列故障和FIFO控制邏輯故障兩大類(lèi),。存儲(chǔ)單元陣列故障模型包括：固定型故障(Stuck-At Fault，SAF),、開(kāi)路故障(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)≠I(mǎi)A or (RAR)≠I(mǎi)A 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取反,，將取反值寫(xiě)到測(cè)試地址上,，與此同時(shí)，讀出測(cè)試地址上的值與temp1做比較,；當(dāng)j為1時(shí),，進(jìn)入第二個(gè)測(cè)試階段，先經(jīng)過(guò)一段時(shí)間的延遲,，然后讀出測(cè)試地址上的值存在temp1中,，與original值作比較，并將temp1值取反寫(xiě)回到測(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ì)前文描述的不同故障類(lèi)型,，本文對(duì)提出的測(cè)試算法能達(dá)到的故障覆蓋率分析如下,。

    耦合故障(CF)： 算法對(duì)FIFO每個(gè)地址的值都采取了翻轉(zhuǎn)和讀寫(xiě)交替操作，但是地址只遞增遍歷一次,，對(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讀寫(xiě)指針重定向表（Redirection Table）,，提出一種FIFO故障檢測(cè)與重定向機(jī)制,。讀寫(xiě)地址生成器生成的讀寫(xiě)指針輸入到重定向表中，產(chǎn)生輸入到FIFO緩存的讀寫(xiě)指針,，其原理圖如圖3所示,，深色方塊代表故障槽。在未檢測(cè)到故障時(shí),，重定向表與FIFO中地址一一順序?qū)?yīng),；當(dāng)檢測(cè)到故障后，測(cè)試電路產(chǎn)生地址更新信號(hào)address_update對(duì)重定向表進(jìn)行更新,，有效避開(kāi)了故障并充分節(jié)省了片上資源,。

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

3.1 功能比較

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

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

    本文采用修改的開(kāi)源片上網(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)蟲(chóng)孔路由器和本文提出的路由器在不同數(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)蟲(chóng)孔路由器相比,，本文路由器延時(shí)改善約25.67%,。

4 結(jié)論

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

參考文獻(xiàn)

[1] 姚磊，蔡覺(jué)平,，李贊,，等.基于內(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ó),，等.一種故障通道隔離的低開(kāi)銷(xiāo)容錯(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）