洪 斌 張紅嶺 于 夢

（1.河北建筑工程學(xué)院，河北 張家口075000；2.華北電力大學(xué)，河北 保定071000）

0 引 言

設(shè)計(jì)中復(fù)雜度的增加使得必須重用嵌入式內(nèi)核，以降低生產(chǎn)率間隙.嵌入式內(nèi)核是預(yù)先設(shè)計(jì)，預(yù)先驗(yàn)證知識(shí)產(chǎn)權(quán)（IP）的，也許是軟件、公司或硬件，而且嵌入式內(nèi)核通常是對功能，大小和通信帶寬的典型異構(gòu).許多研究人員在爭論認(rèn)為有必要使用一個(gè)可擴(kuò)展的通信方法滿足大型片上系統(tǒng)（SoC）的高通信要求網(wǎng)絡(luò)芯片（NOC）的設(shè)計(jì)是新興的技術(shù)，它包含多個(gè)相互關(guān)聯(lián)的異構(gòu)設(shè)備，通過使用片上基于分組的通信范例，溝通連接于一個(gè)可擴(kuò)展的互連網(wǎng)絡(luò).NOC提供了幾個(gè)優(yōu)點(diǎn)，包括模塊化，更高的性能，更好的結(jié)構(gòu)，和兼容的核心設(shè)計(jì)與重用.NOC使用各種的拓?fù)浣Y(jié)構(gòu)，如mesh、torus、fat－tree和ring（網(wǎng)格／圓環(huán)，胖樹模型和環(huán)路）.一個(gè)二維網(wǎng)格拓?fù)溆膳帕性谥本€圍成的網(wǎng)格中的節(jié)點(diǎn)組成，網(wǎng)格中的每個(gè)節(jié)點(diǎn)雙向連接到它的頂部，底部，左部和相鄰的右部.每個(gè)節(jié)點(diǎn)包含一個(gè)與核心相關(guān)的多端口開關(guān).

一個(gè)有效的NoC（其滿足依賴于應(yīng)用程序的約束）設(shè)計(jì)是一個(gè)復(fù)雜的任務(wù)，它包括合成網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，流量特性建模，和設(shè)置設(shè)計(jì)參數(shù).在NOC中的一個(gè)困難問題是拓?fù)溆成涞馁Y源優(yōu)化成確定的目標(biāo)函數(shù).這種映射問題是一個(gè)約束二次分配問題的實(shí)例，一個(gè)NP難問題.關(guān)于NoC的實(shí)現(xiàn)中另一個(gè)值得關(guān)注的問題是選擇一個(gè)有效的路由策略，當(dāng)從死鎖和活鎖提供自由的時(shí)候.路由運(yùn)算法則也許是確定的或者擁有適應(yīng)性.數(shù)據(jù)包被發(fā)送前，路由路徑已被被選擇，因此確定性路由需要較少的資源.然而，它不使用網(wǎng)絡(luò)充分發(fā)揮其潛力，尤其是當(dāng)有一個(gè)重負(fù)荷.各種靜態(tài)路由技術(shù)已經(jīng)被提出如XY、切換XY，和加權(quán)切換XY路由.在XY路由，分組將首先送到在x方向，然后沿著垂直的y維度.在XY路由策略可以應(yīng)用到普通的二維網(wǎng)狀拓?fù)洌a(chǎn)生最小的鎖死自由NOC路徑，但需要可用帶寬的費(fèi)用.此外，XY路由無法與不規(guī)則網(wǎng)格工作，因?yàn)橐恍╂溄涌赡軐?dǎo)致死端［4］.為了緩解與延遲相關(guān)的阻塞，提出了自適應(yīng)路由技術(shù).

1 映射和NOC路由配置

1.1 模擬退火映射

在實(shí)施退火算法的關(guān)鍵要素有：1）初始配置的定義，2）配置空領(lǐng)域的定義，和探索它的擾動(dòng)算子，3）成本函數(shù)，4）冷卻進(jìn)度表.

1）配置表示：我們提出了一種退火配置是使用一個(gè)二維矢量建模，其中一個(gè)核心和一個(gè)開關(guān)的位置（X，Y形）在二維網(wǎng)格.每個(gè)核心連接到通信網(wǎng)絡(luò)，使用一個(gè)開關(guān)連接到相鄰的開關(guān).一個(gè)單元可以在迭代退火過程中根據(jù)鄰域函數(shù)改變其核心和轉(zhuǎn)換開關(guān).

2）初始配置：通過在網(wǎng)中隨機(jī)定位核心，生成初始配置.

3）領(lǐng)域函數(shù)能：算法初步探討可能的映射，通過隨機(jī)選擇兩個(gè)瓷片和交換他們在網(wǎng)格上的位置的.這個(gè)過程會(huì)重復(fù)，如果違反區(qū)域限制.

4）成本函數(shù)：給出了內(nèi)核，目的是找到一個(gè)映射和路由路徑分配，最大限度地減少帶寬.一個(gè)通信通道的通信成本被表示為一個(gè)路徑長度的函數(shù)和潛在的阻塞，當(dāng)他占據(jù)多個(gè)路由通道時(shí)可能造成這種阻塞［5］.成本函數(shù)的減少是受面積限制的.

1.2 路由

我們提出了一種路由算法，選擇兩個(gè)路徑中的一個(gè)，依據(jù)網(wǎng)絡(luò)狀態(tài)和隊(duì)列占據(jù).因此，如果檢測到擁塞，數(shù)據(jù)包將被趕到一個(gè)擁擠而自由的路徑.該算法利用在一個(gè)最大程度為4的樹狀圖中深度優(yōu)先搜索并可以將相鄰的跳數(shù)對移動(dòng)到其中.該算法，如圖2所示，是基于一種迷宮方法，該方法已被證明在人工智能應(yīng)用領(lǐng)域是非常有效的，數(shù)據(jù)包根據(jù)一組規(guī)則將通過一個(gè)迷宮圖路由，只有當(dāng)達(dá)到阻塞、連接斷開或者丟包，才會(huì)將數(shù)據(jù)包重新路由.該算法意味著一個(gè)相對于數(shù)據(jù)包位置的局部網(wǎng)路知識(shí)，并要求在網(wǎng)絡(luò)中遇到一個(gè)路由交集，當(dāng)交集被記住時(shí)選擇該路徑.如果選擇的路徑由于擁塞等通往死端（deadend），然后數(shù)據(jù)包將被路由前跳到下一路徑，直到到達(dá)最終目的地.在每一跳躍，下一個(gè)跳躍的選擇是基于的相對當(dāng)前位置的終點(diǎn)地的.優(yōu)先權(quán)顯示在表1中.例如，如果目標(biāo)高于現(xiàn)有的路由器，然后數(shù)據(jù)包通過路由跳到高于當(dāng)前的路由器.然而，如果該數(shù)據(jù)包第二次由于阻塞被重新路由，它將被路由到合適的當(dāng)前路由器，根據(jù)表1.2第一排.因此，在最壞的情況下，一個(gè)路由器在宣告數(shù)據(jù)包無法傳遞前可能被訪問過四次.優(yōu)先事項(xiàng)清單確保數(shù)據(jù)包路由到最終目的地的同時(shí)保證路由是無死鎖的.路由是環(huán)路的，因?yàn)槊總€(gè)路徑是一個(gè)深度優(yōu)先搜索樹.

圖2 路由算法

表1 下一個(gè)躍點(diǎn)選擇基于當(dāng)前和下一個(gè)路由器的位置

在圖3中使用VOPD映射的例子說明我們的路由算法.假設(shè)一個(gè)100位大小的數(shù)據(jù)包從7位被發(fā)送到ip9.基于該算法，ip9的優(yōu)先權(quán)是低于ip7的.因此，第一次是下跳到ip6.然而，iP6已經(jīng)被分配了一個(gè)780位通信量，不能容納額外的100位.該算法回溯，基于表1的第二選擇是通向的.在3.被分配了32位的通信量，該通信量最多679位，可以容納更多的100位.被選擇作為第一次跳躍；13中的通行量被調(diào)整為132位，并成為源路由器.第二跳的優(yōu)先權(quán)是下跳到可容納100位的，同時(shí)成為源.最后，下一跳是向下的跳到，恰好是最終的目的地.請注意，上述路線不在網(wǎng)格中顯示.

圖3 映射和路由路徑分配視頻對象平面解碼器每個(gè)單元格與路由器的注釋和分配帶寬

2 算 法

如圖4所示提出的算法，從選擇一個(gè)映射開始然后執(zhí)行一個(gè)序列的迭代.在每次迭代中，通過在網(wǎng)格上隨機(jī)選擇兩個(gè)磁片并交換它們的位置，在原來的鄰域映射中生成一個(gè)新的配置，該網(wǎng)格中退火設(shè)置代表不同帶寬和面積花費(fèi)得中間網(wǎng)格.安置算法首先通過選擇一個(gè)單元格添并加一行一列確定網(wǎng)格中的磁片數(shù)，這樣，每列單元格的寬度等于該列最大核心的寬度，每行單元格的高度等于該行最高的核心的高度.該算法重復(fù)上述過程，直到所有的核心都被考慮過了.該算法在映射下一個(gè)的核心的地方，高通信節(jié)點(diǎn)定位彼此接近，受面積限制.路由路徑分配在下次被執(zhí)行，伴隨成本函數(shù)的變化，和ΔCost被計(jì)算.如果ΔCost是負(fù)的，從Ci到Ci＋1是允許的.如果成本函數(shù)增加，轉(zhuǎn)變被接受的概率是基于玻爾茲曼分布的.溫度逐漸降低，從幾乎每一個(gè)被提出轉(zhuǎn)變不論是積極的還是消極的的高初始值.在沒有進(jìn)一步的變化發(fā)生時(shí)，接受冷凍溫度.實(shí)驗(yàn)測定了冷卻進(jìn)度表如下：TINIT＝40，α＝0.99，β＝100，和M0＝5.算法重復(fù)以上過程的最大迭代次數(shù)，它被設(shè)置為1，000.

圖4 退火映射算法

3 實(shí)驗(yàn)結(jié)果

我們使用Java實(shí)現(xiàn)了所提出的方法，和開發(fā)多線程應(yīng)用程序，其中每個(gè)核心和一個(gè)開關(guān)都作為一個(gè)獨(dú)立的線程實(shí)現(xiàn).線程在二維網(wǎng)格中基于我們所提出的映射和布局算法相互連接.接下來我們用各種基準(zhǔn)使連通多樣性，通信質(zhì)量，寸和占用量.該標(biāo)準(zhǔn)包括GRAPH2，和graph3m設(shè)計(jì)在；H.263視頻編碼器／解碼器和MP3音頻解碼多媒體的基準(zhǔn)在，linearp13，linearp14，和linearp15，和VOPD和DSP濾波器在.圖3和圖5分別顯示了VOPD和linearp13實(shí)例的的映射結(jié)果.映射也說明了系統(tǒng)級的平面圖被我們的系統(tǒng)獲得.通過我們的算法，每個(gè)節(jié)點(diǎn)都標(biāo)注有最大，由路由器和所分配帶寬所允許的帶寬.圖6清楚地表明對于阻塞和帶寬，我們的路由方案優(yōu)于所有確定性路由方案.表II示出了由我們的算法發(fā)現(xiàn)的區(qū)域和帶寬，對于所有未遂的基準(zhǔn).此外，我們有生成一個(gè)隨機(jī)的60節(jié)點(diǎn)的核心通信圖，并產(chǎn)生隨機(jī)寬帶的隨機(jī)路由，這核心的100%參與交流.如圖7所示的結(jié)果表明，在最壞的情況下，9%的通信通道被封鎖，這非常顯著，由XY或切換XY路由算法下，與阻塞的數(shù)據(jù)包的數(shù)目相比.應(yīng)該指出的時(shí)，當(dāng)在無阻塞時(shí)，希望平均數(shù)相比其他路由算法有時(shí)甚至更好.

圖5 映射和路由路徑分配實(shí)例13每個(gè)單元格與路由器的注釋和分配帶寬

表2 測試基準(zhǔn)的面積和帶寬數(shù)據(jù)

圖6 路由比較結(jié)果

圖7 一個(gè)隨機(jī)的60節(jié)點(diǎn)的核心通信圖

4 結(jié) 論

應(yīng)用程序映射方法非常有效，它基于網(wǎng)格體系結(jié)構(gòu)和路由路徑分配同時(shí)最大限度地減少面積和帶寬.

［1］G.Ascia，V.Catania，and M.Palesi.Multi－Objective Mapping for Mesh－Based NoC Architectures.In Proc.of the ICHSC／ICSS，2004

［2］G.Ascia，V.Catania，and M.Palesi.A Multi－Objective GeneticApproach to Mapping Problem on Network－on－Chip.JUCS，22（4），2006

［3］D.Atienza，F(xiàn).Angiolini，S.Murali，A.Pullini，L.Benini，and G.DeMicheli.Network－On－Chip Design and Synthesis Outlook.Integration－The VLSI journal，41（2），2008

［4］E.Bolotin，A.Morgenshtein，I.Cidon，and A.Kolodny.Automatic andHardware－Efficient SoC Integration by QoS NOC.Proc.ICECS，2004

［5］S.Bourduas，H.Chan，and Z.Zilic.Blocking－Aware Task Assignmentfor Wormwhole Routed Network－on－Chip.In Proc.NEWCAS，2007

［6］W.J.Dally and B.Towles.Route Packets，Not Wires：On－ChipInterconnection Networks.In Proc.DAC，2001

［7］T.Dumitras and R.Marculescu.On－Chip Stochastic Communication.In Proc.DATE，2003

［8］J.Hu and R.Marculescu.Energy Aware Mapping for Tile－Based NoCArchitectures Under Performance Constraints.In Proc.ASPDAC，2003