Music-Inspired Harmony Search Algorithm for Fixed Outline Non-Slicing VLSI Floorplanning

Authors: K. Sivasubramanian, K. B. Jayanthi

Abstract:

Floorplanning plays a vital role in the physical design process of Very Large Scale Integrated (VLSI) chips. It is an essential design step to estimate the chip area prior to the optimized placement of digital blocks and their interconnections. Since VLSI floorplanning is an NP-hard problem, many optimization techniques were adopted in the literature. In this work, a music-inspired Harmony Search (HS) algorithm is used for the fixed die outline constrained floorplanning, with the aim of reducing the total chip area. HS draws inspiration from the musical improvisation process of searching for a perfect state of harmony. Initially, B*-tree is used to generate the primary floorplan for the given rectangular hard modules and then HS algorithm is applied to obtain an optimal solution for the efficient floorplan. The experimental results of the HS algorithm are obtained for the MCNC benchmark circuits.

Keywords: Floor planning, harmony search, non-slicing floorplan, very large scale integrated circuits.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1107443

References:

[1] H. Murata, K. Fujiyoshi and Y. Kajitani, “VLSI module placement based on rectangle-packing by the sequence-pair”, IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, no. 12, pp. 1518-1524, 1996.
[2] S. Nakatake, K. Fujiyoshi, H. Murata and Y. Kajitani, “Module placement on BSG-structure and IC layout applications”, in Proceedings of IEEE/ACM International Conf. on Computer Aided Design, pp. 484-491, 1996.
[3] P.-N. Guo, C.-K. Chengand T. Yoshimura, “An O-Tree Representation of Non-Slicing Floorplan and Its Applications,” in Proceedings of the 36th Annual ACM/IEEE Design Automation Conference (ACM, 1999, pp. 268–273, 1999.
[4] Y-C Chang, Y-W Chang, G-M Wu and S-W Wu, “B*-Trees: A New Representation for Non-Slicing Floorplans” ACM, 2000.
[5] K. S. Leeand 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–3922, 2005.
[6] S. L. Kangand 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.
[7] Z.W. Geem, J.H. Kimand G.V. Loganathan, “Harmony search optimization: application to pipe network design”, International Journal of Modeling and Simulation, vol. 22, no. 2, pp.125–133, 2002.
[8] Z. W. Geem, “Harmony search algorithm for solving Sudoku”, in Proceedings of the 11th international conference, KES 2007 and XVII Italian workshop on neural networks conference on Knowledge-based intelligent information and engineering systems: Part I. 2007, Springer- Verlag: Vietrisul Mare, Italy.
[9] W. Huang, D. Chen and R. Xu, “A new heuristic algorithm for rectangle packing” Comput. Oper.Res., vol. 34, no. 11, pp. 3270–3280, 2007.
[10] Y. Pang, C.-K. Cheng and T. Yoshimura, “An enhanced perturbing algorithm for floorplan design using the O-tree representation”, in Proceedings of the International Symposium on Physical Design, ACM, pp. 168–173, 2000.
[11] T.-C. Chen and Y.-W. Chang, “Modern floorplanning based on B*-tree and fast simulated annealing” IEEE Trans. Comput. Aided Des.Integr.Circuits Syst., vol. 25, no. 4, pp. 637–650, 2006.
[12] S. Anand, S. Saravanasankar and P. Subbaraj, “Customized simulated annealing based decision algorithms for combinatorial optimization in VLSI floorplanning problem”,Comput. Optim.Appl., vol. 52, no. 3, pp. 667–689, 2012.
[13] C.-S Hoo, K. Jeevan, V. Ganapathy and H. Ramiah.“Variable-Order Ant System for VLSI multiobjective floorplanning” Elsevier Journal on Applied Soft-Computing, vol. 13, pp. 3285–3297, 2013.
[14] Y. Ma, S. Dong, X. Hong, Y. Cai, C.-K Cheng and J. Gu, “VLSI Floorplanning with Boundary Constraints Based on Corner Block List”, IEEE, pp 509-514,2001.
[15] J. Cohoon, S. Hegde, W. Martin, and D. Richards, “Distributed genetic algorithms for the floorplan design problem,” IEEE Trans. Comput.- Aided Design Integr. Circuits Syst., vol. 10, no. 4, pp. 483–492, 1991.
[16] M. Rebaudengo and M. Reorda, “GALLO: A genetic algorithm for floorplan area optimization,” IEEE Trans. Comput.-Aided Design Integr.Circuits Syst., vol. 15, no. 8, pp. 943–951,1996.
[17] C. Valenzuela and P.Wang, “VLSI placement and area optimization using a genetic algorithm to breed normalized postfix expressions,” IEEE Trans.Evol. Comput., vol. 6, no. 4, pp. 390–401, 2002.
[18] B. Gwee and M. Lim, “A GA with heuristic based decode for IC floorplanning,” Integr., VLSI J., vol. 28, no. 2, pp. 157–172, 1999.
[19] N. Xu, X.-L Hon, S.-QDong and H.-BYu, “TSCSP: Tabu Search Algorithm for VLSI Module Placement Based on the Clustering Sequence-Pair”, IEEE, 2003.
[20] M. Tang and A. Sebastian,A genetic algorithm for VLSI floorplanning using O-tree representation. In Applications of Evolutionary Computing, Springer, Berlin,pp. 215–224, 2005.
[21] T.-Y. Sun, S.-T.Hsieh, H.-M.Wang and C.-W. Lin, “Floorplanning based on particle swarm optimization”, in IEEE Computer Society Annual Symposium on Emerging VLSI Technologies and Architectures, 2006.
[22] M. Tang and X. Yao, “A Memetic Algorithm for VLSI Floorplanning”, IEEE transactions on systems, man, and cybernetics—part b: cybernetics, vol. 37, no. 1, pp. 62-69, 2007.
[23] P. Fernando and S. Katkoori, “An Elitist Non-Dominated Sorting based Genetic Algorithm for Simultaneous Area and Wirelength Minimization in VLSI Floorplanning” In 21st International Conference on VLSI Design, India, IEEE Computer Society, pp. 337-342, 2008.
[24] G. Chen, W. Guo, H. Cheng, X. Fen and X. Fang, “VLSI Floorplanning Based on Particle Swarm Optimization” in Proceedings of 3rd International Conference on Intelligent System and Knowledge Engineering, IEEE, pp. 1020-1025, 2008.
[25] G. Chen, W. Guo and Y. Chen, “A PSO-based intelligent decision algorithm for VLSI floorplanning”, Springer, Soft Computing, pp. 1329–1337, 2010.
[26] J. Chen, W. Zhu, and M. M. Ali, “A Hybrid Simulated Annealing Algorithm for Nonslicing VLSI Floorplanning”, IEEE transactions on systems, man and cybernetics—part c: applications and reviews, vol. 41, no. 4, pp. 544-553, 2011.
[27] D. Sengupta, A. Veneris, S. Wilton, A. Ivanov and R. Saleh, “Sequence Pair Based Voltage Island Floorplanning”, in Proceedings of the 2011 International Green Computing Conference and Workshops, IEEE computer society Washington, pp. 1-6, 2011.
[28] I.H. Shanavas and R.K. Gnanamurthy, “Wirelength Minimization in Partitioning and Floorplanning Using Evolutionary Algorithms” Hindawi Publishing Corporation VLSI Design, vol. 10, Article ID 896241, 9 pages, 2011.
[29] Z. Chen, J. Chen, W. Guo and G. Chen, “A Coevolutionary Multi- Objective PSO algorithm for VLSI Floorplanning” 8th International Conference on Natural Computation (ICNC), IEEE, pp. 712-728, 2012.
[30] T. Singha, H. S. Dutta and M. De, “Optimization of Floor-planning using Genetic Algorithm” Procedia Technology, vol. 4, pp. 825 – 829, 2012.
[31] P.Sivaranjani and A.S. Kumar,“Thermal-Aware Non-slicing VLSI Floorplanning Using a Smart Decision-Making PSO-GA Based Hybrid Algorithm” Circuits Syst Signal Process, DOI 10.1007/s00034-015- 0020-x, 2015.
[32] Z.W. Geem, J.H. Kimand G.V. Loganathan,“A new heuristic optimization algorithm: harmony search”, Simulation,vol. 76, no. 2, pp.60–68, 2001.
[33] J. Fourie, S. Mills, and R. Green, “Harmony filter: a robust visual tracking system using the improved harmony search algorithm,” Image and Vision Computing, vol. 28, no. 12, pp. 1702–1716, 2010.
[34] J. Chen and W. Zhu, “A Hybrid Genetic Algorithm for VLSI Floorplanning”, in International Conference on Intelligent Computing and Intelligent Systems (ICIS), IEEE, 2010, pp. 128-132.