• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

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

• 论文 • 上一篇    下一篇

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

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

  1. (天津工业大学计算机科学与软件学院,天津 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   

  1. (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

摘要:

智能优化算法作为解决大规模集成电路芯片设计中布图规划问题的经典方法已被研究多年。结合异构三维片上网络布图问题的具体特点,采用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