馬 悅， 宋國治， 張大坤

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

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

馬 悅， 宋國治， 張大坤

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

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

三維片上網(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)勢成為當(dāng)前的片上網(wǎng)絡(luò)的一個重要的研究方向[3].本文提出了一種基于模擬退火算法的改進(jìn)溫度下降函數(shù)的自適應(yīng)映射算法.通過改進(jìn)的溫度下降函數(shù)和自適應(yīng)的鄰域解生成策略，來保證在溫度較高時算法的全局性搜索和溫度較低時局部性充分搜索的實(shí)現(xiàn).改進(jìn)后模擬退火算法在收斂速度和功耗上面與傳統(tǒng)的模擬退火算法相比，有了較大的性能提升.

1 3D NoC映射問題

1.1 研究現(xiàn)狀

目前使用的映射算法大致分為兩類：啟發(fā)式映射算法；非啟發(fā)式算法.啟發(fā)式算法主要代表有：基于遺傳算法的映射算法；基于粒子群算法的映射算法；基于模擬退火算法的映射算法以及基于禁忌搜索算法的映射算法等.非啟發(fā)式算法主要包括：異構(gòu)3D NoC映射算法；常規(guī)3D NoC熱感知方法以及快速低能耗映射方法SYMMAP等[4].本文選用模擬退火算法來進(jìn)行映射，通過改變模擬退火算法的溫度下降函數(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的一個或多個性能指標(biāo)達(dá)到最優(yōu).有關(guān)片上網(wǎng)絡(luò)的映射問題是一個非多項(xiàng)式時間復(fù)雜性問題(NP-hard problem)[5-6].

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

定義1 特定任務(wù)的應(yīng)用特征圖ACG,G(V，E)為有向非循環(huán)加權(quán)圖，頂點(diǎn)vi∈V，代表著一個執(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中的一個資源節(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)化.映射的同時必須滿足以下的約束條件：

?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

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

2 NoC評估模型

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

面向3D NoC的映射算法，我們定義一個適應(yīng)值函數(shù)Cost=MAXFit-(dxwx+dywy+dz)，其中：MAXFit是預(yù)先設(shè)置好的最大適應(yīng)值；dx、dy、dz代表的是通信節(jié)點(diǎn)在3個坐標(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ā)送一個微片(flit)的功耗Ebit,(i-j)=μERbit+μHELHbit+μVELVbit,其中：μ表示節(jié)點(diǎn)i到節(jié)點(diǎn)j經(jīng)過的路由器個數(shù);μH和μV分別是信息傳輸?shù)侥康墓?jié)點(diǎn)所經(jīng)過的水平方向和垂直方向的條數(shù)；ERbit表示一個微片通過一個路由器時消耗的能量;ELHbit和ELVbit分別表示一個微片通過一條水平方向和垂直方向的線路時消耗的能量[9].

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

3.1 ISA的提出

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

Ti+1=Ti×r，

(1)

Ti+1=Ti-ΔT，

(2)

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

傳統(tǒng)模擬退火算法SA-1，在溫度較高的時候，溫度下降較快，模擬退火算法的全局性沒有得到實(shí)現(xiàn)，導(dǎo)致算法極容易陷入局部最優(yōu)的困境；而SA-2算法，由于每次下降的溫度相同，在算法運(yùn)行中，溫度函數(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代表著初始溫度.對于溫度下降方式，我們使用自然數(shù)e的冪函數(shù)來構(gòu)造了本文中新的溫度下降函數(shù)，將溫度的下一時刻的改變在與外循環(huán)相關(guān)的基礎(chǔ)上，建立與片上網(wǎng)絡(luò)規(guī)模的關(guān)聯(lián).構(gòu)造了一個根據(jù)不同規(guī)模的片上網(wǎng)絡(luò)映射問題而改變的溫度下降函數(shù)，目的在于在算法初始階段和接近算法結(jié)束這兩個階段可以取得平滑的溫度下降方式.從而可以保證算法初始階段的全局性和終止階段局部搜索的充分性實(shí)現(xiàn).

本文取初始溫度為100 ℃，終止溫度是0.000 1 ℃.從圖2中可以看出當(dāng)溫度較高的時候，式(3)下降的速度比式(1)和(2)慢，更加有利于實(shí)現(xiàn)模擬退火算法的全局性.3個函數(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)該是滿足其中的解盡可能地遍布整個解的空間，以防止算法只能實(shí)現(xiàn)局部最優(yōu).傳統(tǒng)的模擬退火算法所使用的方法雖然可以有效地生成鄰域解，但由于本身策略的局限性，新解與當(dāng)前解的曼哈頓距離(hi,j)是相對較小的[12].這不利于在算法運(yùn)行初期實(shí)現(xiàn)算法的全局性.鑒于此種情況，本文提出利用概率p來選擇鄰域解的生成方法.

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

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

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

3.3 ISA算法的流程

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

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

第2步：在可行解空間中通過改進(jìn)鄰域生成算法來生成新解Xi +1, 并計算其相應(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自動加1，跳轉(zhuǎn)到第2步.

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

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

4.1 不同算法的收斂速度對比

在基于Ubuntu操作系統(tǒng)下，本文使用Access Noxim仿真器針對經(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ù)的模擬退火算法對應(yīng)的實(shí)驗(yàn)結(jié)果.

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

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

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

4.2 功耗對比

本文用DVOPD來做有關(guān)功耗的仿真實(shí)驗(yàn)，在Code Blocks軟件上，分別采用ISA、SA-1和SA-2 3種模擬退火算法來生成通信文件.我們進(jìn)行10次實(shí)驗(yàn)，共生成10個通信文件，對每個通信文件在仿真器上進(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)于另外兩種算法.功耗對比如圖5所示.

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

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

如圖5中，在最高功耗、最低功耗和總功耗上，ISA所對應(yīng)的結(jié)果都要優(yōu)于其他兩種.ISA算法對比SA-1和SA-2兩種基于傳統(tǒng)溫度下降函數(shù)的模擬退火算法，總功耗分別減少了2.5%和6.89%；最低功耗分別下降了2.83%和13.83%；最高功耗分別下降了5.59%和7.21%.綜合3種結(jié)果的對比可知，提出的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] 黃翠, 張大坤, 宋國治. 三維片上網(wǎng)絡(luò)映射算法研究綜述[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

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

馬悅(1993—)，男，安徽亳州人，主要從事三維片上網(wǎng)絡(luò)映射拓?fù)鋬?yōu)化研究，E-mail: 1508011127@qq.com;通信作者：宋國治(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