Comparative Study of Ant Colony and Genetic Algorithms for VLSI Circuit Partitioning
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.
[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
[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
@article{"International Journal of Information, Control and Computer Sciences:63014", author = "Sandeep Singh Gill and Rajeevan Chandel and Ashwani Chandel", title = "Comparative Study of Ant Colony and Genetic Algorithms for VLSI Circuit Partitioning", 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.", volume = "3", number = "4", pages = "1203-5", }
