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

Abstract

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.

Keywords

VLSI / physical design / circuit partitioning / particle swarm optimization

References

[1] DuttS, DengW Y. A probability-based approach to VLSI circuit partitioning. In: Proceedings of the 33rd Design Automation Conference. 1996, 100-105

[2] DuttS. Cluster-aware iterative improvement techniques for partitioning large VLSI circuits. ACM Transactions on Design Automation of Electronic Systems, 2002, 7(1): 91-121

[3] WeiY C, ChengC K. Ratio cut partitioning for hierarchical designs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991, 10(7): 911-921

[4] FiducciaC M, MattheysesB M. A linear-time heuristic for improving network partitions. In: Proceedings of the 19th Design Automation Conference. 1982, 175-181

[5] KrishnamurthyB. An improved min-cut algorithm for partitioning VLSI networks, IEEE Transactions on Computer. 1984, 100(5): 438-446

[6] IqbalS M A, MonirM I, SayeedT. 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-480

[7] LiJ H, BehjatL. A connectivity based clustering algorithm with application to VLSI circuit partitioning. IEEE Transactions on Circuits and Systems II: Express Briefs, 2006, 53(5): 384-388

[8] BarnardS T, SimonH D. Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Concurrency: Practice and Experience, 1994, 6(2): 101-117

[9] LangK J. Fixing two weaknesses of the spectral method. In: Proceedings of the 2005 Neural Infromation Processing Systems. 2005, 715-722

[10] KolarD, PuksecJ D, BranicaI. VLSI circuit partition using simulated annealing algorithm. In: Proceedings of the 12th IEEE Mediterranean on Electrotechnical Conference. 2004, 205-208

[11] SaitS M, El-MalehA H, Al-AbajiR H. General iterative heuristics for VLSI multiobjective partitioning. In: Proceedings of the 2003 IEEE International, Symposium on Circuits and Systems. 2003, 5: V497-V500

[12] ChenZ Q, WangR L, OkazakiK. An efficient genetic algorithm based approach for the minimum graph bisection problem. International Journal of Computer Science and Network Security, 2008, 8(6): 118-124

[13] NanG F, LiM Q, KouJ 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-2188

[14] SaitS M, El-MalehA H, Al-AbajiR H. Evolutionary algorithms for VLSI multi-objective netlist partitioning. Engineering Applications of Artificial Intelligence, 2006, 19(3): 257-268

[15] KennedyJ, EberhartR C. Particle swarm optimization. In: Proceedings of the IEEE International Conference on Neural Networks. 1995, 1942-1948

[16] WangY, CaiZ X. A hybrid multi-swarm particle swarm optimization to solve constrained optimization problems. Frontiers of Computer Science in China, 2009, 3(1): 38-52

[17] PengS J, ChenG L, GuoW Z. A multi-objective algorithm based on discrete PSO for VLSI partitioning problem. Quantitative Logic and Soft Computing, 2010, 82: 651-660

[18] ChenG L, GuoW Z, ChenY Z. A PSO-based intelligent decision algorithm for VLSI floorplanning. Soft Computing, 2010, 14(12): 1329-1337

[19] LiuH, CaiZX, WangY. Hybridizing particle swarm optimization with differential evolution for constrained numerical and engineering optimization. Applied Soft Computing, 2010, 10(2): 629-640

[20] FuY G, DingM Y, ZhouC 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-526

[21] HungJ C. Modified particle swarm optimization structure approach to direction of arrival estimation. Applied Soft Computing, 2013, 13(1): 315-320

[22] GuoW Z, ZhangB, ChenG L, WangX F, XiongN. 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] PengS J, ChenG L, GuoW Z. A discrete PSO for partitioning in VLSI circuit. In: Proceedings of the 2009 International Conference on Computational Intelligence and Software Engineering. 2009, 1-4

[24] AreibiS, ThompsonM. A new model for macrocell partitioning. In: Proceedings of the 16th International Conference on Computers and Their Applications. 2001, 161-165

[25] AbabeiC, NavaratnasothieS, BazarganK, KarypisG. Multi-objective circuit partitioning for cut size and path-based delay minimization. In: Proceedings of the International Conference on Computer-Aided Design. 2002, 181-185

[26] KahngA B, XuX. 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-471

[27] KennedyJ, EberhartR C. A discrete binary version of the particle swarm algorithm. In: Proceedings of the 1997 World Multiconference on Systemics, Cybernetics and Informatics. 1997, 4104-4109

[28] ClercM. Discrete particle swarm optimization, illustrated by the traveling salesman problem. New Optimization Techniques in Engineering, 2004, 141: 219-239

[29] ChenW N, ZhangJ, ChungH S H, ZhongW L, WuW G, ShiY H. A novel set-based particle swarm optimization method for discrete optimization problems. IEEE Transactions on Evolutionary Computation, 2010, 14(2): 278-300

[30] QinJ, LiX, YinY. An algorithmic framework of discrete particle swarm optimization. Applied Soft Computing, 2012, 12(3): 1125-1130

[31] PanQ K, TasgetirenM F, LiangY 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-31

[32] GuoW Z, XiongN X, VasilakosA V, ChenG L, YuC 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-62

[33] BallingR. The maximin fitness function: multiobjective city and regional planning. In: Proceedings of the 2nd International Conference on Evolutionary Multi-Criterion Optimization. 2003, 1-15

[34] LaumannsM, ThieleL, DebK, ZitzlerE. Combining convergence and diversity in evolutionary multi-objective optimization. Evolutionary Computation, 2002, 10(3): 263-282

[35] SteuerR E. Multiple Criteria Optimization: Theory, Computation, and Application. New York: John Wiley Sons, 1986

[36] ZitzlerE, LaumannsM, and ThieleL. SPEA2: improving the strength pareto evolutionary algorithm. In: GiannakoglouK. C., TsahalisD. T., P’eriauxJ., PapailiouK. D., FogartyT., eds. Evolutionary Methods for Design Optimization and Control with Applications to Industrial Problems, International Center for Numerical Methods in Engineering, 2001, 95-100

[37] ZitzlerE. Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications. Zurich: Swiss Federal Institute of Technology, 1999

[38] ZitzlerE, ThieleL, LaumannsM, FonsecaC M, Da FonsecaV G. Performance assessment of multiobjective optimizers: an analysis and review. IEEE Transactions on Evolutionary Computation, 2003(7): 117-132

[39] ConoverW J. Practical Nonparametric Statistics. New York: Wiley, 1999

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg