International Journal of Information Engineering and Electronic Business (IJIEEB)
IJIEEB Vol. 4, No. 4, 8 Aug. 2012
Cover page and Table of Contents: PDF (size: 265KB)
Memetic Programming Approach for Floorplanning Applications
Full Text (PDF, 265KB), PP.39-45
Views: 0 Downloads: 0
Author(s)
Index Terms
Floorplan problem, memetic algorithm, local search, area, delay, layout optimization
Abstract
Floorplanning is a very crucial step in modern VLSI design. It dominates the top level spatial structure of a chip and initially optimizes the interconnections. Thus a good floorplan solution among circuit modules definitely has a positive impact on the placement, Routing and even manufacturing. In this paper the classical floorplanning that usually handles only block packing to minimize silicon rate, so modern floorplanning could be formulated as a fixed outline floorplanning. It uses some algorithms such as B-TREE representation, simulated annealing and adaptive fast simulated annealing, comparing above three algorithms the better efficient solution came from adaptive fast simulated annealing, it's leads to faster and more stable convergence to the desired floorplan solutions, but the results are not an optimal solution, to get an optimal solution it's necessary to choose effective algorithm. Combining global and local search is a strategy used by many optimization approaches. Memetic algorithm is an evolutionary algorithm that includes one or more local search phases within its evolutionary cycle. The algorithm combines a hierarchical design technique, genetic algorithms, constructive techniques and advanced local search to solve VLSI floorplanning problem.
Cite This Paper
R. Varatharajan, Muthu Senthil, Perumal sankar, "Memetic Programming Approach for Floorplanning Applications", International Journal of Information Engineering and Electronic Business(IJIEEB), vol.4, no.4, pp.39-45, 2012. DOI:10.5815/ijieeb.2012.04.06
Reference
[1]Hameem shanavas, "Evolutionary algorithmical approach for vlsi floorplanning problem" in international journal of computer theory and engineering,2009.
[2]A. B. Kahng, "Classical floorplanning harmful?," in Proc. Int. Symp.Phys. Design, 2000, pp. 207–213.
[3]R. H. J. M. Otten, "Efficient floorplan optimization," in Proc. Int. Conf.Comput. Design, 1983, pp. 499–502.
[4]S. N. Adya and I. L. Markov, "Fixed-outline floorplanning through better local search," in Proc. Int. Conf. Comput. Design, 2001, pp. 328–334.
[5]H. H. Chan, S. N. Adya, and I. L. Markov, "Are floorplan representations important in digital design?," in Proc. ACM Int. Symp. Physical Design, San Francisco, CA, Apr. 2005, pp. 129–136.
[6]Jackey Z,yan and chris chu " Deferred decision making enabled fixed outline floorplanning algorithm"IEEE Transcation on computer aided design of integrated circuits and systems,march 2010
[7]B. Kahng, "Classical floorplanning harmful?," in Proc. ACM Int. Symp.Physical Design, San Diego, CA, Apr. 2000, pp. 207–213.
[8]S. N. Adya and I. L. Markov, "Fixed- outline floorplanning through better local search," in Proc. IEEE Int. Conf. Computer Design, Austin,TX, 2001, pp. 328–334.
[9]Chang-Tzu Lin, De Sheng Chen, Yiwen.Wang, "An Efficient Genetic Algorithm for Slicing Floorplan Area Optimization"Proceedings of the International Symposium on Circuits And Systems,pp. 879-882, 2002.
[10]Changq Tzu Lin, De Sheng Chen, Yiwen Wangs, Hsin-Hsien Ho "Modern Floorplanning with Abutment and Fixed-Outline Constraints", Proceedings of the International Symposium on Circuits and Systems, pp. 879-882, 2002.
[11]S. Kirpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by simulated annealing," Science, vol. 220, no. 4598, pp. 671–680, May 1983.
[12]J. H. Y. Law and E. F. Y. Young, "Multi-bend bus driven floorplanning," in Proc. ACM Int. Symp. Physical Design, San Francisco, CA, Apr. 2005,pp. 113–120.
[13]C.-T. Lin, D.-S. Chen, and Y.-W. Wang, "Robust fixed-outline floorplanning through evolutionary search," in Proc. IEEE/ACM Asia andSouth Pacific Design Automation Conf., Yokohama, Japan, Jan. 2004,pp. 42–44.
[14]H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, "Rectanglepacking based module placement," in Proc.IEEE/ACM Int. Conf.Computer-Aided Design, San Jose, CA, Nov. 1995, pp. 472–479.
[15]Parquet: Fixed-Outline Floorplanner. [Online]. Available: http://vlsicad.eecs.umich.edu/BK/parquet/
[16]F. Rafiq, M. Chrzanowska-Jeske, H. H. Yang, and N. Sherwani, "Busbased integrated floorplanning," in Proc. IEEE Int. Symp. Circuits and Systems, Phoenix-Scottsdale, AZ, May 2002, pp. 875–878.
[17]S. M. Sait and H. Youssef, VLSI Physical Design Automation: Theory and Practice. Singapore: World Scientific, 1999.
[18]C. Sechen and A. Sangiovanni-Vincentelli, "The TimberWolf placement and routing package," IEEE J. Solid-State Circuits, vol. SSC-20, no. 2,pp. 510–522, Apr. 1985.
[19]Stephen Coe, Shawki Areibi, Medhat Moussa "A Hardware Memetic Accelerator for VLSI Circuit Partitioning" University of Guelph,School of Engineering, Guelph, Canada, 2003.
[20]T.C.Chen andY.W.Chang, "Modern floor planning based on fast simulated annealing", in Procz ACM Int Symp Physical Design San Francisco, CA, Apr.2005, and pp 104–112.
[21]Natalio Krasnogor and Jim Smith, "A Tutorial for Competent Memetic Algorithms: Model, Taxonomy and Design Issues", IEEE transactionson evolutionary computation, vol.a, no.b, ccc200d, March 2005.
[22]Natalio Krasnogor, Alberto Aragon and Joaquin Pacheco. "MEMETIC ALGORITHMS", School of Computer Science and I.T. University of Nottingham. England 2005.
[23]Tung-Chieh Chen, Student Member IEEE, and Yao Wen Chang,"Modern floor planning based on B-tree and fast simulated annealing"Member IEEE transactions on computer-aided design of integrated circuits and systems, vol.25, April 2006.
[24]Maolin Tang, Member IEEE, and XinYao, Fellow IEEE "A Memetic Algorithm for VLSI Floor planning". IEEE transactions on systems, man, and cyber net, vol.37, no.1, february2007.
[25]The MCNC Benchmark Problems for VLSI Floorplanning. [Online]. Available: http://www.mcnc.org.