[發明專利]一種基于片上網絡的無死鎖路由方法

有效

• 申請號: 201110321481.2
• 申請日: 2011-10-21
• 公開（公告）號: CN102333038A
• 公開（公告）日: 2012-01-25
• 發明（設計）人: 武鵬;付宇卓;蔣江;劉婷
• 申請（專利權）人: 上海交通大學
• 主分類號: H04L12/56
• 分類號: H04L12/56
• 代理公司: 上海思微知識產權代理事務所(普通合伙) 31237
• 代理人: 鄭瑋

技術領域

本發明屬于片上網絡技術領域，涉及一種路由方法，尤其涉及一種基于片上網絡的無死鎖路由方法。

背景技術

隨著半導體工藝技術步入納米階段，在單一芯片中集成上億晶體管已經成為現實，如何解決傳統共享總線通信結構中存在的延遲、通信性能瓶頸等問題就成為了重要的研究方向。片上網絡NoC(Network?on?Chip)作為一種新的片上通信系統結構在性能上相比于傳統總線結構有了極大的提升。而在現有的片上網絡中，最主要采用的是2D網格的拓撲結構，這種拓撲結構工藝上較容易實現，對絕大多數應用也具備較好的性能。本發明就是基于片上網絡的通信結構和傳統2D網格的拓撲結構來設計實現的。

同時，隨著工藝尺寸的不斷縮小，芯片越來越容易受到外界的干擾。串擾、耦合噪聲以及宇宙射線照射帶來的軟錯誤逐漸成為制約系統可靠性的關鍵因素。另一方面，空天、金融等行業領域又需要很高的可靠性要求，面對這種有高可靠性要求的應用，就需要設計具有容錯能力的系統來滿足這些需求。通常的具有容錯能力的系統會利用時間冗余、空間冗余、信息冗余等方法來提高系統的可靠性。

發明內容

本發明所要解決的技術問題是：提供一種基于片上網絡的無死鎖路由方法，可實現空間上的三模冗余，提高系統的可靠性。

為解決上述技術問題，本發明采用如下技術方案：

一種基于片上網絡的無死鎖路由方法，所述方法包括如下步驟：在源節點將數據包復制n份，其中，n≥3；在片上網絡中設定n條自源節點至目的節點的不交叉的通道，n份數據包分別在n條通道上傳輸；n份數據包到達目的節點后再通過表決器得到正確結果，實現了空間上的冗余。

作為本發明的一種優選方案，在源節點將數據包復制三份；在片上網絡中設定三條自源節點至目的節點的不交叉的通道，三份數據包分別在三條通道上傳輸；三份數據包到達目的節點后再通過表決器得到正確結果，實現了空間上的三模冗余。

作為本發明的一種優選方案，在片上網絡中開設四條虛通道，其中兩條分別為XY通道和YX通道，另外兩條是紅通道和黑通道；具有高可靠性要求的數據包在源節點首先拷貝成三份，其中的兩份分別通過XY通道和YX通道向目的節點發包；第三份數據包首先通過源節點的紅通道/黑通道發送到與前兩條通道不同的相鄰節點，再通過XY通道/YX通道發送到距離目的節點為一的節點，必須在源節點與目的節點組成的矩形區域以外，保證與另外兩份數據包無交叉路徑；再通過黑通道/紅通道發送到目的節點。

進一步地，如果源節點是偶節點則通過黑通道發送到與前兩條通道不同的相鄰節點，再通過YX通道發送到距離目的節點為一的節點，必須在源節點與目的節點組成的矩形區域以外，保證與另外兩份數據包無交叉路徑；再通過紅通道發送到目的節點；如果源節點是奇節點則通過紅通道發送到與前兩條通道不同的相鄰節點，再通過XY通道發送到距離目的節點為一的節點，必須在源節點與目的節點組成的矩形區域以外，保證與另外兩份數據包無交叉路徑；再通過黑通道發送到目的節點。

進一步地，所有紅通道都是從奇節點為源節點，發送到偶節點；紅通道對所有偶節點來說都是接收通道，對所有奇節點都是發出通道；黑通道與之相反。

進一步地，所述奇節點、偶節點的定義為：將片上網絡的左下角router節點的坐標定位為(1，1)，向右為X正向，向上為Y正向，將任一router節點的XY坐標相加，如果為奇數該節點就是奇節點，如果該節點XY坐標相加為偶數就是偶節點。

本發明的有益效果在于：本發明提出的基于片上網絡的無死鎖路由方法，第一次在2D網格的片上網絡中提出了一種三條非交叉路徑的路由算法，并且嚴格證明了不會帶來死鎖問題。可以利用本發明的路由算法來實現空間上的三模冗余，提高系統的可靠性。

附圖說明

圖1為一個經典的2D網格片上網絡結構圖。

圖2為一個紅黑通道示意圖。

圖3為一個本發明無死鎖路由方法的實際示例圖。

具體實施方式

下面結合附圖詳細說明本發明的優選實施例。

實施例一

本發明揭示了一種非交叉無死鎖的三路徑路由算法，可以將具有高可靠性要求的數據包復制三份在片上網絡中進行傳輸，到目的節點后再通過表決器得到正確結果，實現了空間上的三模冗余。由于宇宙射線等造成的軟錯誤在時間和空間上都具有隨機性，因此本發明設計的無交叉路由可以保證同一個軟錯誤最多只會影響一份數據包，從而在目的節點完全可以通過表決器得到正確結果。同時本發明可以嚴格證明的無死鎖路由，可保證不會引起系統的崩潰。