Solving Cell Placement Problem Using Harmony Search Algorithms
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.
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
K. Shahookar, P. Mazumder, “VLSI Cell Placement Techniques”, ACM Computer Survey, Vol. 23, No. 2, pp. 143–220, 1991
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
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
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
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
Z. W. Geem, “Optimal cost design of water distribution networks using harmony search”, Engineering Optimization, Vol. 38, No. 3, pp. 259-277, 2010
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
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
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
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
M. Padberg, “Harmony Search Algorithms for binary optimization problems”, in: Operations Research Proceedings, pp. 343–348, Springer, 2012
M. G. H. Omran, M. Mahdavi, “Global-best harmony search”, Applied Mathematics and Computation, Vol. 198, No. 2, pp. 643–656, 2008
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
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
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
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
PDF Downloads 82
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.