Solving Cell Placement Problem Using Harmony Search Algorithms
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 placementDownloads
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
License
Authors who publish with this journal agree to the following terms:
- Authors retain the copyright and grant the journal the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) after its publication in ETASR with an acknowledgement of its initial publication in this journal.
