Comparative Study of Ant Colony and Genetic Algorithms for VLSI Circuit Partitioning

Authors: Sandeep Singh Gill, Rajeevan Chandel, Ashwani Chandel

Abstract:

This paper presents a comparative study of Ant Colony and Genetic Algorithms for VLSI circuit bi-partitioning. Ant colony optimization is an optimization method based on behaviour of social insects [27] whereas Genetic algorithm is an evolutionary optimization technique based on Darwinian Theory of natural evolution and its concept of survival of the fittest [19]. Both the methods are stochastic in nature and have been successfully applied to solve many Non Polynomial hard problems. Results obtained show that Genetic algorithms out perform Ant Colony optimization technique when tested on the VLSI circuit bi-partitioning problem.

Keywords: Partitioning, genetic algorithm, ant colony optimization, non-polynomial hard, netlist, mutation.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1082181

References:

[1] Eugene L. Lawler, Karl N. Levitt, and James Turner, "Module Clustering to minimize delay in Digital Networks", IEEE Transactions on Computers, Vol. C-18 , No.1, pp. 47-57,Jan, 1969.
[2] B.W. Kerhinghan, S. Lin, "An efficient heuristic procedure for partitioning graphs", Bell System Tech. Journal, Vol. 49, pp. 291 - 307, Feb,1970.
[3] D.G. Schweikert and B.W. Kernighan, "A proper model for the partitioning of electrical circuits," Proc. ACM/IEEE Design Automation Workshop, pp. 57-62, 1972.
[4] C.M. Fiduccia and Mattheyses, "A Linear time heuristic for improving network partitions", Proc. 19th IEEE Design and Automation Conference, IEEE Press, Piscataway, NJ, USA , pp. 175-182, 1982..
[5] B. Krishnamurthy, "An improved min-cut algorithm for partitioning VLSI circuits", IEEE Trans. on Computers, Vol. C-33, May, 1989.
[6] L.A. Sanchis, "Multiple way network partitioning", IEEE Trans. on Computers, Vol. 38, No. 1, pp. 62-81 ,1989.
[7] Wei and Cheng, "Ratio-cut partitioning for hierarchical design", IEEE transc. on Computer Aided Design, pp. 911-921, July 1991.
[8] Jason Cong,L.Hagen, Andrew Kahng, "Net partitions yield better module partitions" , 29th ACM/IEEE Design Automation Conference , Anaheim, CA, USA , pp. 47-52 ,1992.
[9] Shawki Areibi and Anthony Vannelli, "Circuit partitioning using a tabu search approach", IEEE International Symposium on Circuits and Systems , Chicago, Illinois, pp. 1643-1646, March,1993.
[10] K.Shahookar and Mazumder "Genetic Multiway partitioning", IEEE 8th International Conference on VLSI Design, New Delhi, India, pp. 365- 369, 4-7 Jan 1995.
[11] James Cane, Theodre Manikas, "Genetic Algorithms vs Simulated Annealing: A comparison of approaches for solving circuit partitioning problem", Technical report, University of Pittsburgh.
[12] S. M. Sait, and H. Youseff, "VLSI Physical Design Automation", McGraw Hill Publishers, New Jersey, 1995.
[13] George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar, "Multilevel Hypergraph Partitioning: Applications in VLSI Domain", IEEE 34th Design Automation Conference., Anaheim, California, United States, ACM Press New York, NY, USA., pp 526-529,1997.
[14] S. Areibi, "Memetic Algorithms for VLSI Physical Design: Implementation Issues", Genetic and Evolutionary computation Conference, San Fransisco, California, pp140-145, July, 2001.
[15] S. Areibi, "Recursive and flat partitioning for VLSI circuit design", The 13th International Conference on Microelectronics, Rabat, Morocco, pp.237-240, 2001.
[16] C. Ababei, S.Navaratnasothie, K. Bazargan and G. Karypis, "Multiobjective Circuit partitioning for Cutsize and path-base delay minimization", IEEE International Conference on Computer aided Design,2002.
[17] Maurizio Palesi,Tony Givargis, "Multi-Objective Design Space Exploration Using Genetic Algorithms", Proceedings of the 10th International symposium on Hardware/software codesign, ACM Press, Estes Park, Colorado , pp. 67-72 ,2002.
[18] Greg Stitt, Roman Lysecky, Frank Vahid, "Dynamic Hardware/Software Partitioning: A First Approach" ACM/IEEE Design Automation Conference 2003, Anaheim, California, USA,pp 250-255, June 2-6, 2003.
[19] P. Mazumder, E.M. Rudnik, "Genetic Algorithms for VLSI Design, Layout and Test Automation", Pearson Education, 2003.
[20] R. Banos, C. Gil, M.G. Montoya, and J. Ortega, "A Parallel evolutionary algorithm for circuit partitioning", Proceedings of the Eleventh Euromicro conference on Parallel, Distributed, and network based Processing, 2003.
[21] Sadiq M. Sait, Aiman H.El-Maleh, and Raslan H. Al-Abaji, "Enhancing performance of iterative heuristics for VLSI net list partitioning", ICECS-2003, pp. 507-510, 2003.
[22] D. Kolar, J. Divokovic Puksec and Ivan Branica, "VLSI Circuit partitioning using Simulated annealing Algorithm", IEEE Melecon, Dubrovnik, Croatia, May 12-15, 2004.
[23] D.E. Goldberg, "Genetic Algorithms in Search, Optimization and Machine learning", Pearson Education, 2004.
[24] P. Ghafari , E. Mirhard, M.Anis, S. Areibi and M. Elmary, " A low power partitioning methodology by maximizing sleep time and minimizing cut nets", IWSOC, Bauf, Alberta, Canada, pp. 368-371, July, 2005.
[25] Naveed Sherwani, "Algorithms for VLSI Physical Design and Automation", Third edition, Springer (India) Private Limited, New Delhi, 2005
[26] G. Wang, W. Gang and R.Kastner, "Application Partitioning on programmable platforms using Ant Colony Optimization", Journal of Embedded Computing, Vol.2, Issue 1, 2006.
[27] Marco Dorigo and Thomas Stutzle, "Ant Colony Optimization", Prentice Hall of India Private Limited, 2006.
[28] Shawki Areibi and Fujian Ali, "A Hardware/Software co-design approach for VLSI circuit partitioning", IEEE International Workshop on SoC, Cairo, Egypt, pp.179-184, December, 2006.
[29] K.A. Sumitra Devi, N.P. Banashree and Annamma Abraham, "Comparative Study of Evolutionary Model and Clustering Methods in Circuit Partitioning Pertaining to VLSI Design", Proceeding of World Academy of Science, Engineering and Technology, April, 2007.
[30] http://www.gigascale.org/bookshelf