胡 明，季雙雙

(蕪湖職業(yè)技術學院 網絡工程學院，安徽 蕪湖 241003)

隨著半導體技術的進步，片上系統(SoC)技術被廣泛地應用到各種領域。片上系統包含的一系列核心工作都需要靠一定的拓撲結構和互聯方式實現。在規(guī)模較小的系統中，往往采用總線互聯的方式，但連接結點增加時容易產生對總線的爭奪，每次只能進行兩個結點之間的通信，導致系統通信的帶寬太小。交叉開關矩陣也是一種常用的互聯機制，其實現了片上網絡每兩個結點的直接互聯，實現了低延時和高吞吐率，但是容易產生通信通道的浪費[1]。

片上網絡系統(下文簡稱NoC)平衡了通信延時和通信成本的關系，它將片上系統的結點以網絡的形式連接，在大規(guī)模結點的片上系統中得到廣泛運用。目前，應用最廣泛的片上網絡系統的拓撲結構是網格結構，它將每個核心結點通過網格的結構連接起來，既具有較低的成本，又可以達到較低的通信延時。網格結構也易于半導體工藝的實現，可以對其中任意兩個核心結點提供多條通信路徑，具有較高的容錯能力。

1 路由算法分類

NoC路由算法根據路徑決策來分可分為無關路由、自適應路由及部分自適應路由。無關路由是指對于指定的發(fā)送結點和目標結點，在不同的時間下都采用相同的路由策略而不考慮當前網絡的狀態(tài)。而自適應路由針對的是指定的發(fā)送結點和目標結點，每次的路由決策會根據網絡故障、擁塞及硬件溫度等情況發(fā)生變化，實現整體的最優(yōu)決策。部分自適應路由則綜合了無關路由和自適應路由，針對不同的情況采取不同的路由方式[2]。

1.1 NoC無關路由算法

NoC無關路由所做的決策與片上網絡的擁塞程度、故障結點無關，它可以按固定方法發(fā)送數據包，也可以沿隨機路徑發(fā)送數據包。雖然無關路由算法簡單，但是一般按照固定策略發(fā)送數據包的路由策略沒有容錯能力，在片上結點出現故障時將失效。NoC無關路由算法包括：維序路由算法、禁止轉向算法及泛洪算法[3]。

1.2 NoC自適應路由算法

自適應路由主要是指對網絡中擁塞的自適應。當網絡中的某些結點負載過重時，自適應路由算法可以自動檢測并繞過這些結點，選擇另一條空閑的路徑。

自適應路由的策略一般是建立在對擁塞考察的基礎上，按其對擁塞的感知程度可分為本地擁塞感知和區(qū)域擁塞感知。本地擁塞感知往往考察本路由單元的相鄰路由單元的擁塞情況，其實現較為簡單，僅需在路由單元加入擁塞決策函數即可實現擁塞的自適應。區(qū)域擁塞感知需綜合考察全局結點的狀態(tài)，其路由策略往往優(yōu)于僅考察鄰居結點的路由策略，但其硬件和算法實現較復雜。

自適應路由根據適應程度分為完全自適應路由和部分自適應路由。完全自適應路由在綜合考慮各方向的擁塞程度的基礎上，選擇最優(yōu)的方向發(fā)送數據包；而部分自適應路由在路由策略上有所限制，在綜合考慮擁塞程度和路由方向限制的因素后選擇路由策略。

1.3 NoC容錯路由算法

容錯路由算法是在存在故障的片上網絡實現正常通信的路由算法。對于可能出現故障的片上網絡，可以通過沿不同路徑重復發(fā)送相同的數據包來解決，也可以在故障結點處通過繞路發(fā)送數據包來解決[4]。對于發(fā)送單一數據包的路由，又可以跟據對待故障的粒度分成故障塊路由、單故障路由及細粒度故障路由[5]。

1.4 源路由算法

源路由算法是指路由決策全部完成于發(fā)送數據包的源結點。源結點將路由路徑加入數據包的頭部，網絡結點根據頭部的路由信息對數據包進行轉發(fā)，不再參與路由決策。源路由算法中應用較多的是NoC-LS(LinkState，鏈路狀態(tài))算法。該算法也被應用于宏觀計算機網絡的路由算法中。其思想是每個片上網絡的結點都存儲一份整個網絡上的狀態(tài)信息(鏈路延時、故障等)[6]。當網絡發(fā)生變化時，每個片上網絡結點都向鄰居結點發(fā)送TEST數據包，當鄰居結點接收到TEST數據包后，將回復ECHO數據包。結點根據是否收到回復的ECHO數據包判斷鏈路是否出現了故障。當某條鏈路出現故障時，該結點將故障鏈路的位置作為數據包廣播給片上網絡的所有的結點，結點收到故障信息后更新當前的片上網絡信息表。當需要進行路由決策時，在源結點處根據存儲的整個網絡結點的延時和故障信息使用路由算法找出最佳路徑。

2 源路由算法分析

源路由算法的優(yōu)點是在尋找路由決策的時候具有全局的鏈路信息，因此路由策略可以綜合各種信息找出最佳路徑。但該算法的實現和網絡信息的存儲較復雜，不適用于結點結構簡單的片上網絡中。

2.1 迷宮BFS尋路算法

圖1 BFS 尋路算法示意圖

BFS算法通過兩個線性表實現，open表用來存放源結點，從open表中取出結點向4個方向擴展結點；close表用來存放已擴展結點。過程是從open表中取出所有結點，如果close表中無擴展結點，就放入open表尾，直至結束。

為了最后得出路由的策略，每個片上網絡的結點需實時監(jiān)測其相鄰結點的故障情況，當鄰居結點出現故障時，需要廣播故障信息給片上網絡的所有結點。片上網絡每個結點需存儲并更新片上網絡結點的狀態(tài)，記錄故障結點的位置。

迷宮BFS尋路算法優(yōu)、缺點明顯，源結點和目標結點之間必有一條最短路徑，但需要擴展更多的結點路徑，效率比較低。

圖1是迷宮BFS尋路算法示意圖。黑色的結點是出現故障或通信出現擁塞的結點，也可以是在電路交換中被獨占通信的結點；淺灰色結點是在算法過程中擴展出的結點；深灰色結點是最終找出的路由路徑。從擴展的結點可以看到，迷宮BFS尋路算法具有一定的盲目性，即使目的結點在源結點的西北方，原結點仍然會忽視目的結點的方向而向周圍4個方向都擴展結點，這樣做雖然總能找到最短路徑，但其效率低下。

2.2 迷宮 A*尋路算法

圖2 A*尋路算法示意圖

為了解決BFS尋路算法的盲目性，往往會在搜索過程中加入啟發(fā)式函數加快尋路速度。對目前所有的啟發(fā)式尋路算法來說，使用最多的是A*尋路算法，它是目前在游戲領域中應用最廣泛的尋路算法。其主要優(yōu)點是通過啟發(fā)式函數來預測當前結點到目標結點的距離，選擇性的擴展與目標結點距離較近的結點，從而加速找到通向目的結點的路徑。可以證明當當前結點到目的結點的估計距離不大于當前結點到目的結點的實際距離時，A*算法總能找到最短路徑。

A*算法最重要的內容就是啟發(fā)式函數。令f(x)=g(x)+h(x)，x表示某一結點，g(x)表示已知源結點到x結點實際路由距離，h(x)表示x結點到目標結點的預測距離，f(x)則表示整個預測距離。A*算法同樣設置兩個線性表(open 表和 close 表)，其中open 表用來維護待擴展的結點，close 表放置擴展結束的結點。當h(x)=0 時，A*算法就是 BFS 算法。A*尋路算法示意圖如圖2所示。

3 路由算法測試分析

采用黑盒測試法，分別對BFS尋路算法和A*算法進行測試。測試數據為隨機數據，測試模擬在真實的片上網絡上，所有的IP核處于對等的位置，源發(fā)送結點與接收目的結點隨機生成，故障結點率分為0/10%/30%3檔，隨機生成5000組數據，在擴展出合法路徑的測試數據中取擴展結點和路徑長度的平均值。測試結果見表1-表6。

表1 故障結點率0擴展結點數測試

表2 故障結點率 10%擴展結點數測試

表3 故障結點率 30%擴展結點數測試

從表1-表3可以看出，采用 A*算法尋路與 BFS 算法相比，由于加入了啟發(fā)式函數，其擴展的結點數大大減少，降低了路由算法的時間復雜度和空間復雜度，即使是A*算法增加了open 表的維護，在網絡規(guī)模增大時，其效率提升仍明顯。

表4 故障結點率0 時間空間占用測試

表5 故障結點率10% 時間空間占用測試

表6 故障結點率30% 時間空間占用測試

從表4-表6可以看出，A*算法對于大規(guī)模片上網絡來說優(yōu)勢明顯，當網絡規(guī)模增大，A*算法不會盲目擴展目標結點。而對于小規(guī)模片上網絡，BFS算法和A*算法效率差不多，甚至BFS算法更優(yōu)于A*算法。

4 迷宮尋路算法的擴展

迷宮A*路由算法加入結點擁塞權值，實現擁塞自適應路由。此外，可通過提高容錯粒度，提高A*算法效率。

4.1 擁塞自適應路由

將網絡中的每個結點附上相應的權值作為通過該結點的代價，即可將 A*算法用于實現擁塞自適應的路由，具體方法如下：

每個片上網絡結點檢測其自身結點的擁塞情況，例如數據包進入該結點到離開該結點的等待時間，將該時間以正相關的方式映射為 1～N的某一整數值。1 表示結點最為空閑，N 表示結點最為繁忙。此時每隔一段固定時間將該整數值及對應結點的編號廣播給片上網絡的所有結點。這樣每個結點都能獲得整個網絡結點的擁塞情況。

此時代價函數g(x)修改為從源結點到當前結點 x 已經走過的權值和，啟發(fā)式函數為當前結點x到目的結點預測的權值和，可以根據網絡擁塞情況計算如下：h(x)=k*(|xx—xt| + |yx—yt|), 1kN。其中k根據擁塞程度確定，當片上網絡整體擁塞程度較高時，需提高k的值，反之降低k的值。

4.2 提高容錯粒度

粒度是指在路由策略中，對待路由單元的故障的宏觀程度。之前提出的迷宮A*尋路算法，是把出現故障的路由結點都視為不可用結點，該方法的粒度較大，浪費路由資源較多。

對于僅考慮鏈路故障的容錯策略，需設置數組存儲每個結點4個方向鏈路的有效情況：link_enable[x][y][dir]表示坐標為(x,y)的結點其dir方向的鏈路是否正常。在進行結點擴展時，需要考慮擴展方向的其鏈路是否正常，若正常則擴展該相鄰結點，否則不擴展。

5 結語

片上網絡核心的性能隨著半導體行業(yè)的發(fā)展而逐漸提升，在高級的片上網絡上，每一個核心都被視作一個基本的 CPU 單元，使得源路由算法參考計算機領域的路由算法成為可能。本文介紹了各類型NoC 路由算法，給出了迷宮BFS算法和迷宮A*算法分析，根據實驗結果給出了擴展措施。