A hybrid multi-objective PSO algorithm with local search strategy for VLSI partitioning

详细信息    查看全文

• 作者：Wenzhong Guo (1)
  Genggeng Liu (1)
  Guolong Chen (1)
  Shaojun Peng (1)
  
• 关键词：VLSI ; physical design ; circuit partitioning ; particle swarm optimization
• 刊名：Frontiers of Computer Science in China
• 出版年：2014
• 出版时间：April 2014
• 年：2014
• 卷：8
• 期：2
• 页码：203-216
• 全文大小：604 KB
• 参考文献：1. Dutt S, Deng W Y. A probability-based approach to VLSI circuit partitioning. In: Proceedings of the 33rd Design Automation Conference. 1996, 100鈥?05
  2. Dutt S. Cluster-aware iterative improvement techniques for partitioning large VLSI circuits. ACM Transactions on Design Automation of Electronic Systems, 2002, 7(1): 91鈥?21 CrossRef
  3. Wei Y C, Cheng C K. Ratio cut partitioning for hierarchical designs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991, 10(7): 911鈥?21 CrossRef
  4. Fiduccia C M, Mattheyses B M. A linear-time heuristic for improving network partitions. In: Proceedings of the 19th Design Automation Conference. 1982, 175鈥?81 CrossRef
  5. Krishnamurthy B. An improved min-cut algorithm for partitioning VLSI networks, IEEE Transactions on Computer. 1984, 100(5): 438鈥?46 CrossRef
  6. Iqbal S M A, Monir M I, Sayeed T. A concurrent approach to clustering algorithm with applications to VLSI domain. In: Proceedings of the 11th International Conference on Computer and Information Technology. 2008, 476鈥?80
  7. Li J H, Behjat L. A connectivity based clustering algorithm with application to VLSI circuit partitioning. IEEE Transactions on Circuits and Systems II: Express Briefs, 2006, 53(5): 384鈥?88 CrossRef
  8. Barnard S T, Simon H D. Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Concurrency: Practice and Experience, 1994, 6(2): 101鈥?17 CrossRef
  9. Lang K J. Fixing two weaknesses of the spectral method. In: Proceedings of the 2005 Neural Infromation Processing Systems. 2005, 715鈥?22
  10. Kolar D, Puksec J D, Branica I. VLSI circuit partition using simulated annealing algorithm. In: Proceedings of the 12th IEEE Mediterranean on Electrotechnical Conference. 2004, 205鈥?08 CrossRef
  11. Sait S M, El-Maleh A H, Al-Abaji R H. General iterative heuristics for VLSI multiobjective partitioning. In: Proceedings of the 2003 IEEE International, Symposium on Circuits and Systems. 2003, 5: V497鈥揤500 CrossRef
  12. Chen Z Q, Wang R L, Okazaki K. An efficient genetic algorithm based approach for the minimum graph bisection problem. International Journal of Computer Science and Network Security, 2008, 8(6): 118鈥?24
  13. Nan G F, Li M Q, Kou J S. Two novel encoding strategies based genetic algorithms for circuit partitioning. In: Proceedings of the 3rd International Conference on Machine Learning and Cybernetics. 2004, 2182鈥?188
  14. Sait S M, El-Maleh A H, Al-Abaji R H. Evolutionary algorithms for VLSI multi-objective netlist partitioning. Engineering Applications of Artificial Intelligence, 2006, 19(3): 257鈥?68 CrossRef
  15. Kennedy J, Eberhart R C. Particle swarm optimization. In: Proceedings of the IEEE International Conference on Neural Networks. 1995, 1942鈥?948 CrossRef
  16. Wang Y, Cai Z X. A hybrid multi-swarm particle swarm optimization to solve constrained optimization problems. Frontiers of Computer Science in China, 2009, 3(1): 38鈥?2 CrossRef
  17. Peng S J, Chen G L, Guo W Z. A multi-objective algorithm based on discrete PSO for VLSI partitioning problem. Quantitative Logic and Soft Computing, 2010, 82: 651鈥?60
  18. Chen G L, Guo W Z, Chen Y Z. A PSO-based intelligent decision algorithm for VLSI floorplanning. Soft Computing, 2010, 14(12): 1329鈥?337 CrossRef
  19. Liu H, Cai ZX, Wang Y. Hybridizing particle swarm optimization with differential evolution for constrained numerical and engineering optimization. Applied Soft Computing, 2010, 10(2): 629鈥?40 CrossRef
  20. Fu Y G, Ding M Y, Zhou C P. Phase Angle-encoded and quantumbehaved particle swarm optimization applied to three-dimensional route planning for UAV. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, 2012, 42(2): 511鈥?26 CrossRef
  21. Hung J C. Modified particle swarm optimization structure approach to direction of arrival estimation. Applied Soft Computing, 2013, 13(1): 315鈥?20 CrossRef
  22. Guo W Z, Zhang B, Chen G L, Wang X F, Xiong N. A PSO-optimized minimum spanning tree-based topology control Scheme for wireless sensor networks. International Journal of Distributed Sensor Networks, 2013 (2013): Article 985410
  23. Peng S J, Chen G L, Guo W Z. A discrete PSO for partitioning in VLSI circuit. In: Proceedings of the 2009 International Conference on Computational Intelligence and Software Engineering. 2009, 1鈥?
  24. Areibi S, Thompson M. A new model for macrocell partitioning. In: Proceedings of the 16th International Conference on Computers and Their Applications. 2001, 161鈥?65
  25. Ababei C, Navaratnasothie S, Bazargan K, Karypis G. Multi-objective circuit partitioning for cut size and path-based delay minimization. In: Proceedings of the International Conference on Computer-Aided Design. 2002, 181鈥?85
  26. Kahng A B, Xu X. Local Unidirectional bias for cutsize-delay tradeoff in performance-driven bipartitioning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2003, 23(4): 464鈥?71 CrossRef
  27. Kennedy J, Eberhart R C. A discrete binary version of the particle swarm algorithm. In: Proceedings of the 1997 World Multiconference on Systemics, Cybernetics and Informatics. 1997, 4104鈥?109
  28. Clerc M. Discrete particle swarm optimization, illustrated by the traveling salesman problem. New Optimization Techniques in Engineering, 2004, 141: 219鈥?39 CrossRef
  29. Chen W N, Zhang J, Chung H S H, Zhong W L, Wu W G, Shi Y H. A novel set-based particle swarm optimization method for discrete optimization problems. IEEE Transactions on Evolutionary Computation, 2010, 14(2): 278鈥?00 CrossRef
  30. Qin J, Li X, Yin Y. An algorithmic framework of discrete particle swarm optimization. Applied Soft Computing, 2012, 12(3): 1125鈥?130 CrossRef
  31. Pan Q K, Tasgetiren M F, Liang Y C. A discrete particle swarm optimization algorithm for the permutation flowshop sequecing problem with makespan criteria. In: Proceedings of the 26th SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence. 2006, 19鈥?1
  32. Guo W Z, Xiong N X, Vasilakos A V, Chen G L, Yu C L. Distributed / k-connected fault-tolerant topology control algorithms with PSO in future autonomic sensor systems. International Journal of Sensor Networks, 2012, 12(1): 53鈥?2 CrossRef
  33. Balling R. The maximin fitness function: multiobjective city and regional planning. In: Proceedings of the 2nd International Conference on Evolutionary Multi-Criterion Optimization. 2003, 1鈥?5 CrossRef
  34. Laumanns M, Thiele L, Deb K, Zitzler E. Combining convergence and diversity in evolutionary multi-objective optimization. Evolutionary Computation, 2002, 10(3): 263鈥?82 CrossRef
  35. Steuer R E. Multiple Criteria Optimization: Theory, Computation, and Application. New York: John Wiley Sons, 1986
  36. Zitzler E, Laumanns M, and Thiele L. SPEA2: improving the strength pareto evolutionary algorithm. In: K. C. Giannakoglou, D. T. Tsahalis, J. P鈥檈riaux, K. D. Papailiou, T. Fogarty, eds. Evolutionary Methods for Design Optimization and Control with Applications to Industrial Problems, International Center for Numerical Methods in Engineering, 2001, 95鈥?00
  37. Zitzler E. Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications. Zurich: Swiss Federal Institute of Technology, 1999
  38. Zitzler E, Thiele L, Laumanns M, Fonseca C M, Da Fonseca V G. Performance assessment of multiobjective optimizers: an analysis and review. IEEE Transactions on Evolutionary Computation, 2003 (7): 117鈥?32
  39. Conover W J. Practical Nonparametric Statistics. New York: Wiley, 1999
  
• 作者单位：Wenzhong Guo (1)
  Genggeng Liu (1)
  Guolong Chen (1)
  Shaojun Peng (1)
  
  1. College of Mathematics and Computer Science, Fuzhou University, Fuzhou, 350116, China
  
• ISSN：1673-7466

文摘

Very large scale integration (VLSI) circuit partitioning is an important problem in design automation of VLSI chips and multichip systems; it is an NP-hard combinational optimization problem. In this paper, an effective hybrid multi-objective partitioning algorithm, based on discrete particle swarm optimzation (DPSO) with local search strategy, called MDPSO-LS, is presented to solve the VLSI twoway partitioning with simultaneous cutsize and circuit delay minimization. Inspired by the physics of genetic algorithm, uniform crossover and random two-point exchange operators are designed to avoid the case of generating infeasible solutions. Furthermore, the phenotype sharing function of the objective space is applied to circuit partitioning to obtain a better approximation of a true Pareto front, and the theorem of Markov chains is used to prove global convergence. To improve the ability of local exploration, Fiduccia-Matteyses (FM) strategy is also applied to further improve the cutsize of each particle, and a local search strategy for improving circuit delay objective is also designed. Experiments on ISCAS89 benchmark circuits show that the proposed algorithm is efficient.