A Survey of Various Algorithms for Vlsi Physical Design

Authors: Rajine Swetha R, B. Shekar Babu, Sumithra Devi K.A

Abstract:

Electronic Systems are the core of everyday lives. They form an integral part in financial networks, mass transit, telephone systems, power plants and personal computers. Electronic systems are increasingly based on complex VLSI (Very Large Scale Integration) integrated circuits. Initial electronic design automation is concerned with the design and production of VLSI systems. The next important step in creating a VLSI circuit is Physical Design. The input to the physical design is a logical representation of the system under design. The output of this step is the layout of a physical package that optimally or near optimally realizes the logical representation. Physical design problems are combinatorial in nature and of large problem sizes. Darwin observed that, as variations are introduced into a population with each new generation, the less-fit individuals tend to extinct in the competition of basic necessities. This survival of fittest principle leads to evolution in species. The objective of the Genetic Algorithms (GA) is to find an optimal solution to a problem .Since GA-s are heuristic procedures that can function as optimizers, they are not guaranteed to find the optimum, but are able to find acceptable solutions for a wide range of problems. This survey paper aims at a study on Efficient Algorithms for VLSI Physical design and observes the common traits of the superior contributions.

Keywords: Genetic Algorithms, Physical Design, VLSI.

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

References:

[1] Palesi Maurizio and Tony Givargis, "Multi-Objective Design Space Exploration Using Genetic Algorithms", Proceedings of the 10thInternational Symposium on Hardware/software Codesign, ACM Press,Estes Park, Colorado, pp 67-72, 2002.
[2] W. Tan, et al., "An efficient multi-way algorithm for balance partitioning of VLSI Circuits", IEEE International Conference on Computer Design, pp 608-613, 1997.
[3] Schnecke V., Vornberger O (1997) Hybrid Genetic Algorithms for Constrained Placement Problems. IEEE Transactions on Evolutionary Computation. Vol. I. No.4. :266-277.
[4] Sandeep Singh Gill, Rajeevan Chandel, and Ashwani Chandel , " Comparative study of Ant Colony and Genetic Algorithms for VLSI circuit partitioning" , International Journal of Electrical and Computer Engineering 4:6 2009
[5] P. Mazumder, E.M. Rudnik, "Genetic Algorithms for VLSI Design, Layout and Test Automation", Pearson Education, 2003.
[6] A. E. Caldwell, A. B. Kahng and I. L. Markov, "Can Recursive Bisection Alone Produce Routable Placements?", In Proc. Design Automation Conf, pp. 477- 482, 2000.
[7] G. Karypis and V. Kumar, "Multilevel k-way hypergraph
[8] partitioning," In Proc. Design Automation Conf, pp. 343-348, 1998.
[9] G. Karypis, R. Aggarwal, V. Kumar and S. Shekhar, "Multilevel Hypergraph Partitioning: Applications in VLSI Domain," In Proc. Design Automation Conf, pp. 526-529, 1997.
[10] Chang-Tzu Lin, De-Sheng Chen and Yi-Wen Wang, "An Efficient Genetic Algorithm for Slicing Floorplan Area Optimization," In Proc. Int.Symp. on Circuits and Systems, pp.879 -882, 2002.
[11] Chang-Tzu Lin, De-Sheng Chen and Yi-Wen Wang, "An Efficient Genetic Algorithm for Slicing Floorplan Area Optimization," In Proc. Int.Symp. on Circuits and Systems, pp.II-879 -II-882, 2002.
[12] Jens Lienig, James P.Cohoon, "Lecture notes in computer science ",volume-1141,Parallel Problem Solving from NatureÔÇöPPSN IV , In pp. 839-848,1996.
[13] Sathyamoorthy S, Andaljayalakshmi G.,"Hybrid Genetic algorithm For VLSI Macro Cell layout",In 6th online World conference on soft computing in industrial applications, September 10-24,2001.
[14] Sandeep sign Gill, Dr.Rajeevan Chandel, Dr.Ashwani Chandel,"Genetic Algorithm Based Approach To circuit Partioning",International Journal of computer and electrical engineering ,Vol. 2,No. 2, April,2010.
[15] D.E. Goldberg, "Genetic Algorithms in Search, Optimization and Machine learning", Pearson Education, 2004.
[16] http://www.gigascale.org/bookshelf
[17] Chang-Tzu Lin, De-Sheng Chen and Yi-Wen Wang, "Robust Fixedoutline Floorplanning Through Evolutionary Search," In Proc. Asia and South Pacific on Design Automation Conf, pp. 42-44, 2004.
[18] Saurabh N. Adya and Igor L. Markov, "Consistent Placement of Macro- Blocks Using Floorplanning and Standard-Cell Placement," In Proc. Int. Symp. on Physical Design, pp. 12-17, 2002
[19] S.-Y. Ho, and X.-I. Chang, "An efficient generalized multiobjective evolutionary algorithm," In Proc. Genetic and Evolutionary Computation Conference, pp. 871-878, 1999