高效映射和可靠的最低的寬帶和地區(qū)的網(wǎng)絡框架的方法

洪 斌 張紅嶺 于 夢

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

0 引 言

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

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

1 映射和NOC路由配置

1.1 模擬退火映射

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

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

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

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

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

1.2 路由

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

圖2 路由算法

表1 下一個躍點選擇基于當前和下一個路由器的位置

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

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

2 算 法

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

圖4 退火映射算法

3 實驗結果

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

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

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

圖6 路由比較結果

圖7 一個隨機的60節(jié)點的核心通信圖

4 結 論

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

［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