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

臧明相， 王 婷， 周文宏

(西安電子科技大學 計算機學院，陜西 西安 710071)

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

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

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

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

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

(1)

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

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

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

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

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

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

(2)

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

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

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

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

2.2 局部搜索

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

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

(3)

調(diào)整序為多個調(diào)整算子的序列，記為

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

(4)

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

D=f(yl)δ,

(5)

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

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

(6)

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

2.3 電荷及電力計算

類電磁算法中電荷的大小與待優(yōu)化的目標函數(shù)值有關．目標函數(shù)值較優(yōu)的粒子電荷較大，反之則較小．基于此考慮，映射粒子yi的電荷量計算為

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

(7)

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

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

(8)

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

(9)

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

2.4 粒子移動

(10)

圖2 IP核任務特征圖APCG

3 仿真與分析

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

仿真機的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路由，最小運行周期為 1 000 個時鐘周期，預熱階段設定為5個時鐘周期．并且采用恒定比特流，片間隔為2．

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

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

圖4 通信能耗的對比圖

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

4 總 結(jié)

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

[1] 張劍賢, 楊銀堂, 周端, 等. 自適應混沌遺傳退火的片上網(wǎng)絡映射[J]. 北京郵電大學學報, 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] 楊盛光, 李麗, 高明倫, 等. 面向能耗和延時的NoC映射方法[J]. 電子學報, 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處理單元隨機舍入的啟發(fā)式應用映射[J]. 計算機輔助設計與圖形學學報, 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)絡映射算法[J]. 西安電子科技大學學報, 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)絡映射[J]. 電子學報, 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] 姜建國, 龍秀萍, 田旻, 等. 一種基于佳點集的類電磁機制算法[J]. 西安電子科技大學學報, 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]. 計算機應用研究, 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]. 電子學報, 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]. 國防科技大學學報, 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] 姜建國, 王雙記, 劉永青, 等. 一種實用的類電磁機制算法[J]. 西安電子科技大學學報, 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]. 西南師范大學學報, 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.