文獻(xiàn)標(biāo)識(shí)碼： A
DOI：10.16157/j.issn.0258-7998.2017.02.006
中文引用格式： 林辛鑫，王君實(shí)，林水生，等. 低開(kāi)銷(xiāo)片上網(wǎng)絡(luò)容錯(cuò)傳輸機(jī)制[J].電子技術(shù)應(yīng)用，2017，43(2)：33-35，39.
英文引用格式： Lin Xinxin，Wang Junshi，Lin Shuisheng，et al. Low overhead fault tolerant transmission mechanism for Network-on-Chip[J].Application of Electronic Technique，2017，43(2)：33-35，39.
0 引言
隨著越來(lái)越多的處理器核(Cores)集成到單個(gè)芯片上，片上網(wǎng)絡(luò)（Network-On-Chips，NoCs）因其高帶寬和良好的靈活性、可擴(kuò)展性，已經(jīng)成為片上系統(tǒng)（System-on-Chips，SoCs）主流的通信結(jié)構(gòu)[1]。然而，隨著技術(shù)的快速發(fā)展，電路故障的幾率也隨之增長(zhǎng)，因此，想要實(shí)現(xiàn)高可靠性和高性能，容錯(cuò)手段尤為重要。
數(shù)據(jù)鏈路上的比特錯(cuò)誤被認(rèn)為是片上最突出的錯(cuò)誤來(lái)源[2]，它主要是由信道干擾造成的，例如串?dāng)_和耦合噪聲。為了解決這個(gè)問(wèn)題，曾有許多研究者提出可容錯(cuò)的片上網(wǎng)絡(luò)傳輸機(jī)制[3]，糾錯(cuò)和重傳是兩個(gè)常用的解決方法[4]。使用糾錯(cuò)編碼（Error Correction Codes，ECCs）盡管可以糾正一定數(shù)量的錯(cuò)誤，但糾錯(cuò)能力有限[5]。容錯(cuò)主要在數(shù)據(jù)鏈路層和傳輸層，分別對(duì)應(yīng)點(diǎn)到點(diǎn)（Hop-to-Hop，H2H）和端到端（End-to-End，E2E）[6]。H2H的糾錯(cuò)方法需要在每個(gè)路由器的每個(gè)端口提供一個(gè)譯碼器，以便在每一跳都能對(duì)數(shù)據(jù)包進(jìn)行糾錯(cuò)；而E2E的糾錯(cuò)方法只需在到達(dá)目的地后糾錯(cuò)。顯然，H2H極大地減少了面積開(kāi)銷(xiāo)，但糾錯(cuò)能力也被削弱。此外，重傳可以用來(lái)彌補(bǔ)糾錯(cuò)編碼的不足，提高可靠性。通過(guò)重傳，數(shù)據(jù)包無(wú)需在每一跳進(jìn)行糾錯(cuò)。然而，過(guò)多的重傳會(huì)導(dǎo)致更大的時(shí)延（Latency）和功耗（Power Consumption），特別是當(dāng)源地址和目的地址距離很大時(shí)這種開(kāi)銷(xiāo)更為致命[7]。另外，重傳也會(huì)帶來(lái)更大的網(wǎng)絡(luò)負(fù)載，從而導(dǎo)致網(wǎng)絡(luò)的擁塞和飽和。因此，為了平衡性能與開(kāi)銷(xiāo)，必須在重傳的次數(shù)和ECC的復(fù)雜度之間進(jìn)行權(quán)衡。
本文提出了一種針對(duì)鏈路上瞬時(shí)故障[8]的傳輸機(jī)制，在每一個(gè)路由器只對(duì)數(shù)據(jù)包的首部進(jìn)行輕量級(jí)的檢錯(cuò)，而將所有數(shù)據(jù)的糾錯(cuò)轉(zhuǎn)移到網(wǎng)絡(luò)接口(Network Interfaces，NIs)中進(jìn)行。該方案可以在不增加額外開(kāi)銷(xiāo)的情況下，提供比H2H和E2E更高的可靠性。
1 容錯(cuò)機(jī)制描述
本文所提出的傳輸機(jī)制采用了ECC和E2E超時(shí)重傳機(jī)制[9]。數(shù)據(jù)包在源NIs中編碼，并在目的NIs進(jìn)行譯碼。如果譯碼正確，目的節(jié)點(diǎn)向源節(jié)點(diǎn)發(fā)送一個(gè)確認(rèn)信號(hào)（ACK）確認(rèn)傳送成功；否則，直接丟包。為了實(shí)現(xiàn)重傳機(jī)制，源節(jié)點(diǎn)的NIs將對(duì)數(shù)據(jù)包進(jìn)行備份。如果在發(fā)包后的特定時(shí)間內(nèi)沒(méi)有收到ACK，源NIs將重傳備份的數(shù)據(jù)包，當(dāng)收到正確的ACK再將備份的包從緩存中刪除。在正確接收前，數(shù)據(jù)包可能需要重傳多次。
所有NIs都將提供譯碼器，重用這些單元進(jìn)行糾錯(cuò)，可以在提高可靠性的同時(shí)降低硬件開(kāi)銷(xiāo)。包頭在路由器中檢錯(cuò)，而負(fù)載部分通過(guò)旁路通道傳輸，并不進(jìn)行檢測(cè)。如果沒(méi)有檢測(cè)到錯(cuò)誤，數(shù)據(jù)包將遵循路由算法傳輸?shù)较乱粋€(gè)路由器，如圖1右上部分所示。
如果在包頭中檢測(cè)到錯(cuò)誤，數(shù)據(jù)包將進(jìn)入本地NIs進(jìn)行糾錯(cuò)，包括包頭和負(fù)載。隨后，校正過(guò)的數(shù)據(jù)包回到網(wǎng)絡(luò)中繼續(xù)傳輸，如圖1左上部分所示。當(dāng)然，如果錯(cuò)誤個(gè)數(shù)超出糾錯(cuò)碼的糾錯(cuò)能力，數(shù)據(jù)包將在此處被直接丟棄，如圖1右下部分所示。
如上所述，路由器提供的是簡(jiǎn)單的檢錯(cuò)電路而非譯碼電路，極大降低了面積和功耗。另一方面，重用NIs中的譯碼器進(jìn)行糾錯(cuò)和重傳機(jī)制使得可靠性有了保障。
2 關(guān)鍵電路結(jié)構(gòu)
2.1 網(wǎng)絡(luò)接口結(jié)構(gòu)
為了讓糾錯(cuò)后的數(shù)據(jù)包能重新回到網(wǎng)絡(luò)中，需要在NIs中增加一個(gè)回送通道和相應(yīng)的控制邏輯。在本方案中，到達(dá)目的NIs的不僅是正確的數(shù)據(jù)包，還有頭部包含錯(cuò)誤的數(shù)據(jù)包。因此，所有數(shù)據(jù)包都將首先經(jīng)過(guò)譯碼器對(duì)包括包頭和負(fù)載的所有數(shù)據(jù)進(jìn)行糾錯(cuò)。如果某一個(gè)包的錯(cuò)誤個(gè)數(shù)超過(guò)了糾錯(cuò)碼的能力，則在此丟掉它。
如果正確糾錯(cuò)的數(shù)據(jù)包的目的地址與NIs的地址相匹配，數(shù)據(jù)包將進(jìn)入輸出隊(duì)列，等待上層處理單元（Processing Elements，PEs）調(diào)用，如圖2(a)所示。否則數(shù)據(jù)包將進(jìn)入回送緩存（Buffer），如圖2(b)所示。在這種情況下，ECC的輸出不是原信息而是編碼后的碼字。此處使用回送緩存的目的是為了保證數(shù)據(jù)包的完整性，回送緩存比輸入隊(duì)列更優(yōu)先使用輸入信道。一旦輸入信道中沒(méi)有數(shù)據(jù)包，回送緩存可以立刻使用該信道注入數(shù)據(jù)。
2.2 糾錯(cuò)檢錯(cuò)編碼
本文采用了一種結(jié)合漢明（7，4）碼和交織的奇偶校驗(yàn)碼的作為檢錯(cuò)器（Detectors）。它可以糾正單個(gè)比特的隨機(jī)錯(cuò)誤并檢測(cè)2 bit的突發(fā)錯(cuò)誤。
漢明碼具有低開(kāi)銷(xiāo)、易于實(shí)現(xiàn)的特性，被廣泛應(yīng)用于NoCs[10]。編碼電路如圖3所示，首先使用漢明（7，4）碼對(duì)數(shù)據(jù)進(jìn)行編碼，隨后將得到的7 bit碼字分為奇數(shù)部分和偶數(shù)部分，分別采用奇偶校驗(yàn)碼編碼。最后的碼字由來(lái)自漢明碼的7 bit數(shù)據(jù)（r[0]-r[6]）和2 bit的奇偶校驗(yàn)位（c[0]，c[1]）構(gòu)成。
數(shù)據(jù)包在NIs進(jìn)行完全的編碼和譯碼。漢明碼在NIs中譯碼，而奇偶校驗(yàn)碼在每一次糾錯(cuò)后都要進(jìn)行更新。
在每個(gè)路由器中，只使用奇偶校驗(yàn)碼檢錯(cuò)，重新生成新的比特（s[0]，s[1]），并與原校驗(yàn)位（c[0]，c[1]）進(jìn)行比較。如果s和c相同，數(shù)據(jù)很可能是正確的。如果漢明（7，4）碼中只有一位錯(cuò)誤，s與c會(huì)有1 bit不同。因此，該檢錯(cuò)碼能覆蓋漢明碼中的所有可糾正的錯(cuò)誤。
3 仿真結(jié)果
3.1 硬件開(kāi)銷(xiāo)
在這一部分，ECC電路和網(wǎng)絡(luò)的面積、功耗、時(shí)序使用Synopsys Design Compiler的TSMC 45 nm 標(biāo)準(zhǔn)元件庫(kù)進(jìn)行綜合得到。
譯碼器、檢錯(cuò)器的關(guān)鍵電路時(shí)延和功耗如表1所示。顯然相比于漢明碼，本文提出的編碼只增加了0.55 ns的時(shí)延和5.5280 uW的能耗。在路由器中，檢錯(cuò)器比漢明碼的譯碼器更為簡(jiǎn)單，其時(shí)延僅僅是譯碼器的39.85%。
不同片上網(wǎng)絡(luò)結(jié)構(gòu)的面積如表2所示。由于H2H中每個(gè)路由器的每個(gè)端口都放置了譯碼器，其面積比基準(zhǔn)NoC增加了12.14%。而本文提出的方法在路由器的每個(gè)端口只需要一個(gè)簡(jiǎn)單的檢錯(cuò)電路，因此相對(duì)于基準(zhǔn)NoC只增加了1.48%的面積，并且比H2H少了10.66%。
3.2 時(shí)延和功耗開(kāi)銷(xiāo)
本部分結(jié)果使用ESYNet仿真器在8×8的蟲(chóng)洞交換網(wǎng)絡(luò)中對(duì)時(shí)延和功耗進(jìn)行仿真得到。數(shù)據(jù)包注入率為0.01 包/周期/路由器，采用均勻分布的隨機(jī)注入方式。路由算法為XY路由算法。通常情況下，一個(gè)數(shù)據(jù)包分為5片，但ACK包的長(zhǎng)度僅有1片。本文僅處理瞬時(shí)故障，錯(cuò)誤率從0.0到0.003錯(cuò)誤/比特/周期。對(duì)比項(xiàng)分別為H2H和E2E下的糾錯(cuò)加上E2E超時(shí)重傳。如表1所示，漢明碼譯碼器的最大時(shí)延遠(yuǎn)大于檢錯(cuò)器的時(shí)延，因此在仿真時(shí)，H2H需要為每個(gè)路由器的譯碼增加一個(gè)周期的時(shí)延。由于進(jìn)行了重傳，所有方案到達(dá)率理論上都能達(dá)到100%。
時(shí)延和功耗的仿真結(jié)果如圖4所示。從折線(xiàn)圖圖4(a)可以看出，當(dāng)沒(méi)有發(fā)生故障時(shí)，H2H方案的時(shí)延最大，因?yàn)樗拿恳惶黾恿艘粋€(gè)周期（Cycle）；E2E和提出的方案具有相同的時(shí)延。隨著錯(cuò)誤率的逐漸增加，E2E由于沒(méi)有糾錯(cuò)機(jī)制，其時(shí)延迅速增加并且在錯(cuò)誤率等于0.000 2時(shí)超過(guò)H2H。這是由大量的重傳造成的。相對(duì)于H2H，本文提出的方案在時(shí)延上略有優(yōu)勢(shì)，這是因此采用了輕量級(jí)的檢錯(cuò)碼。首先，由于檢錯(cuò)碼實(shí)現(xiàn)簡(jiǎn)單，在路由器中無(wú)需增加一級(jí)流水，即無(wú)需額外一個(gè)Cycle。此外，檢錯(cuò)碼覆蓋了大多數(shù)可糾正的錯(cuò)誤，因此減少了重傳的次數(shù)。
柱狀圖圖4(b)描述了功耗的變化情況，與時(shí)延具有相似的趨勢(shì)。在沒(méi)有故障時(shí)，3種方法有相同的功耗，隨著錯(cuò)誤率的增加，E2E的功耗同樣迅速增加，而H2H和提出的方案具有相似的走勢(shì)并且增長(zhǎng)緩慢。由于路由器的功耗比譯碼器或檢錯(cuò)器要大得多，顯然功耗主要來(lái)自重傳。E2E中大量的重傳導(dǎo)致了巨大的功耗。而對(duì)于另兩種方法，由于有效的容錯(cuò)機(jī)制極大減少了重傳帶來(lái)的功耗。
4 結(jié)論
本文提出了一種低開(kāi)銷(xiāo)的解決鏈路瞬時(shí)故障的傳輸機(jī)制。在每個(gè)路由器中，輕量級(jí)的檢錯(cuò)碼被用來(lái)對(duì)包頭檢錯(cuò)，而數(shù)據(jù)包的糾錯(cuò)則在NIs中由漢明碼來(lái)完成，超時(shí)重傳機(jī)制用來(lái)處理被丟棄的包。邏輯時(shí)序分析和仿真結(jié)果顯示，本文提出的方案能更好地實(shí)現(xiàn)可靠性、性能和開(kāi)銷(xiāo)之間的平衡。它不但能提供和H2H一樣的可靠性，并且比H2H和E2E具有更低的面積、時(shí)延和功耗上的開(kāi)銷(xiāo)。
參考文獻(xiàn)
[1] 付方發(fā)．基于片上網(wǎng)絡(luò)的MPSoC關(guān)鍵技術(shù)研究[D]．哈爾濱：哈爾濱工業(yè)大學(xué)航天學(xué)院，2012.
[2] SRIDHARA S R，SHANBHAG N R.Coding for system-on-chip networks: a unified framework[J].IEEE transactions on very large scale integration(VLSI) systems，2005，13(6)：655-667.
[3] MURALI S，THEOCHARIDES T，VIJAYKRISHNAN N，et al.Analysis of error recovery schemes for networks on chips[J].Trans.VLSI Systems，2000，8(4)：379-391.
[4] LEHTONEN T，LILJEBERG P，PLOSILA J.Analysis of forward error correction methods for nanoscale networks-on-chip[C].Proceedings of the 2nd international conference on Nano-Networks.ICST(Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering)，2007：3.
[5] BERTOZZI D，BENINI L，G De MICHELI，Error control schemes for on-chip communication links：the energy-reliability tradeoff[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2005(6)：818-831.
[6] PANDE P P，GANGULY A，F(xiàn)EERO B，et al.Design of low power & reliable networks on chip through joint crosstalk avoidance and forward error correction coding[C].2006 21st IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems.IEEE，2006：466-476.
[7] PARK D，NICOPOULOS C，KIM J，et al.Exploring fault-tolerant network-on-chip architectures[C].International Conference on Dependable Systems and Networks(DSN'06).IEEE，2006：93-104.
[8] YU Q，AMPADU P.Transient and permanent error co-management method for reliable networks-on-chip[C].Networks-on-Chip(NOCS)，2010 Fourth ACM/IEEE International Symposium on.IEEE，2010：145-154.
[9] SHAMSHIRI S，GHOFRANI A，CHENG K T.End-to-end error correction and online diagnosis for on-chip networks[C].2011 IEEE International Test Conference.IEEE，2011：1-10.
[10] DUTTA A，TOUBA N A.Reliable network-on-chip using a low cost unequal error protection code[C].22nd IEEE International Symposium on Defect and Fault-Tolerance in VLSI Systems(DFT 2007).IEEE，2007：3-11.
作者信息:
林辛鑫，王君實(shí)，林水生，黃樂(lè)天
（電子科技大學(xué) 通信與信息工程學(xué)院，四川 成都611731）