Music-Inspired Harmony Search Algorithm for Fixed Outline Non-Slicing VLSI Floorplanning
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.
[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.
[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.
@article{"International Journal of Electrical, Electronic and Communication Sciences:70344", author = "K. Sivasubramanian and K. B. Jayanthi", title = "Music-Inspired Harmony Search Algorithm for Fixed Outline Non-Slicing VLSI Floorplanning", 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.", volume = "9", number = "6", pages = "587-8", }
