Call for Paper - March 2022 Edition
IJCA solicits original research papers for the March 2022 Edition. Last date of manuscript submission is February 22, 2022. Read More

Performance Enhancement of Standard Cell Placement Techniques using Memetic Algorithm

Print
PDF
Evolutionary Computation for Optimization Techniques
© 2010 by IJCA Journal
Number 2 - Article 8
Year of Publication: 2010
Authors:
Aaquil Bunglowala
Dr. B. M. Singhi
Dr. Ajay Verma
10.5120/1535-138

Aaquil Bunglowala, Dr. B M Singhi and Dr. Ajay Verma. Performance Enhancement of Standard Cell Placement Techniques using Memetic Algorithm. IJCA Special Issue on Evolutionary Computation (2):83–86, 2010. Full text available. BibTeX

@article{key:article,
	author = {Aaquil Bunglowala and Dr. B. M. Singhi and Dr. Ajay Verma},
	title = {Performance Enhancement of Standard Cell Placement Techniques using Memetic Algorithm},
	journal = {IJCA Special Issue on Evolutionary Computation},
	year = {2010},
	number = {2},
	pages = {83--86},
	note = {Full text available}
}

Abstract

The growing complexity in the electronic hardware now necessitates in improving the performance of searching algorithms. Genetic algorithms do not guarantee global optimum solution to NP-Hard problems but are generally good at finding acceptable solution to problems. In complex combinatorial spaces, hybridization with other optimization techniques can greatly improve the efficiency of search. Memetic algorithm (MA) is an improvisation over genetic algorithms (GA) that combines global and local search by using evolutionary algorithms to perform exploration while the local search methods are used for exploitation. Here, exploitation is the process of visiting entirely new regions of a search space where the gain can also be high.

This paper discusses the (MAs) as a solution to Standard Cell Placement (SCP) problem and procedures are laid down to strike a balance between genetic search and local search in MAs. A comparison of MA with the already established results for SCP using conventional and Hybrid techniques by the author depicts improvement in the performance of SCP algorithm in terms of solution quality and computing speed. About 15% improvement in overall wire-length was observed along side it being 25% faster over the Tabu Search (TS) algorithm discussed in previous works of the author.

Reference

  • Beumont, O., Legrand, A. and Robert, Y., “Optimal algorithms for scheduling divisible workloads on heterogeneous systems”, Proceedings of The International Parallel and Distributed Processing Symposium, 2003
  • Areibi, S., Bao, X., Grewal, G., Banerji, D., Du, P., “A Comparison of Heuristics for FPGA Placement”, ACTA International Journal of Computers and Applications
  • Bunglowala, A., Singhi, B.M. et. al, “Performance Evaluation and Comparison and Improvement of Standard Cell Placement in VLSI Design”, International Conference on Emerging Trends in Engineering and Technology, July 2008 [also published on CSDL, IEEE]
  • Bunglowala, A., Singhi, B.M., “A Solution to combinatorial Optimization Problem using Memetic Algorithms”, International Journal of Computer System Applications [IJCSA], ICAC, February 2008.
  • Casanova, H., Legrand, A., Zagorodnov, D. and Berman, F., “Heuristics for scheduling parameter sweep applications in Grid environments”, Heterogeneous Computing Workshop 2000, IEEE Computer Society Press, pp. 349-363.
  • Cohoon, J.P. and Paris, W.D., “Genetic Placement”, Proceedings of IEEE International Conference on Computer Aided Design, Santa Clara, 1986, p.p. 422-425
  • Donath, W.E., “Complexity Theory and Design Automation”, Proceedings of 17th Design Automation Conference, 1980
  • Dutt, N.D. and Gajski, D.D., “Design Synthesis and Silicon Compilation”, IEEE Design and Test of Computers, 1990, p.p. 8-23
  • “First workshop on memetic algorithms (WOMA I),” Proc. 2000 Genetic and Evolutionary Computation Conference Workshop Program, pp. 95–130, July 8, 2000
  • Gajski, D.D., “New VLSI Tools” Guest Editor’s Introduction, IEEE Computers, 1983, p.p. 11-14
  • Garey, M.R. and Johnson, D.S., “Computers and Intractability”, A Guide to the Theory of NP-Completeness, San Francisco, 1979
  • Goldberg, D. E. and Voessner, S., “Optimizing global-local search hybrids,” in Proc. 1999 Genetic and Evolutionary Computation Conf., Orlando, FL, July 13–17, 1999, pp. 220–228.
  • Land, M.W.S., “Evolutionary algorithms with local search for combinatorial optimization,” Ph.D. dissertation, Univ. of California, San Diego, 1998.
  • Leighton, F.T., “Complexity Issues in VLSI”, Cambridge, 1983
  • Lengauer, T. “Combinatorial Algorithm for Integrated Circuit Layout”, Chichester, New York, 1990
  • Sahni, S. and Bhatt, A., “The Complexity of Design Automation Problems”, Proceedings of 17th Design Automation Conference, 1980, p.p. 402-411
  • Shahookar, K. and Mazumder, P. “VLSI Placement Techniques”, ACM Computing Serveys 1991, p.p. 143-220
  • Shewani, N.A., “Algorithms for VLSI Physical Design Automation”, Boston, 1993
  • Tagliarini, G.A., Christ, J.F. and Page, E.W., “Optimization using Neural Networks”, IEEE Transaction on Computers, 1991, p.p. 1347-1358