一种用于片上网络布图规划的改进模拟退火与粒子群混合算法

J4 ›› 2016, Vol. 38 ›› Issue (05): 863-870.

一种用于片上网络布图规划的改进模拟退火与粒子群混合算法

宋国治，涂遥，张大坤，温越博

（天津工业大学计算机科学与软件学院,天津 300387）

收稿日期:2015-12-04 修回日期:2016-02-11 出版日期:2016-05-25 发布日期:2016-05-25
基金资助:
国家自然科学基金（61272006)；国家级大学生创新创业训练计划（201510058050)

A NoC floorplanning scheme based on a hybrid of
particle swarm optimization and simulated annealing

SONG Gouzhi，TU Yao，ZHANG Dakun，WEN Yuebo

（School of Computer Science and Software Engineering,Tianjin Polytechnic University,Tianjin 300387,China）

Received:2015-12-04 Revised:2016-02-11 Online:2016-05-25 Published:2016-05-25

摘要/Abstract

摘要：

智能优化算法作为解决大规模集成电路芯片设计中布图规划问题的经典方法已被研究多年。结合异构三维片上网络布图问题的具体特点，采用B*tree间接描述布图问题中的解结构，针对模拟退火收敛速度慢、优化效率低的缺点，对搜索策略和概率性的劣向转移作出了改进，并将改进后的模拟退火思想引入粒子群优化算法中，使结合后的算法结合了粒子群并行计算的特点和模拟退火能够实现全局优化的特点。通过仿真实验验证，所提出的该混合改进算法在解决布图问题中要优于传统模拟退火算法。

关键词: 布图规划, 片上网络, 模拟退火, 粒子群优化算法

Abstract:

Using intelligent optimization algorithms as a method to solve the problem of floorplanning in the design of VLSI has been a trend for so many years. In order to solve the slow convergence speed and low efficiency of optimization for the simulated annealing (SA) algorithm and to improve the search strategy and probabilistic inferior transfer, combing the features of the floorplanning problem for heterogeneous 3D NoCs, we adopt the B*tree to indirectly describe the structure of the answer to floorplanning problems. We then introduce the improved SA algorithm into the PSO algorithm, and the resulting hybrid algorithm possesses the advantages of PSO's parallel computing and the SA's global optimization. Simulation results validate the superiority of the new hybrid algorithm to the traditional SA.

Key words: floorplanning；NoC；simulated annealing；particle swarm optimization

宋国治，涂遥，张大坤，温越博. 一种用于片上网络布图规划的改进模拟退火与粒子群混合算法[J]. J4, 2016, 38(05): 863-870.

SONG Gouzhi，TU Yao，ZHANG Dakun，WEN Yuebo. A NoC floorplanning scheme based on a hybrid of
particle swarm optimization and simulated annealing [J]. J4, 2016, 38(05): 863-870.

参考文献［15］

［1］	Wang Jinmin,Chen Dongxiang,Ma Fengning,et al.A simulated annealing packing algorithm［J］. CAD&CG,1998,10(3):253259.(in Chinese)
［2］	Wang Dingwei, Wang Junwei, Wang Hongfeng, et al. Intelligent optimization methods［M］. Beijing:Higher Education Press,2007.(in Chinese)
［3］	Jiao Hong,Hong Xianlong. A twostage simulatedannealing algorithm for Macro cell array placement［J］. Computer Engineering and Design,1997,18(3):4951.(in Chinese)
［4］	Xie Yun. The date structure and simulated annealing algorithm for solving the placement problem［J］. Micro Computer Information,1999,15(5):3233.(in Chinese)
［5］	Kennedy J,Eberhart R C. Particle swarm optimization［C］∥Proc of IEEE International Conference on Neutral Networks,1995:19421948.
［6］	Zhao Changhong. The researeh of VLSI floorplan algorithm［D］. Shanghai:Fudan University,2006.(in Chinese)
［7］	Otten R. Automatic floorplan design［C］∥Proc of DAC,1982:261267.
［8］	Wong D F,Liu C L. A new algorithm for foorplan design［C］∥Proc of DAC,1986:101107.
［9］	Murata H,Fujiyoshi K,Nakatake S,et al. Rectanglepacking based module placement［C］∥Proc of ICCAD,1995:472479.
［10］	Tang X, Tian R, Wang D F. Fast evaluation of sequence pair in block placement by longest common subsequence computation ［J］. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems,2001,20(12):14061413.
［11］	Guo P N,Cheng C K,Yoshimura T. An Otree representation of nonslicing floorplan and its applications［C］∥Proc of the 36th Design Automation Conference,ACM/ IEEE,1999:268273.
［12］	Chang Y C,Chang Y W,Wu G M,et al. B*tree:A new representation for nonslicing floorplans［C］∥Proc of the 37th Design Automation Conference ACM/ IEEE,2000:458463.
［13］	Lin J M, Chang Y W. TCG: A transitive closure graphbased representation for nonslicing foorplans［C］∥Proc ofDAC,2001:764769.
［14］	Ingber L. Very fast simulated Reannealing［J］. Mathematical Conputer Modeling,1989,12(8):967973.
［15］	Wang Ling. Intelligent optimization methods［M］. Beijing:Tsinghua University Press,2004.(in Chinese)
［16］	Ababei C，de Paulo V. 3D networkonchip architectures using homogeneous meshes and heterogeneous floorplans［J］. International Journal of Reconfigurable Computing,2010,Article ID 603059.
［17］	Mineo C,Jenkal R,Melamed S,et al. Interdie signaling in three dimensional integrated circuits［C］∥Proc of IEEE Custom Integrated Circuits Conference(CICC ’08),2008:655658.
［18］	Rabaey J M. Digital integrated circuits:A design perspective［M］.2nd edition. NJ:PrenticeHall,Upper Saddle River,2003.
	附中文参考文献：
［1］	王金敏,陈东祥,马丰宁,等. 布局问题的模拟退火算法［J］. 计算机辅助设计与图形学报,1998,10(3):253259.
［2］	汪定伟,王俊伟,王洪峰,等. 智能优化算法［M］. 北京:高等教育出版社, 2007.
［3］	焦虹,洪先龙. 宏单元阵列布局的两步模拟退火算法［J］. 计算机工程与设计,1997,18(3):4951.
［4］	谢云.解布局问题的四元组数据结构及其模拟退火算法［J］. 微计算机信息,1999,15(5):3233.
［6］	赵长虹. 超大规模集成电路的平面布图规划算法研究［D］. 上海：复旦大学, 2006.
［15］	王凌. 智能优化算法及其应用［M］. 北京:清华大学出版社,2004.

[1]	高文才, 陈小文. 一种基于混合加固的容软错误NoC路由器[J]. 计算机工程与科学, 2023, 45(08): 1376-1382.
[2]	葛一漩, 李晨, 陈小文, 鲁建壮, 郭阳. 一种定制片上网络设计探索算法的设计与实现[J]. 计算机工程与科学, 2023, 45(06): 970-978.
[3]	王林, 王燕丽, 安泽远. 改进粒子群算法优化回声状态网络的电力需求预测研究[J]. 计算机工程与科学, 2022, 44(08): 1457-1466.
[4]	康子扬, 彭凌辉, 周干, 林博, 王蕾. 一种用于片上网络的拥塞感知哈密尔顿最短路径路由算法[J]. 计算机工程与科学, 2022, 44(06): 986-993.
[5]	陈小帆, 杨智杰, 彭凌辉, 王世英, 周干, 李石明, 康子扬, 王耀, 石伟, 王蕾. 一种类脑处理器片上网络的验证框架[J]. 计算机工程与科学, 2022, 44(05): 769-778.
[6]	赵炳巍, 贾峰, 曹岩, 孙瑜, 刘一鸿. 基于模拟退火算法的人工势场法路径规划研究[J]. 计算机工程与科学, 2022, 44(04): 746-752.
[7]	张晶, 魏淼, . 基于Delaunay三角划分策略的WSN区域覆盖优化研究[J]. 计算机工程与科学, 2021, 43(11): 1944-1951.
[8]	石伟, 龚锐, 刘威, 王蕾, 冯权友, 张剑锋. 面向高带宽I/O的片上网络优化[J]. 计算机工程与科学, 2021, 43(09): 1538-1545.
[9]	袁也, 王刚, 刘晓光, 李雨森. 新型电路版图布局布线算法设计[J]. 计算机工程与科学, 2021, 43(07): 1185-1191.
[10]	齐星云, 戴艺, 赖明澈, 常俊胜, 董德尊. 基于偏折路由的双环片上网络[J]. 计算机工程与科学, 2021, 43(03): 381-388.
[11]	赵凤1,2，孔令润1,2，马改妮1,2. 多目标粒子群和人工蜂群混合优化的阈值图像分割算法[J]. 计算机工程与科学, 2020, 42(02): 281-290.
[12]	陈丽芳,冯力静,刘保相. 神经网络规则优化建模与应用[J]. 计算机工程与科学, 2019, 41(12): 2247-2254.
[13]	朱永超1，周川1，崔玉伟2，郭健1，吴益飞1. 基于模拟退火算法的改进主/副版本调度算法[J]. 计算机工程与科学, 2019, 41(09): 1534-1540.
[14]	马晗，常安定，陈童，李江杰. 基于文化混合优化算法的旅行商问题求解[J]. 计算机工程与科学, 2019, 41(07): 1273-1278.
[15]	赵志刚，莫海淼，温泰，李智梅，郭杨. 一种自适应调整种群子代数量与步长的优化算法——爆米花算法[J]. 计算机工程与科学, 2019, 41(05): 900-909.