Solving Cell Placement Problem Using Harmony Search Algorithms

R. M. Al Qasem, S. M. Massadeh

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

Full Text:

PDF

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

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




eISSN: 1792-8036     pISSN: 2241-4487