0 引言

　　以2000年由瑞典皇家理工學(xué)院Hemani、Janstch等人首先在論文中明確定義了“Network on Chip”的概念為標志[1]，片上網(wǎng)絡(luò)正式成為一個研究領(lǐng)域已經(jīng)15年了。自該領(lǐng)域誕生之初起，片上網(wǎng)絡(luò)的可靠性設(shè)計就被作為一個重要問題被各國研究者所重視。Benini和Micheli分析了片上通信網(wǎng)絡(luò)的分層模型并且給出了每層模型應(yīng)該具備的功能時，明確提出了可靠性設(shè)計的需求[2]。片上網(wǎng)絡(luò)的可靠性問題隨著集成電路工藝的進步和片上網(wǎng)絡(luò)互聯(lián)規(guī)模的擴大變得日趨嚴重。一方面集成電路工藝在向納米級演進的過程中，由于加工精度、功耗密度、集成規(guī)模等因素而導(dǎo)致工藝誤差、老化、單粒子翻轉(zhuǎn)等問題日益嚴重，從而導(dǎo)致器件的故障概率極大增加。另一方面隨著片上網(wǎng)絡(luò)規(guī)模的擴大而導(dǎo)致的總元件數(shù)量的上升，導(dǎo)致片上網(wǎng)絡(luò)中故障發(fā)生的總量急劇上升。因此通過合理的容錯設(shè)計方法提升片上網(wǎng)絡(luò)的可靠性成為片上網(wǎng)絡(luò)進一步發(fā)展過程中繞不開的一大難題。

　　集成電路的故障類型依據(jù)其發(fā)生頻率和產(chǎn)生條件可以劃分為臨時性故障(Transient Fault)、間歇性故障(Intermittent Fault)以及永久性故障(Permanent Fault)三類[3]。參考文獻[4]中總結(jié)了多種不同的物理效應(yīng)和三類故障的對應(yīng)關(guān)系。臨時性故障主要由于孤立事件翻轉(zhuǎn)（Single Event Upset，SEU和Single Event Transient，SET）以及電子系統(tǒng)內(nèi)部噪聲引起。此類故障的主要特點是臨時出現(xiàn)且發(fā)生位置隨機分布，與外界環(huán)境和工作條件關(guān)系不大。與臨時性故障相對應(yīng)的是永久性故障，主要由工藝誤差、老化、電遷移等原因引起的元器件損傷造成。永久性故障一旦發(fā)生將永久存在，且故障的總量將隨著集成電路使用時間的增加而持續(xù)增大。永久故障的位置分布有一定的隨機性，但由老化、電遷移等原因引起的永久性故障則在一定程度上受溫度、功耗密度等內(nèi)外部環(huán)境因素的影響。間歇性故障介于臨時性故障和永久性故障之間，主要是由于不同因素而導(dǎo)致的時序問題而誘發(fā)。雖然某些因老化等因素導(dǎo)致的間歇性故障會隨著集成電路使用時間的增加而退化為永久性故障，但更多的間歇性故障則是由于特定時刻串擾（Crosstalk）、溫度變化（Temperature Variation）、電壓緊急（Voltage Emergency）等內(nèi)外部環(huán)境因素造成的時序問題而引發(fā)。因而這些時序問題發(fā)生的時間和概率雖然也呈現(xiàn)出一定的隨機性，但卻更容易發(fā)生在集成電路中關(guān)鍵路徑（Critical Path）和受環(huán)境因素影響更大的區(qū)域。由于間歇性故障和臨時性故障均不會持續(xù)發(fā)生，在以往的一些研究中通常將其歸為一類故障加以研究[5]。但隨著集成電路工藝的進步和低壓/近閾值集成電路設(shè)計方法的興起，間歇性故障由于其發(fā)生概率極大提升而成為了一個重要問題[6]，近年來針對這類故障的研究明顯增加。

　　由于集成電路故障成因和類型的研究大多屬于器件和工藝層面的研究內(nèi)容，在研究容錯設(shè)計時通常需要根據(jù)設(shè)計目標的特點將其抽象為特定的故障模型以便深入研究。在抽象的過程中將不可避免地簡化故障的某些特征，而不合理的特征取舍可能導(dǎo)致基于此模型的容錯設(shè)計研究出現(xiàn)偏差，進而設(shè)計出容錯效率較低的硬件結(jié)構(gòu)或出現(xiàn)過度設(shè)計（Over Design）。對于片上網(wǎng)絡(luò)而言，故障可以在數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層和傳輸層分別被抽象為不同的模型。數(shù)據(jù)鏈路層主要將故障抽象為鏈路上信號的阻塞（Stuck-at）和翻轉(zhuǎn)（Upset）[7]。網(wǎng)絡(luò)層的故障模型主要為自適應(yīng)容錯路由研究服務(wù)，傳統(tǒng)上將故障劃分為鏈路故障和路由器故障[8]。在傳輸層的故障模型則主要是考慮數(shù)據(jù)包內(nèi)容錯誤或完全丟失[9]。這些模型在很大程度上降低了容錯設(shè)計的復(fù)雜度，但相應(yīng)的也隱藏了一些關(guān)鍵特性。但更為嚴重的是，這些模型大多直接借鑒傳統(tǒng)的計算機/通信網(wǎng)絡(luò)故障模型，對片上網(wǎng)絡(luò)的特異性沒有給予足夠的體現(xiàn)。造成這種情況的部分原因是因為片上網(wǎng)絡(luò)在研究的初期大多以架構(gòu)設(shè)計、拓撲分析、路由算法研究等相對高層次的研究為主，與之相伴的容錯設(shè)計研究也大多采用相對粗糙的模型。

　　隨著片上網(wǎng)絡(luò)研究的全面成熟和片上多核技術(shù)的普及，片上網(wǎng)絡(luò)已經(jīng)從系統(tǒng)結(jié)構(gòu)設(shè)計層面轉(zhuǎn)向?qū)崿F(xiàn)與應(yīng)用層面。自2007年Tilera公司推出了基于片上網(wǎng)絡(luò)互聯(lián)結(jié)構(gòu)的64核處理器Tile64[10]起，基于片上網(wǎng)絡(luò)的多核處理器芯片日漸增多。多倫多大學(xué)ABDELFATTAH M S等人于2014年發(fā)布了面向現(xiàn)場可編程門陣列（FPGA）的嵌入式片上網(wǎng)絡(luò)[11]則標志著片上網(wǎng)絡(luò)開始被用于多核處理器芯片以外其他類型的芯片中。而在這一過程中片上網(wǎng)絡(luò)的實現(xiàn)結(jié)構(gòu)也日益明確，多數(shù)關(guān)鍵模塊的實現(xiàn)形式已有一些基本定論。因此我們有條件重新思考在當前和未來集成電路工藝條件下片上網(wǎng)絡(luò)故障模型的合理性，從而得到更加合理、可行、適用的故障模型，為進一步提升容錯設(shè)計的容錯效率并減少過度設(shè)計帶來的額外開銷奠定基礎(chǔ)。同時正確地分析導(dǎo)致故障行為的物理效應(yīng)，也將有助于設(shè)計合理的容錯方案。本文將分別對現(xiàn)有片上網(wǎng)絡(luò)故障模型和容錯設(shè)計方法的合理性進行初步分析，為從事片上網(wǎng)絡(luò)容錯設(shè)計的相關(guān)研究者提供參考。

1 片上網(wǎng)絡(luò)故障模型合理性分析

　　傳統(tǒng)的片上網(wǎng)絡(luò)故障模型在片上網(wǎng)絡(luò)容錯設(shè)計的研究中曾發(fā)揮過重要作用，但隨著片上網(wǎng)絡(luò)的發(fā)展以及實用化程度的提高，片上網(wǎng)絡(luò)故障模型與實際的片上網(wǎng)絡(luò)故障行為之間的差距日益明顯。因此需要從造成片上網(wǎng)絡(luò)故障行為集成電路物理效應(yīng)出發(fā)，重新審視片上網(wǎng)絡(luò)故障模型的合理性。

　　1.1 傳輸層故障模型分析

　　傳統(tǒng)網(wǎng)絡(luò)的傳輸層故障模型主要分為數(shù)據(jù)包內(nèi)容錯誤與數(shù)據(jù)包完全丟失。其中數(shù)據(jù)包丟失是傳統(tǒng)網(wǎng)絡(luò)傳輸層所要解決的主要問題。造成傳統(tǒng)網(wǎng)絡(luò)中傳輸層數(shù)據(jù)包丟失的主要原因包括：

　　(1)數(shù)據(jù)包內(nèi)容錯誤超過底層協(xié)議可以恢復(fù)的極限而被底層硬件（如網(wǎng)卡等）直接丟棄而造成的數(shù)據(jù)包丟失；

　　(2)數(shù)據(jù)報頭錯誤導(dǎo)致錯誤的傳輸，如IP報頭、TCP報頭校驗錯誤時數(shù)據(jù)包會被丟棄而造成數(shù)據(jù)包丟失；

　　(3)由于傳輸過程中鏈路擁塞而導(dǎo)致數(shù)據(jù)包超過生存時間而被丟棄。

　　由于數(shù)據(jù)包內(nèi)容成果底層協(xié)議可以恢復(fù)的極限這一問題和底層故障概率以及容錯設(shè)計能力有關(guān)，傳統(tǒng)網(wǎng)絡(luò)中數(shù)據(jù)包由于傳輸距離較遠而容易出現(xiàn)錯誤，而片上網(wǎng)絡(luò)底層的故障概率卻并不一定很高。對這一問題的具體探討將在1.3節(jié)中再詳細討論。

　　相比于傳統(tǒng)網(wǎng)絡(luò)，片上網(wǎng)絡(luò)的傳輸層故障有其不同的特征。相對于傳統(tǒng)網(wǎng)絡(luò)，片上網(wǎng)絡(luò)的規(guī)模偏小且拓撲結(jié)構(gòu)相對固定，因而在設(shè)計之初可以通過多種仿真方法對片上網(wǎng)絡(luò)的傳輸帶寬作較為精確的分析。同時由于片上網(wǎng)絡(luò)所承載的是多處理器核心之間傳輸?shù)男畔?，由于信息傳輸實時性要求較高而導(dǎo)致?lián)砣苊馐瞧暇W(wǎng)絡(luò)設(shè)計優(yōu)化過程中必須要考慮的重要問題。因此由于鏈路擁塞而丟棄數(shù)據(jù)包這種行為通常在片上網(wǎng)絡(luò)中并不被允許，因而這一故障原因在片上網(wǎng)絡(luò)中并不存在。

　　與傳統(tǒng)網(wǎng)絡(luò)大多采用串行傳輸方式不同，片上網(wǎng)絡(luò)基本是基于Flit的并行傳輸方式，通常在首個Flit中包含地址、控制等重要信息。由于采用并行傳輸?shù)姆椒?，不同的位通常采用不同的物理連線傳輸并獨立地存儲于不同的存儲單元中，因此針對重要信息的位所用物理連線和存儲單元可以采用有別于普通位的保護措施以加強。如對地址信息采用性能更強的糾錯編碼，控制信號采用三模冗余（TMR）等[12]，這些鏈路層容錯措施將有效降低甚至消除由于報頭錯誤而導(dǎo)致的數(shù)據(jù)包丟失的問題。

　　綜上，在一個容錯設(shè)計合理的片上網(wǎng)絡(luò)中，傳輸層故障模型中的數(shù)據(jù)包丟失故障可以基本忽略。因此需要充分地分析底層設(shè)計的容錯能力以確定正確傳輸層故障模型是否需要考慮丟包故障。

　　1.2 網(wǎng)絡(luò)層故障模型分析

　　在過去10多年片上網(wǎng)絡(luò)容錯路由的研究通常面向由永久性故障引起的片上網(wǎng)絡(luò)路由節(jié)點或鏈路功能性問題，通常認為由于制造缺陷、老化等原因造成的晶體管失效是導(dǎo)致永久性故障的主要原因。在傳統(tǒng)網(wǎng)絡(luò)的網(wǎng)絡(luò)層故障模型中，故障一般被分為鏈路故障和路由節(jié)點故障以方便容錯路由算法的研究。在早期的片上網(wǎng)絡(luò)容錯路由的研究中也普遍地采用了這樣的劃分方法，這一時期片上網(wǎng)絡(luò)的研究大多停留在架構(gòu)設(shè)計與分析的層面。但隨著Intel等公司先后發(fā)布了一系列基于片上網(wǎng)絡(luò)的多核處理器芯片[13]之后，片上網(wǎng)絡(luò)的硬件實現(xiàn)結(jié)構(gòu)日益明確，相應(yīng)的網(wǎng)絡(luò)層故障模型也需要革新。

　　傳統(tǒng)網(wǎng)絡(luò)中路由節(jié)點故障可能由多種原因?qū)е?，如路由器的電源失效?dǎo)致其因斷電而無法工作，整個路由器的功能將完全喪失而導(dǎo)致與其相連的鏈路均處于斷開狀態(tài)。片上網(wǎng)絡(luò)路由節(jié)點與傳統(tǒng)網(wǎng)絡(luò)路由節(jié)點不同的是其功能完全由晶體管組成的邏輯電路實現(xiàn)，而晶體管并不會出現(xiàn)大面積同時失效的情況。因此，如果單個晶體管的失效不會導(dǎo)致整個片上網(wǎng)絡(luò)路由節(jié)點的功能完全喪失，則片上網(wǎng)絡(luò)路由節(jié)點故障實質(zhì)上并不存在。

　　一個典型的片上網(wǎng)絡(luò)路由節(jié)點硬件實現(xiàn)結(jié)構(gòu)如圖1所示。

　　從圖1中可以看出其數(shù)據(jù)通路（Data path）可劃分為輸入緩沖器、交換矩陣、輸出寄存器等三個部分。其中輸入緩沖器中任何晶體管失效最多只能導(dǎo)致與自身相關(guān)的輸入鏈路出現(xiàn)故障，輸出寄存器中任何晶體管失效同樣最多只能導(dǎo)致與自身相關(guān)的輸出鏈路失效。因而這兩部分任意晶體管失效均無法造成整個路由節(jié)點出現(xiàn)工作不正常的情況而導(dǎo)致路由節(jié)點故障。交換矩陣中的故障行為和其具體的實現(xiàn)結(jié)構(gòu)有關(guān)，參考文獻[14]中給出了三種不同的交換矩陣實現(xiàn)方式，可以分別由傳輸管矩陣、三態(tài)門矩陣以及標準CMOS邏輯門實現(xiàn)的多路復(fù)用器。傳輸管矩陣和三態(tài)門矩陣相比于標準的CMOS邏輯門的多路復(fù)用器而言雖然具有更小的面積和更低的功耗，但由于這兩種方案均存在延遲難以確定、驅(qū)動能力偏弱、可能由于控制信號的時序問題而產(chǎn)生臨時性的短路等問題而在實際的芯片中較少采用。采用傳輸管矩陣構(gòu)建交換矩陣時，若某個傳輸管由于某種原因處于導(dǎo)通狀態(tài)，則至少有一對輸入線與輸出線處于短路狀態(tài)，如圖 2（a）所示。處于這種狀態(tài)的交換矩陣不但影響故障傳輸管所在的輸出，還有可能通過短接的輸入線影響到其他輸出的電平。而采用的三態(tài)門矩陣和標準CMOS邏輯門的多路復(fù)用器構(gòu)建的交換矩陣由于其單向傳輸?shù)奶匦?，則只會影響到故障所在的輸出，如圖2（b）所示。由此可見，在不采用傳輸管矩陣構(gòu)建交換矩陣時，單個晶體管的失效只影響其所在的輸出端口，而不會波及其余輸出端口。因而在大多數(shù)不采用傳輸管實現(xiàn)交換矩陣的路由節(jié)點中，數(shù)據(jù)通路上任意位置出現(xiàn)單個晶體管失效均可以被等效為輸入鏈路故障或輸出鏈路故障，而不會出現(xiàn)路由節(jié)點功能整體失效的情況。

　　在對路由節(jié)點的架構(gòu)分析中，路由節(jié)點控制通路（Control path）故障通常被認為會導(dǎo)致路由節(jié)點整體功能失效。這是因為架構(gòu)設(shè)計人員在仿真中習(xí)慣于調(diào)用同樣的功能函數(shù)來模擬各個輸入和輸出鏈路的路由、仲裁等功能。但在實際的路由節(jié)點硬件結(jié)構(gòu)中，路由計算單元通常與輸入緩沖器配對實現(xiàn)，而仲裁電路則通常與輸出寄存器配對實現(xiàn)。這樣設(shè)計的原因是可以保證多個輸入輸出鏈路可以同時完成路由計算/仲裁的工作，從而最大限度地利用硬件并行工作的特性提升包交換的速度。參考文獻[15]中給出了路由計算模塊和仲裁模塊實現(xiàn)的示意圖，從中可以較為明確地獲悉這種配對的特性。因此，當某個路由計算單元中晶體管失效而導(dǎo)致該單元工作不正常時，可以認為與之配對的輸入緩沖器工作不正常而將其等價為輸入鏈路故障。而當某個仲裁模塊中晶體管失效而導(dǎo)致該單元工作不正常時也可以認為與之配對的輸出寄存器工作不正常而等效為輸出鏈路故障。因此，在一般情況下路由節(jié)點控制邏輯中單個晶體管失效也不會造成其整體功能失效。隨著失效晶體管數(shù)量的增加，可能出現(xiàn)多條輸入/輸出鏈路故障，從而使得節(jié)點大部分功能喪失。此時可以將多條鏈路故障等效為路由節(jié)點故障。

　　結(jié)合上面的分析可以得出這樣的結(jié)論，在使用常規(guī)的片上網(wǎng)絡(luò)路由器硬件結(jié)構(gòu)設(shè)計方案時，單個或少量的晶體管失效通常不會引起路由節(jié)點整體功能的失效或故障。這些故障基本可以被等效為鏈路故障而非路由節(jié)點故障。但隨著一些新的仲裁方法或路由算法的提出，其對應(yīng)的電路結(jié)構(gòu)可能會發(fā)生一些變化而導(dǎo)致出現(xiàn)路由節(jié)點故障的可能，但出現(xiàn)這種故障的可能性需要進一步探討。針對一個具體的片上網(wǎng)絡(luò)設(shè)計其容錯方案時對片上網(wǎng)絡(luò)路由節(jié)點的具體電路結(jié)構(gòu)進行適當?shù)姆治?，即可以確定是否有必要采用路由節(jié)點故障模型。目前大部分容錯路由的研究者已經(jīng)開始更傾向于使用鏈路故障模型而非路由節(jié)點故障模型。

　　1.3 鏈路層故障模型分析

　　鏈路層故障模型主要考慮由于數(shù)據(jù)在傳輸過程中某些比特位的翻轉(zhuǎn)、呆滯等現(xiàn)象造成該位出現(xiàn)錯誤。造成鏈路層故障的物理效應(yīng)有很多。元件老化、電遷移效應(yīng)、制造誤差等原因造成的某位信號線短路或斷路可以被認為是鏈路層的永久性故障，單粒子翻轉(zhuǎn)效應(yīng)等影響存儲單元狀態(tài)而造成數(shù)據(jù)錯誤可以被認為是鏈路層的臨時性故障，電壓緊急、串擾（Crosstalk）等在特定的外部環(huán)境或特定工作狀態(tài)下引起的數(shù)據(jù)錯誤可以被認為是鏈路層的間歇性故障。因而鏈路層故障實際包含了臨時性故障、間歇性故障和永久性故障三種不同的故障分類。這三種故障在鏈路層雖然故障行為表現(xiàn)相近，但由于其成因的區(qū)別導(dǎo)致使用鏈路層故障模型時其故障概率和故障注入方式有所區(qū)別。

　　臨時性故障由于是由單粒子翻轉(zhuǎn)等原因引起的，其發(fā)生時間和位置均近似呈隨機分布。因此針對臨時性故障的鏈路層故障模型可以視為以一定的概率隨機在更改任意位置、任意信號線的值，并不需要對故障的注入做特殊的處理。發(fā)生間歇性故障則明顯的受到環(huán)境以及具體硬件結(jié)構(gòu)的影響，其發(fā)生的時間和位置存在一定的規(guī)律性，但故障是否發(fā)生仍然具有一定的隨機性。永久性故障根據(jù)其產(chǎn)生原因不同，故障出現(xiàn)的規(guī)律也有較大區(qū)別。由加工誤差引起的永久性故障在分布時具有隨機性，但由于老化引起的永久性故障則明顯與環(huán)境有關(guān)，因而其空間位置的分布不是完全隨機的。所以鏈路層間歇性故障和永久性故障的發(fā)生概率和空間分布問題是一個需要討論的問題。

　　首先對鏈路層間歇性故障的發(fā)生概率和空間分布加以討論。串擾（Crosstalk）被認為是引起鏈路層間歇性故障的一個重要因素。一般認為由于信號線上特定的信號跳變引起某些信號變化延遲，若恰好與時鐘抖動等因素相配合則容易導(dǎo)致該信號被保存為一個錯誤的值，從而引發(fā)故障。一般片上網(wǎng)絡(luò)容錯設(shè)計研究者在考慮串擾引起的間歇性故障時，通常習(xí)慣于從信號跳變過程本身去加以考慮，通過編碼或其他方式改變跳變的圖案（Pattern）來對其加以避免[16]。但實際上串擾本身是否會發(fā)生其實需要一定的外部條件，同時其是否會引起故障實際上更取決于其是否真正破壞了數(shù)字集成電路的時序。要發(fā)生串擾通常需要信號線線距和線長均滿足一定的條件，因而可能發(fā)生串擾的位置通常在兩個路由節(jié)點之間的互聯(lián)線上而非其內(nèi)部連線。但從參考文獻[17]中明確給出的路由節(jié)點中各級流水線延遲的情況來看，在鏈路傳輸（Link Transmission，LT）即兩個路由節(jié)點之間信號傳輸階段的延遲要遠遠小于其他級流水線。換言之，在常規(guī)拓撲結(jié)果中鏈路傳輸本身并不處于關(guān)鍵路徑（Critical Path）上。因而不管是否出現(xiàn)因為串擾而導(dǎo)致信號延遲的情況，在鏈路傳輸階段的時序余量可以充分保證被下一級路由節(jié)點接收的信號處于穩(wěn)定狀態(tài)。但對于某些面向特定應(yīng)用的非規(guī)則片上網(wǎng)絡(luò)而言[18]，在網(wǎng)絡(luò)中存在一定的長走線，因而可能由于延遲較大而容易受到串擾的影響。造成間歇性故障的其他因素諸如電壓緊急、溫度等同樣導(dǎo)致特定位置的信號出現(xiàn)故障，通常這些故障更多出現(xiàn)在關(guān)鍵路徑上。在設(shè)計階段雖然設(shè)計者無法準確地預(yù)知所有故障發(fā)生的位置與概率，但卻可以通過對設(shè)計方案進行仿真與分析確定容易發(fā)生故障的薄弱環(huán)節(jié)，從而合理地設(shè)置和使用鏈路層故障模型。

　　鏈路層永久性故障的發(fā)生概率和空間分布同樣有一定規(guī)律可循。由于老化引起的永久性故障與老化條件有關(guān)，因而分析并確定容易引起老化的環(huán)境因素對確定這類故障發(fā)生的概率和空間分布是有很大幫助的。溫度是引起晶體管老化的重要原因，對于集成電路的溫度分布可以在設(shè)計階段即通過一系列的熱仿真得到。而由于工藝誤差或制造過程引起的永久性故障比較難以精確建模，但可以通過分析電路模塊的規(guī)模簡單等效得到，在此不再贅述。

2 容錯設(shè)計方法合理性分析

　　片上網(wǎng)絡(luò)的容錯設(shè)計方法已有相當數(shù)量的論文討論，但這些論文通常只注重介紹容錯方法本身，而對容錯設(shè)計方法的使用前提與使用場景缺乏深入分析與討論。這一現(xiàn)象導(dǎo)致容錯設(shè)計方法的合理性存在較大問題，因而本文結(jié)合之前對故障模型的分析對容錯設(shè)計方法的合理性進行必要的分析。

　　2.1 基于離線測試的容錯方法

　　基于離線測試的容錯方法是一種最基本的容錯方法，其目的在于提高芯片的良品率。較為典型的基于離線測試的容錯方法即為片上網(wǎng)絡(luò)自適應(yīng)路由。大多數(shù)自適應(yīng)路由都是在故障狀態(tài)已知的前提下，通過外部所給出的故障信息按自適應(yīng)路由算法調(diào)整信息的傳輸路徑以避開出現(xiàn)故障的鏈路或路由節(jié)點。

　　按具備自適應(yīng)路由能力的路由節(jié)點對故障信息的知曉程度不同，自適應(yīng)路由可分為基于全局信息的自適應(yīng)路由算法、基于局部信息的自適應(yīng)路由算法和基于本地信息的自適應(yīng)路由算法三類?；谌中畔⒌淖赃m應(yīng)路由算法需要使用整個網(wǎng)絡(luò)的各個資源的狀態(tài)信息。當然，一個路由器需要確切知曉網(wǎng)絡(luò)中所有資源的狀態(tài)信息非常困難，代價非常高。因而此類算法常采用空間迭代，使得每個路由器獲得等價的全局信息，如Q-Routing[19]。基于局部信息的自適應(yīng)路由算法需要路由節(jié)點知曉臨近節(jié)點的信息，F(xiàn)oN[20]以及FRR[21]是此類算法的典型代表。相比于全局信息，獲取局部信息的代價要小很多。此類自適應(yīng)路由算法也一直在優(yōu)化故障信息傳輸?shù)拈_銷?；诒镜匦畔⒌淖赃m應(yīng)路由算法則只關(guān)注與路由節(jié)點相連的鏈路或節(jié)點的狀態(tài)，Gradient算法[22]就是該類算法的代表。這三類算法中雖然基于全局信息的自適應(yīng)路由算法效果最好，但由于其信息傳播開銷最大而較少有人研究?；诒镜匦畔⒌淖赃m應(yīng)路由算法性能提升受到較大限制而導(dǎo)致優(yōu)化空間較小，但在故障概率較低的情況下已經(jīng)足以滿足設(shè)計需求。基于局部信息的自適應(yīng)路由算法是前幾年研究的熱點，其難點在于平衡信息傳播開銷、算法復(fù)雜度等多方面的因素。

　　在傳統(tǒng)的自適應(yīng)路由方法的研究論文中幾乎不曾提及如何檢測并確定某條鏈路或路由節(jié)點已處于故障狀態(tài)，其通常認為故障信息已經(jīng)確認并作為已知前提開展研究。因而，離線測試作為一種基本的檢測手段可以直接與這些自適應(yīng)路由算法相配合作為提高良品率的方法。但需要注意的是離線測試只能針對出廠后的芯片加以檢測，因而主要檢測由于生產(chǎn)加工問題而引起故障。這類故障的成因、分布及其行為在前文已有分析。在選擇或設(shè)計合理的自適應(yīng)路由算法時應(yīng)對其充分加以考慮，避免使用與之不相符合的故障模型或錯誤估計故障概率。

　　2.2 基于在線測試的容錯方法

　　與基于離線測試的容錯方法不同，基于在線測試的容錯方法往往需要與一定的在線測試手段相配合。首先通過在線測試確定故障的位置或發(fā)生的概率，再采取相應(yīng)的方法繞開或替換故障單元以達到容錯的目的。

　　基于編碼的在線檢測方法是開銷較小、實現(xiàn)也較為方便的一種。這種方法通過檢錯或糾錯編碼檢測傳輸過程中數(shù)據(jù)出現(xiàn)的錯誤。但由于糾錯編碼同時也具備錯誤數(shù)據(jù)恢復(fù)的功能，因而在大多數(shù)研究中把這類方法歸結(jié)于容錯方法而非在線檢測方法。但實際上合理運用糾錯或檢錯編碼并與測試數(shù)據(jù)注入方法配合是可以達到在線檢測效果的，在后文中將對此做一定的分析?；诰幋a的方法可以很方便地與重傳機制相配合構(gòu)成較為高效的混合糾錯重傳機制（hybrid FEC/ARQ）[23]，該方法對于臨時性故障的容錯效果較好。但使用混合糾錯重傳機制會導(dǎo)致比較大硬件開銷和傳輸延遲，因而通常被用于傳輸層容錯。

　　按照特定的規(guī)則向網(wǎng)絡(luò)注入專門的測試數(shù)據(jù)包，可以根據(jù)包的到達情況和接受到的數(shù)據(jù)對片上網(wǎng)絡(luò)的鏈路和路由節(jié)點加以檢測。與基于編碼的方法不同的是，由于發(fā)送的數(shù)據(jù)包內(nèi)容是確定的，可以在接收端通過比對檢測出鏈路中多個數(shù)據(jù)故障。由于其傳輸路徑可以提前設(shè)置，可以對路由節(jié)點中不同的傳播路徑加以測試[24]。使用特定的測試數(shù)據(jù)包不但可以判斷鏈路層故障引起的數(shù)據(jù)錯誤，還可以通過數(shù)據(jù)包能否正常地通過特定的傳輸路徑來判斷路由節(jié)點中某些控制邏輯是否出錯。當測試出路由節(jié)點的問題后將其映射為鏈路故障模型，再配合自適應(yīng)路由算法即可以實現(xiàn)網(wǎng)絡(luò)層容錯設(shè)計。采用專門測試數(shù)據(jù)包的另外一個優(yōu)點在于通過統(tǒng)計已到達數(shù)據(jù)包的錯誤概率，在明確數(shù)據(jù)包傳輸路徑的基礎(chǔ)上可以求解出不同鏈路或傳輸路徑上包的錯誤概率，進而對于診斷間歇性故障有極大的好處。

　　在線測試的另外一種方式是采用在線的內(nèi)建自測試(BIST)電路。這類在線測試方法需要針對片上網(wǎng)絡(luò)設(shè)計專門的電路測試電路[25]，并用適當?shù)姆椒▽⒈粶y電路與其他的部分電路隔離。采用內(nèi)建自測試電路可以在更細粒度的層面檢測故障，有利于采用更細粒度的錯誤恢復(fù)機制。但內(nèi)建自測試電路測試的規(guī)模與其測試粒度有關(guān)，測試粒度越細則電路復(fù)雜度和規(guī)模越大。近年來將內(nèi)建自測試電路用于片上網(wǎng)絡(luò)容錯設(shè)計的研究者主要把精力放在如何平衡在線檢測性能、粒度和代價。

　　2.3 基于糾錯和硬件冗余的容錯方法

　　糾錯與硬件冗余從本質(zhì)上來說屬于同一類方法。糾錯依靠傳輸更多的信息使得數(shù)據(jù)錯誤可以被修復(fù)，硬件冗余則通過在網(wǎng)絡(luò)中增加更多的硬件資源以使當部分硬件出現(xiàn)故障時片上網(wǎng)絡(luò)仍然可以正常運行。在傳輸更多信息時必然涉及到使用更多的硬件資源如連線或存儲單元來，因而也是一種意義上硬件冗余。嚴格意義上說，片上網(wǎng)絡(luò)自適應(yīng)路由算法就是利用了片上網(wǎng)絡(luò)互聯(lián)資源的硬件冗余來達到容錯目的。

　　糾錯的效果與糾錯編碼的復(fù)雜度以及傳輸過程中出現(xiàn)錯誤的概率有關(guān)。在端到端傳輸?shù)腻e誤概率顯然大于在兩個路由節(jié)點之間傳輸?shù)腻e誤概率。因而在兩個路由節(jié)點之間才有糾錯編碼的效果顯然好于端到端傳輸，但后者的面積、延遲、功耗等開銷要遠遠小于前者[26]。各種開銷的增加實際上會導(dǎo)致片上網(wǎng)絡(luò)的整體性能下降，在很多時候使得容錯設(shè)計失去了原本的意義。換言之，如果主動降低片上網(wǎng)絡(luò)的性能如運行速度等，往往可以使得間歇性故障概率下降而在使用端到端糾錯達到同樣的效果。這方面的研究目前尚缺乏比較全面和深入的分析。

3 結(jié)語

　　本文結(jié)合片上網(wǎng)絡(luò)的硬件實現(xiàn)結(jié)構(gòu)和先進工藝集成電路物理效應(yīng)對片上網(wǎng)絡(luò)存在的故障行為進行了總結(jié)，分別就傳輸層、網(wǎng)絡(luò)層和鏈路層的故障模型進行了詳細的分析。通過分析表明現(xiàn)有的故障模型是存在一定的適用范圍的。在此基礎(chǔ)上對不同故障模型所適用的應(yīng)用場景也進行了歸納總結(jié)。在分析故障模型的基礎(chǔ)上對現(xiàn)有的片上網(wǎng)絡(luò)容錯方法進行了總結(jié)，對其合理性和應(yīng)用方法作了初步分析。從本文的研究可以看出，片上網(wǎng)絡(luò)容錯設(shè)計雖然經(jīng)過多年的發(fā)展已經(jīng)取得了長足的進步，但目前各個研究點還相對孤立而未形成全面完善的解決方案或研究結(jié)論。片上網(wǎng)絡(luò)容錯設(shè)計還有賴于各國研究者的進一步大力研究。

參考文獻

　　[1] HEMANI A，JANTSCH A，KUMAR S，et al.Network on chip：An architecture for billion transistor era[C].In Proceedings of 18th conference of Norchip，2000：1-8.