來(lái) 耀,荊明娥

(復(fù)旦大學(xué) 專用集成電路與系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，上海 201203)

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

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

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

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

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

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

2 BFS尋路算法

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

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

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

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

3 A*尋路算法

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

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

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

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

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

算法流程圖如圖2所示．

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

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

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

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

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

4.1 open表的優(yōu)化

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

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

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

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

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

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

(1)

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

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

4.3 雙向搜索

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

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

(2)

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

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

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

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

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

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

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

(3)

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

5 路由算法的測(cè)試

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

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

5.1 算法測(cè)試結(jié)果

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

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

算法在運(yùn)行過(guò)程中找出的平均路徑長(zhǎng)度與平均擴(kuò)展結(jié)點(diǎn)數(shù)如表2所示．

表2 算法平均路徑長(zhǎng)度與平均擴(kuò)展結(jié)點(diǎn)數(shù)測(cè)試結(jié)果

5.2 算法測(cè)試分析

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

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

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

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

6 結(jié) 論

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

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