基于改進(jìn)模擬退火的三維片上網(wǎng)絡(luò)映射算法研究

馬 悅， 宋國(guó)治， 張大坤

(天津工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與軟件學(xué)院 天津 300387)

基于改進(jìn)模擬退火的三維片上網(wǎng)絡(luò)映射算法研究

馬 悅， 宋國(guó)治， 張大坤

(天津工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與軟件學(xué)院 天津 300387)

在基于模擬退火算法的基礎(chǔ)上提出了一種改進(jìn)溫度下降函數(shù)和自適應(yīng)的生成鄰域解的新型算法.該算法通過新提出的溫度下降函數(shù)，使得在初始溫度較高的時(shí)候下降較為平滑，同時(shí)在鄰域解的生成過程中采用新的生成鄰域解的方式，充分實(shí)現(xiàn)算法的全局性，克服傳統(tǒng)模擬退火算法易陷入局部最優(yōu)解的困境; 同時(shí)在溫度較低時(shí)候，平滑的溫度下降方式也有利于進(jìn)行充分的局部搜索，取得最優(yōu)解.實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的模擬退火算法相比，提出的新型的模擬退火算法在三維片上網(wǎng)絡(luò)的映射過程中，在功耗和收斂速度兩個(gè)方面有顯著的提升.

三維片上網(wǎng)絡(luò)； 模擬退火算法； 溫度下降函數(shù)； 鄰域解

0 引言

片上網(wǎng)絡(luò)(network-on-chip, NoC)是片上系統(tǒng)(system-on-chip, SoC)的概念的延展[1-2].先是為了取代片上系統(tǒng)的總線連接方式從而合理高效地在單一芯片上連接數(shù)量龐大的處理單元(processing elements, PE)而提出的目前主流的二維片上網(wǎng)絡(luò)架構(gòu).單一芯片上的集成度越來越高，受限于節(jié)點(diǎn)之間距離增大帶來的高功耗、高延遲，三維片上網(wǎng)絡(luò)(3D NoC)又被提出以其更短的全局互連、更低的互損功耗、更好的性能、更高的封裝密度以及更小的體積等諸多優(yōu)勢(shì)成為當(dāng)前的片上網(wǎng)絡(luò)的一個(gè)重要的研究方向[3].本文提出了一種基于模擬退火算法的改進(jìn)溫度下降函數(shù)的自適應(yīng)映射算法.通過改進(jìn)的溫度下降函數(shù)和自適應(yīng)的鄰域解生成策略，來保證在溫度較高時(shí)算法的全局性搜索和溫度較低時(shí)局部性充分搜索的實(shí)現(xiàn).改進(jìn)后模擬退火算法在收斂速度和功耗上面與傳統(tǒng)的模擬退火算法相比，有了較大的性能提升.

1 3D NoC映射問題

1.1 研究現(xiàn)狀

目前使用的映射算法大致分為兩類：?jiǎn)l(fā)式映射算法；非啟發(fā)式算法.啟發(fā)式算法主要代表有：基于遺傳算法的映射算法；基于粒子群算法的映射算法；基于模擬退火算法的映射算法以及基于禁忌搜索算法的映射算法等.非啟發(fā)式算法主要包括：異構(gòu)3D NoC映射算法；常規(guī)3D NoC熱感知方法以及快速低能耗映射方法SYMMAP等[4].本文選用模擬退火算法來進(jìn)行映射，通過改變模擬退火算法的溫度下降函數(shù)和鄰域解生成策略，在較短的時(shí)間內(nèi)可以獲得較優(yōu)的映射結(jié)果.

1.2 映射問題定義

片上網(wǎng)絡(luò)映射就是在已知NoC體系結(jié)構(gòu)和IP核間通信量的基礎(chǔ)上，按某種方法將給定應(yīng)用特征圖 (application characteristic graph, ACG)上的IP核 (包括微處理器、DSP以及各種專用功能模塊等)分配到NoC拓?fù)浣Y(jié)構(gòu)圖 (topology architecture graph, TAG)中的各資源節(jié)點(diǎn)上，使得3D NoC的一個(gè)或多個(gè)性能指標(biāo)達(dá)到最優(yōu).有關(guān)片上網(wǎng)絡(luò)的映射問題是一個(gè)非多項(xiàng)式時(shí)間復(fù)雜性問題(NP-hard problem)[5-6].

為了清楚地描述映射問題，這里我們給出兩個(gè)定義：

定義1 特定任務(wù)的應(yīng)用特征圖ACG,G(V，E)為有向非循環(huán)加權(quán)圖，頂點(diǎn)vi∈V，代表著一個(gè)執(zhí)行特定任務(wù)的IP核，用整數(shù)來表示，不同數(shù)字代表不同的頂點(diǎn).有向弧ei,j∈E，表示節(jié)點(diǎn)vi與vj之間的通信關(guān)系，權(quán)重wi,j代表vi與vj的通信量.

定義2 給定的片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖TAG,T(R，P)為有向圖，頂點(diǎn)ri∈R，表示NoC中的一個(gè)資源節(jié)點(diǎn)；有向弧pi,j∈P表示從ri到rj的路徑.hi,j表示從ri到rj之間的曼哈頓距離.

由定義我們給出3D NoC的映射過程為：給定的G和T,在函數(shù)map( )的作用下找到G→T下的最優(yōu)解,使得目標(biāo)函數(shù)盡可能的優(yōu)化.映射的同時(shí)必須滿足以下的約束條件：

?vi∈V?map(vi);?vi≠vj?map(vi)≠map(vj);size(j)≤size(T).

圖1 經(jīng)典DVOPD應(yīng)用特征圖Fig.1 Classical ACG DVOPD

約束條件保證每個(gè)資源節(jié)點(diǎn)與通信任務(wù)節(jié)點(diǎn)一一對(duì)應(yīng).圖1所示就是經(jīng)典的DVOPD圖，節(jié)點(diǎn)共有32個(gè)，從1～32代表32個(gè)不同的IP核.兩個(gè)節(jié)點(diǎn)間的有向箭頭代表著之間存在通信，有向箭頭上的數(shù)字表示權(quán)重，在面向片上網(wǎng)絡(luò)的架構(gòu)上就是節(jié)點(diǎn)之間的通信流量.在DVOPD圖中，32個(gè)節(jié)點(diǎn)就對(duì)應(yīng)著32的階乘種可能性，這樣形成的解空間是非常巨大的.在本文研究的三維片上網(wǎng)絡(luò)映射問題上，我們使用智能優(yōu)化的方法來求解.在巨大的解空間中，運(yùn)用基于模擬退火的改進(jìn)算法搜索較優(yōu)解，取得較好的三維片上網(wǎng)絡(luò)的映射方案.

2 NoC評(píng)估模型

2.1 目標(biāo)函數(shù)

面向3D NoC的映射算法，我們定義一個(gè)適應(yīng)值函數(shù)Cost=MAXFit-(dxwx+dywy+dz)，其中：MAXFit是預(yù)先設(shè)置好的最大適應(yīng)值；dx、dy、dz代表的是通信節(jié)點(diǎn)在3個(gè)坐標(biāo)軸方向距離；wx、wy代表的是權(quán)重.因?yàn)槿S片上網(wǎng)絡(luò)采用了TSV技術(shù)，在z軸方向的傳輸功耗要遠(yuǎn)遠(yuǎn)小于水平方向上的功耗[7-8]，所以這里就不再乘以權(quán)重.

2.2 功耗模型

節(jié)點(diǎn)i與節(jié)點(diǎn)j之間發(fā)送一個(gè)微片(flit)的功耗Ebit,(i-j)=μERbit+μHELHbit+μVELVbit,其中：μ表示節(jié)點(diǎn)i到節(jié)點(diǎn)j經(jīng)過的路由器個(gè)數(shù);μH和μV分別是信息傳輸?shù)侥康墓?jié)點(diǎn)所經(jīng)過的水平方向和垂直方向的條數(shù)；ERbit表示一個(gè)微片通過一個(gè)路由器時(shí)消耗的能量;ELHbit和ELVbit分別表示一個(gè)微片通過一條水平方向和垂直方向的線路時(shí)消耗的能量[9].

3 改進(jìn)模擬退火算法

3.1 ISA的提出

3.1.1 改進(jìn)溫度下降函數(shù) 模擬退火算法是一種啟發(fā)式的隨機(jī)尋優(yōu)的算法，在算法中我們使用溫度下降函數(shù)來控制溫度的下降方式，對(duì)應(yīng)著SA算法中的外循環(huán)[8].具體來說就是溫度決定著SA進(jìn)行的是廣域搜索還是局域搜索.當(dāng)溫度較高的時(shí)候，當(dāng)前鄰域內(nèi)的解會(huì)以極大的可能性被接收，此時(shí)的SA算法相當(dāng)于進(jìn)行著廣域搜索；當(dāng)溫度變低的時(shí)候，基于當(dāng)前解生成的劣解被拒絕的可能性越來越大，這時(shí)候SA算法就從廣域搜索變成了局域搜索.這里我們列出兩種傳統(tǒng)的溫度下降函數(shù)：

Ti+1=Ti×r，

(1)

Ti+1=Ti-ΔT，

(2)

其中：Ti+1代表下一時(shí)刻的溫度；Ti代表當(dāng)前時(shí)刻的溫度；ΔT代表每一步溫度下降的大??；T0代表初始的溫度.為了便于理解和敘述，這里我們記基于傳統(tǒng)溫度下降函數(shù)(1)的模擬退火算法為SA-1,基于傳統(tǒng)溫度下降函數(shù)(2)的模擬退火算法SA-2.

傳統(tǒng)模擬退火算法SA-1，在溫度較高的時(shí)候，溫度下降較快，模擬退火算法的全局性沒有得到實(shí)現(xiàn)，導(dǎo)致算法極容易陷入局部最優(yōu)的困境；而SA-2算法，由于每次下降的溫度相同，在算法運(yùn)行中，溫度函數(shù)的斜率是不變的.這樣在溫度高的時(shí)候，我們要求的全局性搜索與溫度低的時(shí)候的充分的局部性搜索得不到實(shí)現(xiàn)，實(shí)驗(yàn)效果也是最差的[10-11].鑒于此我們提出了新的溫度下降函數(shù)：

Tcount=exp(-(count/DIM)2)×(T0-TN)+TN，

(3)

其中：count代表外循環(huán)次數(shù)，溫度每下降一次count自增1；DIM代表3D NoC的規(guī)模大小(節(jié)點(diǎn)數(shù)目)；TN代表終止溫度；T0代表著初始溫度.對(duì)于溫度下降方式，我們使用自然數(shù)e的冪函數(shù)來構(gòu)造了本文中新的溫度下降函數(shù)，將溫度的下一時(shí)刻的改變?cè)谂c外循環(huán)相關(guān)的基礎(chǔ)上，建立與片上網(wǎng)絡(luò)規(guī)模的關(guān)聯(lián).構(gòu)造了一個(gè)根據(jù)不同規(guī)模的片上網(wǎng)絡(luò)映射問題而改變的溫度下降函數(shù)，目的在于在算法初始階段和接近算法結(jié)束這兩個(gè)階段可以取得平滑的溫度下降方式.從而可以保證算法初始階段的全局性和終止階段局部搜索的充分性實(shí)現(xiàn).

本文取初始溫度為100 ℃，終止溫度是0.000 1 ℃.從圖2中可以看出當(dāng)溫度較高的時(shí)候，式(3)下降的速度比式(1)和(2)慢，更加有利于實(shí)現(xiàn)模擬退火算法的全局性.3個(gè)函數(shù)在接近終止溫度的時(shí)候，可以看出式(3)先收斂，式(1)其次，式(2)最后收斂.我們將在后面用仿真實(shí)驗(yàn)來證明此結(jié)論.

圖2 三種溫度下降函數(shù)的曲線Fig.2 Curves of 3 temperature functions

3.1.2 鄰域解的生成方法的改進(jìn) SA算法是基于鄰域搜索的，鄰域定義的出發(fā)點(diǎn)應(yīng)該是滿足其中的解盡可能地遍布整個(gè)解的空間，以防止算法只能實(shí)現(xiàn)局部最優(yōu).傳統(tǒng)的模擬退火算法所使用的方法雖然可以有效地生成鄰域解，但由于本身策略的局限性，新解與當(dāng)前解的曼哈頓距離(hi,j)是相對(duì)較小的[12].這不利于在算法運(yùn)行初期實(shí)現(xiàn)算法的全局性.鑒于此種情況，本文提出利用概率p來選擇鄰域解的生成方法.

改進(jìn)的鄰域生成策略：

1) 初始設(shè)p=1,當(dāng)p>rand( )時(shí)，我們采用向左循環(huán)移動(dòng)一位的方法生成新解，否則執(zhí)行2).

2) 采用傳統(tǒng)隨機(jī)確定兩個(gè)節(jié)點(diǎn)的位置，然后互換兩個(gè)節(jié)點(diǎn)從而生成新解.

3.3 ISA算法的流程

本文將提出的新的溫度下降函數(shù)(3)和自適應(yīng)的鄰域解的生成方法應(yīng)用到傳統(tǒng)的模擬退火算法中，提出ISA(improved simulated annealing algorithm)算法.ISA算法的總體流程如下：

第1步：設(shè)置一個(gè)初始控制溫度T0，TN，i=0,p=1，產(chǎn)生Xi通過目標(biāo)函數(shù)計(jì)算f(Xi).

第2步：在可行解空間中通過改進(jìn)鄰域生成算法來生成新解Xi +1, 并計(jì)算其相應(yīng)的目標(biāo)函數(shù)值f(Xi+1)，算出Δf=f(Xi)-f(Xi+1).

第3步：如果Δf<0，則把新解作為當(dāng)前解；否則，新解就按Metropolis準(zhǔn)則判斷是否接受.若p>rand(),接受，其中p=exp(-Δf/Ti)，則把Xi+1作為當(dāng)前解；否則讓Xi繼續(xù)作為當(dāng)前解.

第4步：判斷該溫度下是否已經(jīng)充分搜索，若充分搜索，執(zhí)行第5步;否則執(zhí)行第2步.

第5步：判斷Ti是否小于TN，若小于，則循環(huán)終止，跳到第6步；否則，i自動(dòng)加1，跳轉(zhuǎn)到第2步.

第6步：返回當(dāng)前解和當(dāng)前解的適應(yīng)值.

4 仿真實(shí)驗(yàn)與結(jié)果分析

4.1 不同算法的收斂速度對(duì)比

在基于Ubuntu操作系統(tǒng)下，本文使用Access Noxim仿真器針對(duì)經(jīng)典的通信軌跡圖VOPD和DVOPD進(jìn)行仿真實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果如圖3和4所示，圖中縱坐標(biāo)軸代表著適應(yīng)值，橫坐標(biāo)代表迭代次數(shù)，適應(yīng)值大小與NoC的性能成正相關(guān)，適應(yīng)值越大代表著性能越好.圖中3條折線分別代表著ISA、SA-1、SA-2 3種基于不同溫度下降函數(shù)的模擬退火算法對(duì)應(yīng)的實(shí)驗(yàn)結(jié)果.

圖3 3種溫度下降函數(shù)下VOPD收斂速度

圖4 3種溫度下降函數(shù)下DVOPD收斂速度

其中ISA算法的收斂速度最好，SA-1的收斂速度居中，可以收斂到最優(yōu)解，但收斂速度與ISA相比明顯存在差距.SA-2收斂速度最差，且不能迭代到最優(yōu)解.對(duì)DVOPD的仿真實(shí)驗(yàn)進(jìn)一步證明了ISA算法在面向通信任務(wù)規(guī)模較大時(shí)，算法的性能更是優(yōu)于基于兩種傳統(tǒng)的溫度下降函數(shù)的模擬退火算法.

4.2 功耗對(duì)比

本文用DVOPD來做有關(guān)功耗的仿真實(shí)驗(yàn)，在Code Blocks軟件上，分別采用ISA、SA-1和SA-2 3種模擬退火算法來生成通信文件.我們進(jìn)行10次實(shí)驗(yàn)，共生成10個(gè)通信文件，對(duì)每個(gè)通信文件在仿真器上進(jìn)行仿真實(shí)驗(yàn).基于3種算法的10次功耗結(jié)果如表1所示.

在實(shí)驗(yàn)中我們主要比較了總功耗、最低功耗和最高功耗.其中總功耗代表著三維片上網(wǎng)絡(luò)的整體耗能情況，直觀地反映了3種算法下的優(yōu)劣情況.最低功耗表示算法獲得最優(yōu)解的能力.這里比較最高功耗是為了驗(yàn)證在最壞情況下ISA性能依舊優(yōu)于另外兩種算法.功耗對(duì)比如圖5所示.

表1 DVOPD 3種算法的10次功耗Tab.1 Power consumption of DVOPD in three algorithms J

圖5 3種溫度函數(shù)對(duì)應(yīng)算法的功耗對(duì)比圖

如圖5中，在最高功耗、最低功耗和總功耗上，ISA所對(duì)應(yīng)的結(jié)果都要優(yōu)于其他兩種.ISA算法對(duì)比SA-1和SA-2兩種基于傳統(tǒng)溫度下降函數(shù)的模擬退火算法，總功耗分別減少了2.5%和6.89%；最低功耗分別下降了2.83%和13.83%；最高功耗分別下降了5.59%和7.21%.綜合3種結(jié)果的對(duì)比可知，提出的ISA算法在三維片上網(wǎng)絡(luò)的映射問題上可以得到更優(yōu)的映射結(jié)果.

[1] DALLY W J，TOWLES B.Route packets, not wires: on-chip interconnection networks[C]// Proceedings of the 38th Design Automation Conference. Las Vegas,2001:684-689.

[2] KUMAR S，JANTSCH A，SOININEN J P,et al. A network on chip architecture and design methodology[C]// Proc Symp VLSI. Monterey,2002:105-112.

[3] PAVLIDIS V F, FRIEDMAN E G. 3-D topologies for networks-on-chip[J].Very large scale integration systems IEEE transactions on, 2007, 15(10):1081-1090.

[4] 黃翠, 張大坤, 宋國(guó)治. 三維片上網(wǎng)絡(luò)映射算法研究綜述[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2016,37(2):193-201.

[5] SAHNI S，GONZALES T．P-complete approximation problems[J]. Journal of the association for computing machinery (ACM), 1976，23(3):555-565．

[6] 張振.基于3D-MESH的CMP片上網(wǎng)絡(luò)映射方法研究[D].廣州：廣東工業(yè)大學(xué)，2012.

[7] KIM J, PAK J S, CHO J. High-frequency scalable electrical model and analysis of a through silicon via (TSV)[J]. IEEE transactions on components packaging and manufacturing technology, 2011, 1(2): 181-195.

[8] 江鵬. TSV功耗建模與3D NoC功耗分析[D]. 西安：西安電子科技大學(xué), 2012.

[9] HU J, MARCULESCU R. Energy and performance-aware mapping for regular noc architectures[J]. IEEE Trans Comput Aided Des Integr Circuits Syst, 2010, 24(4):551-562.

[10]ZHONG L, SHENG J, JING M, et al. An optimized mapping algorithm based on simulated annealing for regular NoC architecture[C]//ASIC (ASICON), 2011 IEEE 9th International Conference on IEEE.Xiamen, 2011:389-392.

[11]RADU C, VINTAN L. Domain-knowledge optimized simulated annealing for network-on-chip application mapping[M]. Berlin: Springer Berlin Heidelberg, 2013:473-487.

[12]LEI T, KUMAR S. A two-step genetic algorithm for mapping task graphs to a network on chip architecture[C]// 2003 Euromicro Symposium on Digital System Design. Belek-Antalya，2003:180-180.

(責(zé)任編輯：王?？?

Research on Mapping for Three-dimensional Network-on-Chip Based on Improved Simulated Annealing Algorithm

MA Yue, SONG Guozhi, ZHANG Dakun

(SchoolofComputerScience&SoftwareEngineering,TianjinPolytechnicUniversity,Tianjin300387,China)

A new method to improve the declined function of temperature and the adaptive generation of neighborhood solution was proposed based on the simulated annealing algorithm (SA). The algorithm mades the decline of temperature in the higher initial temperature more smooth by the new function, and it adopted the new way of generating neighborhood solution, thus fully realized the global convergence. So it could overcome the plight of the local optimal solution. And in the condition of low temperature, it could sufficiently find the optimal solution by this function. The experimental results showed that the improved simulated annealing algorithm(ISA) significantly improved the performance of power consumption and the speed of convergence compared with the SA.

3D network-on-chip；simulated annealing algorithm；declined function of temperature；neighborhood solution

2016-11-24

國(guó)家自然科學(xué)基金項(xiàng)目(61272006)；國(guó)家大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目(201510058050).

馬悅(1993—)，男，安徽亳州人，主要從事三維片上網(wǎng)絡(luò)映射拓?fù)鋬?yōu)化研究，E-mail: 1508011127@qq.com;通信作者：宋國(guó)治(1977—)，男，黑龍江哈爾濱人，副教授，主要從事三維片上網(wǎng)絡(luò)、無線傳感器網(wǎng)絡(luò)及異構(gòu)網(wǎng)絡(luò)融合研究,Email:guozhi.song@googlemail.com．

TP305

A

1671-6841(2017)03-0009-05

10.13705/j.issn.1671-6841.2016325