楊微

（廣州大學(xué)華軟軟件學(xué)院軟件工程系，廣州 510990）

低功耗片上網(wǎng)絡(luò)映射算法研究

楊微

（廣州大學(xué)華軟軟件學(xué)院軟件工程系，廣州 510990）

提出改進(jìn)的片上網(wǎng)絡(luò)蟻群映射算法，并為驗(yàn)證該映射算法對(duì)低功耗片上網(wǎng)絡(luò)性能的提升，結(jié)合具體應(yīng)用進(jìn)行仿真實(shí)驗(yàn)。比較該改進(jìn)蟻群算法與一般蟻群算法、粒子群算法的映射結(jié)果的優(yōu)劣。仿真實(shí)驗(yàn)選取5組實(shí)驗(yàn)結(jié)果進(jìn)行性能對(duì)比分析。實(shí)驗(yàn)結(jié)果顯示改進(jìn)的蟻群算法能夠在收斂速度、停滯現(xiàn)象等方面都有取得較好的性能，獲得的映射解在功耗函數(shù)下可以取得更低的功耗。

片上網(wǎng)絡(luò)；低功耗；片上網(wǎng)絡(luò)映射；粒子群算法；蟻群算法

0 引言

功耗問(wèn)題作為阻礙集成電路不斷發(fā)展的主要問(wèn)題，對(duì)未來(lái)集成電路（IC）設(shè)計(jì)帶來(lái)多方面挑戰(zhàn)，例如對(duì)芯片的封裝和散熱方面的設(shè)計(jì)的挑戰(zhàn)，對(duì)芯片的性能以及穩(wěn)定性方面的挑戰(zhàn)等，因此功耗問(wèn)題也越來(lái)越受到工業(yè)界和學(xué)術(shù)界的關(guān)注。而NoC（Network-on-Chip）作為未來(lái)大規(guī)模并行處理器的首選架構(gòu)，是未來(lái)芯片設(shè)計(jì)的發(fā)展方向，它不僅被廣泛應(yīng)用于高性能服務(wù)器等大規(guī)模計(jì)算系統(tǒng)，也被移動(dòng)和無(wú)線(xiàn)通信終端等嵌入式高性能SoC設(shè)計(jì)所采用，因此對(duì)NoC功耗進(jìn)行低功耗設(shè)計(jì)意義重大。目前國(guó)內(nèi)外很多研究機(jī)構(gòu)和學(xué)者都從不同方面對(duì)NoC的功耗問(wèn)題進(jìn)行了研究，并提出了改進(jìn)優(yōu)化NoC的方案。例如在物理硬件方面，文獻(xiàn)[1]在NoC中采用低擺幅信號(hào)，并通過(guò)實(shí)驗(yàn)證明低擺幅信號(hào)不僅在功耗方面有優(yōu)化作用；在軟件應(yīng)用方面，文獻(xiàn)[2]對(duì)硬件實(shí)現(xiàn)開(kāi)關(guān)鏈路進(jìn)行了研究，他們通過(guò)設(shè)置硬件計(jì)數(shù)器獲取網(wǎng)絡(luò)運(yùn)行時(shí)的鏈路的實(shí)時(shí)狀態(tài)，并以此為依據(jù)選擇關(guān)閉或者開(kāi)啟鏈路。這種方法可以有效降低靜態(tài)功耗，但是相比于硬件實(shí)現(xiàn)，軟件編譯指導(dǎo)可以獲得更好的性能；在拓?fù)浣Y(jié)構(gòu)上，文獻(xiàn)[3]中基于對(duì)應(yīng)用的通信量分析所得的數(shù)據(jù)的基礎(chǔ)上，對(duì)規(guī)則拓?fù)浣Y(jié)構(gòu)進(jìn)行裁剪的技術(shù)，即把不用的多余的I/O、路由單元進(jìn)行裁剪，給通信量比較頻繁、路由單元更多的資源，實(shí)驗(yàn)數(shù)據(jù)表明這種技術(shù)可以有效減少面積消耗以及NoC能耗等。

本文是在算法應(yīng)用的層面對(duì)低功耗片上網(wǎng)絡(luò)進(jìn)行研究，基于改進(jìn)蟻群算法的片上網(wǎng)絡(luò)低功耗映射方案研究，在分析片上網(wǎng)絡(luò)功耗的基礎(chǔ)上，對(duì)蟻群算法進(jìn)行了改進(jìn)，提出基于改進(jìn)蟻群算法的片上網(wǎng)絡(luò)低功耗映射算法。

1 改進(jìn)低功耗片上網(wǎng)映射算法研究

1.1 低功耗片上網(wǎng)絡(luò)映射問(wèn)題建模

片上網(wǎng)絡(luò)的映射，有定義：

本文研究的重點(diǎn)是低功耗片上網(wǎng)絡(luò)映射，因此這里的目標(biāo)函數(shù)設(shè)定為功耗的約束。在這里我們研究中以文獻(xiàn)[4]提出的基于單個(gè)路由節(jié)點(diǎn)功耗模型為目標(biāo)函數(shù)。依據(jù)文獻(xiàn)[4]，NoC片上網(wǎng)絡(luò)映射在功耗模型下的目標(biāo)函數(shù)如公式（1）所示：

即低功耗片上網(wǎng)絡(luò)映射模型為：

在上面片上網(wǎng)絡(luò)的映射模型中，對(duì)于有N個(gè)任務(wù)的應(yīng)用輸入，對(duì)應(yīng)有N!種排列方式，構(gòu)成映射模型的解空間，顯然片上網(wǎng)絡(luò)映射問(wèn)題屬于組合優(yōu)化即二次分配問(wèn)題（QAP）的范疇。二次分配屬于NP難問(wèn)題，所謂NP難，就是對(duì)于一個(gè)問(wèn)題除了窮舉該問(wèn)題所有解域內(nèi)的解以外，找不到一種多項(xiàng)式的解決方法。利用群體智能算法在合理的時(shí)間里得到NP問(wèn)題較滿(mǎn)意的解，即以“解的精確性”換取“時(shí)間的合理性”一直以來(lái)成為學(xué)術(shù)界研究的重點(diǎn)。論文中引入蟻群算法作為NoC映射的基本算法，并在此基礎(chǔ)上對(duì)算法進(jìn)行了改進(jìn)。

1.2 改進(jìn)低功耗片上網(wǎng)絡(luò)映射算法設(shè)計(jì)

（1）問(wèn)題描述及改進(jìn)

蟻群算法是模擬自然界中螞蟻尋找食物的過(guò)程來(lái)解決問(wèn)題。在自然界中，螞蟻覓食過(guò)程中，蟻群總能夠?qū)ふ业揭粭l從蟻巢和食物源的最優(yōu)路徑。論文中結(jié)合低功耗片上網(wǎng)絡(luò)的特點(diǎn)，對(duì)基本蟻群算法的改進(jìn)如下：

①一般的蟻群算法是在每次迭代后依次更新信息素矩陣，改進(jìn)蟻群算法設(shè)立了更新集用來(lái)更新信息素矩陣。從每次迭代后解中以一定的概率擇優(yōu)選擇加入到更新集中，這有助于加快算法的收斂速度。

②改進(jìn)蟻群算法更新集的更新方案：當(dāng)蟻群內(nèi)所有的螞蟻完成一輪搜索后取得解集稱(chēng)為候選集，記為C={Antk(ck-ek)|1≤k≤M}，ck為螞蟻完成搜索后得到的一個(gè)解，ek為功耗函數(shù)的值。按照一定的方案從候選集中選取解加入到更新集中，信息素矩陣的更新依據(jù)更新集中的元素進(jìn)行，更新集記為CR={Antk(ck-ek)|1≤k≤M}。令比較參數(shù)к=0.5（參數(shù)值的選擇考慮到概率事件的平等性）。構(gòu)造更新解的代碼為：

③一般蟻群算法為每只螞蟻選擇下一個(gè)節(jié)點(diǎn)的方法是：以某種概率搜索節(jié)點(diǎn)，每搜到一個(gè)，就將該節(jié)點(diǎn)加入到OpenK中，并且從ClosedK中刪除該節(jié)點(diǎn)。該過(guò)程重復(fù)n-1次，直到所有的節(jié)點(diǎn)都遍歷過(guò)一次。改進(jìn)蟻群算法螞蟻下一個(gè)訪(fǎng)問(wèn)節(jié)點(diǎn)的確立方案：為了避免算法在尋優(yōu)過(guò)程中陷入局部搜索，保證螞蟻的全局搜索空間，以一部分概率使螞蟻在選擇下一個(gè)位置結(jié)點(diǎn)時(shí)放棄對(duì)當(dāng)前高期望解的追逐而轉(zhuǎn)向其他低期望的位置結(jié)點(diǎn)。這可以提高算法的全局搜索能力，避免陷入局部最優(yōu)解。

（2）基于改進(jìn)蟻群算法的低功耗NoC映射算法步驟

改進(jìn)蟻群算法在功耗函數(shù)的限制下求解NoC映射問(wèn)題的過(guò)程為：

①初始化設(shè)置：螞蟻數(shù)M=2n/3、控制參數(shù)（α，β，ρ= 0.6，Q）、算法迭代的次數(shù)NC、最優(yōu)解Antmin為無(wú)窮大、信息素矩陣所有元素初始化為0、OpenK為空、ClosedK表中加入所有的拓?fù)浣Y(jié)構(gòu)節(jié)點(diǎn)（n個(gè)）、M只螞蟻的位置并在OpenK中加入起始節(jié)點(diǎn)，ClosedK中去掉該起始節(jié)點(diǎn)。

③蟻群得到的解集為候選集，更新目標(biāo)函數(shù)（公式1）的值得到候選集內(nèi)最優(yōu)個(gè)體為Ant局部最優(yōu)，算法當(dāng)前最優(yōu)解Ant最優(yōu)，更新Ant最優(yōu)，按照概率決定是否把候選解集中的解加入到更新集中。

④更新信息素矩陣，以更新集中的解來(lái)更新信息素矩陣。

⑤檢查終止條件：是否有螞蟻沒(méi)有完成一次循環(huán)？是，轉(zhuǎn)到步驟②繼續(xù)執(zhí)行；是否達(dá)到算法最大迭代的次數(shù)NC？否，轉(zhuǎn)到步驟②；轉(zhuǎn)到步驟⑤輸出最優(yōu)值A(chǔ)nt全局最優(yōu)。

⑥輸出最優(yōu)值A(chǔ)nt全局最優(yōu)。

基于改進(jìn)蟻群算法的低功耗NoC映射算法流程如圖1：

圖1 低功耗NoC映射算法流程圖

2 仿真測(cè)試及結(jié)果分析

2.1 仿真測(cè)試實(shí)例以及實(shí)驗(yàn)環(huán)境介紹

（1）硬件平臺(tái)：AMD Athlon P360 Dual-Core CPU @2.3.0GHz 2.00GB內(nèi)存；

（2）軟件平臺(tái)：操作系統(tǒng)Windows 7旗艦版；映射算法的開(kāi)發(fā)語(yǔ)言為C++語(yǔ)言；實(shí)驗(yàn)仿真環(huán)境是在Dev-C++5.4.1環(huán)境下進(jìn)行。在實(shí)驗(yàn)中選擇2D-Mesh結(jié)構(gòu)作為映射拓?fù)浣Y(jié)構(gòu)。

仿真實(shí)驗(yàn)中選擇MPEG4譯碼器作為測(cè)試實(shí)例來(lái)驗(yàn)證本文提出的低功耗片上網(wǎng)絡(luò)映射算法的性能。MPEG4任務(wù)流圖如圖2所示。

圖2 MPEG-4譯碼器任務(wù)流程圖

各個(gè)參數(shù)的選擇如表1所示，在仿真實(shí)驗(yàn)中最大迭代次數(shù)NC設(shè)置為300。

表1 改進(jìn)蟻群算法的實(shí)驗(yàn)參數(shù)表

2.2 實(shí)驗(yàn)結(jié)果及其結(jié)果分析

仿真實(shí)驗(yàn)對(duì)改進(jìn)的蟻群算法、一般蟻群算法以及粒子群算法（分別獨(dú)立執(zhí)行50次，并從中選擇5次進(jìn)行對(duì)比）在收斂速度、功耗等方面的性能。

如表2，通過(guò)比較以上五組實(shí)驗(yàn)仿真數(shù)據(jù)數(shù)據(jù)，可以看到改進(jìn)的蟻群算法所得的解功耗函數(shù)在309.84 (mW)左右浮動(dòng)，粒子群算法獲得的解功耗函數(shù)值在522.74(mW)左右浮動(dòng)，相對(duì)比粒子群算法，在功耗方面改進(jìn)蟻群算法優(yōu)化比例的平均值為59%，證明了改進(jìn)的蟻群算法具有更好的低功耗性。

表2 改進(jìn)蟻群算法和一般蟻群算法性能對(duì)比

如表3，通過(guò)比較以上五組仿真實(shí)驗(yàn)數(shù)據(jù)，,可以看到基本蟻群算法獲得的解在446.68（mW）左右浮動(dòng)，這說(shuō)明一般蟻群算法相比于粒子群算法能夠獲得更好的解，同時(shí)在功耗方面改進(jìn)蟻群算法的算法優(yōu)化比例的平均值為69%，證明具有比基本蟻群算法更好的低功耗性。

表3 改進(jìn)蟻群算法和粒子群算法功耗對(duì)比

仿真實(shí)驗(yàn)還比較這三類(lèi)算法的收斂趨勢(shì)，其收斂趨勢(shì)對(duì)比如圖3所示。

從算法的收斂趨勢(shì)圖上可以看到改進(jìn)蟻群算法相對(duì)比于基本蟻群算法以及粒子群算法，具有更好的收斂性，可以用更少的時(shí)間獲得全局最優(yōu)解。其中，改進(jìn)的蟻群算法相對(duì)比于基本蟻群算法，算法的停滯現(xiàn)象得到了改善，算法的收斂速度更快，并能獲得更優(yōu)的功耗函數(shù)值。

圖3 算法的收斂趨勢(shì)圖

3 結(jié)語(yǔ)

近年來(lái)，一方面，節(jié)能意識(shí)的增強(qiáng)推動(dòng)低功耗片上網(wǎng)絡(luò)設(shè)計(jì)技術(shù)的發(fā)展，另一方面，由于能耗上升導(dǎo)致的芯片溫度上升，進(jìn)而對(duì)芯片性能和穩(wěn)定性的影響也推進(jìn)了工業(yè)界和學(xué)術(shù)界對(duì)低功耗片上網(wǎng)絡(luò)研究。而更巧妙的片上網(wǎng)絡(luò)架構(gòu)設(shè)計(jì)、更多地集成處理核心、更低的片上網(wǎng)絡(luò)功耗、更優(yōu)的性能等都是未來(lái)片上網(wǎng)絡(luò)技術(shù)發(fā)展的主要方向[5]。論文從片上網(wǎng)絡(luò)映射問(wèn)題分析以及片上網(wǎng)絡(luò)低功耗建模入手，提出改進(jìn)的蟻群算法；通過(guò)仿真實(shí)驗(yàn)證明改進(jìn)的低功耗算法獲得的映射解具有更好的低功耗性，接下的工作是從更多的層面去研究片上網(wǎng)絡(luò)（NoC）的功耗問(wèn)題并進(jìn)行低功耗設(shè)計(jì)，提出更加準(zhǔn)確完善的功耗函數(shù)作為性能評(píng)估依據(jù)，綜合功耗、延時(shí)、吞吐量等多性能指標(biāo)去提升片上網(wǎng)絡(luò)的性能，并平衡片上網(wǎng)絡(luò)的功耗問(wèn)題。

[1] Lee K,Lee S J,Yoo H J.Low-Power Network-on-Chip for High-Performance SoC Design[J].Very Large Scale Integration(VLSI)Systems,IEEE Transactions on,2006,14(2):148～160

[2] L.Benini,G.D.Micheli.Networks on Chips:A New SOC Paradigm[J].IEEE Computer，35,1(Jan.),2002：70～78

[3] Jalabert A,Murali S,Benini L,et al.×PipesCompiler:A Tool for Instantiating Application Specific Networks on Chip[C].Design,Automation and Test in Europe Conference and Exhibition,2004.Proceedings.IEEE,2004,2:884～889

[4] 楊微,張振,劉怡俊.基于改進(jìn)粒子群的3D-Mesh CMP片上網(wǎng)絡(luò)映射算法[J].計(jì)算機(jī)應(yīng)用研究,2013,30(5):1345～1348

[5] 李麗,許居衍.片上網(wǎng)絡(luò)技術(shù)發(fā)展現(xiàn)狀及趨勢(shì)淺析[J].電子產(chǎn)品世界,2009,16(1):32～37

[6] 沈劍良,嚴(yán)明,李思昆,等.NoC低功耗技術(shù)研究綜述[J].計(jì)算機(jī)工程與科學(xué),2009,31(A01):88～92[7] Networks-on-Chips:Theory and Practice[M].CRC Press,2011

[8] Lee K,Lee S J,Yoo H J.SILENT:Serialized Low Energy Transmission Coding for On-Chip Interconnection Networks[C].Proceedings of the 2004 IEEE/ACM International Conference on Computer-Aided Design.IEEE Computer Society,2004:448～451

[9] 駱祖瑩.芯片功耗與工藝參數(shù)變化:下一代集成電路設(shè)計(jì)的兩大挑戰(zhàn)[J].計(jì)算機(jī)學(xué)報(bào),2007,30(7):1054～1063

Research on the Low-Power Mapping Algorithm of NoC

YANG Wei
（School of Software Engineer，South China Institute of Software Engineering，GZU，Guangzhou 510990）

Presents the improved ant colony algorithm for network on chip,and to verify the mapping algorithm on network performance and low power on chip,combined with the practical application of the simulation experiment.Compares the mapping results of the improved ant colony algorithm and general ant colony algorithm and PSO's.Analyzes the comparative performance of 5 groups selected simulation results which show that the improved ant colony algorithm has achieved better performance in convergence speed,stagnation,etc,and mapping solution obtained in power function can be achieved at lower power consumption.

Network-on-Chip;Low Power Consumption;Mapping of NoC;Particle Swarm Optimization;Ant Colony Algorithm

1007-1423（2015）03-0010-05

10.3969/j.issn.1007-1423.2015.03.003

楊微（1987－），女，江西撫州人，碩士，研究方向?yàn)橛?jì)算機(jī)體系結(jié)構(gòu)、NoC基礎(chǔ)

2014-12-09

2014-12-30

國(guó)家自然科學(xué)基金項(xiàng)目（No.61106019）、廣東省“省部產(chǎn)學(xué)研結(jié)合項(xiàng)目”（No.2011B090400408、No.2011A090200022）