微信服务号

微信订阅号

2025年4月5日 18:35 星期六
首页 > 过刊浏览>2011年第22卷第5期 >833-842. DOI:10.3724/SP.J.1001.2011.03980
PDF HTML阅读 XML下载 导出引用 引用提醒
求解VLSI 电路划分问题的混合粒子群优化算法
作者:
基金项目:

国家自然科学基金(10871221, 61070020); 国家重点基础研究发展计划(973)(2006CB805904, 2011CB808000); 福建省自然科学基金(A0820002, 2009J01284); 福建省科技创新平台计划(2009J1007)


Hybrid Particle Swarm Optimization Algorithm for VLSI Circuit Partitioning
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [23]
    • |
  • 相似文献 [20]
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    电路划分是VLSI 物理设计过程中的一个关键阶段.该问题本质上是一个NP 困难的组合优化问题.针对该问题,提出了一种带FM 策略的混合粒子群优化算法.引入遗传算法的两点交叉算子和随机两点交换变异算子,保证了粒子在位置更新后依然可行;为了提高算法的局部搜索能力,将具有较强局部搜索能力的FM 策略融入算法的位置更新;设计了种群多样性变异策略,提高了种群多样性,避免了易陷入局部最优的缺陷.对ISCAS89 标准测试电路的仿真实验结果表明,所构造的算法是有效的.

    Abstract:

    Circuit partitioning is an important part of any very large scale integration (VLSI) physical design automation, but it is a NP-hard combinatorial optimization problem. In this paper, a hybrid particle swarm optimization algorithm with FM strategy is proposed to approch this problem. Inspired by the mechinism of genetic algorithm (GA), two-point crossover and random two-point exchange mutation operators have been designed to avoid generating infeasible solutions. To improve the ability of local exploration, FM strategy is applied to the proposed algorithm to update its position. A mutation strategy is also built into the proposed algorithm to achieve better diversity and break away from local optima. Experiments on ISCAS89 benchmark circuits show that the proposed algorithm is efficient.

    参考文献
    [1] Wei YC, Cheng CK. Ratio cut partitioning for hierarchical designs. IEEE Trans. on Computer-Aided Design of Integrated Circuitsand Systems, 1991,10(7):1-2. [doi: 10.1109/43.87601]
    [2] Eberhart RC, Kennedy J. A new optimizer using particles swarm theory. In: Proc. of the 6th Int’l Symp. on Micro Machine andHuman Science. Nagoya: IEEE Inc., 1995. 1-2. [doi: 10.1109/MHS.1995.494215]
    [3] Fiduccia CM, Mattheyses BM. A linear-time heuristic for improving network partitions. In: Proc. of the 19th IEEE/ACM DesignAutomation Conf. Las Vegas: IEEE Inc., 1982. 1-2. [doi: 10.1109/DAC.1982.1585498]
    [4] Li JH, Behjat L. A connectivity based clustering algorithm with application to VLSI circuit partitioning. IEEE Trans. on Circuitsand Systems II: Express Briefs, 2006,53(5):1-2. [doi: 10.1109/TCSII.2005.862174]
    [5] Iqbal SMA, Monir MI, Sayeed T, Uddin AHMM. A concurrent approach to clustering algorithm with applications to VLSI domain.In: Proc. of the 11th Int’l Conf. on Computer and Information Technology. Khulna: IEEE Inc., 2008. 1-2. [doi: 10.1109/ICCITECHN.2008.4802982]
    [6] Chang JY, Liu YC, Wang TC. Faster and better spectral algorithms for multi-way partitioning. In: Proc. of Asia and South PacificDesign Automation Conf. Wanchai: IEEE Inc., 1999. 1-2. [doi: 10.1109/ASPDAC.1999.759715]
    [7] Yang HZ, Hu GZ. A approach to analyzing laplace spectrum and spanning tree with application to circuit partitioning. Science inChina (Series E), 2003,33(6):1-2 (in Chinese with English abstract).
    [8] Kolar D, Puksec JD, Branica I. VLSI circuit partition using simulated annealing algorithm. In: Proc. of the 12th IEEEMediterranean on Electrotechnical Conf. Dubrovnik: IEEE Inc., 2004. 1-2. [doi: 10.1109/MELCON.2004.1346809]
    [9] Nan GF, Li MQ, Kou JS. Two novel encoding strategies based genetic algorithms for circuit partitioning. In: Proc. of the 3rd Int’lConf. on Machine Learning and Cybernetics. Shanghai: IEEE Inc., 2004. 1-2. [doi: 10.1109/ICMLC.2004.1382160]
    [10] Chen ZQ, Wang RL, Okazaki K. An efficient genetic algorithm based approach for the minimum graph bisection problem. Int’lJournal of Computer Science and Network Security, 2008,8(6):1-2.
    [11] Guo WZ, Chen GL, Xia T. A self-adaptive strategy of data streams scheduling on heterogeneous cluster. Journal of ComputerAided Design & Computer Graphics, 2009,21(8):1-2 (in Chinese with English abstract).
    [12] Guo WZ, Xiong NX, Vasilakos AV, Chen GL, Cheng HJ. Multi-Source temporal data aggregation in wireless sensor networks.Wireless Personal Communications, 2011,56(3):1-2. [doi: 10.1007/s11277-010-9976-9]
    [13] Guo WZ, Chen GL. An efficient discrete particle swarm optimization algorithm for multi-criteria minimum spanning tree. PatternRecognition and Artificial Intelligence, 2009,22(4):1-2 (in Chinese with English abstract).
    [14] Chen GL, Guo WZ, Chen YZ. A PSO-based intelligent decision algorithm for VLSI floorplanning. Soft Computing, 2010,14(12):1-2. [doi: 10.1007/s00500-009-0501-6]
    [15] Peng SJ, Chen GL, Guo WZ. A discrete PSO for partitioning in VLSI circuit. In: Proc. of the Int’l Conf. on ComputationalIntelligence and Software Engineering. Wuhan: IEEE Inc., 2009. 1-2. [doi: 10.1109/CISE.2009.5364339]
    [16] Deng FA, Zhou T, Xu Y. Theory and Application of Soft Computing Method. Beijing: Science Press, 2008. 1-2 (in Chinese).
    [17] Parsopoulos KE, Vrahatis MN. Recent approaches to global optimization problems through particle swarm optimization. NaturalComputing, 2002,1(2-3):1-2. [doi: 10.1023/A:1016568309421]
    [18] Salman A, Ahmad I, Al-Madani S. Particle swarm optimization for task assignment problem. Microprocessors and Microsystems,2002,26(8):1-2. [doi: 10.1016/S0141-9331(02)00053-4]
    [19] Kennedy J, Eberhart RC. A discrete binary version of the particle swarm algorithm. In: Proc. of the IEEE Int’l Conf. on Systems,Man and Cybernetics. Orlando: IEEE Inc., 1997. 1-2. [doi: 10.1109/ICSMC.1997.637339]
    [20] Clerc M. Discrete particle swarm optimization—Illustrated by the traveling salesman problem. 2000. http://www.mauriceclerc.net
    [21] Pan QK, Tasgetiren MF, Liang YC. A discrete particle swarm optimization algorithm for the permutation flowshop sequecingproblem with makespan criteria. In: Proc. of the 26th SGAI Int’l Conf. on Innovative Techniques and Applications of ArtificialIntelligence. Cambridge: Springer-Verlag, 2006. 1-2. [doi: 10.1007/978-1-84628-663-6_2]
    [22] Clerc M, Kennedy J. The particle swarm-explosion, stability, and convergence in a multidimensional complex space. IEEE Trans.on Evolutionary Computation, 2002,6(1):1-2. [doi: 10.1109/4235.985692]
    [23] Li N, Sun DB, Zou T, Qin YQ, Wei Y. An analysis for a particle’s trajectory of PSO based on difference equation. Chinese Journalof Computers, 2006,29(11):1-2 (in Chinese with English abstract).
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

郭文忠,陈国龙,XIONG Naixue,彭少君.求解VLSI 电路划分问题的混合粒子群优化算法.软件学报,2011,22(5):833-842

复制
分享
文章指标
  • 点击次数:6165
  • 下载次数: 6809
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2010-06-30
  • 最后修改日期:2011-01-06
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19791524位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号