{"title":"Comparative Study of Ant Colony and Genetic Algorithms for VLSI Circuit Partitioning","authors":"Sandeep Singh Gill, Rajeevan Chandel, Ashwani Chandel","volume":28,"journal":"International Journal of Electrical and Computer Engineering","pagesStart":1149,"pagesEnd":1154,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/14013","abstract":"<p>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.<\/p>\r\n","references":"[1] Eugene L. Lawler, Karl N. Levitt, and James Turner, \"Module\r\nClustering to minimize delay in Digital Networks\", IEEE Transactions\r\non Computers, Vol. C-18 , No.1, pp. 47-57,Jan, 1969.\r\n[2] B.W. Kerhinghan, S. Lin, \"An efficient heuristic procedure for\r\npartitioning graphs\", Bell System Tech. Journal, Vol. 49, pp. 291 - 307,\r\nFeb,1970.\r\n[3] D.G. Schweikert and B.W. Kernighan, \"A proper model for the\r\npartitioning of electrical circuits,\" Proc. ACM\/IEEE Design Automation\r\nWorkshop, pp. 57-62, 1972.\r\n[4] C.M. Fiduccia and Mattheyses, \"A Linear time heuristic for improving\r\nnetwork partitions\", Proc. 19th IEEE Design and Automation\r\nConference, IEEE Press, Piscataway, NJ, USA , pp. 175-182, 1982..\r\n[5] B. Krishnamurthy, \"An improved min-cut algorithm for partitioning\r\nVLSI circuits\", IEEE Trans. on Computers, Vol. C-33, May, 1989.\r\n[6] L.A. Sanchis, \"Multiple way network partitioning\", IEEE Trans. on\r\nComputers, Vol. 38, No. 1, pp. 62-81 ,1989.\r\n[7] Wei and Cheng, \"Ratio-cut partitioning for hierarchical design\", IEEE\r\ntransc. on Computer Aided Design, pp. 911-921, July 1991.\r\n[8] Jason Cong,L.Hagen, Andrew Kahng, \"Net partitions yield better\r\nmodule partitions\" , 29th ACM\/IEEE Design Automation Conference ,\r\nAnaheim, CA, USA , pp. 47-52 ,1992.\r\n[9] Shawki Areibi and Anthony Vannelli, \"Circuit partitioning using a tabu\r\nsearch approach\", IEEE International Symposium on Circuits and\r\nSystems , Chicago, Illinois, pp. 1643-1646, March,1993.\r\n[10] K.Shahookar and Mazumder \"Genetic Multiway partitioning\", IEEE 8th\r\nInternational Conference on VLSI Design, New Delhi, India, pp. 365-\r\n369, 4-7 Jan 1995.\r\n[11] James Cane, Theodre Manikas, \"Genetic Algorithms vs Simulated\r\nAnnealing: A comparison of approaches for solving circuit partitioning\r\nproblem\", Technical report, University of Pittsburgh.\r\n[12] S. M. Sait, and H. Youseff, \"VLSI Physical Design Automation\",\r\nMcGraw Hill Publishers, New Jersey, 1995.\r\n[13] George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar,\r\n\"Multilevel Hypergraph Partitioning: Applications in VLSI Domain\",\r\nIEEE 34th Design Automation Conference., Anaheim, California,\r\nUnited States, ACM Press New York, NY, USA., pp 526-529,1997.\r\n[14] S. Areibi, \"Memetic Algorithms for VLSI Physical Design:\r\nImplementation Issues\", Genetic and Evolutionary computation\r\nConference, San Fransisco, California, pp140-145, July, 2001.\r\n[15] S. Areibi, \"Recursive and flat partitioning for VLSI circuit design\", The\r\n13th International Conference on Microelectronics, Rabat, Morocco,\r\npp.237-240, 2001.\r\n[16] C. Ababei, S.Navaratnasothie, K. Bazargan and G. Karypis, \"Multiobjective\r\nCircuit partitioning for Cutsize and path-base delay\r\nminimization\", IEEE International Conference on Computer aided\r\nDesign,2002.\r\n[17] Maurizio Palesi,Tony Givargis, \"Multi-Objective Design Space\r\nExploration Using Genetic Algorithms\", Proceedings of the 10th\r\nInternational symposium on Hardware\/software codesign, ACM Press,\r\nEstes Park, Colorado , pp. 67-72 ,2002.\r\n[18] Greg Stitt, Roman Lysecky, Frank Vahid, \"Dynamic Hardware\/Software\r\nPartitioning: A First Approach\" ACM\/IEEE Design Automation\r\nConference 2003, Anaheim, California, USA,pp 250-255, June 2-6,\r\n2003.\r\n[19] P. Mazumder, E.M. Rudnik, \"Genetic Algorithms for VLSI Design,\r\nLayout and Test Automation\", Pearson Education, 2003.\r\n[20] R. Banos, C. Gil, M.G. Montoya, and J. Ortega, \"A Parallel evolutionary\r\nalgorithm for circuit partitioning\", Proceedings of the Eleventh\r\nEuromicro conference on Parallel, Distributed, and network based\r\nProcessing, 2003.\r\n[21] Sadiq M. Sait, Aiman H.El-Maleh, and Raslan H. Al-Abaji, \"Enhancing\r\nperformance of iterative heuristics for VLSI net list partitioning\",\r\nICECS-2003, pp. 507-510, 2003.\r\n[22] D. Kolar, J. Divokovic Puksec and Ivan Branica, \"VLSI Circuit\r\npartitioning using Simulated annealing Algorithm\", IEEE Melecon,\r\nDubrovnik, Croatia, May 12-15, 2004.\r\n[23] D.E. Goldberg, \"Genetic Algorithms in Search, Optimization and\r\nMachine learning\", Pearson Education, 2004.\r\n[24] P. Ghafari , E. Mirhard, M.Anis, S. Areibi and M. Elmary, \" A low\r\npower partitioning methodology by maximizing sleep time and\r\nminimizing cut nets\", IWSOC, Bauf, Alberta, Canada, pp. 368-371, July,\r\n2005.\r\n[25] Naveed Sherwani, \"Algorithms for VLSI Physical Design and\r\nAutomation\", Third edition, Springer (India) Private Limited, New\r\nDelhi, 2005\r\n[26] G. Wang, W. Gang and R.Kastner, \"Application Partitioning on\r\nprogrammable platforms using Ant Colony Optimization\", Journal of\r\nEmbedded Computing, Vol.2, Issue 1, 2006.\r\n[27] Marco Dorigo and Thomas Stutzle, \"Ant Colony Optimization\", Prentice\r\nHall of India Private Limited, 2006.\r\n[28] Shawki Areibi and Fujian Ali, \"A Hardware\/Software co-design\r\napproach for VLSI circuit partitioning\", IEEE International Workshop\r\non SoC, Cairo, Egypt, pp.179-184, December, 2006.\r\n[29] K.A. Sumitra Devi, N.P. Banashree and Annamma Abraham,\r\n\"Comparative Study of Evolutionary Model and Clustering Methods in\r\nCircuit Partitioning Pertaining to VLSI Design\", Proceeding of World\r\nAcademy of Science, Engineering and Technology, April, 2007.\r\n[30] http:\/\/www.gigascale.org\/bookshelf","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 28, 2009"}