低功耗片上網絡映射算法研究

楊微

（廣州大學華軟軟件學院軟件工程系，廣州 510990）

低功耗片上網絡映射算法研究

楊微

（廣州大學華軟軟件學院軟件工程系，廣州 510990）

提出改進的片上網絡蟻群映射算法，并為驗證該映射算法對低功耗片上網絡性能的提升，結合具體應用進行仿真實驗。比較該改進蟻群算法與一般蟻群算法、粒子群算法的映射結果的優劣。仿真實驗選取5組實驗結果進行性能對比分析。實驗結果顯示改進的蟻群算法能夠在收斂速度、停滯現象等方面都有取得較好的性能，獲得的映射解在功耗函數下可以取得更低的功耗。

片上網絡；低功耗；片上網絡映射；粒子群算法；蟻群算法

0 引言

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

本文是在算法應用的層面對低功耗片上網絡進行研究，基于改進蟻群算法的片上網絡低功耗映射方案研究，在分析片上網絡功耗的基礎上，對蟻群算法進行了改進，提出基于改進蟻群算法的片上網絡低功耗映射算法。

1 改進低功耗片上網映射算法研究

1.1 低功耗片上網絡映射問題建模

片上網絡的映射，有定義：

本文研究的重點是低功耗片上網絡映射，因此這里的目標函數設定為功耗的約束。在這里我們研究中以文獻[4]提出的基于單個路由節點功耗模型為目標函數。依據文獻[4]，NoC片上網絡映射在功耗模型下的目標函數如公式（1）所示：

即低功耗片上網絡映射模型為：

在上面片上網絡的映射模型中，對于有N個任務的應用輸入，對應有N!種排列方式，構成映射模型的解空間，顯然片上網絡映射問題屬于組合優化即二次分配問題（QAP）的范疇。二次分配屬于NP難問題，所謂NP難，就是對于一個問題除了窮舉該問題所有解域內的解以外，找不到一種多項式的解決方法。利用群體智能算法在合理的時間里得到NP問題較滿意的解，即以“解的精確性”換取“時間的合理性”一直以來成為學術界研究的重點。論文中引入蟻群算法作為NoC映射的基本算法，并在此基礎上對算法進行了改進。

1.2 改進低功耗片上網絡映射算法設計

（1）問題描述及改進

蟻群算法是模擬自然界中螞蟻尋找食物的過程來解決問題。在自然界中，螞蟻覓食過程中，蟻群總能夠尋找到一條從蟻巢和食物源的最優路徑。論文中結合低功耗片上網絡的特點，對基本蟻群算法的改進如下：

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

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

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

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

改進蟻群算法在功耗函數的限制下求解NoC映射問題的過程為：

①初始化設置：螞蟻數M=2n/3、控制參數（α，β，ρ= 0.6，Q）、算法迭代的次數NC、最優解Antmin為無窮大、信息素矩陣所有元素初始化為0、OpenK為空、ClosedK表中加入所有的拓撲結構節點（n個）、M只螞蟻的位置并在OpenK中加入起始節點，ClosedK中去掉該起始節點。

③蟻群得到的解集為候選集，更新目標函數（公式1）的值得到候選集內最優個體為Ant局部最優，算法當前最優解Ant最優，更新Ant最優，按照概率決定是否把候選解集中的解加入到更新集中。

④更新信息素矩陣，以更新集中的解來更新信息素矩陣。

⑤檢查終止條件：是否有螞蟻沒有完成一次循環？是，轉到步驟②繼續執行；是否達到算法最大迭代的次數NC？否，轉到步驟②；轉到步驟⑤輸出最優值Ant全局最優。

⑥輸出最優值Ant全局最優。

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

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

2 仿真測試及結果分析

2.1 仿真測試實例以及實驗環境介紹

（1）硬件平臺：AMD Athlon P360 Dual-Core CPU @2.3.0GHz 2.00GB內存；

（2）軟件平臺：操作系統Windows 7旗艦版；映射算法的開發語言為C++語言；實驗仿真環境是在Dev-C++5.4.1環境下進行。在實驗中選擇2D-Mesh結構作為映射拓撲結構。

仿真實驗中選擇MPEG4譯碼器作為測試實例來驗證本文提出的低功耗片上網絡映射算法的性能。MPEG4任務流圖如圖2所示。

圖2 MPEG-4譯碼器任務流程圖

各個參數的選擇如表1所示，在仿真實驗中最大迭代次數NC設置為300。

表1 改進蟻群算法的實驗參數表

2.2 實驗結果及其結果分析

仿真實驗對改進的蟻群算法、一般蟻群算法以及粒子群算法（分別獨立執行50次，并從中選擇5次進行對比）在收斂速度、功耗等方面的性能。

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

表2 改進蟻群算法和一般蟻群算法性能對比

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

表3 改進蟻群算法和粒子群算法功耗對比

仿真實驗還比較這三類算法的收斂趨勢，其收斂趨勢對比如圖3所示。

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

圖3 算法的收斂趨勢圖

3 結語

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

[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] 楊微,張振,劉怡俊.基于改進粒子群的3D-Mesh CMP片上網絡映射算法[J].計算機應用研究,2013,30(5):1345～1348

[5] 李麗,許居衍.片上網絡技術發展現狀及趨勢淺析[J].電子產品世界,2009,16(1):32～37

[6] 沈劍良,嚴明,李思昆,等.NoC低功耗技術研究綜述[J].計算機工程與科學,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] 駱祖瑩.芯片功耗與工藝參數變化:下一代集成電路設計的兩大挑戰[J].計算機學報,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－），女，江西撫州人，碩士，研究方向為計算機體系結構、NoC基礎

2014-12-09

2014-12-30

國家自然科學基金項目（No.61106019）、廣東省“省部產學研結合項目”（No.2011B090400408、No.2011A090200022）