片上網絡容錯路由算法分析和評價

摘 要：片上網絡技術是借鑒并行分布式計算機及傳統計算機網絡的概念解決片上多核系統的通信問題。片上網絡代替片上總線通信，解決了片上總線結構所引起的可擴展性、效率、面積、功耗等問題。然而，片上網絡在數據傳輸過程中可能由于各種原因產生故障，因此片上網絡可靠性研究是當前一個研究熱點。首先總結了片上網絡故障分類，比較和分析了當前片上網絡容錯算法并給出其優勢和缺陷，最后對全文進行總結，并給出了片上網絡容錯算法的展望。

關鍵詞：

中圖分類號： ＴＰ３０２．８ 文獻標識碼： Ａ 文章編號：２０９５－２１６３（２０１１）０３－００６４－０３

Ａｎａｌｙｓｉｓ ａｎｄ Ｅｖａｌｕａｔｉｏｎ ｏｆ Ｆａｕｌｔ－ｔｏｌｅｒａｎｔ Ｒｏｕｔｉｎｇ Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ＮｏＣ

ＬＩ Ｂｅｎｊｕａｎ， ＷＡＮＧ Ｊｉａｆａｎｇ， ＪＩＡＮＧ Ｙｕ， ＬＩ Ｘｕｌｉａｎｇ

Ａｂｓｔｒａｃｔ： Borrowing ideas from the concept of parallel distributed processing system and traditional computer networks， Network-on-Chip technology solves the problems of multi-core SoC . NoC takes the place of the bus on the SoC to solve the reliability， power consumption， area， efficiency which caused by the bus .However， NoC may result in the faults when it transmits the data. So the reliability of network on-chip is a hot topic currently. This paper summarizes the classification of the network on-chip faults， analyzes and compares the fault-tolerant algorithms meanwhile， points out the advantages and disadvantages of these algorithms. Then the paper gives a conclusion. finally presents future works about fault-tolerant routing algorithms on NoC.

Ｋｅｙ ｗｏｒｄｓ：

０ 引言

根據ＩＴＲＳ（Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｔｅｃｈｎｏｌｏｇｙ Ｒｏａｄｍａｐ ｆｏｒ Ｓｅｍｉｃｏｎｄｕｃｔｏｒｓ，國際半導體技術路線圖）中的預測[１]，到２０１８年，單個芯片上集成的晶體管數目將達到２５６０億個。傳統以總線互連的片上系統無法滿足用戶對可展性、能耗、面積、可重用性、服務質量等方面需求。

２０００年，片上網絡（Ｎｅｔｗｏｒｋ ｏｎ Ｃｈｉｐ，以下簡稱ＮｏＣ）的概念被提出[２]。圖１顯示了一個二維４×４ ｍｅｓｈ ＮｏＣ結構，由圖可知：ＮｏＣ主要由交換單元、網絡接口和鏈路組成。在４×４ｍｅｓｈ中，一個晶體被分割成１６個對稱的功能獨立的子模塊。ＩＰ核被映射到這些塊上并同ＮｏＣ進行通信，每個ＩＰ核都與一個網絡接口和交換單元相連。每個交換單元都與４個鄰居交換單元相連。每個網絡結點由路由器、ＩＰ核、網絡接口組成，各個網絡結點又由鏈路相連接構成一個片上網絡。

片上網絡的研究內容包括拓撲結構、交換機制、服務質量、應用映射、路由器結構、路由算法等６個方面。在研究近年來國內外研究成果的基礎上，本文將片上網絡故障分為硬故障和軟故障兩種，并對解決硬故障的容錯路由算法進行分析和評價，最后指出片上網絡路由容錯算法的研究方向。

１ 片上網絡故障分析

在片上網絡研究領域，ＮｏＣ故障主要分兩種：一種是永久性故障（ｐｅｒｍａｎｅｎｔ ｆａｕｌｔｓ），主要由電轉移、制作工藝和測試挑戰等引起的加速老化效應導致的，又稱為硬故障[３]；另一種是瞬時性故障（ｔｒａｎｓｉｅｎｔ ｆａｕｌｔｓ），主要由于片上網絡路由器及之間的鏈路受到串擾、電磁干擾和電源噪聲的影響，而引起信號、邏輯值和數據位出錯等故障，又稱為軟故障。目前針對軟故障主要是包括校正、重傳、混合糾錯在內的三種解決方法。永久性故障是路由器資源模塊故障，一旦發生，就會永遠存在，不可逆轉；包括路由器節點失效和鏈路失效（圖２所示）[４]。硬故障是突發性的，又是永久性的，一旦發生，除了更換硬件外是無法修復的。所以在實際ＮｏＣ設計中，往往采用一定的容錯路由算法或者添加冗余硬件來實現對硬故障區域的繞道，從而解決問題。

２ ＮｏＣ容錯路由算法

在ＮｏＣ中，路由算法主要確定數據包的轉發端口，從而確定數據包從源節點到目的節點的轉發路徑。容錯路由算法就是在路由算法的基礎上增加容錯功能。容錯路由算法的優劣，直接決定了網絡時延和吞吐，影響ＮｏＣ物理設計。總體來說，Ｎｏｃ容錯路由算法可以分為基于自適應思想容錯路由算法、基于洪泛思想的容錯路由算法和混合類型容錯路由算法。

２．１ 基于自適應思想的容錯路由算法

適應性路由算法的特點是分組數據包從源節點到目的節點不只是存在唯一的一條路徑，而是多條路徑[５]。因此，適應性路由算法具有一定的容錯功能，好的適應性路由算法應能很好地解決網絡擁塞狀況，從而達到均衡網絡中各節點的負載，提高網絡整體性能的目的。根據路由適應性程度的不同，適應性路由又可以分為完全適應性路由和部分適應性容錯路由算法兩大類。

部分適應性容錯路由算法，主要通過限制一些方向的轉向來避免環路的形成，從而避免死鎖的產生。該類型的容錯路由算法主要有先西優先路由（Ｗｅｓｔ－ｆｉｒｓｔ Ｒｏｕｔｉｎｇ），北最后路由（Ｎｏｒｔｈ－ｌａｓｔ Ｒｏｕｔｉｎｇ），負優先路由（ｎｅｇａｔｉｖｅ－ｆｉｒｓｔ Ｒｏｕｔｉｎｇ）以及奇偶轉向路由（Ｏｄｄ－Ｅｖｅｎ Ｒｏｕｔｉｎｇ）[６]。

完全適應性容錯路由進一步提高了路由的適應性程度，因而獲得更好的網絡性能，但算法的實現比較復雜，研究的相對較少。以Ｄｙｘｙ路由算法[７]為例，主要思想是比較分組的當前節點和目的節點的各維坐標，當某維相同，則避開該維轉向其他維路由，否則，選擇向擁塞程度最小的相鄰節點路由，Ｄｙｘｙ是在維序路由的基礎上改進的一種路由算法，且充分考慮了網絡的擁塞情況。

２．２ 基于洪泛思想的容錯路由算法

基于此思想的容錯路由算法主要包括：直接洪泛（ｄｉｒｅｃｔ ｆｌｏｏｄｉｎｇ）、概率洪泛（ｐｒｏｂａｂｉｌｉｔｙ ｆｌｏｏｄｉｎｇ）、Ｎ－冗余隨機走動（Ｎ－ｒｏｄｏｍ ｗａｌｋ）路由容錯算法[３]。

概率洪泛路由算法是最簡單的隨機路由算法。

圖３是概率洪泛路由算法的實例，洪泛過程描述如下：Ｓ表示源節點，Ｄ表示目的節點。Ａ、Ｂ、Ｃ、Ｅ、Ｆ、Ｇ、Ｈ分別為中間節點。如果Ｓ要發送報文到Ｄ，需要查找由Ｓ到Ｄ的路徑。這時Ｓ需要將路由請求以概率ｐ發送給所有的鄰節點Ａ、Ｂ、Ｃ和Ｆ。當Ｃ和Ｆ收到路由請求后，同樣將報文轉發給所有的鄰節點。依此類推下去，Ｇ會收到分別來自于節點Ｃ和Ｆ發送過來的同一報文，在此過程中，Ｇ將轉發先到的報文給其所有的鄰節點，后到的報文內容如果相同，則將相同報文丟棄。

直接洪泛容錯路由算法將目的節點的位置考慮到擴散過程中，降低了概率擴散算法中盲目的擴散數據所引起的較大的功耗。在直接擴散算法中，源節點以不同概率向其鄰居節點發送數據包，離目的節點近的節點以較高的概率發送，離目的節點較遠的節點以較低的概率發送數據包副本，如此重復，直到數據包路由到目的節點。

文獻[３]還提出了一種新的考慮目的節點位置的容錯算法：Ｎ－冗余隨機走動算法。算法在由發送端開始的第一跳采用泛洪機制，但數據包的拷貝數量事先預訂好，即Ｎ。從第二跳開始，所有收到數據包的節點都在Ｎ／Ｓ／Ｗ／Ｅ四端口中選擇一個最優端口，將數據發送出去。這種算法中的一個關鍵點在于第一跳中數據包拷貝份數Ｎ的確定，文獻指出利用Ｍａｒｋｏｖ鏈與隨機走動理論推算[８]。

２．３ 混合類型容錯路由算法

混合類型的容錯路由算法可以分以下三種情況：一是可以分為無故障和有故障兩個階段，數據包在從源節點路由到目的節點的過程中，可以在這兩個階段多次轉換。二是確定性路由和自適應路由結合的容錯路由算法。三是洪泛路由和奇偶轉向相結合的容錯路由算法。

３ 評價和分析

本文是基于三種容錯思想進行容錯路由算法的分析。表１對以上三種思想的容錯路由算法的特點進行了總結。

延遲、吞吐量、功耗是片上網絡容錯路由算法的評價標準。時延由發送時延、傳輸時延和接收時延三部分組成。如公式（１）所示：

Ｌｉ＝Ｌｓｅｎｄｅｒ＋Ｌｔｒａｎｓｐｏｒｔ＋Ｌｒｅｃｅｉｖｅｒ （１）

而電路設計中主要用平均時延進行線路延遲分析。所謂平均時延，就是指在給定周期內發送數據包從源節點到目的節點所需時間的平均值。假設Ｎ為在給定周期內所接收到包的數目，Ｌｉ為第ｉ個包的時延，如公式（２）。

Ｌａｖｇ＝ （２）

片上網絡中，消息吞吐量是指接收到的數據包長度占整個發送數據包長度的比值，公式（３）為消息吞吐量Ｔ的具體形式。

Ｔ＝ （３）

對直接洪泛、概率洪泛、Ｎ－冗余容錯路由算法的在網絡中有一個錯誤的情況下的成功傳輸百分比如表２所示。由此

表中可以看出，概率洪泛和直接洪泛容錯路由算法有相近的成功傳輸百分比，而Ｎ－冗余隨機走動算法則有更高的可靠性和容錯能力。

４ 結束語

片上網絡（ＮｏＣ）是未來芯片技術的發展趨勢，解決片上網絡故障是影響片上網絡性能的關鍵因素。本文對片上網絡故障分為硬故障和軟故障，并總結了解決硬故障的容錯路由算法。基于自適應思想、洪泛思想、混合思想三個方面對容錯路由算法進行討論和分析。今后研究工作的重點是在現有的容錯路由算法的基礎上，設計、研究出在功耗、容錯能力、延遲等各個性能上達到平衡的容錯路由算法。

參考文獻：

[１] ＢＥＮＩＮＩ Ｌ，ＤＥ ＭＩＣＨＥＬＩ Ｇ．Ｎｅｔｗｏｒｋｓ ｏｎ ｃｈｉｐｓ：ａ ｎｅｗ ＳｏＣ Ｐａｒ－

ａｄｉｇｍ[Ｊ]．ＩＥＥＥ Ｃｏｍｐｕｔｅｒ，２００２：７０－７８．

[２] 高明倫，杜高明． ＮｏＣ：下一代集成電路主流設計技術[Ｊ]． 微電子

學，２００６，３６（４）．

[３] ＳＥＹＲＡＦＩ Ｍ，ＡＳＡＤ Ａ． Ａ ｎｅｗ ｌｏｗ ｃｏｓｔ ｆａｕｌｔ ｔｏｌｅｒａｎｔ ｓｄｏｌｕｔｉｏｎ

ｆｏｒ ｍｅｓｈ ｂａｓｅｄ ＮｏＣｓ[Ｊ]． Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｅｌｅｃｔｒｏｎｉ－

ｃｓ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ，２０１０，Ｖ２－２０７－Ｖ２－２１３．

[４] ＰＩＲＲＥＴＴＩ Ｍ，ＬＩＮＫ Ｇ Ｍ，ＢＲＯＯＫＳ Ｒ Ｒ，ｅｔ ａｌ． Ｆａｕｌｔ ｔｏｌｅｒａｎｔ

ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｎｅｔｗｏｒｋ－ｏｎ－ｃｈｉｐ ｉｎｔｅｒｃｏｎｎｅｃｔ[Ｃ]／／ Ｐｒｏｃ． Ｏｆ ＩＥＥ－

ＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ａｎｎｕａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ ＶＬＳＩ． Ｔａｍｐａ ＵＳＡ： Ｉ－

ＥＥＥ Ｐｒｅｓｓ ，２００４：４６－５１．

[５] ＮＩ Ｃ Ｇ． Ｔｈｅ ｔｕｒｎ ｍｏｄｅｌ ｆｏｒ ａｄａｐｔｉｖｅ ｒｏｕｔｉｎｇ[Ｊ]． ＡＣＭｖｏｌ５，１９９４，

５：８７４－９０２．

[６] ＣＨＩＵ Ｍ． Ｔｈｅ ｏｄｄ－ｅｖｅｎ ｔｕｒｎ ｍｏｄｅｌ ｆｏｒ ａｄａｐｔｉｖｅ ｒｏｕｔｉｎｇ[Ｊ]．ＩＥＥＥ

Ｔｒａｎｓ． Ｏｎ ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｓｙｓｔｅｍｓ，２０００：７２９－７３８．

[７] ＬＩ Ｍｉｎｇ， ＺＥＮＧ Ｑｉｎｇａｎ， ＪＯＮＥ Ｗｅｎｂｅｎ． ＤｙＸＹ－Ａ ｐｒｏｘｉｍｉｔｙ ｃ－

ｏｎｇｅｓｔｉｏｎ－ａｗａｒｅ ｄｅａｄｌｏｃｋ－ｒｒｅｅ ｄｙｎａｍｉｃ ｒｏｕｔｉｎｇ ｍｅｔｈｏｄ ｆｏｒ ｎｅｔ－

ｗｏｒｋ ｏｎ ｃｈｉｐ[Ｊ]． ＤＡＣ，２００６：８４９－８５２．

[８] ＳＴＥＷＡＲＴ Ｗ Ｊ． Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ ｔｈｅ ｎｕｍｅｒｉｃａｌ ｓｏｌｕｔｉｏｎｓ ｏｆ ｍ－

ａｒｋｏｖ ｃｈａｉｎｓ[Ｊ]． Ｅｌｉｚａｂｅｔｈ： Ｐｒｉｎｃｅｔｏｎ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ，１９９４：１０４

－１０５．