[發明專利]2D-Mesh拓補結構下的片上網絡偏轉容錯路由算法

在審

• 申請號: 201410384174.2
• 申請日: 2014-08-06
• 公開（公告）號: CN104202241A
• 公開（公告）日: 2014-12-10
• 發明（設計）人: 楊勇;才華;吳劍飛;陳玉群;谷欣超;韓太林;劉俊杰
• 申請（專利權）人: 長春理工大學
• 主分類號: H04L12/703
• 分類號: H04L12/703;H04L12/771;H04L12/757
• 代理公司: 長春市吉利專利事務所 22206
• 代理人: 李曉莉

技術領域

本發明屬于片上網絡容錯路由方法領域，具體涉及一種2D-Mesh拓補結構下的片上網絡偏轉容錯路由算法。

背景技術

片上網絡(network-on-chip，Noc)是在原有的片上系統(system-on-chip，Soc)通信方式上發展而來，是一種全新的片上通信機制。原有的片上系統是基于總線傳輸的方式，難以滿足現在的網絡傳輸需求，因此借鑒于計算機網絡，產生了片上網絡。基于片上網絡(NoC)的系統能更好地適應在未來復雜多核片上系統(SoC)設計中使用的全局異步局部同步的時鐘機制，在性能上顯著優于原總線方式的片上系統。2D-mesh拓撲片上網絡是由m行×n列的路由節點共同構成的二維路由矩陣，是具有普遍代表性的片上網絡基本形式之一。片上網絡中每一個節點包含一個交換機和IP核。在2D-Mesh網絡中，一個節點不僅能傳送和接收信息，還能充當路由器對其附近節點轉發信息，隨著更多節點的相互連接和可能的路徑數量的增加，片上網絡的總帶寬會大大增加。并且如果某個路由器發生故障，信息由其他路由器通過備用路徑傳送，所以這種mesh片上網絡結構穩定性強。

然而，一個路由器出現故障，失效的路由器是不能用的，因此這時候，片上網絡已經被修改并形成不規律的新拓撲結構。如果路由算法按原有公知的X-Y初始路由方式而僅向失效的路由器繼續發送數據包，片上網絡將被阻塞，數據無法繼續傳遞。因此，必須修改或重新配置路由算法以便適應新形成的片上網絡拓補結構。設計一種適用于2D-Mesh拓補結構下的片上網絡偏轉容錯路由算法成為亟待解決的研發課題。

目前，有人提出了使用虛擬信道來保證容錯路由的無死鎖特性，可以在一個有故障的路由或者有缺陷的區域之間使用虛擬信道按照某種路徑發送數據包。但是此方法必須保證片上網絡的硬件路由器成本非常低，需要額外的系統開銷，片上網絡日益增強的高復雜性和大面積的花費對于此方式效果不十分理想。

發明內容

為了解決現有使用虛擬信道來保證無死鎖特性的容錯路由算法成本高昂，無法滿足片上網絡日益增強的高復雜性和拓展需求，目前缺少適用于2D-Mesh拓補結構下的片上網絡偏轉容錯路由算法以避免路由節點繼續向已經擁塞或故障的鄰近節點繼續傳遞數據，進而造成片上網絡長期被阻塞的技術問題，本發明提供一種2D-Mesh拓補結構下的片上網絡偏轉容錯路由算法。

本發明解決技術問題所采取的技術方案如下：

2D-Mesh拓補結構下的片上網絡偏轉容錯路由算法，其特征在于：該方法包括如下步驟：

步驟一：給m×n的2D-mesh拓撲片上網絡定義變量、全局路由器、基礎的X-Y傳輸規則、邊緣路由表和容錯偏轉決策模型，其具體包括如下子步驟：

步驟1.1：分別定義變量，包括：內部路由節點、邊緣路由節點和ping命令的測試超時時間；

內部路由節點：在m×n的2D-mesh拓撲片上網絡上的一個當前路由節點，若與該當前路由節點直接相連的其它路由節點共有四個，則將這類有四個鄰近路由節點的當前路由節點稱為內部路由節點；

邊緣路由節點：在m×n的2D-mesh拓撲片上網絡上的一個當前路由節點，若與該當前路由節點直接相連的其它路由節點的總數不大于三個，則將這類至多有三個鄰近路由節點的當前路由節點稱為邊緣路由節點；

ping命令的測試超時時間：定義一個確定的時間常數T，當前路由節點對其它鄰近路由節點進行ping測試命令時，若被測試的路由節點在時長為T的時間段內一直沒有反饋，則將該被測試路由節點所在的路徑判定為非通路；

步驟1.2：定義基礎的X-Y傳輸規則為：

2Dmesh拓撲的片上網絡上，由m×n個路由節點組成的矩形陣列上的每一個路由節點都具有自己的唯一坐標，設任意一個路由節點A的坐標值(x,y)，另外一個任意路由節點B的坐標值(p,q)，則從路由節點A(x,y)始發并去往路由節點B(p,q)時，其遵循如下的基礎規則：

當路由節點A(x,y)與B(p,q)的橫坐標和縱坐標均不相同時，A(x,y)總是忽略縱坐標上的差值，并優先選擇能使橫坐標差值的絕對值縮小的那一個橫軸上的鄰近路由節點作為下一跳時的交付地址；

當路由節點A(x,y)與B(p,q)的橫坐標相同但縱坐標不相同時，A(x,y)總是優先選擇能使縱坐標差值的絕對值縮小的那一個縱軸上的鄰近路由節點作為下一跳時的交付地址；

從路由節點A(x,y)始發并去往路由節點B(p,q)時，按上述基礎X-Y傳輸規則所確定的總跳步數初始值T_初的表達式為：