A genetic algorithm based multi objective optimization technique for very large-scale integration (VLSI) circuit partitioning has been proposed. An efficient fitness function that simultaneously optimizes minimum net cut size and delay time and maximum sleep time has been worked out along with minimum power consumption. Use of bipartition has balanced the circuit perfectly. Circuit partitioning is a non-polynomial (NP) hard problem. I have used Genetic algorithm (GA)-based optimization as it shows a global optimum solution. This is a hyper graph - based solution. Since it is a part of a physical design, all the computational part including input-output (IO) pads are converted into a hyper graph. Genetic algorithm is an evolutionary optimization technique based on Darwinian Theory of natural selection. Fitness value has been evaluated and solution with low fitness value has been discarded. The method has been applied on the net list files used in ISPD’98 circuit benchmark suite where each file contained 20-30 nodes. MATLAB18a was used to code all the algorithms. The improvement of net cut size, delay and sleep time was 40.62%, 41.54% and 95.42% respectively compared to initial bipartition of circuit. Thus, the proposed methodology might be promising for current trends in VLSI circuit partitioning.

Partitioning, Genetic Algorithm, NP-hard, Net list, Sleep time, Delay Crossover, Mutation, Cut size

[1] B.W. Kernighan, S. Lin, An efficient heuristic procedure for partitioning graphs, The Bell System Technical Journal, 1970, 49: 291-372. DOI: 10.1002/j.1538-7305.1970.tb01770.x
[2] C.M. Fiducca, R.M. Mattheyses, S. Areibi, Mimetic algorithms for VLSI Physical Design: Implementation Issues. Genetic and Evolutionary computation, Proceedings of the 19th Design automation Conference, IEEE Press, 1992, 175-181.
[3] L.D.E. Goldberg, Genetic algorithms in search, optimization and machine learning. Pearson Education, 2004.
[4] S. Areibi, Mimetic algorithms for VLSI Physical Design: Implementation Issues. Genetic and Evolutionary computation Conference, San Fransisco, California, 2001, 140-145.
[5] C. Ababei, S. Navaratnasothie, K. Bazargan, G. Karypis, Multi-objective circuit partitioning for cut-size and path-base delay minimization. IEEE International Conference on Computer aided Design, 2002. DOI: 10.1109/ICCAD.2002.1167532
[6] M. Palesi, T. Givargis, Multi-objective design space exploration using genetic algorithms, Proceedings of the 10th international symposium on Hardware/software codesign, ACM Press, Estes Park, Colorado, 2002, 67-72. DOI: 10.1145/774789.774804
[7] Z.Q. Chen, Y.F. Yin, A new crossover operator for real-coded genetic algorithm with selecting breeding based on difference between individuals, Natural Computation (ICNC), 2012 Eighth International Conference, 2012, 644-648. DOI: 10.1109/ICNC.2012.6234556
[8] S.Y. Yuen, C.K. Chow, A genetic algorithm that adaptively mutates and never revisits, Evolutionary Computation, 2009, 13: 454-472. DOI: 10.1109/TEVC.2008.2003008
[9] W. Jigang, T. Srikanthan, Efficient algorithms for hardware/software partitioning to minimize hardware area, Circuits and System, 2006, IEEE Asia Pacific Conference, 1875-1878. DOI: 10.1109/APCCAS.2006.342205
[10] S.S. Gill, R. Chandel, A. Chandel, Genetic algorithm-based approach to circuit partitioning, International Journal of Computer and Electrical Engineering, 2010, 2: 1793-1863. DOI: 10.7763/IJCEE.2010.V2.136
[11] P. Arato, S. Juhasz, Z.A. Mann, D. Papp, Hardware-Software partitioning in embedded system design, International Conference on Complex, Intelligent and Software Intensive Systems, 2003, 197-202. DOI:10.1109/ISP.2003.1275838
[12] A. Prakkash, R.K. Lal, PSO: An approach to multi-objective VLSI Partitioning. Proceedings of the 2nd International Conference on Innovations in Information, Embedded and Communication systems. IEEE, 2015. DOI: 10.1109/ICIIECS.2015.7192971
[13] N. Sherwani, Algorithms for VLSI physical design automation. 3rd edition, Springer (India) Private limited, New Delhi, 2005.
[14] A.H. Farrahi, M. Sarrafzadeh, System partitioning to maximize sleep time, Proceedings of the 1995 IEEE/ACM International Conference on computer Aided Design, San Jose, California, USA, 1995, 452-455. DOI: 10.1109/ICCAD.1995.480155
[15] P. Ghafari, E. Mirhard, M. Anis, S. Areibi, M. Elmary, A low power partitioning methodology by maximizing sleep time and minimizing cut nets. IWSOC, Bauf, Alberta, Canada, 2005, 368-371. DOI: 10.1109/IWSOC.2005.15
[16] J.J. Cong, K.S. Leung, Optimal wire sizing under Elmore delay model, IEEE Transactions on Computer Aided Design of Integrated Circuits and System, 1995, 14: 3. DOI: 10.1109/DAC.1996.545625.
[17] P. Zarkesh, J.A. Davis, J.D. Meindail, Prediction of Net-Length Distribution for global interconnects, In a Heterogeneous system-on-a-chip. IEEE Transaction on VlSA Systems, 2000, 8: 6. DOI: 10.1109/92.902259
[18] K.P. Subbaraj, P. Sivasundari, S. Kumar, An effective mimetic algorithm for VLSI partitioning problem, International conference on ICTES Chennai India, 2007, 667-670.
[19] J.H. Holland, Adaption in natural and artificial system: An introductory analysis with applications to biology, control and artificial intelligence, MIT press, 1992.
ISBN:02620821