[發明專利]一種基于層次化Q-routing規劃的路由方法

有效

• 申請號: 202110389260.2
• 申請日: 2021-04-12
• 公開（公告）號: CN113079093B
• 公開（公告）日: 2022-03-15
• 發明（設計）人: 李楨旻;翁曉峰;王鏡涵;李天瑜;馬宇晴;杜高明;宋宇鯤
• 申請（專利權）人: 合肥工業大學
• 主分類號: H04L45/12
• 分類號: H04L45/12;H04L41/12;H04L45/00;H04L45/24
• 代理公司: 安徽省合肥新安專利代理有限責任公司 34101
• 代理人: 陸麗莉;何梅生

本發明公開了一種基于層次化Q?routing規劃的路由方法，是通過感知網路的擁塞情況和互聯鏈路使用情況，全局分層次并行規劃得到高效率的數據傳輸鏈路。本發明的算法是一種基于查找表的路由算法，路由算法將規劃后的方向存儲在各個路由器節點的學習模塊里的路由表中，數據包通過訪問所在路由器節點的學習模塊里的路由表得到路徑信息。本發明在拆分式Q?routing基礎上構造了層次化設計，利用多層擁塞感知器及多層并行學習大大降低了算法的收斂時間，從而提高了片上網絡數據傳輸效率，還壓縮了路由表，減少了硬件資源消耗。

技術領域

本發明屬于集成電路片上網絡的通信技術領域，特別涉及一種基于層次化Q-routing規劃的片上網絡路由方法。

背景技術

隨著摩爾定律逐漸失效，半導體工藝的發展逐漸放緩，單核處理器的工作頻率遇到瓶頸難以快速增長。傳統總線結構的片上系統(System on Chip，SoC)擴展性差、并行度低等缺點日趨明顯，要想提高整顆芯片的工作頻率，需要使用傳統總線以外的新方法，即片上網絡(Network on Chip,NoC)通信。NoC具有良好的擴展性，可以并行地處理芯片內部多個IP核的數據，有效解決了功耗、性能、面積等問題。

NoC包括拓撲結構、路由算法和交換技術等方面，本專利研究其中的路由算法。路由算法為在NoC中的數據包提供傳輸方向，是NoC中極為重要的一環。一種優良的路由算法將通過迅速、合理的路徑規劃，提高傳輸效率，增大吞吐量。

拆分式Q-routing是一種基于強化學習的片上網絡路由算法。用以在源路由器節點到目標路由器節點之間尋找到耗時最短的路由路徑。可以較好解決NoC在傳輸大量數據時帶來的數據延時、功耗增加、路由器溫度升高等問題。但隨著片上網絡的規模不斷增大，網絡擁塞將會越來越嚴重，拆分式Q-routing將出現路徑規劃時間太長，以至于失去時效性，難以滿足需求的問題。

發明內容

針對現有技術的不足，本發明提出了一種基于層次化Q-routing規劃的路由方法，以期彌補傳統Q-routing的不足，進一步提高NoC的傳輸性能、減低功耗、增大吞吐量；同時能通過壓縮路由表減少硬件電路面積。

本發明為達到上述發明目的，采用如下技術方案：

本發明一種基于層次化Q-routing規劃的路由方法，是應用于由w個路由器節點、w個資源節點和若干條互連通道所組成的片上網絡中，所述路由器節點包含輸入端口、輸出端口、擁塞感知器、多路選通器、訪問路由表；其特點是，在所述路由器節點中設置學習模塊；所述學習模塊包括：學習方式仲裁器、層次化控制模塊、路由表選擇模塊、3個子學習模塊、3個路由表；所述路由方法是按如下步驟進行：

步驟1：將所有路由器節點按照如下規則劃分三層網絡結構，從而形成金字塔結構；所述規則為：

在第1層網絡結構中將w個路由器節點以每x²個節點劃分為一組，從而構成由個虛擬路由器組所構成的第1層網絡結構；

在第2層網絡結構中將個虛擬路由器組以每y²個節點劃分為一組，從而構成由個虛擬路由器組所構成的第2層網絡結構；

在第3層網絡結構中將個虛擬路由器組以z²個節點劃分為一組，從而構成由1個虛擬路由器組所構成的第3層；

3個子學習模塊和3個路由表對應各個層的網絡結構；每個子學習模塊均包括：R矩陣、Q矩陣、Q值比較器；

令L₁^i,h表示第1層網絡結構中第i個路由器節點所對應的第h個子學習模塊，ix²，h＝1,2,3；

令L_jⁱ表示第j層網絡結構中第i個虛擬路由器組，j≠1；