Solving Cell Placement Problem Using Harmony Search Algorithms

Authors

  • R. M. Al Qasem Department of Computer Engineering, Al Balqa Applied University, Amman, Jordan
  • S. M. Massadeh Department of Computer Engineering, Al Balqa Applied University, Amman, Jordan
Volume: 8 | Issue: 4 | Pages: 3172-3176 | August 2018 | https://doi.org/10.48084/etasr.2113

Abstract

Cell placement is a phase in the chip design process, in which cells are assigned to physical locations. A placement algorithm is a way that satisfies the objectives and minimizes the total area while keeping enough space for routing. Cell placement is an NP-complete problem of very large size. In order to solve this problem, diversified heuristic algorithms are used. In this work, a new algorithm is proposed based on the harmony search algorithm. The harmony search algorithm mimics music improvisation process to find the optimal solution. Cell placement problem has many constraints, so in this work, the harmony search algorithm is modified to adapt to these constraints. Experiment results show that this algorithm is efficient for solving cell placement and is characterized by good performance, solution quality and likelihood of optimality.

Keywords:

optimization, harmony search, cell placement

Downloads

Download data is not yet available.

References

T. W. Manikas, M. H. Mickle, “A Genetic Algorithm for Mixed Macro and Standard Cell Placement”, 45th Midwest Symposium on Circuits and Systems, Vol. 2, pp 115-118, 2002

G. Nan, M. Li, D. Lin, J. Kou, “Adaptive Simulated Annealing for Standard Cell Placement”, Advances in Natural Computation, Lecture Notes in Computer Science, Vol. 3612, pp. 943-947, Springer, 2005 DOI: https://doi.org/10.1007/11539902_117

K. Shahookar, P. Mazumder, “VLSI Cell Placement Techniques”, ACM Computer Survey, Vol. 23, No. 2, pp. 143–220, 1991 DOI: https://doi.org/10.1145/103724.103725

Z. W. Geem, J. H. Kim, G. V. Loganathan, “A new heuristic optimization algorithm: harmony search,” Simulation, Vol. 76, No. 2, pp. 60–68, 2001 DOI: https://doi.org/10.1177/003754970107600201

K. S. Lee, Z. W. Geem, “A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice”, Computer Methods in Applied Mechanics and Engineering, Vol. 194, No. 36–38, pp. 3902–3933, 2005 DOI: https://doi.org/10.1016/j.cma.2004.09.007

K. S. Lee, Z. W. Geem, “A new structural optimization method based on the harmony search algorithm”, Computers and Structures, Vol. 82, No. 9-10, pp. 781–798, 2004 DOI: https://doi.org/10.1016/j.compstruc.2004.01.002

Z. W. Geem, C. L. Tseng, Y. Park, “Harmony search for generalized orienteering problem: best touring in China”, Lecture Notes in Computer Science, Vol. 3612, pp. 741–750, Springer, 2005 DOI: https://doi.org/10.1007/11539902_91

Z. W. Geem, “Optimal cost design of water distribution networks using harmony search”, Engineering Optimization, Vol. 38, No. 3, pp. 259-277, 2010 DOI: https://doi.org/10.1080/03052150500467430

Z. W. Geem, J. H. Kim, G. V. Loganathan, “Harmony search optimization: application to pipe network design”, International Journal of Modelling and Simulation, Vol. 22, No. 2, pp. 125–133, 2002 DOI: https://doi.org/10.1080/02286203.2002.11442233

Z. W. Geem, K. S. Lee, Y. Park, “Application of Harmony Search to Vehicle Routing”, American Journal of Applied Sciences, Vol. 2, No. 12, pp. 1552–1557, 2005 DOI: https://doi.org/10.3844/ajassp.2005.1552.1557

X. Wang, X. Z. Gao, S. J. Ovaska, “Fusion of clonal selection algorithm and harmony search method in optimisation of fuzzy classification systems”, International Journal of Bio-Inspired Computation, Vol. 1, No. 1-2, pp. 80–88, 2009 DOI: https://doi.org/10.1504/IJBIC.2009.022776

Z. W. Geem, “Novel derivative of harmony search algorithm for discrete design variables”, Applied Mathematics and Computation, Vol. 199, No. 1, pp. 223–230, 2008 DOI: https://doi.org/10.1016/j.amc.2007.09.049

M. Padberg, “Harmony Search Algorithms for binary optimization problems”, in: Operations Research Proceedings, pp. 343–348, Springer, 2012 DOI: https://doi.org/10.1007/978-3-642-29210-1_55

M. G. H. Omran, M. Mahdavi, “Global-best harmony search”, Applied Mathematics and Computation, Vol. 198, No. 2, pp. 643–656, 2008 DOI: https://doi.org/10.1016/j.amc.2007.09.004

Q. K. Pan, P. N. Suganthan, J. J. Liang, M. F. Tasgetiren, “A local-best harmony search algorithm with dynamic subpopulations”, Engineering Optimization, Vol. 42, No. 2, pp. 101–117, 2010 DOI: https://doi.org/10.1080/03052150903104366

D. F. Wong, C. L. Liu, “A New Algorithm for Floorplan Design”, 23rd ACM/IEEE Design Automation Conference, Las Vegas, Nevada, USA, pp. 101–107, February 6, 1986 DOI: https://doi.org/10.1109/DAC.1986.1586075

J. P. Cohoon, S. U. Hedge, W. N. Martin, D. S. Richards, “Distributed genetic algorithms for the floorplan design problem”, IEEE Transactions on Computer-Aided Design, Vol. 10, No. 4, pp. 483–492, 1991 DOI: https://doi.org/10.1109/43.75631

M. Mahdavi, M. Fesanghary, E. Damangir, “An improved harmony search algorithm for solving optimization problems”, Applied Mathematics and Computation, Vol. 188, No. 2, pp. 1567–1579, 2007 DOI: https://doi.org/10.1016/j.amc.2006.11.033

Downloads

How to Cite

[1]
R. M. Al Qasem and S. M. Massadeh, “Solving Cell Placement Problem Using Harmony Search Algorithms”, Eng. Technol. Appl. Sci. Res., vol. 8, no. 4, pp. 3172–3176, Aug. 2018.

Metrics

Abstract Views: 339
PDF Downloads: 222

Metrics Information
Bookmark and Share