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

J4 ›› 2016, Vol. 38 ›› Issue (5): 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(5): 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(5): 863-870.

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