基于改進模擬退火的三維片上網絡映射算法研究

馬 悅， 宋國治， 張大坤

(天津工業大學 計算機科學與軟件學院 天津 300387)

基于改進模擬退火的三維片上網絡映射算法研究

馬 悅， 宋國治， 張大坤

(天津工業大學 計算機科學與軟件學院 天津 300387)

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

三維片上網絡； 模擬退火算法； 溫度下降函數； 鄰域解

0 引言

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

1 3D NoC映射問題

1.1 研究現狀

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

1.2 映射問題定義

片上網絡映射就是在已知NoC體系結構和IP核間通信量的基礎上，按某種方法將給定應用特征圖 (application characteristic graph, ACG)上的IP核 (包括微處理器、DSP以及各種專用功能模塊等)分配到NoC拓撲結構圖 (topology architecture graph, TAG)中的各資源節點上，使得3D NoC的一個或多個性能指標達到最優.有關片上網絡的映射問題是一個非多項式時間復雜性問題(NP-hard problem)[5-6].

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

定義1 特定任務的應用特征圖ACG,G(V，E)為有向非循環加權圖，頂點vi∈V，代表著一個執行特定任務的IP核，用整數來表示，不同數字代表不同的頂點.有向弧ei,j∈E，表示節點vi與vj之間的通信關系，權重wi,j代表vi與vj的通信量.

定義2 給定的片上網絡拓撲結構圖TAG,T(R，P)為有向圖，頂點ri∈R，表示NoC中的一個資源節點；有向弧pi,j∈P表示從ri到rj的路徑.hi,j表示從ri到rj之間的曼哈頓距離.

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

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

圖1 經典DVOPD應用特征圖Fig.1 Classical ACG DVOPD

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

2 NoC評估模型

2.1 目標函數

面向3D NoC的映射算法，我們定義一個適應值函數Cost=MAXFit-(dxwx+dywy+dz)，其中：MAXFit是預先設置好的最大適應值；dx、dy、dz代表的是通信節點在3個坐標軸方向距離；wx、wy代表的是權重.因為三維片上網絡采用了TSV技術，在z軸方向的傳輸功耗要遠遠小于水平方向上的功耗[7-8]，所以這里就不再乘以權重.

2.2 功耗模型

節點i與節點j之間發送一個微片(flit)的功耗Ebit,(i-j)=μERbit+μHELHbit+μVELVbit,其中：μ表示節點i到節點j經過的路由器個數;μH和μV分別是信息傳輸到目的節點所經過的水平方向和垂直方向的條數；ERbit表示一個微片通過一個路由器時消耗的能量;ELHbit和ELVbit分別表示一個微片通過一條水平方向和垂直方向的線路時消耗的能量[9].

3 改進模擬退火算法

3.1 ISA的提出

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

Ti+1=Ti×r，

(1)

Ti+1=Ti-ΔT，

(2)

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

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

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

(3)

其中：count代表外循環次數，溫度每下降一次count自增1；DIM代表3D NoC的規模大小(節點數目)；TN代表終止溫度；T0代表著初始溫度.對于溫度下降方式，我們使用自然數e的冪函數來構造了本文中新的溫度下降函數，將溫度的下一時刻的改變在與外循環相關的基礎上，建立與片上網絡規模的關聯.構造了一個根據不同規模的片上網絡映射問題而改變的溫度下降函數，目的在于在算法初始階段和接近算法結束這兩個階段可以取得平滑的溫度下降方式.從而可以保證算法初始階段的全局性和終止階段局部搜索的充分性實現.

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

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

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

改進的鄰域生成策略：

1) 初始設p=1,當p>rand( )時，我們采用向左循環移動一位的方法生成新解，否則執行2).

2) 采用傳統隨機確定兩個節點的位置，然后互換兩個節點從而生成新解.

3.3 ISA算法的流程

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

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

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

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

第4步：判斷該溫度下是否已經充分搜索，若充分搜索，執行第5步;否則執行第2步.

第5步：判斷Ti是否小于TN，若小于，則循環終止，跳到第6步；否則，i自動加1，跳轉到第2步.

第6步：返回當前解和當前解的適應值.

4 仿真實驗與結果分析

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

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

圖3 3種溫度下降函數下VOPD收斂速度

圖4 3種溫度下降函數下DVOPD收斂速度

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

4.2 功耗對比

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

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

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

圖5 3種溫度函數對應算法的功耗對比圖

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

[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] 黃翠, 張大坤, 宋國治. 三維片上網絡映射算法研究綜述[J]. 小型微型計算機系統, 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片上網絡映射方法研究[D].廣州：廣東工業大學，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]. 西安：西安電子科技大學, 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.

(責任編輯：王海科)

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

國家自然科學基金項目(61272006)；國家大學生創新創業訓練計劃項目(201510058050).

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

TP305

A

1671-6841(2017)03-0009-05

10.13705/j.issn.1671-6841.2016325