DOI: 10.3724/SP.J.1001.2011.03980

Journal of Software (软件学报) 2011/22:5 PP.833-842

Hybrid Particle Swarm Optimization Algorithm for VLSI Circuit Partitioning

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.

Key words:circuit partitioning,min cut,particle swarm optimization,very large scale integration circuit

ReleaseDate:2014-07-21 15:49:02

[1] Wei YC, Cheng CK. Ratio cut partitioning for hierarchical designs. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 1991,10(7):911-921. [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 and Human Science. Nagoya: IEEE Inc., 1995. 39-43. [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 Design Automation Conf. Las Vegas: IEEE Inc., 1982. 175-181. [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 Circuits and Systems II: Express Briefs, 2006,53(5):384-388. [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. 476-480. [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 Pacific Design Automation Conf. Wanchai: IEEE Inc., 1999. 81-84. [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 in China (Series E), 2003,33(6):562-567 (in Chinese with English abstract).杨华中,胡冠章.电路划分问题的Laplace谱分析和生成树法.中国科学(E辑),2003,33(6):562-567.

[8] Kolar D, Puksec JD, Branica I. VLSI circuit partition using simulated annealing algorithm. In: Proc. of the 12th IEEE Mediterranean on Electrotechnical Conf. Dubrovnik: IEEE Inc., 2004. 205-208. [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’l Conf. on Machine Learning and Cybernetics. Shanghai: IEEE Inc., 2004. 2182-2188. [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’l Journal of Computer Science and Network Security, 2008,8(6):118-124.

[11] Guo WZ, Chen GL, Xia T. A self-adaptive strategy of data streams scheduling on heterogeneous cluster. Journal of Computer Aided Design & Computer Graphics, 2009,21(8):1175-1181 (in Chinese with English abstract).郭文忠,陈国龙,夏添.异构机群下数据流自适应分配策略.计算机辅助设计与图形学学报,2009,21(8):1175-1181.

[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):359-370. [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. Pattern Recognition and Artificial Intelligence, 2009,22(4):597-604 (in Chinese with English abstract).郭文忠,陈国龙.一种求解多目标最小生成树问题的有效离散粒子群优化算法.模式识别与人工智能,2009,22(4):597-604.

[14] Chen GL, Guo WZ, Chen YZ. A PSO-based intelligent decision algorithm for VLSI floorplanning. Soft Computing, 2010,14(12): 1329-1337. [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 Computational Intelligence and Software Engineering. Wuhan: IEEE Inc., 2009. 1-4. [doi: 10.1109/CISE.2009.5364339]

[16] Deng FA, Zhou T, Xu Y. Theory and Application of Soft Computing Method. Beijing: Science Press, 2008. 155-159 (in Chinese).邓方安,周涛,徐扬.软计算方法理论及应用.北京:科学出版社,2008.155-159.

[17] Parsopoulos KE, Vrahatis MN. Recent approaches to global optimization problems through particle swarm optimization. Natural Computing, 2002,1(2-3):235-306. [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):363-371. [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. 4104-4108. [doi: 10.1109/ICSMC.1997.637339]

[20] Clerc M. Discrete particle swarm optimization—Illustrated by the traveling salesman problem. 2000.

[21] Pan QK, Tasgetiren MF, Liang YC. A discrete particle swarm optimization algorithm for the permutation flowshop sequecing problem with makespan criteria. In: Proc. of the 26th SGAI Int’l Conf. on Innovative Techniques and Applications of Artificial Intelligence. Cambridge: Springer-Verlag, 2006. 19-31. [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):58-73. [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 Journal of Computers, 2006,29(11):2052-2061 (in Chinese with English abstract).李宁,孙德宝,邹彤,秦元庆,尉宇.基于差分方程的PSO算法粒子运动轨迹分析.计算机学报,2006,29(11):2052-2061.