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.
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
