[發明專利]一種針對片上網絡的低復雜度和可擴展的容錯路由算法

無效

• 申請號: 201010167572.0
• 申請日: 2010-05-06
• 公開（公告）號: CN101834797A
• 公開（公告）日: 2010-09-15
• 發明（設計）人: 石澤文;虞志益;曾曉洋;陳秀平;惠志達;楊金達
• 申請（專利權）人: 復旦大學
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04L1/00
• 代理公司: 上海正旦專利代理有限公司 31200
• 代理人: 陸飛;盛志范

技術領域

本發明屬于可靠性計算技術領域，具體涉及一種針對Mesh拓撲結構的片上網絡的低復雜度、可擴展的高性能容錯路由算法。

背景技術

隨著“功耗墻”(power?wall)限制單核處理器的性能提升，計算系統設計逐漸的過渡到多核(Multicore)、眾核(Many-core)乃至片上網絡的領域。盡管到目前為止，商用處理器的核數還比較少，但是在可以預見的未來核數將沿著“新摩爾定律”，每代在原有的基礎上加倍。一些有代表性的工作比如Tilera64(64核)，英特爾的Teraflop(80核)，加州大學戴維斯分校的167核計算平臺。

容錯性設計傳統上只用于對穩定性要求特別高的領域，比如宇航和軍用，但是在深亞微米乃至納米工藝下，越來越高的集成度以及越來越多的互聯器件使得我們很難在可以接受的良品率下保證芯片被正確地制造，而且在芯片的使用壽命過程中由于材料老化、電遷移(EM)和柵氧擊穿(OBD)等原因造成的永久性故障也越來越明顯。隨著“摩爾定律”的演進、集成度的增加和單芯片晶體管的數量不斷增加，永久性故障的出現將會更加頻繁。正如英特爾的研究人員在歐洲測試座談會的一篇邀請報告中指出的一樣，在下一個十年里，我們可以看到單芯片中集成有一千億只晶體管，這是好消息，因為我們可以集成進更多的功能，植入成百上千的IP核，但壞消息是：200億只晶體管會在制造中產生缺陷，更有100億只晶體管會在第一年使用過程中失效。

當芯片的一部分失效的時候，如何確保其他部位還可以正常工作，對于多核處理器來說，容錯性設計已經上升到和性能(能量效率)、易編程性同等重要的地位，而且對于多核處理器來說，內在的冗余性使其在容錯性方面具有天然的優勢。現有的容錯路由方案都不同程度的存在著這樣那樣的局限性，在這種背景下，本發明提出了一種超低復雜度、擴展性能優越和可重配置能力強的容錯路由算法。

發明內容

本發明的目的在于針對Mesh拓撲結構的片上網絡(Network-on-Chip)，提出一種超低復雜度、擴展性能優越和可重配置能力強的容錯路由算法，硬件開銷可以保持恒定而不隨系統規模的擴大而增加，當新的節點出錯的情況下，系統可以通過簡單的重新配置之后仍舊能夠正常工作，同時其硬件復雜度相對傳統容錯路由算法可以做到更小。

本發明方法采取一種“分而治之”的策略，將2維mesh分成若干個區域，包括4個角部區域，4個邊界區域和1個中心區域，每個區域采用各自的容錯路由策略(如圖2所示)，各個區域單獨可以容納位于該區域的各種出錯形式，同時它們又可以很好的協同工作以容納那些跨越若干區域的出錯情況，在沒有節點出錯的條件下，這三種路由策略又可以退化歸并為一種。還有這幾種方法硬件實現的開銷必須大致近似，以便較好的嵌進規則mesh的瓦片結構。同時幾個區域之間的接口設計也必須進行最大限度的簡化，最好是保證幾種方法的內在一致性，以便更好的整合。

鑒于路由表法不太適用于功耗受限的片上網絡系統，同時查表法訪問延時的不可擴展和開銷隨系統的規模指數級的增長，我們采取純邏輯電路實現的方式以克服這些問題。

本發明在路由器的東、南、西、北四個輸出端口都定義了若干個比特位，包括2個路由限制位和一個連接位，其中路由限制位表征從某個端口輸出時能否在下一跳進行某個方向的跳轉，比如Rns意味著從當前節點的北端口輸出后下一步能否向南部轉彎，其他限制位可以類似的解釋；連接位則表征從某一端口看出去跟周圍的節點是否連接(‘1’則連接，‘0’則斷開)，比如Cn為‘0’意味著跟北方的節點斷開了或者該節點已經是Mesh結構的邊緣。通過高度優化的路由運算邏輯，可以非常高效簡單的表達出路由算法。

容錯路由方案主要分為以下幾步：

1)根據當前節點位置和目標節點位置的相對信息，給出初步的的方位信息(N1，S1，E1，W1)；比如目標節點在當前節點的東北方位，則N1和E1均為‘1’；

2)根據路由限制位信息和第一步求解的大致方位信息，給出候選的路由輸出端口信息N2，S2，E2，W2，計算如公式(1)所示；同樣以目標位置在當前節點的東北方位為例，如果北邊輸出可以在下一跳轉向東的路由限制位Rne設為‘1’，那么根據公式(1)，N2為有效的輸出端口候選位，其中表征目標節點在當前節點的非東方，其他的符號如Rnw和可以類似的理解。