|
|
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 |
|
|
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
|
|
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
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|