類(lèi)電磁優(yōu)化的片上網(wǎng)絡(luò)低功耗映射算法

臧明相， 王 婷， 周文宏

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

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

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

針對(duì)原始類(lèi)電磁算法的以上缺陷，提出了一種改進(jìn)的類(lèi)電磁片上網(wǎng)絡(luò)映射算法(Modified EM MAPping algorithm， MEMMAP)．使用輪盤(pán)賭的選擇機(jī)制[14]進(jìn)行種群初始化以克服初始粒子質(zhì)量不均的問(wèn)題；用調(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)的類(lèi)電磁片上網(wǎng)絡(luò)映射算法流程圖

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

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

2.1 基于輪盤(pán)賭選擇機(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上，以此類(lèi)推，IP核xi映射到節(jié)點(diǎn)i上．

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

(2)

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

(1) 通過(guò)旋轉(zhuǎn)輪盤(pá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}．

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

2.2 局部搜索

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

定義調(diào)整算子為T(mén)k(i，j)，表示IP核由位置i調(diào)整至位置j，其過(guò)程表示為

(3)

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

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

(4)

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

D=f(yl)δ,

(5)

其中，δ為門(mén)限選擇概率，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ì)算

類(lèi)電磁算法中電荷的大小與待優(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)化問(wèn)題，提出如下的作用力計(jì)算公式:

(8)

可以看出，對(duì)于當(dāng)前種群中的任意兩個(gè)粒子來(lái)說(shuō)，目標(biāo)函數(shù)值較優(yōu)的粒子吸引目標(biāo)函數(shù)值較差的粒子；反之，目標(biāo)函數(shù)值較差的粒子會(huì)排斥另一個(gè)粒子．也就是說(shuō)，兩個(gè)粒子之間作用力的方向指向其中目標(biāo)函數(shù)值較優(yōu)的粒子．因此，在對(duì)種群中的粒子求合力的過(guò)程中，適當(dāng)?shù)厝サ粢恍?duì)其作用力較小的粒子，對(duì)該粒子所受合力總是指向適應(yīng)度函數(shù)值較優(yōu)的方向這一特點(diǎn)并不會(huì)產(chǎn)生很大的影響，卻能大大地減少算法的計(jì)算量．由此，筆者提出先通過(guò)設(shè)置閾值過(guò)濾掉一部分粒子，再計(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ì)算．這一步的操作簡(jiǎn)化了求和工作，有助于提高計(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)類(lèi)電磁算法所得映射的功耗分布．由圖可見(jiàn)，遺傳算法所得的映射功耗大多集中于中間幾個(gè)節(jié)點(diǎn)，而對(duì)于四周節(jié)點(diǎn)來(lái)說(shuō)，功耗較低．這不利于中間節(jié)點(diǎn)的散熱．蟻群算法的功耗分布較為均勻，但穩(wěn)定后的系統(tǒng)平均功耗較大．類(lèi)電磁算法的功耗趨于平均，且最大功耗也有所減小，系統(tǒng)最終穩(wěn)定的功耗均小于遺傳算法以及蟻群算法．

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

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

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

4 總 結(jié)

筆者采用改進(jìn)類(lèi)電磁映射算法解決功耗均衡和低功耗的片上網(wǎng)絡(luò)映射問(wèn)題．這種算法通過(guò)使用輪盤(pán)賭的選擇機(jī)制進(jìn)行種群初始化，提高了初始粒子質(zhì)量；利用調(diào)整序方法進(jìn)行局部搜索，提高了粒子在局部范圍內(nèi)的精細(xì)搜索能力；并以目標(biāo)函數(shù)為參數(shù)設(shè)計(jì)電荷計(jì)算公式，采用閾值過(guò)濾，提高了計(jì)算合力的效率．仿真結(jié)果表明，在相同的通信任務(wù)下，基于改進(jìn)的類(lèi)電磁算法不僅能更高效地搜索到映射結(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] 姜建國(guó), 龍秀萍, 田旻, 等. 一種基于佳點(diǎn)集的類(lèi)電磁機(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] 王曉娟, 高亮, 陳亞洲. 類(lèi)電磁機(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] 韓麗霞, 王宇平. 求解無(wú)約束優(yōu)化問(wèn)題的類(lèi)電磁機(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)類(lèi)電磁算法在武器目標(biāo)分配問(wèn)題中的應(yīng)用[J]. 國(guó)防科技大學(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] 姜建國(guó), 王雙記, 劉永青, 等. 一種實(shí)用的類(lèi)電磁機(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] 王芳, 邱玉輝. 一種引入輪盤(pán)賭選擇算子的混合粒子群算法[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.