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

作者：Guo, Wenzhong; Liu, Genggeng; Chen, Guolong^*; Peng, Shaojun

来源：Frontiers of Computer Science, 2014, 8(2): 203-216.

DOI：10.1007/s11704-014-3008-y

• VLSI
• physical design
• circuit partitioning
• particle swarm optimization

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.

• 出版日期2014-4
• 单位福州大学