面向3維片上網絡的輕量級細粒度容錯機制

周 君 李華偉 王天成 李曉維

1（計算機體系結構國家重點實驗室（中國科學院計算技術研究所） 北京 100190）2（中國科學院大學 北京 100049）（zhoujun＠ict．ac．cn）

面向3維片上網絡的輕量級細粒度容錯機制

周 君1，2李華偉1王天成1，2李曉維1

1（計算機體系結構國家重點實驗室（中國科學院計算技術研究所） 北京 100190）2（中國科學院大學 北京 100049）
（zhoujun＠ict．ac．cn）

A Lightweight Fine－Grained Fault－Tolerant Scheme for 3DNetworks－on－Chip

片上網絡（networks－on－chip，NoC）是3維集成電路的主要通信技術之一．其中，路由器是3維片上網絡的重要組成部件．現有的面向3維片上網絡中路由器的容錯技術，通常采取路由器整體冗余技術或者直接舍棄失效路由器的方法，這導致網絡資源損失較為嚴重．提出一種面向3維片上網絡的輕量級細粒度容錯機制，充分利用故障路由器中仍能正常運行的有效資源，保障系統通信．提出的容錯機制包括一種高可靠性路由器微體系結構設計和一種與之匹配的容錯路由機制．通過實驗對比和分析，相比較于已有的3維片上網絡容錯機制，提出的細粒度容錯機制具備較高的通信性能和可靠性，同時面積和功耗開銷較小．

片上網絡；3維mesh；細粒度；容錯；路由機制

片上網絡（network－on－chip，NoC）是一種主流的3維集成電路［1－2］通信技術．網絡中的每一個處理單元（processing element，PE）皆通過網絡接口（network interface，NI）及路由器節點（簡稱“節點”，下文同）與網絡中的其他處理單元通信．不同的節點（node）是通過水平或者垂直鏈接（link）與周圍的其他節點通信的．圖1所示的是一個典型的4× 2×3的3維mesh網絡．圖1中每個節點表示一個路由器，是網絡通信的基本單元部件．

Fig．1 A sketch of the 3Dmesh NoC．圖1 3維mesh結構片上網絡示意圖

隨著集成電路復雜度和集成度的提高，片上網絡通信也受到了較為嚴重的影響，部件故障發生概率不斷提高．為了保證集成電路的正常通信，需要引入高效的容錯機制．一般而言，片上網絡的故障分為瞬時性故障和永久性故障．這些故障可能發生在處理單元、鏈接、或者是路由器中．在本文中，我們主要關注的是3維片上網絡中的永久性故障．這類故障不可修復，對于片上網絡的正常功能有較為嚴重的影響．

本文的主要研究目的，是針對資源有限且存在永久性故障的3維片上網絡，提出并實現一種低成本、高可靠性，且通信性能適度降級（相比較于無故障網絡，下文同）的容錯機制．

國內外面向傳統2維片上網絡路由器容錯機制的研究已經有較豐富的研究成果，但是面向3維片上網絡的相關研究進展較少．通常，針對片上網絡路由器永久性故障的容錯機制主要有以下4類［3－4］：

1）將故障的路由器內部模塊由對應的冗余模塊整體替換；

2）通過在路由器中故障部分添加一些外圍邏輯電路使數據包繞過故障區；

3）設計細粒度的高可靠性路由器微體系結構，利用路由器剩余有效資源執行網絡任務；

4）使用容錯路由機制，直接繞過故障路由器．

通常，路由器包含控制通路和數據通路2部分．控制通路包括路由計算單元（routing computation unit，RCU）和仲裁器（arbiter）；數據通路包括流水線寄存器（pipeline register，PR）、端口緩存（port buffer）、內部鏈接和交叉開關（crossbar，CR）．圖2表示的是一個典型的路由器內部模塊面積分布，我們可以從中發現數據通路整體占據了較大的面積［4］．

Fig．2 A typical area distribution of the NoC router．圖2 片上網絡路由器面積的典型分布

由于冗余機制和設計外圍電路的方法會產生一定的面積和功耗需求，電路規模越大該需求越明顯．因此，在低成本的設計前提下，這2項容錯技術對于面積較大的路由器數據通路并不適用．另一方面，控制通路占據的面積相對于數據通路小很多，則可以考慮使用冗余機制或設計外圍電路的方法進行容錯，對系統整體開銷的影響不大．

由于數據通路占據了路由器中的較大面積，這使得數據通路的故障發生概率比控制通路高出很多，因此這里我們主要關注的是數據通路上的功能模塊故障．考慮到系統開銷，成本較低的細粒度高可靠性路由器微體系結構設計和容錯路由機制將是合適的選擇，特別適合于某些資源受限的多處理器芯片．

同時，我們注意到，3維片上網絡中路由器的功能模塊一般比2維片上網絡的對應功能模塊的結構要更加復雜．因此，3維片上網絡路由器的功能模塊故障對網絡通信會產生更加嚴重的影響．這也為引入細粒度的路由器容錯控制提供了可能性，從而獲得較高的通信可靠性．因此，路由器中數據通路上的模塊功能需要細化來提高路由器的容錯能力．

在本文中，我們提出一種面向3維片上網絡的輕量級細粒度容錯機制，包括：

1）一種新的高可靠性路由器微體系結構．在該結構中，我們細化了交叉開關的功能，使得故障路由器中的有效資源可以繼續工作．

2）一種與提出的路由器微體系結構匹配的低成本容錯路由機制．在該機制中，我們給出了一種基于邏輯的3維容錯路由算法．同時，本文還提出一種用于引導該路由算法的3維轉向模型，用于避免網絡通信的死鎖現象，并且保證3維mesh網絡中較高的轉向公平度和流量平衡．

1 片上網絡細粒度容錯機制

已有的面向片上網絡的細粒度容錯機制主要面向的是傳統的2維片上網絡．

在文獻［5］中，一個傳統的2維片上網絡路由器中的交叉開關被分為2個獨立的子模塊．東向和西向的通信由行交叉開關子模塊管理．類似地，北向和南向的通信由列交叉開關子模塊控制．這種結構可以緩解路由器中東－西向和南－北向2個維度上可能出現的通信競爭，并且在其中一個交叉開關子模塊出現故障時保證路由器的部分功能依然可以正常執行．在文獻［6］中，2維片上網絡的路由器故障被分為靜態故障與動態故障2類．該文提出了動態緩存交換機制（dynamic buffer swapping，DBS）和動態多路選擇器交換機制（dynamic MUX swapping，DMS），分別用于發生故障的路由器輸入緩存和交叉開關，用有效的模塊“交換”失效的資源．與前二者不同，文獻［4］關注的是路由器中的“切片級（slicelevel）”故障，作者采用時分復用（time division multiplexer）技術，利用數據通路上功能模塊的有效切片維持路由器的正常操作．

以上的容錯機制主要關注的是路由器微體系結構的可靠性設計．此外，也有一些容錯機制不僅設計了不同的路由器結構，同時還提出了相應的防死鎖路由機制．在文獻［7］中，作者通過在線的診斷，獲得路由器中永久性故障的細節信息；同時，結合網絡中的通信沖突區域信息，提出了一種基于代價矩陣的自適應路由機制．其中，代價矩陣用于判斷路由器合法輸出端口的優先級．緩存重用技術是文獻［8］中提出的另一種容錯技術．通過在路由器同一端口的輸入緩存和輸出緩存之間添加一種自通信通道（selfcommunication channel，SCC），經由有效內部鏈接繞過2個端口之間的故障鏈接．此外，該文還使用經典的奇偶轉向模型（Odd－Even turn model）［9］確保網絡無死鎖．

但是，針對片上網絡，尤其是3維片上網絡，現有方案中很少提出與路由器可靠性設計相匹配的容錯路由機制，從而缺少一個整體的、可以獲得較高通信可靠性和適度性能降級特性的片上網絡容錯機制．路由器微體系結構和路由機制之間的關聯在之前的工作中沒有得到較好的重視和體現．

在本文中，我們提出的輕量級細粒度容錯機制是面向3維mesh片上網絡的一個整體的容錯解決機制．具體而言，我們設計出一種新的針對路由器數據通路的可靠性微體系結構及其故障模型．此外，我們還提出一種與該高可靠性路由器微體系結構匹配的、基于邏輯的低成本容錯路由機制，其中還包括用于引導該路由機制的公平3維轉向模型和用于驅使數據包避開通信沖突區域的端口選擇機制．

2 相關工作

路由器可靠性設計、路由算法的執行方式和網絡防死鎖方法是本文方法的核心組成部分，本節將提供針對這些方面的一些背景技術．

2．1 路由器微體系結構

在傳統2維片上網絡中，每個路由器有5個端口．每個端口對應一個方向：東（east，E），南（south，S），西（west，W），北（north，N）和本地（local，L）．在3維網絡中，隨著垂直鏈接的引入，又添加了上（up，U）和下（down，D）2個方向的端口．如圖3（a）所示，標準的7×7路由器在3維片上網絡中應用廣泛［10］．

Fig．3 Conceptual view of the routers in 3DNoCs．圖3 3維片上網絡路由器概念圖

在文獻［11］中，Lafi等人提出一種層次化路由器，其示意圖如圖3（b）所示．該路由器由一個5×5的水平子路由器和一個4×4的垂直子路由器組成．在這個結構中，路由器的整體功能并沒有改變，同時可以有效緩解不同內部子路由器之間的通信競爭．與標準的路由器相比，層次化路由器可以獲得較高的系統通信性能和容錯能力．

但是，層次化路由器內部2個子路由器以及本地端口間的密切聯系是彼此的功能獨立性的一大阻礙．例如，垂直子路由器的故障不僅影響到本地數據的接收與發送，還會影響到來自或待發送至水平子路由器的數據包通信．因此，我們提出一種新的高可靠性路由器微體系結構來更好地解決這一問題．

2．2 基于邏輯的分布式路由

一般而言，路由算法有2種實現方式：一種是基于邏輯，另一種是基于路由表．基于邏輯的路由算法，比如XYZ路由，具備時間和空間的有效性，不足是這種方法的靈活性較差．而基于路由表的實現方式比較靈活，不過可能引入較大的面積和時延開銷．

Flich等人在文獻［12］中提出一種基于邏輯的分布式路由算法（logic－based distributed routing，LBDR）．該算法是一種最短路徑路由算法，通過4個連接位（CE，CS，CW，CN）和8個路由位（REN，RES，RSE，RSW，RWN，RWS，RNE，RNW）由轉向模型引導執行．其中，連接位表明相應的鄰居節點是否可連接，路由位表明鄰居節點是否能夠接收需要發生該路由位下標所示轉向的數據包．例如，CE＝1和RES＝1表明當前節點的東邊鄰居節點是可連通的，同時能夠接收東南方向的數據包（允許ES轉向）．此外，作者在文獻［12］中還將LBDR拓展至任意方向（即東、南、西、北4個方向）的前2跳場景，并命名為LBDRe（extended LBDR）方法．

考慮到LBDR及LBDRe的低成本特性和較好的靈活性，本文在3維場景下對其進行了融入容錯特性的拓展，詳見3．3節的介紹．

2．3 3維轉向模型

通常，轉向模型和虛通道技術是2種最常見的用于解決片上網絡死鎖問題的方法［13－15］．由于虛通道會引入額外的緩存面積和復雜的控制邏輯，因此轉向模型對于開銷敏感的電路更加適用．

在3維mesh網絡中，若干轉向模型也被相繼提出．Glass等人在文獻［16］中提出了3種轉向模型，分別是West－South－First，North－Up－Last和Negative－First．這些模型是基于2維場景中的West－First，North－Last和Negative－First模型［16］拓展而來．在文獻［17］中，Pasricha等人提出另一種3維轉向模型4NP－First．這個模型可以分為2個子模型：4N－First和4P－First．虞瀟等人在文獻［18］中將3維空間劃分為8個區域，共禁止12個轉向．基于此模型，作者提出了一種名為TFRA的高度自適應路由算法．Chiu在文獻［9］中，給出了一種基于奇偶轉向模型拓展的經典3維轉向模型OE－3D．在文獻［19］中，Dahir等人同樣也是在奇偶轉向模型的基礎上設計了名為Balanced－OE的3維轉向模型．在該模型中，奇偶轉向模型和一種修改后的奇偶轉向模型分別被應用于3維集成電路的奇數器件層和偶數器件層，使得網絡流量相對于OE－3D變得更加平衡．由于文獻［17－18］中在全網絡范圍中存在不同的轉向模型，需要使用虛通道支持，因此，這2種方法并不適用于低開銷容錯機制的設計．

Balanced－OE作為OE－3D的改進型版本，是目前最新提出的3維轉向模型．在3．4節中，我們將對Balanced－OE的轉向公平度和網絡通信流量平衡作進一步的改進．

3 本文方法

本文目的是提升路由器微體系結構的可靠性，同時利用LBDR和LBDRe的特點使我們的容錯機制輕量級化．

3．1 可靠性路由微體系結構

針對文獻［11］中的層次化路由器，一旦數據包需要在水平和垂直方向之間交叉路由，同時某一個子路由器出現故障，則會使整個層次化路由器的功能失效．此外，當數據包到達目的節點，如果垂直子路由器存在故障，則對應的處理單元將無法獲得該數據包．

在本文中，我們提出一種新的高可靠性路由微體系結構Re－MA（reliable micro－architecture），來進一步提高3維片上網絡的通信可靠性．如圖4所示，本文提出的路由器微體系結構主要針對數據通路上的重要模塊交叉開關進行優化，而并不像層次路由器那樣將路由器劃分為若干子路由器．圖4中，交叉開關劃分為水平交叉開關子模塊和垂直交叉開關子模塊2部分．為了獲得較好的容錯能力，我們選用文獻［5］中的2維交叉開關結構設計水平交叉開關子模塊，通過設置行交叉開關和列交叉開關（即圖4所示的行通信模塊和列通信模塊），分離水平2維空間中的東－西向和南－北向通信，緩解通信競爭，提高子模塊容錯能力．和層次化路由器中的子路由器類似，Re－MA中的每個交叉開關子模塊都是控制不同方向維度上的通信．但與之不同的是，Re－MA中每個交叉開關子模塊的功能相對獨立，之間關聯較少．在數據包被路由分流模塊分流之后，數據包可以根據自己的目的端口選擇對應的交叉開關子模塊進行輸出操作．在這樣的架構下，即使其中一個交叉開關子模塊出現故障無法正常使用，也不影響所有輸入路由器的數據包通過另一個交叉開關子模塊輸出．并且，本地輸出端口獨立于其他輸出端口，這樣本地的輸出操作就不會受到路由器水平、垂直通信的影響．

Fig．4 The proposed Re－MA for routers．圖4 路由器的Re－MA結構

應注意到，Re－MA是2級流水架構．第1級流水由路由分流模塊負責執行，其中包括路由計算（routing computing，RC）和開關分配（switch allocating，SA）；第2級流水負責交叉開關傳輸（crossbar traversal，CT）．路由分流模塊其實可以視作一個虛擬模塊，因此在圖4中也是用虛線框表示．該模塊是由路由計算單元、仲裁器和一些額外的分流判斷邏輯構成，主要功能是根據路由計算的結果將由本地處理單元注入網絡或者經過當前路由器的數據包分流至對應的交叉開關子模塊或者是本地端口．此處的分流判斷邏輯可以通過一個簡單的1∶2的DEMUX實現．相對于路由器整體面積而言，其所占比重很小．因此，與控制通路類似，這一部分電路的容錯機制可以通過冗余技術來實現．

3．2 故障模型和故障診斷

故障模型對于一個失效模塊的分析至關重要．故障模型設置的不同會極大影響容錯機制的設計復雜度和執行效率．在引言部分我們已經提到，本文主要關注的是路由器數據通路上的故障模塊．作為數據通路上重要的組成部分，輸入端口緩存和交叉開關占據了數據通路較大的面積比例．例如，在文獻［20］中的示例路由器中，FIFO緩存和交叉開關分別占據了67．68%和11．14%的比例．因此，大部分的故障可能發生在這2個部件上［6，20］．在本文中，我們基于此提出相應的故障模型．

這里，我們引入故障矩陣來記錄檢測到的故障信息．圖5所示是2個故障矩陣的示例．其中，“Input”表示路由器輸入端口，“Output”表示輸出端口．矩陣中的“1”表示相應2個端口之間的通信正常，“0”則表示無法通信的情形．為了避免死鎖，片上網絡中禁止180°的路由轉向，因此相應的矩陣元素值置為“－”．顯然，在圖5（a）中，該故障矩陣對應的路由器的水平交叉開關子模塊中的行通信模塊出現故障，因此目的輸出端口在東－西向的數據包無法正常通過路由器輸出．同理，在圖5（b）中，除了水平交叉開關子模塊中的列通信模塊，路由器的東向（E）端口的輸入緩存也同樣失效．

Fig．5 Examples of the fault matrice for routers．圖5 路由器故障矩陣示例

電路的故障診斷技術主要是用來定位故障的位置，同時確定故障的類型和其他相關信息．由于本文主要關注的是永久性故障，因此適宜采用離線式的診斷技術．離線式故障診斷可以通過生產測試（production test）和內建自檢（built－in self－test，BIST）等技術執行．在本文的容錯機制設計中，負責診斷執行的檢測模塊設置于網絡的各處理單元中，這樣可以緩解路由器的設計成本壓力．

在系統通電后，特定的故障檢測數據包由處理單元中的檢測模塊經由網絡接口發送至本地路由器．通過分析獲得的反饋可以掌握路由器中的故障情況，并建立相應的故障矩陣．同時，故障矩陣也需要在檢測模塊中進行維護．隨后，生成的故障矩陣再次通過網絡端口傳回路由器中的指定寄存器保存，并通過路由器各端口發送至臨近的相關路由器節點（具體操作詳見3．3節）．故障矩陣通過使用路由器中設計的獨立串行線路進行傳輸．所以，存在故障的輸入端口緩存不會給故障矩陣的接收帶來影響．

需要注意的是，以上的相關操作需要在片上網絡的初始化階段內完成．所以，故障的診斷可以與網絡的正常通信相互隔離開來．由于瞬時性故障并不是本文關注的重點，我們設定在網絡常規通信時不進行內建自檢操作．同時，因為只涉及小范圍、小規模（例如，單個故障矩陣的信息量僅30b）的故障信息傳輸，網絡初始化階段不會占用太多的時間．另一方面，在路由器中只需要很少的面積開銷來用于傳輸和存儲故障矩陣．因此，這一部分額外的電路依然可以通過冗余技術來進行低成本的容錯操作．

3．3 輕量級路由算法

考慮到LBDR和LBDRe的低成本和高效率特性，我們在設計的新容錯機制中也采用這些方法來降低系統開銷．

需要注意的是，在3維片上網絡中，一些失效的節點可能會成為“死胡同”節點．一旦成為這種節點，數據包在該節點將無法繼續路由至目的節點．這主要是由于該節點的故障模塊及其他的操作限制導致的．由于LBDR和LBDRe這2個方法都是面向無故障的2維片上網絡設計的，并且獲取的路由信息有限，因此無法直接將其拓展至3維場景來避免可能的“死胡同”節點．這里，為了消除可能的通信“死胡同”現象，當前節點需要獲得更多的路由信息來加以判斷輸出端口的選擇．在本節中，考慮到較低系統開銷的設計需求，我們設定路由信息的來源范圍為距離當前節點2跳距離以內的任意節點，來有效避免數據包路由至“死胡同”節點．例如，如果西向（W）端口是可選擇的輸出端口之一，則不僅是當前節點西邊的距離在2跳范圍內的節點的故障矩陣，其余任意可經由W端口到達并且在2跳范圍之內的節點的故障矩陣也應發送至當前節點．這一點和LBDRe方法不同，后者只接收在某一個方向上的且距離在2跳范圍之內的節點路由信息．

因此，我們將與本文需求較為接近的LBDRe方法拓展至3維場景，并記為LBDRem（modified LBDRe）方法．該方法將容錯能力和“死胡同”現象納入考慮范疇．在3維mesh片上網絡中，除本地端口外，一個節點最多有6個端口．對于6個距離為1跳的鄰居節點而言，LBDRem的連接位的個數增至6b（CE，CS，CW，CN，CU，CD），同時路由位個數增至30b（REN，RES，REU，RED，REE，RSE，RSW，RSU，RSD，RSS，RWN，RWS，RWU，RWD，RWW，RNE，RNW，RNU，RND，RNN，RUN，RUE，RUS，RUW，RUU，RDN，RDE，RDS，RDW，RDD）．這些路由信息所表明的含義與LBDRe中的相同．

類似地，根據3維空間中方向和維度上的推導，對于距離當前節點為2跳的節點，需要另外的30b連接位和126b路由位作為當前節點的“輔助路由信息”．例如，CES表明當前節點的東邊鄰居節點（記為A）是否與節點A的南邊鄰居節點可連接；再比如，RSE?EU表明當前節點的東南方向的、與其距離為2跳的節點（記為B）是否可以允許從節點B西向（W）端口輸入的數據包發生EU轉向．由于原理類似，我們這里不再逐一列舉所有相應的連接位與路由位．作為“輔助路由信息”，距離當前節點2跳距離的節點路由信息主要是用于輔助距離當前節點為1跳范圍的路由信息的取值判斷，從而有效避開可能的“死胡同”節點．這是因為當前節點的下一跳節點選擇，最終還是要根據上面枚舉的6b連接位和30b路由位的取值進行操作．由于本文不考慮路由器節點之間的鏈接故障，因此LBDRem方法中的所有連接位取值始終為“1”．

LBDRem方法的執行步驟為2步：1）比較當前節點和目的節點的網絡坐標．比較的結果將得出可選數據包的繼續行進方向，從而使數據包與目的節點的距離更近一步．2）當前節點檢查掌握的所有路由信息，并決定選擇的合法輸出端口．需要說明的是，這里的路由信息是由在網絡初始化階段獲得的周邊鄰居節點的故障矩陣轉化而來．例如，假設圖5（b）中的故障矩陣來自于當前節點的北邊鄰居節點，則RNU和RND的取值為“0”，而CN，RNE，RNW，RNN的取值則為“1”．

3．4 用于引導路由算法的轉向模型

作為一種最短路徑路由算法，LBDRem可以為3維片上網絡的通信提供足夠的靈活性．但是，若不加入一些其他限制，網絡死鎖現象依然無法避免．作為一種有效且開銷較低的方法，轉向模型對于我們的輕量級容錯機制很適用．

與具有統一限制的轉向模型（即每個節點的轉向限制相同）相比，基于區域的轉向模型，例如2．3節提到的OE－3D和Balanced－OE模型，通常具備更好的路由自適應度和轉向公平性．在網絡的不同區域的節點，需要執行的轉向限制也不相同，這與“完全不同的多個轉向模型”的概念是有區別的，后者需要高成本的虛通道加以支持．以經典的奇偶轉向模型為例，如圖6所示．在2維mesh網絡中的奇數列和偶數列（奇、偶數列取決于列上節點的X坐標的奇偶性）．在奇數列上的所有節點禁止NW和SW轉向，而在偶數列上的節點禁止EN和ES轉向．

Fig．6 Turn constraints of the classical Odd－Even model．圖6 經典奇偶轉向模型示意圖

這里，我們提出一種相比較于最新的Balanced－OE模型轉向更加公平且流量更加平衡的轉向模型，命名為Full－OE（即完全OE模型）．Full－OE模型相比較于Balanced－OE模型的不同之處在于，二者的水平器件層內部的轉向限制不同．在垂直轉向（即層間轉向）方面，Full－OE模型采用和Balanced－OE模型相同的轉向限制．

圖7是Balanced－OE模型的水平器件層的轉向限制示意圖．傳統的奇偶轉向模型和修改后的奇偶轉向模型分別應用于3維集成電路的奇數器件層和偶數器件層．圖7（a）中虛線左邊是奇數列的禁止轉向NW和SW，右邊是偶數列的禁止轉向EN與ES．類似地，圖7（b）中虛線上面是奇數行的禁止轉向EN和WN，下面是偶數行的禁止轉向SE和SW．這一點也是Balanced－OE模型相比較于OE－3D模型的改進之處．OE－3D模型在各平面內僅采用單一的奇偶轉向模型，因此，Balanced－OE模型在整個網絡范圍內可以達到更好的轉向公平度及流量平衡．

ig．7 The prohibited turns of the horizontal layers in Balanced－OE．

圖7 Balanced－OE中水平器件層的轉向限制

在Full－OE模型中，為了進一步改善轉向公平度和網絡流量平衡，我們將奇偶轉向模型和其在2維mesh網絡中的其他3個對稱性“變體”一起加入到3維mesh網絡的水平器件層的轉向限制中，如圖8所示．和圖7類似，在圖8中，虛線左邊是奇數列的禁止轉向，右邊是偶數列的禁止轉向，虛線上面是奇數行的禁止轉向，下面是偶數行的禁止轉向．具體的轉向名不再一一列舉．從圖8（a）～（d），這4個模型依次執行于第4n，4n＋1，4n＋2，4n＋3（n≥0）層．更多不同的層內轉向限制可以使得3維網絡中的轉向公平度獲得提高，并能針對不同方向的數據包使得網絡中各區域的流量更加均衡，有效避免可能的沖突熱區的出現，網絡規模越大，相應的有益效果則越明顯．需要說明的是，禁止轉向和某些故障模塊帶來的實際效果一樣，也都會使得LBDRem算法中的相應路由位置為“0”．

Fig．8 The prohibited turns of the horizontal layers in Full－OE．圖8 Full－OE中的水平器件層轉向限制

3．5 端口選擇機制

由于在路由過程中可能會出現合法的可選擇輸出端口不唯一的情形，因此一個合適的端口選擇機制對于本文提出的完整容錯機制十分必要，以用于避開網絡熱點和沖突區域（congestion area）．

在文獻［21］中，Mak等人提出的動態規劃（dynamic programming，DP）選擇機制是一個面向傳統2維片上網絡的低開銷、高效率的端口選擇機制．相比較于經典的NoP機制［3，22］，DP并不是根據臨近的區域流量情況，而是根據實時的路徑規劃更新情況，在所有備選合法端口中獲取最優的選擇．在傳統2維網絡中，該機制與奇偶轉向模型的結合方案已經獲得較好的實驗效果．因此，我們將DP機制進行3維場景的拓展，記為DP－3D機制，以適用于本文提出的輕量級細粒度容錯機制．

4 本文方法示例及相關分析

4．1 方法示例

Fig．9 An typical example of the proposed scheme．圖9 本文方法的典型示例

為了利于本文所提容錯機制的理解，這里給出了一個具體的方法執行實例．圖9所示是一個典型的4×2×3的3維mesh網絡（注意，這里僅僅是用于方法示意，并沒有限定本文方法的適用規模）．節點0是源節點，節點20是目的節點．圖9中黑色的實心節點是無故障路由器節點，空心的節點（旁邊配有“×”）是存在故障的路由器節點．具體而言，相關的故障描述詳見表1所示：

Table 1 Node Fault Descriptions表1 節點故障描述

在網絡的初始化階段之后，源節點將對接收到的來自于節點1，2，6，7，8，9，15，16的故障矩陣進行分析，獲得這些節點的包括連接位和路由位的相關路由信息．對于節點0，節點1，7，8都是可以選擇的下一跳節點．但是，由于節點9的西向輸入端口的緩存失效，如果數據包在節點8發生UE轉向，則節點9就會成為“死胡同”節點．類似的潛在“死胡同”皆需要避免，否則會極大影響網絡的通信性能．根據Full－OE轉向模型和DP－3D端口選擇機制，我們假定在當前網絡條件下節點1被選為下一跳節點．在數據包到達節點1后，其下一步的路由操作依然需要依靠對在網絡初始化階段來自節點2，3，5，6，9，10，14，17的故障矩陣的分析．節點2，6，9是節點1可選的下一跳節點，隨后的操作與之前相同．類似地，基于當前節點的坐標和目的節點的坐標的比較，數據包依次通過節點14，13，12，并最終到達節點20．在這條路徑上，節點9不再是一個“死胡同”節點．這也說明，“死胡同”節點只是一個動態的概念．

與其他的細粒度容錯機制相比，本文所提的方法可以對3維片上網絡中的有限資源進行更加充分地利用．例如，即使節點9的垂直交叉開關子模塊發生故障，數據包依然可以通過其水平交叉開關子模塊中的列通信模塊繼續路由．節點13亦同理．

4．2 防死鎖特性分析

死鎖是由于數據包始終獲取不了需要的網絡資源，從而無法被發送至目的節點的現象［15］．3維轉向模型的死鎖通常是由平面（層）間和平面（層）內的轉向限制保障避免的．因此，這里將從平面（層）間、平面（層）內2方面進行對應的分析和說明．

設3維空間中X維度的2個方向分別為X＋和X－，分別表示X坐標的增大和減小．同理，我們還可以定義出Y＋，Y－，Z＋，Z－等方向．我們用X＋－Y＋表示一個2維空間中的轉向，該轉向是由X＋方向轉到Y＋方向．類似地，在3維空間中，2維轉向X＋－Y＋，X＋－Y－，X＋－Z＋，X＋－Z－結合在一起，構成了一個3維轉向X＋－YZ．由于本文所提的Full－OE模型采用的平面（層）間的轉向限制和Balanced－OE模型相同，即在奇數層禁止XY－Z－轉向，偶數層禁止Z＋－XY轉向．如同文獻［9］中經典的奇偶轉向模型的Y－X－和X＋－Y之間的聯系在2維空間中完全割裂一樣，Z＋－XY和XY－Z－之間的聯系在3維空間中也完全割裂，確保了平面（層）間無法形成通信抽象環，因此可以預防相應區域的死鎖發生．

另一方面，由于Full－OE模型的水平器件層內部的轉向模型僅僅是在不同的層采用了奇偶轉向模型的所有不同變體，因此，拓展的原理和Balanced－OE對OE－3D的拓展本質上是一樣的，并沒有引入“全新”的轉向限制．因此，Full－OE模型的平面（層）內的轉向限制可以確保相應區域內死鎖的避免．加之平面（層）間的轉向限制，可以保證Full－OE模型在整個3維mesh網絡中的無死鎖需求．

此外，還需要說明的是：1）由于網絡故障導致的路徑限制并不會影響到本文方法中死鎖的預防．這是因為轉向模型本身就是一種避免死鎖的有效方法，路徑限制僅可能導致本是合法的轉向無法繼續執行，而非法的轉向依舊不能使用．2）死胡同和死鎖現象雖然表現相似（即數據包無法繼續傳輸），但二者本質不同．死胡同是由于網絡限制（如故障、轉向模型等）的原因，導致數據包無法繼續“前進”的．

4．3 補充操作及不足

由于LBDRem方法是一個基于最短路徑的路由算法，源節點和目的節點之間的所有中間節點都須處于“最短路徑”上．但是，在一些特殊的場景中，例如源節點和目的節點在3維mesh網絡的同一邊上（即二者的網絡坐標在X，Y，Z這3個維度上有2個維度的坐標值都相等），一旦這2個節點之間的直線路徑（即最短路徑）上存在不可逾越的永久性故障，則會導致二者間通信的失敗．因此這里需要對類似場景做本文所提方法的補充說明．

一旦在2個節點之間的最短路徑上無法找到一個合適的下一跳節點，則在不觸犯Full－OE模型的前提下，在非最短路徑上結合DP－3D機制找到當前節點新的下一跳節點，并在此節點繼續使用2．2節中描述的容錯機制繼續對數據包進行路由．需要注意的是，由于網絡中不允許180°的路由轉向，因此數據包傳輸路徑上的前一個節點不能作為當前節點的下一跳節點的可選對象．

需要說明的是，本文提出的是一種輕量級的細粒度容錯機制，因此和其他的低成本容錯機制類似，本文的方法也存在一些相同的不足，例如由于網絡中的轉向限制和較多的故障致使2個節點之間的通信無法達成．但是與同類型輕量級方法相比，本文在相同的網絡故障率下具備更高的網絡通信可靠性和適度的性能降級特性．由于輕量級容錯機制針對高故障率網絡的性能保障意義不大，因此一般推薦適用的網絡故障率在0%～30%［23－24］，且盡量在10%以內（詳見第5節實驗部分的分析）．

5 實驗與分析

5．1 實驗方法介紹

為了評估本文提出的面向3維mesh網絡的輕量級細粒度容錯機制的通信性能和系統開銷，我們基于意大利卡塔尼亞大學的Noxim模擬器［25］設計了面向3維網絡的周期精準級（cycle－accurate）模擬器NoCer．我們還在若干實際應用的傳輸模式下進行了軌跡驅動（trace－driven）的仿真過程．其中，GEMS模擬器［26］基于全系統模擬器Simics［27］的功能設計，用于獲得實際應用傳輸模式的軌跡文件（trace）．實驗使用的基準測試集是PARSEC［28］．此外，我們還運用NoCer和Synopsys公司的Design Compiler分析了相關的系統開銷．

在本節中，我們將本文提出的容錯機制與其他2種同樣是完整的面向3維mesh網絡的容錯機制進行比較，這3種方法中的路由器微體系結構和容錯路由機制都是互不相同的．我們將7×7的傳統路由器（normal router）、基于路由表的（table－based）容錯路由算法、OE－3D轉向模型和NoP－3D端口選擇機制結合起來，形成第1種方法，命名為NTON方法（為方便說明，選取各部分英文表述的第1個大寫字母）．同樣，我們用層次化路由器（hierarchical router）、Balanced－OE模型和DP－3D選擇機制分別替換NTON方法中的對應部分，就形成了另一種容錯機制，命名為HTBD（命名規則與NTON同理）．類似地，本文提出的方法按照該命名規則可以命名為RLFD方法（Re－MA結構、Logic－based容錯路由、Full－OE模型、DP－3D選擇機制）．為了可以進行全面地比較，NTON，HTBD和本文提出的RLFD方法的網絡通信性能和系統開銷皆須通過上述的模擬器和綜合器進行評估．需要注意的是，本文提出的輕量級細粒度容錯機制適用于任意規模的3維 mesh網絡，這里，我們選用常見的4×4×4三維mesh網絡進行實驗和相應的結果分析．

片上網絡模擬器NoCer的整體參數設置詳見表2所示．我們選擇3種主要的綜合傳輸模式（synthetic traffic pattern）：Uniform，Transpose，Hotspot［15］．這里簡要介紹一下這3種模式．Uniform模式下，網絡中每個節點將一個數據包發送至其他所有節點的可能性相同．在Transpose模式下，一個坐標為（i，j，k）的節點只會將數據包發送至坐標為（I－i－1，J－j－1，K－k－1）的節點．這里，（I，J，K）是這個3維mesh網絡的最大維度．而在Hotspot模式下，某些節點會被設置成“熱點”．相比較于其他節點，這類熱點將會收到比Uniform模式下多h的數據量．這里，h是Hotspot模式的重要參數，常以百分數形式表示．

Table 2 Simulation Parameters of NoCer表2 NoCer模擬器的參數設置

由于本文關注的是存在故障的3維片上網絡，因此網絡中的故障率是一個核心參數．我們將路由器中的故障，包括輸入緩存故障和交叉開關內部故障按照最細的粒度隨機插入網絡中．即將路由器輸入緩存故障、交叉開關內部的水平交叉開關子模塊中的行通信模塊、列通信模塊及垂直交叉開關子模塊的故障作為一個等級的故障獨立開來對待，隨機插入網絡的各路由器中．如果針對具體的故障率，故障部分的數目不是一個整數，則對該數值進行向上取整操作．實驗的結果是通過多次實驗（≥20）取平均值的方式獲取，以消除模擬器中的隨機數的變化可能帶來的影響．

5．2 網絡通信性能分析

全局平均時延（global average latency，GAL）是一個重要的衡量網絡通信性能的指標．GAL的增長趨勢是通過一條在網絡注入率（injection rate，IR）不斷提升下持續變化的光滑曲線來表示的．曲線越平滑，說明容錯機制的時延性能越好．

首先，將3種容錯機制NTON，HTBD，RLFD在3種不同的綜合傳輸模式，以及網絡故障率（faultrate，FR）為0%（即無故障）和5%（常見故障率［3］）2種情形下進行比較．比較結果如圖10所示，RLFD的時延性能在2種故障率和3種綜合傳輸模式下都獲得較好的實驗效果．其中，在故障率為5%的網絡中，本文方法相比于NTON和HTBD的性能優勢更加明顯．特別地，在Uniform和Hotspot（h＝10%）模式下，RLFD可以獲得與無故障網絡中NTON很接近的時延性能．

Fig．10 Global average latency of the fault－tolerant schemes in 4×4×4 3Dmesh NoC．圖10 4×4×4三維mesh網路中的全局平均時延比較

根據上面的實驗，我們可以發現RLFD能夠獲得較好的性能．但是真實的應用程序產生的網絡流量多數是非均勻的，在很多情況下會呈現一種突發特性，這一點與之前的綜合傳輸模式不同．為了進行更加精確的性能分析，我們將PARSEC基準測試集作為3維網絡的負載進行仿真實驗．具體的全系統模擬器參數設置詳見表3所示：

Table 3 Full－System Simulation Configurations表3 全系統模擬參數設置

圖11是將NTON，HTBD，RLFD在PARSEC基準測試集作為負載下的網絡數據包平均延遲全部歸一化為NTON的網絡延遲的實驗結果，其中網路故障率設定為5%．我們可以發現，RLFD依然可以有效地降低數據包的傳輸延遲．特別地，對于類似于canneal和freqmine這樣的高度擁塞的應用程序，網絡提升的性能較為可觀；而對于像streamcluster這樣的低沖突的應用程序而言，性能的提升相對較少．平均來看，通過RLFD可以最大幅度降低12．67%、平均減少7．48%的數據包傳輸延遲．

Fig．11 Packet latency across PARSEC benchmarks．圖11 基于PARSEC基準測試集的數據包傳輸延遲

5．3 網絡通信可靠性分析

定義1．設NS是網絡中注入的全部數據包數目，NA是網絡中所有的目的節點在設定的時間內接收到的數據包的數目．片上網絡傳輸機制的可靠性指標R可以表示為［3，24］：

圖12給出了NTON，HTBD，RLFD三種容錯機制在Hotspot（h＝10%）模式下不同網絡故障率下的通信可靠性比較．實驗結果是在網絡注入率為0．003時獲得的．在網絡故障率分別為1%，5%，10%的4×4×4三維mesh網絡中，RLFD的可靠性指標分別為88．7%，76．4%，43．5%．相比于其他2種機制，本文提出的方法具有一定的優勢．類似的實驗比較結果在另外2種綜合傳輸模式（Uniform和Transpose）下同樣可以獲得．

Fig．12 Reliability of the fault－tolerant schemes under the Hotspot pattern（h＝10%）．圖12 Hotspot模式下（h＝10%）的可靠性指標比較

由于在較高的網絡故障率下，通信可靠性指標普遍偏低，比如故障率為5%和10%時的情形．這說明，相比于冗余技術，輕量級容錯機制在針對高故障率網絡方面確實存在一定的局限性．不過，在本例中，也可以通過降低網絡數據包注入率或者Hotspot模式下的h取值來獲得不同程度的可靠性指標提升．例如，在故障率為1%的網絡中，若數據包注入率降為0．001，本文所提RLFD的可靠性指標可達到98．6%．

5．4 系統開銷

作為一個面向開銷敏感的3維集成電路設計的容錯機制，RLFD同樣具備可以接受的面積與功耗開銷．由于采用了基于邏輯的LBDRem路由算法，并且不需要引入高成本的虛通道技術用于避免網絡死鎖現象，因此相比較于需要虛通道分配器（virtual channel allocator）、額外的復雜控制邏輯，并且是基于路由表實現的容錯機制而言，本文提出的方法需要較少的存儲空間．

我們通過Design Compiler的綜合結果對硬件開銷進行評估，利用的是UMC的90nm工藝庫．本文提出的輕量級細粒度容錯機制在路由器的開銷上相較于傳統的7×7路由器僅提高了5．2%．根據英特爾公司的報告［29］，路由器占據整個tile（即包括本地處理單元、網絡接口和路由器在內）11%左右的面積，因此，本文所提容錯機制的開銷小于1%．

通過NoCer模擬器，我們可以得到如表4中所示的能耗實驗結果．每種方法分別在網絡注入率（IR）為0．001和0．003、網絡故障率為5%的場景下，同時針對3種不同的綜合傳輸模式進行實驗．實驗結果說明本文提出的RLFD在網絡中的操作能耗要全面地低于其他2種容錯機制．尤其是在Hotspot（h＝10%）模式下，實驗效果較為明顯．

Table 4 Operation Energy for Analysis表4 操作能耗分析μJ

另一方面，隨著網絡注入率的提高，RLFD的操作能耗與NTON和HTBD之間的差值會逐步增大．這是因為網絡操作所需要的能量和GAL的變化趨勢是基本保持一致的．例如，在Hotspot（h＝10%）模式下，當網絡數據包注入率為0．001時，RLFD相比于NTON可以節省5．87%的能耗；而當網絡注入率升高為0．005時，RLFD相比于NTON則可以節省高達31．73%的能耗．

6 結束語

在本文中，我們面向3維片上網絡提出一種輕量級細粒度容錯機制．該機制提供了一種高可靠性的路由器微體系結構，以及一種與之匹配的容錯路由機制，二者組成了一個完整的面向3維mesh網絡的容錯機制．此外，本文的方法可以在不使用成本較高的虛通道技術下確保網絡能夠防止死鎖現象的發生．最后的實驗結果說明，本文提出的輕量級細粒度容錯機制相比于之前的相關研究成果，具備較好的通信性能及可靠性，同時系統開銷較小．

其次，本文所提方法在其他3維片上網絡拓撲結構（例如3DTorus，Folded Torus，BFT等）上的拓展，以及與針對路由器間鏈接故障的容錯機制的兼容性問題，是我們以后的重點研究方向．

［1］Banerjee K，Souri S J，Kapur P，et al．3－D ICs：A novel chip design for improving deep－submicrometer interconnect performance and systems－on－chip integration［J］．Proceedings of the IEEE，2001，89（5）：602 633

［2］Wang Di，Zhao Tianlei，Tang Yuxing，et al．A communication feature－oriented 3DNoC architecture design［J］．Journal of Computer Research and Development，2014，51（9）：1971 1979（in Chinese）（王諦，趙天磊，唐遇星，等．一種面向通信特征的3DNoC體系結構設計［J］．計算機研究與發展，2014，51（9）：1971 1979）

［3］Zhou J，Li H，Fang Y，et al．HARS：A high－performance reliable routing scheme for 3DNoCs［C］??Proc of IEEE ISVLSI 2014．Piscataway，NJ：IEEE，2014：393 397

［4］Liu C，Zhang L，Han Y，et al．A resilient on－chip router design through data path salvaging［C］??Proc of ACM?IEEE ASP－DAC 2011．New York：ACM，2011：437 442

［5］Kim J，Nicopoulos C，Park D，et al．A gracefully degrading and energy－efficient modular router architecture for on－chip networks［C］??Proc of ACM?IEEE ISCA 2006．New York：ACM，2006：4 15

［6］Qian Z，Teh Y F，Tsui C．A fault－tolerant network－on－chip design using dynamic reconfiguration of partial－faulty routing resources［C］??Proc of IEEE?IFIP VLSI－SoC 2011．Piscataway，NJ：IEEE，2011：192 195

［7］Kohler A，Schley G，Radetzki M．Fault tolerant network on chip switching with graceful performance degradation［J］．IEEE Trans on Computer－Aided Design of Integrated Circuits and Systems，2010，29（6）：883 896

［8］Zhang S，Han G，Zhang F．Very fine－grained fault－tolerant routing algorithm of NoC based on buffer reuse［C］??Proc of IEEE ICSESS 2013．Piscataway，NJ：IEEE，2013：758 762

［9］Chiu G．The odd－even turn model for adaptive routing［J］．IEEE Trans on Parallel and Distributed Systems，2000，11（7）：729 738

［10］Kim J，Nicopoulos C，Park D，et al．A novel dimensionallydecomposed router on－chip communication in 3Darchitecture［J］．ACM SIGARCH Computer Architecture News，2007，35（2）：138 149

［11］Lafi W，Lattard D，Jerraya A，et al．An efficient hierarchical router for large 3DNoCs［C］??Proc of IEEE RSP 2010．Piscataway，NJ：IEEE，2010：1 5

［12］Flich J，Rodrigo S，Duato J．An efficient implementation of distributed routing algorithms for NoCs［C］??Proc of ACM? IEEE NOCS 2008．New York：ACM，2008：87 96

［13］Seiculescu C，Murali S，Benini L，et al．A method to remove deadlocks in networks－on－chips with wormhole flow control［C］??Proc of IEEE?ACM DATE 2010．Piscataway，NJ：IEEE，2010：1625 1628

［14］Fu B，Han Y，Ma J，et al．An abacus turn model for time? space－efficient reconfigurable routing［C］??Proc of ACM? IEEE ISCA 2011．Piscataway，NJ：IEEE，2011：259 270

［15］Richard H．Deadlock free routing in mesh networks on chip with regions［D］．Link ping，Sweden：Link ping University，2009

［16］Glass C J，Ni L M．Adaptive routing in mesh－connected networks［C］??Proc of IEEE ICDCS 1992．Piscataway，NJ：IEEE，1992：12 19

［17］Pasricha S，Zou Y．A low overhead fault tolerant routing scheme for 3DNetworks－on－Chip［C］??Proc of IEEE ISQED 2011．Piscataway，NJ：IEEE，2011：1 8

［18］Yu Xiao，Li Li，Zhang Yuang，et al．A power－aware dead lock avoid three－dimensional full－adaptive routing algorithm for 3DNoC［J］．Acta Electronica Sinica，2013，41（2）：329 334（in Chinese）（虞瀟，李麗，張宇昂，等．一種面向功耗免死鎖3維全動態3DNoC路由算法［J］．電子學報，2013，41（2）：329 334）

［19］Dahir N，Mak T，Al－Dujaily R，et al．Highly adaptive and deadlock－free routing for three－dimensional networks－on－chip［J］．IET Computers ＆Digital Techniques，2013，7（6）：255 263

［20］Lin S，Shen W，Hsu C，et al．Fault－tolerant router with built－in self－test?self－diagnosis and fault－isolation circuits for 2D－mesh based chip multiprocessors systems［C］??Proc of IEEE VLSI－DAT 2009．Piscataway，NJ：IEEE，2009：72 75

［21］Mak T，Cheung P Y K，Lam K，et al．Adaptive routing in network－on－chips using a dynamic－programming network［J］．IEEE Trans on Industrial Electronics，2011，58（8）：3701 3716

［22］Ascia G，Catania V，Palesi M，et al．Implementation and analysis of a new selection strategy for adaptive routing in networks－on－chip［J］．IEEE Trans on Computers，2008，57（6）：809 820

［23］Akbari S，Shafiee A，Fathy M，et al．AFRA：A low cost high performance reliable routing for 3Dmesh NoCs［C］?? Proc of IEEE?ACM DATE 2012．Piscataway，NJ：IEEE，2012：332 337

［24］Ebrahimi M，Daneshtalab M，Plosila J．Fault－tolerant routing algorithm for 3DNoC using hamiltonian path strategy［C］??Proc of ACM?IEEE DATE 2013．Piscataway，NJ：IEEE，2013：1601 1604

［25］University of Catania．Noxim：The NoC simulator［EB? OL］．（2010－01－26）［2014－12－06］．http：??www．noxim．org

［26］Martin M M K，Sorin D J，Beckmann B M，et al．Multifacet s general execution－driven multiprocessor simulator（GEMS）toolset［J］．ACM SIGARCH Computer Architecture News，2005，33（4）：92 99

［27］Magnusson P S，Christensson M，Eskilson J，et al．Simics：A full system simulation platform［J］．IEEE Computer，2002，35（2）：50 58

［28］Bienia C，Kumar S，Singh J P，et al．The parsec benchmark suite：Characterization and architectural implications［C］?? Proc of IEEE?ACM PACT 2008．Piscataway，NJ：IEEE，2008：72 81

［29］Vangal S R，Howard J，Ruhl G，et al．An 80－tile sub－100－w teraflops processor in 65－nm cmos［J］．IEEE Journal of Solid－State Circuits，2008，43（1）：29 41

Zhou Jun，born in 1984．PhD candidate at the Institute of Computing Technology，Chinese Academy of Sciences．His main research interests include VLSI design and fault－tolerance．

Li Huawei，born in 1974．Professor at the State Key Laboratory of Computer Architecture，Institute of Computing Technology，Chinese Academy of Sciences．IEEE senior member，senior member of China Computer Federation．Her main research interests include VLSI test，verification and design for reliability．

Wang Tiancheng，born in 1983．Received his master degree from the Institute of Computing Technology，Chinese Academy of Sciences in 2009．Engineer at the State Key Laboratory of Computer Architecture．His main research interests include VLSI design and verification．

Li Xiaowei，born in 1964．Professor at the State Key Laboratory of Computer Architecture，Institute of Computing Technology，Chinese Academy of Sciences．IEEE senior member，senior member of China Computer Federation．His main research interests include VLSI test，design for reliability andfaulttolerance．

Zhou Jun1，2，Li Huawei1，Wang Tiancheng1，2，and Li Xiaowei11（State Key Laboratory of Computer Architecture（Institute of Computing Technology，Chinese Academy of Sciences），Beijing100190）2（University of Chinese Academy of Sciences，Beijing100049）

3Dnetwork－on－chip（NoC）is one of the main trends of the communication technology for 3Dintegrated circuits（ICs）．Each processing element（PE）in the networks communicates with its attached router node through the network interface（NI），and different nodes are connected to their neighbors with the horizontal or vertical links．With the increase of complexity and integration level，the interference to the communication of NoCs becomes more and more serious，and the probability of fault occurrence also rises up．In order to guarantee the normal operation of the circuits，effective fault－tolerant schemes need to be designed for the networks．The routers are one of the main components of NoCs．For most of the existing fault－tolerant schemes，faulty routers are usually completely replaced by the redundant ones or even deprecated．In this paper，we propose a lightweight fine－grained fault－tolerant scheme to take full advantage of the remaining valid resources of the routers in 3DNoCs．Our scheme includes a new reliable micro－architecture designed for the routers and a matching lightweight fault－tolerant routing scheme．Experimental results show that the proposed scheme possesses higher performance，improved reliability and lower overhead compared with the state－of－the－art fault－tolerant schemes for 3DNoCs．

networks－on－chip；3Dmesh；fine－granularity；fault－tolerance；routing scheme

TP302

2014－12－29；

2015－06－23

國家自然科學基金項目（61432017，61176040，61221062）；國家“九七三”重點基礎研究發展規劃基金項目（2011CB302501）This work was supported by the National Natural Science Foundation of China（61432017，61176040，61221062）and the National Basic Research Program of China（973Program）（2011CB302501）．