一种求解RSMT布线问题的PSO算法.pdf

《一种求解RSMT布线问题的PSO算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、2014年第5期闽江学院学报No．52014(总第145期)JOURNALOFMINJIANGUNIVERSITYGeneralSerialNo．145一种求解RSMT布线问题的PSO算法陈秀华，朱自然(1．福建船政交通职业学院公共教学部，福建福州350007；2．福州大学数学与计算机科学学院，福建福州350116)摘要：最小直角斯坦纳树(RSMT)问题是超大规模集成电路布线中的重要问题之一，是典型的NP困难组合优化问题．为了有效地解决超大规模集成电路布线中的RSMT问题，提出一种粒子群优化算法，借助直角S

2、teiner树的一些性质，采用Steiner点编码方案，寻找优化的Steiner点位置以减少直角Steiner树的长度．对几组布线模型实例进行了仿真测试，表明了该算法的有效性．关键词：超大规模集成电路(VLSI)；最小直角斯坦纳树；布线算法中图分类号：TP301．6文献标识码：A文章编号：1009—7821(2014)05—0039—06APSOalgorithmforRSMTroutingproblemCHENXiu—hua，ZHUZi-ran(1．DepartmentofBasicCourses，Fuj

3、ianChuanzhengCommunicationsCollege，Fuzhou，Fujian350007，China；2．CollegeofMathematicsandComputerScience，FuzhouUniversity，Fuzhou，Fujian350116，China)Abstract：TherectilinearSteinerminimaltreeproblemisaclassicalNP—completeproblem．Itisim—portantintheverylargescar

4、eintegration(VLSI)routing．InordertosolvetherectilinearSteinermin—imaltreeproblemeffectively，weproposeaparticleswarn'loptimizationalgorithmbasedonpropertiesofrectilinearSteinertree．Inthealgorithm，SteinercodingapproachisadoptedtoreducethelengthofrectilinearS

5、teinertree．Couplesofsimulationtestingresultsonroutingbenchmarksshowthatthepro-posedalgorithmiseffective．Keywords：verylargescaleintegration(VLSI)；rectilinearSteinerminimaltree；routingalgorithm布线问题是超大规模集成电路(VLSI)物理设计的关键环节之一．一个电路芯片会有大量的线网需要连接，同时对于每个线网，又有几百种甚至

6、更多的布线方案．随着设计规模的不断增长，尤其是百万门级芯片的普遍应用，对VLSI布线问题的算法设计提出了巨大的挑战．VLSI布线问题中连接树的目标是连接树的总长度最短，对于多端线网的最佳布线结果是构造最小直角Steiner树(RSMT)]，该问题已被证明是一个NP完全问题_2J．研究者提出了许多基于智能优化技术的解决方法-8]，这些智能算法主要有模拟退火算法，遗传算法¨卜和蚁群算法埔等．文献[3]提出了关于最小直角Steiner树的混合遗传算法，表明智能优化算法在解决这类问题中具有较好的应用前景．收稿日期：

7、2014—05—27基金项目：福建省教育厅科技项目(JA10284，JB07283)；福建省交通科技发展项目(201011)作者简介：陈秀华(1968一)，女，福建安溪人，福建船政交通职业学院公共教学部副教授，硕士朱自然(1991一)，男，福建厦门人，福州大学数学与计算机科学学院硕士研究生．·39·闽江学院学报2014矩粒子群优化算法PSO(particleswarlnoptimization)是Kenney和Eberhart于1995年提出的一种基于种群搜索策略的自适应随机算法．它源于对鸟群和鱼群等群体运

8、动行为的研究，是一种基于迭代的智能优化算法，可用于求解大部分的优化问题．与常规的遗传算法(GA)相比较，它具有算法简单，收敛速度快，且对目标函数要求少等特点，已成为一种重要的优化工具．文献[5]首先提出了一种用于解决VLSI布线问题的离散粒子群优化算法．此方法通过设计基于惩罚的适应度函数，引入遗传算法的变异和交叉算子，增加了种群的多样性并适当地扩展了粒子的寻优范围．文献[19]提出使用PSO算法求解RSMT问题，