A Survey of Various Algorithms for Vlsi Physical Design

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.

Authors:

• Rajine Swetha R
• B. Shekar Babu
• Sumithra Devi K.A

Keywords:

• Genetic Algorithms
• Physical Design
• VLSI.

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