臧明相， 王 婷， 周文宏

(西安電子科技大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安 710071)

片上網(wǎng)絡(luò)(Network on Chip， NoC)解決了芯片內(nèi)眾多IP核復(fù)雜的通信問題．然而，如何實(shí)現(xiàn)片上網(wǎng)絡(luò)的映射才能使功耗最小化的問題正逐漸成為片上網(wǎng)絡(luò)領(lǐng)域的研究熱點(diǎn)[1-3]．在已有的相關(guān)研究中大部分采用啟發(fā)式搜索方法[4]．文獻(xiàn)[5]采用蟻群遺傳算法來解決負(fù)載平衡和低功耗下的片上網(wǎng)絡(luò)映射問題，通過引入遺傳算法來解決蟻群算法對(duì)參數(shù)過于敏感的問題， 并引入混沌模型來解決算法停滯問題．但算法復(fù)雜，所需資源多，效率不高．文獻(xiàn)[6]采用混沌遺傳算法，克服了遺傳算法的早熟現(xiàn)象，可得到更低的通信能耗．但該算法對(duì)整個(gè)種群的所有個(gè)體都實(shí)施混沌操作，在一定程度上會(huì)破壞優(yōu)良的遺傳基因，有時(shí)尋找不到最優(yōu)解．

類電磁機(jī)制算法(Ectromagnetism-like Method，EM)是受電磁場中帶電粒子之間的吸引排斥機(jī)制啟發(fā)提出的．該算法將種群中個(gè)體看做帶電粒子，通過模擬電磁場中帶電粒子間的吸引排斥作用引導(dǎo)粒子朝最優(yōu)解方向移動(dòng)，具有尋優(yōu)機(jī)理簡單、所需資源少、收斂速度快的優(yōu)點(diǎn)．但其初始種群是通過隨機(jī)方式生成的，均勻性欠缺；局部搜索中所用的搜索因子是在算法執(zhí)行前確定的，使得需要提前確定的參數(shù)不夠精簡；而且力的計(jì)算過多依賴于粒子間的距離，導(dǎo)致其尋優(yōu)方向差，效率低[7-13]．

針對(duì)原始類電磁算法的以上缺陷，提出了一種改進(jìn)的類電磁片上網(wǎng)絡(luò)映射算法(Modified EM MAPping algorithm， MEMMAP)．使用輪盤賭的選擇機(jī)制[14]進(jìn)行種群初始化以克服初始粒子質(zhì)量不均的問題；用調(diào)整序進(jìn)行局部搜索，提高了粒子在局部范圍內(nèi)的精細(xì)搜索能力；以目標(biāo)函數(shù)為參數(shù)設(shè)計(jì)電荷計(jì)算公式求解合力，用閾值濾掉作用力甚微的粒子，提高計(jì)算合力的效率，使之搜索最優(yōu)解的效率提高．

1 片上網(wǎng)絡(luò)映射的功耗模型

基于2D Mesh結(jié)構(gòu)片上網(wǎng)絡(luò)數(shù)據(jù)傳輸時(shí)的功耗模型一般為

(1)

圖1 改進(jìn)的類電磁片上網(wǎng)絡(luò)映射算法流程圖

2 求解片上網(wǎng)絡(luò)映射問題的改進(jìn)類電磁算法

針對(duì)片上網(wǎng)絡(luò)映射問題，對(duì)原始類電磁算法中的初始化、局部搜索、電荷及電力的計(jì)算方面進(jìn)行了改進(jìn)，使之適應(yīng)于片上網(wǎng)絡(luò)映射的能耗優(yōu)化問題．改進(jìn)的類電磁片上網(wǎng)絡(luò)映射算法(MEMMAP)基本流程如圖1所示．

2.1 基于輪盤賭選擇機(jī)制的種群初始化

在進(jìn)行迭代計(jì)算之前，需對(duì)種群進(jìn)行初始化，筆者采用實(shí)數(shù)編碼策略．假設(shè)有N個(gè)IP核，分別為x1，x2，x3，…，xN，映射位置有P個(gè)，則初始化每一個(gè)粒子為對(duì)應(yīng)的一種隨機(jī)排列，每一個(gè)xi在yi中的位置p表示第i個(gè)IP核映射到第p個(gè)節(jié)點(diǎn)上．第i個(gè)粒子yi=x1，x2，…，xi(x1，x2，…，xi為1到N的一種排列)，即IP核x1映射到節(jié)點(diǎn)1上，IP核x2映射到節(jié)點(diǎn)2上，以此類推，IP核xi映射到節(jié)點(diǎn)i上．

在原始的類電磁算法中，其初始種群是通過隨機(jī)方式生成的，粒子隨機(jī)性大，全局搜索能力低．因此，筆者提出了一種基于輪盤賭選擇機(jī)制的初始化方法．

(2)

輪盤賭選擇的基本過程為：首先計(jì)算粒子yk，將Ci映射到Vj的概率看做一個(gè)個(gè)體；然后根據(jù)選擇概率的大小把一個(gè)圓盤分成大小不同的扇形，扇形大小和選擇概率成正比．

(1) 通過旋轉(zhuǎn)輪盤，得出一種對(duì)應(yīng)，即將Ci對(duì)應(yīng)到Vj上，如此循環(huán)N次，得出一個(gè)完整的映射方案，把這一方案當(dāng)做粒子yi;

(2) 循環(huán)步驟(1)，直到得出m個(gè)初始粒子{y1，y2，y3， …，ym}．

利用輪盤賭的初始化方法產(chǎn)生的粒子考慮了降低功耗的目標(biāo)，初始化得到的粒子比隨機(jī)方法產(chǎn)生的粒子更加優(yōu)越，提高了算法的搜索性能，為算法更快、更準(zhǔn)確地搜索到全局最優(yōu)解提供了條件．

2.2 局部搜索

局部搜索旨在為類電磁機(jī)制算法提供有效的局部信息，通過在一定范圍內(nèi)搜索比當(dāng)前粒子更優(yōu)的粒子，使粒子朝更精確的解移動(dòng)，進(jìn)行優(yōu)化．筆者提出一種利用調(diào)整序的思想實(shí)現(xiàn)粒子的局部搜索，以提高算法在局部區(qū)域精細(xì)搜索的能力，通過微型變換粒子，尋找當(dāng)前粒子附近的最優(yōu)解．

定義調(diào)整算子為Tk(i，j)，表示IP核由位置i調(diào)整至位置j，其過程表示為

(3)

調(diào)整序?yàn)槎鄠€(gè)調(diào)整算子的序列，記為

S=(T1，T2, …,Tk) ．

(4)

為防止算法陷入局部最優(yōu)，使用門限閾值以在保留粒子多樣性的前提下最大限度地減小退化問題．門限閾值D滿足

D=f(yl)δ,

(5)

其中，δ為門限選擇概率，yl為第l次調(diào)整后的粒子，f(yl)為第l次調(diào)整后的粒子的目標(biāo)函數(shù)值．當(dāng)且僅當(dāng)滿足

|f(yl)-f(yl-1)|≤D

(6)

時(shí)，新生成的粒子被保留．其中，|f(yl)-f(yl-1)|為新粒子和舊粒子的目標(biāo)函數(shù)之差．

2.3 電荷及電力計(jì)算

類電磁算法中電荷的大小與待優(yōu)化的目標(biāo)函數(shù)值有關(guān)．目標(biāo)函數(shù)值較優(yōu)的粒子電荷較大，反之則較?。诖丝紤]，映射粒子yi的電荷量計(jì)算為

qi=(fmax-f(yi))/(fmax-fmin) ,

(7)

其中，f(yi)表示粒子yi的目標(biāo)函數(shù)值，fmax和fmin分別表示本代中的目標(biāo)函數(shù)的最大與最小值．從式(7)可以看出，粒子的功耗越小，即目標(biāo)函數(shù)值越小，它所帶的電荷量就越大．

對(duì)于片上網(wǎng)絡(luò)的映射優(yōu)化問題，提出如下的作用力計(jì)算公式:

(8)

可以看出，對(duì)于當(dāng)前種群中的任意兩個(gè)粒子來說，目標(biāo)函數(shù)值較優(yōu)的粒子吸引目標(biāo)函數(shù)值較差的粒子；反之，目標(biāo)函數(shù)值較差的粒子會(huì)排斥另一個(gè)粒子．也就是說，兩個(gè)粒子之間作用力的方向指向其中目標(biāo)函數(shù)值較優(yōu)的粒子．因此，在對(duì)種群中的粒子求合力的過程中，適當(dāng)?shù)厝サ粢恍?duì)其作用力較小的粒子，對(duì)該粒子所受合力總是指向適應(yīng)度函數(shù)值較優(yōu)的方向這一特點(diǎn)并不會(huì)產(chǎn)生很大的影響，卻能大大地減少算法的計(jì)算量．由此，筆者提出先通過設(shè)置閾值過濾掉一部分粒子，再計(jì)算合力的方法．閾值的設(shè)置公式為

(9)

當(dāng)粒子yj與粒子yi的距離dij>λi時(shí)，粒子yj不參與到y(tǒng)i的合力求和計(jì)算中；反之，當(dāng)粒子yj與粒子yi的距離dij<λi時(shí)，粒子yj就參與求合力的計(jì)算．這一步的操作簡化了求和工作，有助于提高計(jì)算合力的效率．

2.4 粒子移動(dòng)

(10)

圖2 IP核任務(wù)特征圖APCG

3 仿真與分析

設(shè)定4×4的2D-Mesh拓?fù)浣Y(jié)構(gòu)，采用16核Video Object Plane Decoder(VOPD)的通信核圖，如圖2所示．任務(wù)特征圖包含16個(gè)子任務(wù)，分別由數(shù)字1～16表示．每個(gè)子任務(wù)之間有不同的通信流量，通信方向用箭頭表示．

仿真機(jī)的CPU為Intel(R)Core(TM)i5，主頻為 3.10 GHz、3.09 GHz，內(nèi)存為 1.82 GB．使用Matlab軟件編程完成，并在Linux環(huán)境下利用仿真軟件Nirgam 2.1仿真．路由算法采用XY路由，最小運(yùn)行周期為 1 000 個(gè)時(shí)鐘周期，預(yù)熱階段設(shè)定為5個(gè)時(shí)鐘周期．并且采用恒定比特流，片間隔為2．

圖3分別為采用遺傳算法、蟻群算法、改進(jìn)類電磁算法所得映射的功耗分布．由圖可見，遺傳算法所得的映射功耗大多集中于中間幾個(gè)節(jié)點(diǎn)，而對(duì)于四周節(jié)點(diǎn)來說，功耗較低．這不利于中間節(jié)點(diǎn)的散熱．蟻群算法的功耗分布較為均勻，但穩(wěn)定后的系統(tǒng)平均功耗較大．類電磁算法的功耗趨于平均，且最大功耗也有所減小，系統(tǒng)最終穩(wěn)定的功耗均小于遺傳算法以及蟻群算法．

圖3 3種算法所得映射的功耗分布圖

圖4 通信能耗的對(duì)比圖

圖4為3種算法所生成的映射方案．可以看出，遺傳算法容易陷入早熟收斂，效率不高，在 45 s 時(shí)才趨于穩(wěn)定．蟻群算法相比于遺傳算法略有提高，在 40 s 左右功耗趨于穩(wěn)定．而改進(jìn)的類電磁算法效率更高，在 10～ 30 s 之間，功耗迅速趨于穩(wěn)定，且最終功耗較?。z傳算法的功耗最終穩(wěn)定在 10.525 J，蟻群算法的功耗最終穩(wěn)定在 9.845 J，而改進(jìn)的類電磁算法所得到的最終穩(wěn)定功耗僅為 8.745 J，相比之下分別降低了20.35%及12.58%．

4 總 結(jié)

筆者采用改進(jìn)類電磁映射算法解決功耗均衡和低功耗的片上網(wǎng)絡(luò)映射問題．這種算法通過使用輪盤賭的選擇機(jī)制進(jìn)行種群初始化，提高了初始粒子質(zhì)量；利用調(diào)整序方法進(jìn)行局部搜索，提高了粒子在局部范圍內(nèi)的精細(xì)搜索能力；并以目標(biāo)函數(shù)為參數(shù)設(shè)計(jì)電荷計(jì)算公式，采用閾值過濾，提高了計(jì)算合力的效率．仿真結(jié)果表明，在相同的通信任務(wù)下，基于改進(jìn)的類電磁算法不僅能更高效地搜索到映射結(jié)果，并且該映射結(jié)果能耗分布均勻，平均能耗相對(duì)于遺傳算法和蟻群算法分別降低了20.35%及12.58%．

[1] 張劍賢, 楊銀堂, 周端, 等. 自適應(yīng)混沌遺傳退火的片上網(wǎng)絡(luò)映射[J]. 北京郵電大學(xué)學(xué)報(bào), 2011, 34(4): 6-9.

Zhang Jianxian, Yang Yintang, Zhou Duan, et al. NoC Mapping of Adaptive Chaos Genetic Annealing[J]. Journal of Beijing University of Posts and Telecommunications, 2011, 34(4): 6-9.

[2] 楊盛光, 李麗, 高明倫, 等. 面向能耗和延時(shí)的NoC映射方法[J]. 電子學(xué)報(bào), 2008, 36(5): 937-942.

Yang Shengguang, Li Li, Gao Minglun, et al. An Energy-and Delay-aware Mapping Method of NoC[J]. Acta Electronica Sinica, 2008, 36(5): 937-942.

[3] 宋朝輝, 馬光勝, 宋大雷. NoC處理單元隨機(jī)舍入的啟發(fā)式應(yīng)用映射[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2011, 23(7): 1263-1269.

Song Zhaohui, Ma Guangsheng, Song Dalei. Randomized Rounding Heuristic for Application Mapping to NoC Processing Elements[J]. Journal of Computer-Aided Design and Computer Graphics, 2011, 23(7): 1263-1269.

[4] 張劍賢, 周端, 楊銀堂, 等. 一種低能耗的片上網(wǎng)絡(luò)映射算法[J]. 西安電子科技大學(xué)學(xué)報(bào), 2011, 38(4): 95-100.

Zhang Jianxian, Zhou Duan, Yang Yintang, et al. Low Energy Consumption Mapping Algorithm for the Network-on-chip[J]. Journal of Xidian University, 2011, 38(4): 95-100.

[5] 易偉, 王佳文, 潘紅兵, 等. 基于蟻群混沌遺傳算法的片上網(wǎng)絡(luò)映射[J]. 電子學(xué)報(bào), 2011, 39(8): 1832-1836.

Yi Wei, Wang Jiawen, Pan Hongbing, et al. Ant Colony Chaos Genetic Algorithm for Mapping Task Graphs to a Network on Chip[J]. Acta Electronica Sinica, 2011, 39(8): 1832-1836.

[6] Moein-Darbari F, Khademzade A, Gharooni-Fard G. CGMAP: a New Approach to Network-on-Chip Mapping Problem [J]. IEICE Electronics Express, 2009, 6(1): 27-34.

[7] Birbill S, Fang Shucherng. An Electromagnetism-like Mechanism for Global Optimization[J]. Journal of Global Optimization, 2003, 25(3): 263-282.

[8] 姜建國, 龍秀萍, 田旻, 等. 一種基于佳點(diǎn)集的類電磁機(jī)制算法[J]. 西安電子科技大學(xué)學(xué)報(bào), 2011, 38(6): 167-172.

Jiang Jianguo, Long Xiuping, Tian Min, et al. Electromagnetism-like Mechanism Algorithm based on the Good Point Set[J]. Journal of Xidian University, 2011, 38(6): 167-172.

[9] Kaelo P, Ali M M. Differential Evolution Algorithms Using Hybrid Mutation[J]. Computation Optimum Application, 2007, 37(2): 231-246.

[10] 王曉娟, 高亮, 陳亞洲. 類電磁機(jī)制算法及其應(yīng)用[J]. 計(jì)算機(jī)應(yīng)用研究, 2006, 26(3): 67-70.

Wang Xiaojuan, Gao Liang, Chen Yazhou. Electromagnetism-like Mechanism with Its Application[J]. Journal of Computer Applications, 2006, 26(3): 67-70.

[11] 韓麗霞, 王宇平. 求解無約束優(yōu)化問題的類電磁機(jī)制算法[J]. 電子學(xué)報(bào), 2009, 37(3): 664-668.

Han Lixia, Wang Yuping. Electromagnetism-like Mechanism Algorithm for Unconstrained Optimization Problem[J]. Acta Electronica Sinica, 2009, 37(3): 664-668.

[12] 楊曉凌, 邱滌珊, 彭黎, 等. 改進(jìn)類電磁算法在武器目標(biāo)分配問題中的應(yīng)用[J]. 國防科技大學(xué)學(xué)報(bào), 2011, 33(6): 150-153.

Yang Xiaoling, Qiu Dishan, Peng Li, et al. Application of Modified Electromagnetism-like Algorithm in Weapon-target Assignment Problem[J]. Journal of National University of Defense Technology, 2011, 33(6): 150-153.

[13] 姜建國, 王雙記, 劉永青, 等. 一種實(shí)用的類電磁機(jī)制算法[J]. 西安電子科技大學(xué)學(xué)報(bào), 2013, 40(2): 48-53.

Jiang Jianguo, Wang Shuangji, Liu Yongqing, et al. Practical Electromagnetism-like Mechanism Algorithm[J]. Journal of Xidian University, 2013, 40(2): 48-53.

[14] 王芳, 邱玉輝. 一種引入輪盤賭選擇算子的混合粒子群算法[J]. 西南師范大學(xué)學(xué)報(bào), 2006, 31(3): 93-96.

Wang Fang, Qiu Yuhui. A Hybrid Particle Swarm Algorithm with Roulette Selection Operator[J]. Journal of Southwest China Normal University, 2006, 31(3): 93-96.