[發(fā)明專利]一種基于線性規(guī)劃的片上網(wǎng)絡路由方法

在審

• 申請?zhí)枺?/td>: 201710743418.5
• 申請日: 2017-08-25
• 公開（公告）號: CN107395503A
• 公開（公告）日: 2017-11-24
• 發(fā)明（設計）人: 王學香;蔡鵬翔;吳建輝
• 申請（專利權(quán)）人: 東南大學
• 主分類號: H04L12/721
• 分類號: H04L12/721;H04L12/813;H04L12/24
• 代理公司: 蘇州創(chuàng)元專利商標事務所有限公司32103
• 代理人: 范晴

技術領域

本發(fā)明屬于片上系統(tǒng)中的片上網(wǎng)絡領域，特別涉及一種基于線性規(guī)劃的片上網(wǎng)絡路由方法，用于NoC中減少網(wǎng)絡節(jié)點間的通信擁塞狀況的發(fā)生，降低通信延遲以及提高吞吐率。

背景技術

路由算法是影響片上網(wǎng)絡(NoC)性能的主要因素之一。隨著NoC路由算法研究的不斷的深入，現(xiàn)有的通用NoC路由算法在小規(guī)模網(wǎng)絡上能獲得不錯的性能，但是研究人員對于更高性能的追求卻從來沒有停止過，尤其是網(wǎng)絡規(guī)模以及網(wǎng)絡負載越來越大，網(wǎng)絡的擁塞問題也會越來越突出。路由算法幾乎影響了NoC的所有性能指標，即延時(因為消息從源節(jié)點到目的節(jié)點經(jīng)過的跳數(shù)直接由經(jīng)過的實際路徑?jīng)Q定)、吞吐量(因為網(wǎng)絡擁塞的控制是依靠路由算法均衡負載的能力)、功耗(因為每一跳會產(chǎn)生路由器的能量開銷)、服務質(zhì)量(因為路由算法可以在不同的路徑上分配不同的信息流來防止它們之間的相互干擾)和可靠性(因為路由算法可以選擇能夠避免錯誤的路徑)。

發(fā)明內(nèi)容

本發(fā)明目的是：提供一種基于線性規(guī)劃的片上網(wǎng)絡路由方法，解決NoC中路由節(jié)點間的通信擁塞問題，針對目前NoC路由算法在解決此類問題上存在的不足，即在低網(wǎng)絡負載情況下網(wǎng)絡不會發(fā)生擁塞，但是會產(chǎn)生熱點，而在高負載時網(wǎng)絡很容易發(fā)生擁塞，并擁塞狀況會持續(xù)傳播，導致網(wǎng)絡發(fā)生大規(guī)模擁塞。

本發(fā)明的技術方案是：

一種基于線性規(guī)劃的片上網(wǎng)絡路由方法，包括：

S1)在片上網(wǎng)絡中增加一個額外的控制節(jié)點，所述控制節(jié)點和片上網(wǎng)絡中的所有路由節(jié)點相連，彼此之間傳輸狀態(tài)信息與路由信息，不進行數(shù)據(jù)包的傳輸；

S2)在網(wǎng)絡低負載低擁塞情況下，路由節(jié)點選擇擁塞較小的鏈路進行路由，其中：

S2-1)當前節(jié)點與目的節(jié)點的X、Y坐標值都不相同時，獲取當前節(jié)點朝目的節(jié)點X方向的相鄰節(jié)點的擁塞值，再獲取當前節(jié)點朝目的節(jié)點Y方向的相鄰節(jié)點的擁塞值，然后選擇擁塞值較小的相鄰節(jié)點進行路由；

S2-2)當前節(jié)點與目的節(jié)點的X坐標值相同，而Y坐標值不同時，選擇Y向相鄰節(jié)點進行路由；

S2-3)當前節(jié)點與目的節(jié)點的Y坐標值相同，而X坐標值不同時，選擇X向相鄰節(jié)點進行路由；

S3)在網(wǎng)絡擁塞到達設定的閾值后，通過網(wǎng)絡中的主控制節(jié)點收集網(wǎng)絡信息，然后根據(jù)收集的網(wǎng)絡信息采用線性規(guī)劃模型計算路由。

優(yōu)選的，步驟S1中，所述控制節(jié)點在收集網(wǎng)絡信息后，如果有路由節(jié)點需要進行數(shù)據(jù)發(fā)送，先發(fā)送路由請求給控制節(jié)點，由控制節(jié)點計算路由路徑，并將路由路徑信息保存到路徑上的所有路由器上。

優(yōu)選的，步驟S2和S3中，所述片上網(wǎng)絡中的路由節(jié)點之間的物理通道中設置多個虛擬通道，每個虛擬通道的緩存深度一致，當一條物理通道的所有虛擬通道都被占用了時，表示該條鏈路已經(jīng)不允許其他無關數(shù)據(jù)包使用了。

進一步優(yōu)選的，當一條物理通道的虛擬通道的被占用的緩存數(shù)量超過設定閾值T時，表明該網(wǎng)絡路由節(jié)點處于高流量負載情況，否則為低流量負載。

進一步優(yōu)選的，步驟S3中，在通過線性規(guī)劃計算出路由信息后，將該路由信息保存到路由路徑中的所有路由節(jié)點中，更新路由表；在沒有產(chǎn)生路由信息時則不進行任何操作。

進一步優(yōu)選的，步驟S3中，在片上網(wǎng)絡的數(shù)據(jù)包傳輸完成后，跟一個尾flit，在路由節(jié)點收到該flit時，就將與該flit對應的數(shù)據(jù)包路由信息刪除掉，從而更新路由表。

本發(fā)明的優(yōu)點是：

本發(fā)明提出的基于線性規(guī)劃的片上網(wǎng)絡路由方法，通過在網(wǎng)絡中增加主控節(jié)點來收集網(wǎng)絡信息，然后根據(jù)這些信息利用線性規(guī)劃計算出最短路徑，本發(fā)明在網(wǎng)絡擁塞狀況不嚴重時選擇相鄰擁塞狀況最小的鏈路，從而不需進行復雜的計算就能選擇一條合適的路徑。在網(wǎng)絡擁塞到達一定程度后，通過主控制節(jié)點收集網(wǎng)絡信息，然后根據(jù)這些信息采用線性規(guī)劃模型計算路由，以避免擁塞狀況的增加，實現(xiàn)全局流量的整體優(yōu)化與調(diào)整，網(wǎng)絡流量得到靈活控制。

附圖說明

下面結(jié)合附圖及實施例對本發(fā)明作進一步描述：

圖1為本發(fā)明實施例的NoC互聯(lián)架構(gòu)全局視圖；

圖2為本發(fā)明實施例的NoC互聯(lián)架構(gòu)局部視圖；

圖3為本發(fā)明基于線性規(guī)劃的NoC路由方法的路由器結(jié)構(gòu)。

具體實施方式