[發(fā)明專利]針對超大規(guī)模片上網(wǎng)絡容忍眾故障的確定性路徑路由方法

有效

• 申請?zhí)枺?/td>: 201910222208.0
• 申請日: 2019-03-22
• 公開（公告）號: CN110086709B
• 公開（公告）日: 2021-09-03
• 發(fā)明（設計）人: 張穎;陳中勝;季鵬飛;江建慧
• 申請（專利權）人: 同濟大學
• 主分類號: H04L12/703
• 分類號: H04L12/703;H04L12/741;H04L12/751;H04L12/24
• 代理公司: 上海科盛知識產(chǎn)權代理有限公司 31225
• 代理人: 翁惠瑜

本發(fā)明涉及一種針對超大規(guī)模片上網(wǎng)絡容忍眾故障的確定性路徑路由方法，該方法在片上網(wǎng)絡的每個交換機上維護一路由表，各交換機基于該路由表進行在線路由，所述路由表離線生成，生成過程包括：基于Tarjan算法計算片上網(wǎng)絡的最大強連通分量，刪除故障節(jié)點及故障鏈路，利用廣度優(yōu)先遍歷策略遍歷片上網(wǎng)絡剩余節(jié)點及鏈路，生成路由表。與現(xiàn)有技術相比，本發(fā)明不僅能夠容忍多種故障的影響，而且能夠最大化重構NoC中的可用節(jié)點，在平均延遲，吞吐量和能量消耗方面的性能也優(yōu)于現(xiàn)有解決方案。

技術領域

本發(fā)明屬于片上網(wǎng)絡的架構設計和路由技術領域，涉及一種超大規(guī)模片上網(wǎng)絡的路由方法，尤其是涉及一種針對超大規(guī)模片上網(wǎng)絡容忍眾故障的確定性路徑路由方法。

背景技術

憑借強大的并行通信能力，大規(guī)模片上網(wǎng)絡已經(jīng)成為超級計算機中最有前途的結構。而晶圓級NoC(Network On Chip，片上網(wǎng)絡)可以將芯片之間的大量并行通信移動到芯片內(nèi)部，這減少了傳輸延遲，從而顯著提高了計算性能。同時，由于將單個芯片作為小型超級計算機，這種結構可以讓超級計算機更加節(jié)省能量。因此，開發(fā)晶圓級NoC成為進一步提高超級計算機性能的有效措施。

確保高產(chǎn)量是開發(fā)晶圓級NoC的關鍵問題。大規(guī)模晶圓級NoC將遇到許多故障問題，因為芯片上的故障概率與芯片的尺寸成比例。如果在NoC中的任何地方出現(xiàn)故障時直接丟棄每個故障的晶片級NoC，則產(chǎn)量將非常低，并且生產(chǎn)成本不切實際地高。保持晶圓級NoC的高產(chǎn)量的可行解決方案是在晶圓上實現(xiàn)更多的處理路由器(即節(jié)點)，只要芯片上可用節(jié)點的數(shù)量超過設計要求，就將故障芯片視為良好的芯片。幸運的是，NoC通信結構支持此解決方案，因為它為節(jié)點間通信提供了自然的許多備用路徑。我們需要的是一種路由算法，以容忍在晶圓級NoC的制造和操作階段可能發(fā)生的潛在的許多故障。

片上網(wǎng)絡系統(tǒng)主要由以下部分組成：網(wǎng)絡接口、處理單元、路由器和互連網(wǎng)絡，由于其自身元器件的電氣特性而極大地增加了產(chǎn)生故障的可能性。因此，片上網(wǎng)絡需要具備有強大的容錯能力，容錯相關技術是片上網(wǎng)絡的重要支撐技術之一。

由于在NoC中，路由可能會產(chǎn)生循環(huán)依賴以致導致發(fā)生路由死鎖，使路由的數(shù)據(jù)包處在無限等待下一跳緩存區(qū)處于空閑狀態(tài)，這會導致路由的數(shù)據(jù)包無法到達目的地，因此，如何避免死鎖也是容錯路由算法一個很重要的研究內(nèi)容。由于可以使用無故障的鏈路來替換故障連鏈路或者是繞過故障節(jié)點，因此，容錯路由算法可以為NoC提供一定的容錯能力。

其次，在NoC中，如果某一個節(jié)點同一時刻接收或者傳遞過多的數(shù)據(jù)包，就會導致緩存區(qū)一直處于忙碌狀態(tài)，沒有空閑的緩存區(qū)，這會導致需要路由到這一節(jié)點的數(shù)據(jù)包處于等待狀態(tài)，會導致局部的路由擁塞，增加了路由的延遲從而使NoC的性能降低。因此容錯路由算法也需要很好地解決路由擁塞，才能使算法在容錯的同時具備較高的性能。

在NoC的容錯路由算法領域，已經(jīng)有很多的研究成果，但是大部分都沒有考慮NoC中可能存在的眾多故障。

基于Turn model理論提出了幾種容錯路由算法，這些路由算法不依賴于虛擬通道，并且可以又很有的避免死鎖的效果，但是這些路由算法由于嚴格遵守了禁止轉向的規(guī)則，從而導致嚴格禁用了指定的路由轉向，這會導致有一些路由因為這些規(guī)則不能發(fā)生，會造成一定程度的丟包現(xiàn)象。

HamFA算法是一種簡單可行的路由算法，它可以容忍鏈路故障。該算法為NoC的每個節(jié)點分配HamFA ID。然后，它根據(jù)這些HamFA ID將網(wǎng)絡劃分為兩個子通道：升序通道和降序通道。該算法還設置從當前節(jié)點到北鄰居(或南鄰居)節(jié)點的鏈路作為快速鏈路。路由器更傾向于通過快速鏈路發(fā)送數(shù)據(jù)包。當故障出現(xiàn)在快速鏈路上時，路由器使用上行路徑(或下行路徑)。因此，該算法通常容忍單個故障的影響。但是，當快速路徑與下行(或上升)路徑重合，并且故障剛好出現(xiàn)在相應的鏈路上時，該算法將無法容忍這樣的故障。