基于維序路由算法的自適應算法

談俊燕 華迪

（1.常州市工學院電氣信息工程學院 江蘇省常州市 213032 2.常州市信息技術學院電子工程學院 江蘇省常州市 213000）

科技的發展使得單個芯片能夠集成更多的IP 核，但是IP 核數量的逐漸增加使得片上系統（System On Chip, SoC）難以滿足設計需求。而片上網絡（Network On Chip, NoC）能使系統更好地適應復雜多核SoC 設計中使用的全局異步局部同步的時鐘機制，優化網絡的性能。因此NoC 憑借其可升級性和易擴展性，逐漸成為了一種熱門的新興通訊結構。

維序算法是一種經典的3D 片上網絡的確定性路由算法，它的路由路徑僅由源節點和目的節點的地址決定，該算法根據偏移量來決定在哪個維度上進行數據傳送，當數據包在一個維度內傳送完成后不會再次在該維度內傳送，因此維序路由可以有效的防止死鎖的產生。但是由于其算法的路由路徑是固定的，不能根據路徑中各節點情況進行路徑調整和自適應，容易產生節點阻塞而降低效率。因此本研究提出了一種改進的自適應算法，當數據在傳送過程中遇到阻塞時，算法會判斷當前情況，并且改變數據的傳送路徑，從而避開阻塞的數據傳送通道，而在其他空閑通道完成數據傳送，由此顯著降低等待通信通道恢復通暢狀態所額外增加的延遲和時間，極大地提高運行的效率。

1 數據傳輸狀態對比

數據的傳輸通道可分為阻塞狀態和正常狀態。為了得到兩種狀態下數據傳輸通道的特點，可將分別處于阻塞狀態和正常狀態的數據傳輸通道節點100 和節點000 的SwitchContorl 模塊中的所有變量進行仿真對比，得到圖1 所示的仿真波形圖。可以看出當數據傳輸通道正常時，節點100 的SwitchContorl 模塊中auxfree 變量的0端口在數據傳送時變為低電平，而在27 個時鐘周期后又恢復到高電平；當數據傳送通道阻塞時，節點 100 的 SwitchContorl 模塊中auxfree 變量的 0 端口在數據傳送時變為低電平，之后始終保持該狀態不變。

分析數據傳輸過程中通道節點的活動后可以發現，在數據傳送時，節點100 由于阻塞而無法接收到來自節點 200 的發送請求信號的應答信號，因此其一直處于請求狀態，即auxfree 的0 端口長期處于低電平狀態而無法恢復。

2 自適應算法原理

由數據傳輸通道阻塞時的特點可得知，阻塞節點SwitchContorl模塊中的auxfree 變量的0 端口低電平持續脈沖數大于27 個周期。因此本算法通過統計當前節點SwitchContorl 模塊中auxfree 變量的0 端口低電平持續的脈沖數以判定該節點是否出現阻塞情況。

2.1 算法步驟

算法的流程如圖2 所示，具體分為以下四個步驟：

（1）設定閾值為 30 個時鐘周期脈沖，以此作為目標節點auxfree 變量0 端口低電平脈沖數的比較標準值。

圖1：兩種節點SwitchContorl 模塊中auxfree 變量的0 端口信號量仿真波形圖

圖2：算法工作流程圖

圖3：維序路由算法的路由路徑

圖4：自適應算法的路由路徑

（2）統計數據傳送時auxfree 變量0 端口低電平持續的脈沖數。

（3）當0 端口低電平持續時鐘周期脈沖數小于閾值時，繼續該數據傳輸x 方向的維序路由算法；當脈沖數達到設定閾值時，即當前x 方向中存在阻塞，算法就將數據傳送方向轉換為 y 方向并且繼續對auxfree 變量進行判斷。

圖5：總延遲曲線

圖6：總時間曲線

（4）若y 方向的0 端口低電平持續時間小于設定的閾值，則將數據轉發到 y 方向的節點并繼續維序路由算法，若低電平持續時間達到 30 個時鐘周期，則繼續將數據傳送方向轉換為z 方向。

2.2 自適應算法與維序路由算法路由路徑的比較

實驗將數據從源節點000 傳送到節點222，并且把節點100 與節點200 之間的數據傳輸通道手動阻塞，對維序路由算法和基于維序路由的自適應算法進行路由路徑的比較，如圖3 和圖4 所示。

3 實驗結果分析

在實驗測試中選擇節點 222 為源節點，節點 001 和000 分別為目的節點，并且阻塞了節點022 和112。要傳輸的數據包采取單一注入速率的方式，且每次進行測試時使用不同種的注入速率。為了與維序路由算法對比，實驗增加了一組維序路由算法的測試作為對照，選擇節點 000 為源節點，節點 221 和222 分別為目的節點，并且將節點 000 和節點 100 之間的數據傳送通道阻塞 450 個時鐘周期。最后將測試結果制成折線圖，分析自適應算法的性能，如圖5、圖6 所示。

對圖5 總延遲曲線進行分析，發現注入速率小于40%時，維序路由算法在阻塞狀態下的總延遲明顯大于本設計實現的自適應路由算法；而注入速率超過 40%后自適應路由算法圖線消失，表示數據傳送錯誤，經分析后發現是由于自適應算法在數據傳輸時需要對傳輸通道狀態進行一次或者兩次算法判斷，此時數據應處于等待狀態。隨著傳送速度的不斷加快但是判斷速度始終不變，當注入速率超過某一速度時就導致了數據的錯誤傳送，因此本設計中所實現的自適應算法僅適用于注入速率不高于 40%的情況。

對圖6 總時間曲線進行分析，發現注入速率小于40%時，數據傳送完成所需時間隨注入速率的增大而減少，當注入速率為 30%時，數據傳輸所需總時間趨近于飽和。當注入速率為小于10%時，自適應算法完成一次數據傳送所需時間大于維序路由算法中存在阻塞時完成一次數據傳送所需時間。因此，本設計中所實現的自適應算法在注入速率高于10%時才能具有優于維序算法的性能。

4 總結

綜合上面的測試結果和分析，可以看出本設計所提出并實現的基于維序路由算法的自適應算法在數據包注入速率不小于10%且不大于40%的情況下，能夠解決維序路由算法在片上數據傳輸通道阻塞的問題，證明了本設計路由算法的優越性和有效性。