片上網(wǎng)絡(luò)路由優(yōu)化算法分析

胡 明，季雙雙

(蕪湖職業(yè)技術(shù)學(xué)院 網(wǎng)絡(luò)工程學(xué)院，安徽 蕪湖 241003)

隨著半導(dǎo)體技術(shù)的進(jìn)步，片上系統(tǒng)(SoC)技術(shù)被廣泛地應(yīng)用到各種領(lǐng)域。片上系統(tǒng)包含的一系列核心工作都需要靠一定的拓?fù)浣Y(jié)構(gòu)和互聯(lián)方式實(shí)現(xiàn)。在規(guī)模較小的系統(tǒng)中，往往采用總線互聯(lián)的方式，但連接結(jié)點(diǎn)增加時(shí)容易產(chǎn)生對總線的爭奪，每次只能進(jìn)行兩個(gè)結(jié)點(diǎn)之間的通信，導(dǎo)致系統(tǒng)通信的帶寬太小。交叉開關(guān)矩陣也是一種常用的互聯(lián)機(jī)制，其實(shí)現(xiàn)了片上網(wǎng)絡(luò)每兩個(gè)結(jié)點(diǎn)的直接互聯(lián)，實(shí)現(xiàn)了低延時(shí)和高吞吐率，但是容易產(chǎn)生通信通道的浪費(fèi)[1]。

片上網(wǎng)絡(luò)系統(tǒng)(下文簡稱NoC)平衡了通信延時(shí)和通信成本的關(guān)系，它將片上系統(tǒng)的結(jié)點(diǎn)以網(wǎng)絡(luò)的形式連接，在大規(guī)模結(jié)點(diǎn)的片上系統(tǒng)中得到廣泛運(yùn)用。目前，應(yīng)用最廣泛的片上網(wǎng)絡(luò)系統(tǒng)的拓?fù)浣Y(jié)構(gòu)是網(wǎng)格結(jié)構(gòu)，它將每個(gè)核心結(jié)點(diǎn)通過網(wǎng)格的結(jié)構(gòu)連接起來，既具有較低的成本，又可以達(dá)到較低的通信延時(shí)。網(wǎng)格結(jié)構(gòu)也易于半導(dǎo)體工藝的實(shí)現(xiàn)，可以對其中任意兩個(gè)核心結(jié)點(diǎn)提供多條通信路徑，具有較高的容錯(cuò)能力。

1 路由算法分類

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

1.1 NoC無關(guān)路由算法

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

1.2 NoC自適應(yīng)路由算法

自適應(yīng)路由主要是指對網(wǎng)絡(luò)中擁塞的自適應(yīng)。當(dāng)網(wǎng)絡(luò)中的某些結(jié)點(diǎn)負(fù)載過重時(shí)，自適應(yīng)路由算法可以自動(dòng)檢測并繞過這些結(jié)點(diǎn)，選擇另一條空閑的路徑。

自適應(yīng)路由的策略一般是建立在對擁塞考察的基礎(chǔ)上，按其對擁塞的感知程度可分為本地?fù)砣兄蛥^(qū)域擁塞感知。本地?fù)砣兄疾毂韭酚蓡卧南噜徛酚蓡卧膿砣闆r，其實(shí)現(xiàn)較為簡單，僅需在路由單元加入擁塞決策函數(shù)即可實(shí)現(xiàn)擁塞的自適應(yīng)。區(qū)域擁塞感知需綜合考察全局結(jié)點(diǎn)的狀態(tài)，其路由策略往往優(yōu)于僅考察鄰居結(jié)點(diǎn)的路由策略，但其硬件和算法實(shí)現(xiàn)較復(fù)雜。

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

1.3 NoC容錯(cuò)路由算法

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

1.4 源路由算法

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

2 源路由算法分析

源路由算法的優(yōu)點(diǎn)是在尋找路由決策的時(shí)候具有全局的鏈路信息，因此路由策略可以綜合各種信息找出最佳路徑。但該算法的實(shí)現(xiàn)和網(wǎng)絡(luò)信息的存儲(chǔ)較復(fù)雜，不適用于結(jié)點(diǎn)結(jié)構(gòu)簡單的片上網(wǎng)絡(luò)中。

2.1 迷宮BFS尋路算法

圖1 BFS 尋路算法示意圖

BFS算法通過兩個(gè)線性表實(shí)現(xiàn)，open表用來存放源結(jié)點(diǎn)，從open表中取出結(jié)點(diǎn)向4個(gè)方向擴(kuò)展結(jié)點(diǎn)；close表用來存放已擴(kuò)展結(jié)點(diǎn)。過程是從open表中取出所有結(jié)點(diǎn)，如果close表中無擴(kuò)展結(jié)點(diǎn)，就放入open表尾，直至結(jié)束。

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

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

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

2.2 迷宮 A*尋路算法

圖2 A*尋路算法示意圖

為了解決BFS尋路算法的盲目性，往往會(huì)在搜索過程中加入啟發(fā)式函數(shù)加快尋路速度。對目前所有的啟發(fā)式尋路算法來說，使用最多的是A*尋路算法，它是目前在游戲領(lǐng)域中應(yīng)用最廣泛的尋路算法。其主要優(yōu)點(diǎn)是通過啟發(fā)式函數(shù)來預(yù)測當(dāng)前結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的距離，選擇性的擴(kuò)展與目標(biāo)結(jié)點(diǎn)距離較近的結(jié)點(diǎn)，從而加速找到通向目的結(jié)點(diǎn)的路徑?？梢宰C明當(dāng)當(dāng)前結(jié)點(diǎn)到目的結(jié)點(diǎn)的估計(jì)距離不大于當(dāng)前結(jié)點(diǎn)到目的結(jié)點(diǎn)的實(shí)際距離時(shí)，A*算法總能找到最短路徑。

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

3 路由算法測試分析

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

表1 故障結(jié)點(diǎn)率0擴(kuò)展結(jié)點(diǎn)數(shù)測試

表2 故障結(jié)點(diǎn)率 10%擴(kuò)展結(jié)點(diǎn)數(shù)測試

表3 故障結(jié)點(diǎn)率 30%擴(kuò)展結(jié)點(diǎn)數(shù)測試

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

表4 故障結(jié)點(diǎn)率0 時(shí)間空間占用測試

表5 故障結(jié)點(diǎn)率10% 時(shí)間空間占用測試

表6 故障結(jié)點(diǎn)率30% 時(shí)間空間占用測試

從表4-表6可以看出，A*算法對于大規(guī)模片上網(wǎng)絡(luò)來說優(yōu)勢明顯，當(dāng)網(wǎng)絡(luò)規(guī)模增大，A*算法不會(huì)盲目擴(kuò)展目標(biāo)結(jié)點(diǎn)。而對于小規(guī)模片上網(wǎng)絡(luò)，BFS算法和A*算法效率差不多，甚至BFS算法更優(yōu)于A*算法。

4 迷宮尋路算法的擴(kuò)展

迷宮A*路由算法加入結(jié)點(diǎn)擁塞權(quán)值，實(shí)現(xiàn)擁塞自適應(yīng)路由。此外，可通過提高容錯(cuò)粒度，提高A*算法效率。

4.1 擁塞自適應(yīng)路由

將網(wǎng)絡(luò)中的每個(gè)結(jié)點(diǎn)附上相應(yīng)的權(quán)值作為通過該結(jié)點(diǎn)的代價(jià)，即可將 A*算法用于實(shí)現(xiàn)擁塞自適應(yīng)的路由，具體方法如下：

每個(gè)片上網(wǎng)絡(luò)結(jié)點(diǎn)檢測其自身結(jié)點(diǎn)的擁塞情況，例如數(shù)據(jù)包進(jìn)入該結(jié)點(diǎn)到離開該結(jié)點(diǎn)的等待時(shí)間，將該時(shí)間以正相關(guān)的方式映射為 1～N的某一整數(shù)值。1 表示結(jié)點(diǎn)最為空閑，N 表示結(jié)點(diǎn)最為繁忙。此時(shí)每隔一段固定時(shí)間將該整數(shù)值及對應(yīng)結(jié)點(diǎn)的編號(hào)廣播給片上網(wǎng)絡(luò)的所有結(jié)點(diǎn)。這樣每個(gè)結(jié)點(diǎn)都能獲得整個(gè)網(wǎng)絡(luò)結(jié)點(diǎn)的擁塞情況。

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

4.2 提高容錯(cuò)粒度

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

對于僅考慮鏈路故障的容錯(cuò)策略，需設(shè)置數(shù)組存儲(chǔ)每個(gè)結(jié)點(diǎn)4個(gè)方向鏈路的有效情況：link_enable[x][y][dir]表示坐標(biāo)為(x,y)的結(jié)點(diǎn)其dir方向的鏈路是否正常。在進(jìn)行結(jié)點(diǎn)擴(kuò)展時(shí)，需要考慮擴(kuò)展方向的其鏈路是否正常，若正常則擴(kuò)展該相鄰結(jié)點(diǎn)，否則不擴(kuò)展。

5 結(jié)語

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