The week's pick
Reseach Article
Multi-Objective Optimization of Standard Cell Placement using Memetic Algorithm
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 19 - Number 7 |
| Year of Publication: 2011 |
| Authors: Aaquil Bunglowala, Brijmohan Singhi, Ajay Verma |
10.5120/2372-3122
|
Aaquil Bunglowala, Brijmohan Singhi, Ajay Verma . Multi-Objective Optimization of Standard Cell Placement using Memetic Algorithm. International Journal of Computer Applications. 19, 7 ( April 2011), 31-34. DOI=10.5120/2372-3122
Abstract
Beyond the optimization of single parameter (usually the wire-length) in Standard Cell Placement (SCP), focus in the present work is laid on the optimization of speed, power, and the wire length. As discussed in our previous work of hybrid algorithms for single objective optimization of SCP the main advantage of hybridization is the improvement in convergence speed to Pareto front although it leads to increase in computation time per generation. Memetic Algorithm (MA) is a hybrid of Genetic Algorithm (GA) & Local search (LS) wherein we need to strike a right balance of the two for optimum solution. In this paper we work on our previous GA based multi-objective SCP algorithm [2] for simultaneous optimization of power, speed and wire length while maintaining the layout width as constant by choosing initial population to be alleles of high fitness value and apply proper local search to all the members of initial population. Further we compare the results with previously established GA based algorithm by applying the two on ami20, ami33 and ami120 cell library instances. The Memetic algorithm is found to give better results with 10% improvement in wire-length, 7.5% lesser delay and power consumption reduction by nearly 6%.
References
- A. E. Caldwell, A. B. Kahng, and I. L. Markov, "Can Recursive Bisection Alone Produce Routable Placements" Proc.of Design Automation Conference,pp.477-482, 2000.
- Bunglowala, A., Singhi, B. M., “Standard Cell Placement using Iterative & Constructive Heuristics for Multi-Objective Optimization”, published in International Journal of Electronics Engineering, 2(1),2010,pp. 131-135.
- Bunglowala, A., Singhi, B. M., “Performance Evaluation and Comparison and Improvement of Standard Cell Placement Techniques in VLSI Design”, ICETET-IEEE Computer Society, pp. 468-473, 2008.
- G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, "Multilevel Hypergraph Partitioning: Application in VLSI Design," In Proc. of Design Automation Conference, pp. 526-529, 1997.
- H. Ishibuchi and T. Murata, “Multi-objective genetic local search algorithm,” in Proc. of 3rd IEEE Conf. on Evolutionary Computation, Nagoya, Japan, pp 119-124, 1996
- J. Y Sayah et. al., "Design planning for high-performance ASICs", In IBM Journal of Research and Development, Vol. 40, No. 4, pp. 431-452, 1996.
- K. Shahookar and P. Mazumder. VLSI Cell Placement Techniques. ACM Computing Surveys,2(23):143-220, June 1991.
- Sadiq M. Sait and Habib Youssef. Iterative ComputerAlgorithms with Applications in Engineering: Solving Combinatorial Optimization Problems. IEEE Computer Society Press, California, December 1999.
- Virtual-Silicon Technology Inc., http://www.virtual-silicon.com.
- X. Yang, B. Choi, and M. Sarrafzadeh, "Timing-Driven Placement using Design Hierarchy Guided Constraint Generation," In Proc. Int’l Conference on Computer-Aided Design, pp. 177-180, 2002
Index Terms
Keywords