基于A*算法優(yōu)化的片上網(wǎng)絡(luò)源路由算法

來 耀,荊明娥

(復旦大學 專用集成電路與系統(tǒng)國家重點實驗室，上海 201203)

片上網(wǎng)絡(luò)(Networks-on-Chip, NoC)是片上系統(tǒng)(System on a Chip, SoC)重要的硬件形式之一，其將片上系統(tǒng)的結(jié)點以網(wǎng)絡(luò)的形式相連．片上網(wǎng)絡(luò)路由算法是指從一個結(jié)點發(fā)送數(shù)據(jù)包到另一個或多個指定的結(jié)點而選擇其網(wǎng)絡(luò)上的傳輸路徑的算法．好的路由算法不僅需要考慮使單個數(shù)據(jù)包的傳輸延時最短，還要考慮整個片上網(wǎng)絡(luò)工作的整體延時，并且需要一定的防擁塞、防死鎖和容錯機制．

片上網(wǎng)絡(luò)的路由算法從其路由結(jié)果的決策地點來分，可分為源路由和分布式路由[1]．分布式路由是指路由的下一步?jīng)Q策是根據(jù)當前數(shù)據(jù)包所在的路由結(jié)點完成，因此整個路由決策是由數(shù)據(jù)包所經(jīng)過的所有結(jié)點共同決定的．而源路由是指路由的決策在數(shù)據(jù)的發(fā)送結(jié)點(即源結(jié)點)已經(jīng)全部完成，該路由決策將附加在數(shù)據(jù)包的頭部，中間的傳輸結(jié)點根據(jù)數(shù)據(jù)包的路由信息決定下一步的發(fā)送結(jié)點．對于分布式路由，一般途經(jīng)的結(jié)點只做出下一步的路由決策，因此只需考察其周圍結(jié)點的狀況，因此分布式路由一般更易于硬件實現(xiàn)，但缺少決策的宏觀性．對源路由而言，源結(jié)點一般需要得到整個網(wǎng)絡(luò)的信息再產(chǎn)生路由決策，可以做出較為宏觀的決策．

在源路由算法中，最著名的是鏈路狀態(tài)算法(NoC-LS)算法[1]，其思想是每個片上網(wǎng)絡(luò)的結(jié)點都存儲一份整個網(wǎng)絡(luò)上的狀態(tài)信息(鏈路延時、故障等)．當需要進行路由決策時，在源結(jié)點處根據(jù)存儲的整個網(wǎng)絡(luò)結(jié)點的延時和故障信息使用圖論中最短路徑算法找出最佳路徑．該路由算法具有在任何網(wǎng)絡(luò)上運行的通用性，但沒有充分利用片上網(wǎng)絡(luò)拓撲結(jié)構(gòu)的特性，因此其效率不夠高．本文將A*尋路算法應用于片上網(wǎng)絡(luò)中，可以更好地利用片上網(wǎng)絡(luò)的拓撲結(jié)構(gòu)．

1 片上網(wǎng)絡(luò)路由的問題描述

2D-Mesh的片上網(wǎng)絡(luò)可視為N×N的網(wǎng)格，每個片上網(wǎng)絡(luò)的結(jié)點對應于網(wǎng)格中的一個格點．則片上網(wǎng)絡(luò)的源路由問題可看成網(wǎng)格中源結(jié)點(s)到目的結(jié)點(t)的尋路問題．由于片上網(wǎng)絡(luò)處于實時動態(tài)狀態(tài)中，其中將出現(xiàn)擁塞結(jié)點和不可用結(jié)點．對于擁塞自適應的路由策略需要盡可能少的通過擁塞結(jié)點，對于容錯的路由策略需避開不可用結(jié)點[2]．

一個片上網(wǎng)絡(luò)結(jié)點路由問題的例子如圖1(見第606頁)所示，其黑色結(jié)點表示不可用結(jié)點，路由算法則需從s到t找出一條最優(yōu)的路徑．當源路由算法得到路由策略后，將該路徑信息附加在將要發(fā)送數(shù)據(jù)包的頭部，沿途結(jié)點根據(jù)該信息將數(shù)據(jù)包轉(zhuǎn)發(fā)至下一個結(jié)點．

2 BFS尋路算法

圖1 片上網(wǎng)絡(luò)路由問題示意圖Fig.1 Diagram of NoC routing problem

BFS算法即廣度優(yōu)先搜索(Breadth First Search, BFS)算法，其基本思想是設(shè)置兩個線性表： open表和close表．open表使用隊列維護．首先將源結(jié)點放入open表中．每次從open表頭中取出結(jié)點，往周圍4個方向擴展結(jié)點，若擴展的結(jié)點不在close表中，則將結(jié)點放入open表尾．擴展完成后將該結(jié)點放入close表中，即設(shè)為已訪問過．然后不斷地從open表頭中取出結(jié)點進行下一步擴展，直至找到目標結(jié)點為止．

圖2 A*算法流程圖Fig.2 Flow chart of A* algorithm

該算法的優(yōu)點是只要源結(jié)點與目的結(jié)點之間存在路徑，就一定能找到通向目的結(jié)點的最短路徑，但其缺點是具有盲目性，往往擴展出許多遠離目的結(jié)點的路徑，因而其代價較高，影響了整個片上網(wǎng)絡(luò)工作的效率．對于N×N的2D-Mesh結(jié)構(gòu)，該算法的最壞情況是擴展出網(wǎng)格中的所有結(jié)點，因此時間復雜度是O(N2)的[3]．

3 A*尋路算法

3.1 啟發(fā)式函數(shù)的定義

A*尋路是應用最為廣泛的地圖尋路算法，其核心思想是啟發(fā)式函數(shù)的設(shè)計[4]．

對于網(wǎng)格中的每一個結(jié)點x，都存在一個啟發(fā)式函數(shù)的值f(x)．其中：f(x)=g(x)+h(x)；g(x)是從源結(jié)點s到當前結(jié)點x已經(jīng)走過的最短距離(路由步數(shù))，是一個已知量；h(x)為當前結(jié)點x到目的結(jié)點的預測距離，一般設(shè)為到目的結(jié)點的曼哈頓距離．

3.2 算法的執(zhí)行過程

算法運行的過程中需要使用open表和close表分別存儲待擴展的結(jié)點和已擴展的結(jié)點．算法的初始化將源結(jié)點s放入open表中．每次從open表中找到f(x)最小的結(jié)點x，依次取出該結(jié)點的相鄰結(jié)點y，若y在close表中，則忽略；若y在open表中，則將用當前計算出的f(y)更新open表中對應結(jié)點的f(y)值；若既不在open表中也不在close表中，則將擴展出的結(jié)點加入open表．直到擴展出目的結(jié)點t為止．可以看出當h(x)=0時，A*算法就是BFS算法．

算法流程圖如圖2所示．

3.3 片上網(wǎng)絡(luò)路由算法的特殊性

由于A*尋路算法產(chǎn)生的路由策略會在片上網(wǎng)絡(luò)中形成環(huán)路．因此若直接運用到片上網(wǎng)絡(luò)的路由算法中，將產(chǎn)生死鎖，即數(shù)據(jù)包循環(huán)占用緩存導致其無法繼續(xù)傳輸．

因此將A*尋路算法應用于片上網(wǎng)絡(luò)路由算法中，需要增加虛通道來防止死鎖的出現(xiàn)．虛通道方法是一種應用于輸入/輸出通道的算法，即在每個結(jié)點的輸入輸出緩沖區(qū)，劃分出具有不同編號的邏輯通道．對于設(shè)置虛通道解決死鎖的方法也有很多，本文中采用在x方向設(shè)置兩條虛通道x0及x1，而在y方向的通道不設(shè)置虛擬通道的方式[5]，將整個網(wǎng)絡(luò)分成上升子網(wǎng)和下降子網(wǎng)．上升子網(wǎng)包含x0和y+(y軸正向傳輸通道)，下降子網(wǎng)包含x1和y-(y軸負向傳輸通道)．當目的結(jié)點在發(fā)送結(jié)點的上方時，使用上升子網(wǎng)路由；當目的結(jié)點在發(fā)送結(jié)點的下方時，使用下降子網(wǎng)路由．因此任意數(shù)據(jù)包的傳輸過程將只使用其中的一個子網(wǎng)，因而消除了環(huán)形依賴[6]．

對于A*算法的具體修改方案為： 在尋徑時需要記錄最近一次在y方向的路徑是正向還是負向．當數(shù)據(jù)包將要轉(zhuǎn)向x方向?qū)綍r，若上一次在y方向的尋徑是正向，則使用虛擬通道x0，否則使用虛擬通道x1．

4 路由算法的優(yōu)化

4.1 open表的優(yōu)化

A*算法中open表需要進行插入結(jié)點、刪除結(jié)點、找出代價最小的結(jié)點和找出對應結(jié)點更新的操作．因此對open表采用何種數(shù)據(jù)結(jié)構(gòu)對算法效率影響明顯．目前對open表采用的數(shù)據(jù)結(jié)構(gòu)主要有未排序的數(shù)組或鏈表、排序數(shù)組、排序列表、索引數(shù)組、散列表、二叉堆、伸展樹、頂部堆(Heap on Top, HOT)隊列等[4]．不同的數(shù)據(jù)結(jié)構(gòu)各種操作的時間復雜度各不相同，均有各自的常數(shù)時間消耗以及空間復雜度．因此并不能簡單的認為某一種數(shù)據(jù)結(jié)構(gòu)一定優(yōu)于另一種數(shù)據(jù)結(jié)構(gòu)．

對于小規(guī)模的片上網(wǎng)絡(luò)，由于高級數(shù)據(jù)結(jié)構(gòu)操作復雜，匯編成的指令數(shù)也較多，導致常數(shù)時間過大，因此更適合用數(shù)組或鏈表來實現(xiàn)open表．對于大規(guī)模的片上網(wǎng)絡(luò)，隨著數(shù)組和鏈表查找和插入的時間復雜度逐漸上升，此時使用二叉堆、伸展樹等數(shù)據(jù)結(jié)構(gòu)的算法能大大降低open表操作的時間復雜度．

4.2 啟發(fā)式函數(shù)的選擇

圖3 啟發(fā)式函數(shù)權(quán)值的選擇對擴展結(jié)點數(shù)目的影響Fig.3 Influence of selection of Heuristic function weights on the number of extended nodes

對于啟發(fā)式函數(shù)f(x)的選擇往往決定尋徑的效率和尋徑的結(jié)果．為了使A*算法可以找到源結(jié)點到目的結(jié)點的最短路徑，需使h(x)不小于x結(jié)點到目的結(jié)點的實際最短距離．因此上文中提到的h(x)為當前結(jié)點x到目的結(jié)點的曼哈頓距離是保證找到最短路徑的下界．此時若增大h(x)，算法將優(yōu)先擴展目的結(jié)點附近的結(jié)點．在故障結(jié)點數(shù)少的情況下，將提高路徑搜索的效率，但卻不能保證找到最短路徑．因此，當片上故障率較低時，可以適當提高h(x)相對g(x)比例，犧牲路徑長度而加快尋徑速度即：

f(x)=g(x)+w(x)h(x)w(x)>1,

(1)

其中：w(x)既可以為大于1的常數(shù)，也可以根據(jù)x的具體情況來定義w(x)．

圖3(a)是w(x)=1時的擴展結(jié)點情況，圖3(b)是w(x)=2是的擴展結(jié)點情況，可以看出增大預測函數(shù)的權(quán)重可以有效減少算法運行時擴展的結(jié)點數(shù)．

4.3 雙向搜索

A*算法也可以借鑒雙向BFS算法的雙向搜索思想，同時從源結(jié)點和目的結(jié)點開始擴展結(jié)點．選擇啟發(fā)式函數(shù)：

f(x,y)=g(s→x)+h(x→y)+g(t→y).

(2)

每次找出使得f(x,y)最小的結(jié)點x與結(jié)點y進行擴展，減少總體擴展結(jié)點的個數(shù)，并且可以應用并行計算，提高尋徑效率．

4.4 維片上網(wǎng)絡(luò)的擴展

目前的3維片上網(wǎng)絡(luò)幾乎都采用網(wǎng)格結(jié)構(gòu)，即3D上的Mesh結(jié)構(gòu)．其又可分為兩類：

(1)z方向的通道采用相鄰結(jié)點相連結(jié)構(gòu)(3D-Mesh結(jié)構(gòu))；

(2)z方向的通道采用總線結(jié)構(gòu)(疊層Mesh結(jié)構(gòu))[7].

對于情況(1)，只需要在2D-Mesh上的A*尋路算法稍加修改即可得到3D-Mesh下的A*尋路算法．首先將每次擴展的結(jié)點變?yōu)?個，增加Up和Down 2個擴展方向．將啟發(fā)式函數(shù)h(x)擴展為3維上的兩點間曼哈頓距離即可：

h(x)=|xx-xt|+|yx-yt|+|zx-zt|.

(3)

對于情況(2)，為了避免數(shù)據(jù)包占用總線的時間，一般只允許數(shù)據(jù)包通過總線1次．因此當擴展的結(jié)點一旦改變z坐標，則必須直接進入與目的結(jié)點同層的結(jié)點，并且在今后的擴展中都不能改變z(即此時退化為2維A*尋路)．

5 路由算法的測試

測試程序分別使用了單向BFS尋路算法和A*尋路算法,在CPU Intel Core i5-6200U 2.30GHz，內(nèi)存8G的PC環(huán)境中進行測試．采用黑盒測試法，對于不同規(guī)模的片上網(wǎng)絡(luò)，對于30%的不可用結(jié)點率，分別隨機生成5000組網(wǎng)絡(luò)狀態(tài)，主要測試其時間效率和空間占用的情況．

分別測試BFS算法、A*算法以及加速A*算法等3種算法．A*算法與加速A*算法均采用二叉堆結(jié)構(gòu)的open表，其中加速A*算法的啟發(fā)式函數(shù)為f(x)=g(x)+2h(x)．

5.1 算法測試結(jié)果

對于算法的時間效率，對不同的算法測試其在同一個PC環(huán)境下5000組數(shù)據(jù)尋徑的總耗時．而對于算法的空間占用，我們采用測試5000組數(shù)據(jù)中(不包括源結(jié)點與目的結(jié)點不互通的情況)open表與close表最大存儲的結(jié)點數(shù)來量化算法的空間占用情況．算法測試結(jié)果如表1所示．

表1 算法時間效率與空間占用測試結(jié)果

算法在運行過程中找出的平均路徑長度與平均擴展結(jié)點數(shù)如表2所示．

表2 算法平均路徑長度與平均擴展結(jié)點數(shù)測試結(jié)果

5.2 算法測試分析

從測試結(jié)果可以看出，對于越大規(guī)模的片上網(wǎng)絡(luò)，使用A*算法的時間效率優(yōu)勢越大．這是由于在小規(guī)模的片上網(wǎng)絡(luò)中，A*算法與BFS算法擴展出的結(jié)點數(shù)相差不多．而由于A*算法由于每次需要在open表中插入、刪除、查找結(jié)點，對于使用二叉堆的open表來說，其時間復雜度為O(log2N)，其中N為open表的大小．而BFS算法由于其每次加入的結(jié)點代價都是嚴格遞增的，只需要使用隊列實現(xiàn)open表，因此插入、刪除的時間復雜度均為O(1)．因而在小規(guī)模的片上網(wǎng)絡(luò)中，BFS算法甚至會優(yōu)于A*算法．

在片上網(wǎng)絡(luò)規(guī)模逐漸增大時，由于BFS算法的盲目性，其在找到目標結(jié)點之前，將在片上網(wǎng)絡(luò)所有方向擴展目標結(jié)點．由于大規(guī)模網(wǎng)絡(luò)導致BFS算法長時間無法擴展到邊界，此時使用BFS算法擴展的結(jié)點數(shù)將遠遠多于A*算法的結(jié)點數(shù)．因此A*算法的優(yōu)勢將逐漸顯現(xiàn)出來．對比用時數(shù)據(jù)可以看出，在16×16及以上規(guī)模的片上網(wǎng)絡(luò)中，A*算法的用時幾乎均小于BFS算法用時的50%，而加速A*算法的用時均小于BFS算法的30%，時間效率大大提升．

從算法的空間占用上來看，一般情況下close表的空間占用遠大于open表，因此close表的大小可以近似認為擴展的總結(jié)點數(shù)，而A*算法擴展的結(jié)點遠少于BFS算法，因此A*算法的close表的空間占用也優(yōu)于BFS算法．從測試結(jié)果可以看出，不可用結(jié)點數(shù)越少，A*算法的空間占用的提升更明顯，這是由于路徑越簡單，A*算法的預測函數(shù)越準確，其擴展的結(jié)點數(shù)也就越少．即使在30%不可用結(jié)點數(shù)的情況下，A*算法的空間占用約為BFS算法空間占用的70%，加速A*算法的空間占用小于BFS算法空間占用的50%，可以有效減少需要的存儲空間．

根據(jù)算法最后得到的平均路徑長度來看，BFS算法與A*算法路徑長度相同，其均可以找到源結(jié)點到目的結(jié)點的最短路徑．對于加速A*算法而言，其在有不可用結(jié)點的情況下，由于其優(yōu)先擴展預測距離小的結(jié)點，將有一定概率找不到最短路徑．在64×64規(guī)模的片上網(wǎng)絡(luò)上，在2394組合法數(shù)據(jù)中，只有68組數(shù)據(jù)(2.8%)的加速A*算法可以找到最短路徑．因此傳送一個數(shù)據(jù)包占用的結(jié)點數(shù)也相應的增多，更容易引起片上網(wǎng)絡(luò)結(jié)點的擁塞．

6 結(jié) 論

片上網(wǎng)絡(luò)技術(shù)的發(fā)展使得原本只能出現(xiàn)在計算機網(wǎng)絡(luò)的源路由算法可以應用到片上網(wǎng)絡(luò)中，而我們應用迷宮尋徑的各種理論來優(yōu)化源路由算法．此時每一個片上網(wǎng)絡(luò)的結(jié)點都可以看作是一個獨立的CPU單元，從而可以運行A*算法等源路由算法，然后根據(jù)整個片上網(wǎng)絡(luò)的結(jié)點狀態(tài)計算出最佳的路由路徑．

對于A*算法還可以加入對片上網(wǎng)絡(luò)各結(jié)點的擁塞情況，從而實現(xiàn)擁塞自適應的路由[8]．此時需要對各片上結(jié)點賦予擁塞度的權(quán)值，通過權(quán)值的確定以及啟發(fā)式函數(shù)的調(diào)整使得網(wǎng)絡(luò)路由可以有效地避免片上網(wǎng)絡(luò)的擁塞結(jié)點，進一步降低數(shù)據(jù)包的傳輸時間．源結(jié)點的路由算法開銷大于分布式的路由算法，但其采用的路由策略更具有全局性，因此適用于結(jié)點為獨立處理器的片上網(wǎng)絡(luò)．因此，當半導體技術(shù)飛快發(fā)展的今天，片上結(jié)點的源路由算法將會逐漸運用到片上網(wǎng)絡(luò)中．