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

doi:10.1007/s11704-014-3008-y

Front. Comput. Sci.

2014, Vol. 8

Issue (2) : 203-216 https://doi.org/10.1007/s11704-014-3008-y

RESEARCH ARTICLE

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

Wenzhong GUO,Genggeng LIU,Guolong CHEN(

),Shaojun PENG

College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China

Download: PDF(547 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): Guolong CHEN

Issue Date: 24 June 2014

Cite this article:

Wenzhong GUO,Genggeng LIU,Guolong CHEN, et al. A hybrid multi-objective PSO algorithm with local search strategy for VLSI partitioning[J]. Front. Comput. Sci., 2014, 8(2): 203-216.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-014-3008-y
https://academic.hep.com.cn/fcs/EN/Y2014/V8/I2/203

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 doi: 10.1145/504914.504918
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 doi: 10.1109/43.87601
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 doi: 10.1109/TC.1984.1676460
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 doi: 10.1002/cpe.4330060203
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 doi: 10.1109/MELCON.2004.1346809
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 doi: 10.1016/j.engappai.2005.09.008
15	KennedyJ, EberhartR C. Particle swarm optimization. In: Proceedings of the IEEE International Conference on Neural Networks. 1995, 1942-1948 doi: 10.1109/ICNN.1995.488968
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 doi: 10.1007/s11704-009-0010-x
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 doi: 10.1007/s00500-009-0501-6
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 doi: 10.1016/j.asoc.2009.08.031
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 doi: 10.1109/TSMCA.2011.2159586
21	HungJ C. Modified particle swarm optimization structure approach to direction of arrival estimation. Applied Soft Computing, 2013, 13(1): 315-320 doi: 10.1016/j.asoc.2012.08.006
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 doi: 10.1155/2013/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 doi: 10.1109/CISE.2009.5364339
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 doi: 10.1109/TCAD.2004.825847
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 doi: 10.1007/978-3-540-39930-8_8
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 doi: 10.1109/TEVC.2009.2030331
30	QinJ, LiX, YinY. An algorithmic framework of discrete particle swarm optimization. Applied Soft Computing, 2012, 12(3): 1125-1130 doi: 10.1016/j.asoc.2011.11.012
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 doi: 10.1504/IJSNET.2012.047720
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 doi: 10.1007/3-540-36970-8_1
34	LaumannsM, ThieleL, DebK, ZitzlerE. Combining convergence and diversity in evolutionary multi-objective optimization. Evolutionary Computation, 2002, 10(3): 263-282 doi: 10.1162/106365602760234108
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 doi: 10.1109/TEVC.2003.810758
39	ConoverW J. Practical Nonparametric Statistics. New York: Wiley, 1999

[1]	Yihui LIANG, Han HUANG, Zhaoquan CAI. PSO-ACSC: a large-scale evolutionary algorithm for image matting[J]. Front. Comput. Sci., 2020, 14(6): 146321-.
[2]	Wei-Neng CHEN, Da-Zhao TAN. Set-based discrete particle swarm optimization and its applications: a survey[J]. Front. Comput. Sci., 2018, 12(2): 203-216.
[3]	Cui HUANG, Dakun ZHANG, Guozhi SONG. A novel mapping algorithm for three-dimensional network on chip based on quantum-behaved particle swarm optimization[J]. Front. Comput. Sci., 2017, 11(4): 622-631.
[4]	Genggeng LIU,Wenzhong GUO,Rongrong LI,Yuzhen NIU,Guolong CHEN. XGRouter: high-quality global router in X-architecture with particle swarm optimization[J]. Front. Comput. Sci., 2015, 9(4): 576-594.
[5]	Priyanka CHAWLA,Inderveer CHANA,Ajay RANA. A novel strategy for automatic test data generation using soft computing technique[J]. Front. Comput. Sci., 2015, 9(3): 346-363.
[6]	Wei ZHAO, Ye SAN. RBF neural network based on q-Gaussian function in function approximation[J]. Front Comput Sci Chin, 2011, 5(4): 381-386.
[7]	Yong WANG, Zixing CAI. A hybrid multi-swarm particle swarm optimization to solve constrained optimization problems[J]. Front Comput Sci Chin, 2009, 3(1): 38-52.
[8]	Yuhui SHI, Russ EBERHART. Monitoring of particle swarm optimization[J]. Front Comput Sci Chin, 2009, 3(1): 31-37.

Viewed

Full text

Abstract

Cited

Shared

Discussed