The selection of an appropriate partitioning approach significantly impacts integrated circuit (IC) size and performance. Inaccurate initial partitioning may lead to cascading issues throughout the physical design flow, affecting the performance of subsequent stages in the physical design process. Clustering the chip design into functional units and placing heavily communicating units in proximity can optimize wiring efficiency and improve overall chip performance. In this paper, we introduce a unique application of the bat algorithm (BA) to address the minimum cut cost in partitioning problems. Further, the BA is a nature-inspired metaheuristic algorithm capable of handling intricate and restricted optimization scenarios. The performance of the proposed partitioning with the BA was verified with several experiments on the MCNC and ISPD-98 benchmark datasets.
Citation: Velamala Pavan Kumar, Aravindhan Alagarsamy. A balanced computational approach for multilevel VLSI circuit partitioning strategy with bat algorithm[J]. AIMS Electronics and Electrical Engineering, 2025, 9(3): 390-404. doi: 10.3934/electreng.2025018
The selection of an appropriate partitioning approach significantly impacts integrated circuit (IC) size and performance. Inaccurate initial partitioning may lead to cascading issues throughout the physical design flow, affecting the performance of subsequent stages in the physical design process. Clustering the chip design into functional units and placing heavily communicating units in proximity can optimize wiring efficiency and improve overall chip performance. In this paper, we introduce a unique application of the bat algorithm (BA) to address the minimum cut cost in partitioning problems. Further, the BA is a nature-inspired metaheuristic algorithm capable of handling intricate and restricted optimization scenarios. The performance of the proposed partitioning with the BA was verified with several experiments on the MCNC and ISPD-98 benchmark datasets.
| [1] | Sait SM, Habib Youssef (1995) VLSI Physical Design Automation: Theory and Practice, 1 Eds., World Scientific, New York: IEEE Press, 35-75. |
| [2] |
Yodtean A, Chantngarm P (2004) Hybrid algorithm for bisection circuit partitioning. Proceedings of IEEE Region 10 Conference 500: 324-327. https://doi.org/10.1109/TENCON.2004.1414935 doi: 10.1109/TENCON.2004.1414935
|
| [3] |
Manikandan R, Vijay L (2014) Effective clustering algorithms for VLSI circuit partitioning problems. Contemporary Engineering Sciences 7: 923-929. https://doi.org/10.12988/ces.2014.4653 doi: 10.12988/ces.2014.4653
|
| [4] | Rajeswari P, Chandra T (2018) Memetic multilevel hypergraph partitioning. Proceedings of the Genetic and Evolutionary Computation Conference 347-354. https://doi.org/10.1145/3205455.3205475 |
| [5] |
Yang XS (2010) A New Metaheuristic Bat-Inspired Algorithm. Studies in Computational Intelligence 284: 65-74. https://doi.org/10.1007/978-3-642-12538-6_6 doi: 10.1007/978-3-642-12538-6_6
|
| [6] | Alagarsamy A, Gopalakrishnan L (2018) MBA: A new cluster based bandwidth and power aware mapping for 2D NoC. Proceedings of Int. Conf. on Circuits and Systems in Digital Enterprise Technology, 1-5. https://doi.org/10.1109/ICCSDET.2018.8821150 |
| [7] |
Shehab M, Abu-Hashem MA, Shambour MK, Alsalibi AI, Alomari OA, Gupta JN, et al. (2023) A Comprehensive Review of Bat Inspired Algorithm: Variants, Applications, and Hybridization. Arch Comput Method Eng 30: 765-797. https://doi.org/10.1007/s11831-022-09817-5 doi: 10.1007/s11831-022-09817-5
|
| [8] | Sinha B, Laskar NM, Sen R, Baishnab KL (2015) Heuristics in Physical Design Partitioning: A review. Int. Conf. on Innovations in Information, Embedded and Communication Systems, 1-5. https://doi.org/10.1109/ICIIECS.2015.7192900 |
| [9] | Shanavas IH, Gnanamurthy RK, Thangaraj TS (2010) A Novel Approach to Find the Best Fit for VLSI Partitioning - Physical Design. Int. Conf. on Advances in Recent Technologies in Communication and Computing, 330-332. https://doi.org/10.1109/ARTCom.2010.93 |
| [10] | Andre R, Schlag S, Schulz C (2018) A survey on an optimal solution for VLSI circuit partitioning in physical design using DPSO & DFFA algorithms. Proceedings of the International Conference on Intelligent Sustainable Systems, 868-872. https://doi.org/ISS1.2017.8389301 |
| [11] | Lei X, Liang W, Li KC, Luo H, Hu J, Cai J, et al. (2019) A New Multilevel Circuit Partitioning Algorithm Based on the Improved KL Algorithm. Proceedings of Int. Conf. on High Performance and Smart Computing, 178-182. https://doi.org/10.1109/BigDataSecurity-HPSC-IDS.2019.00041 |
| [12] | Manikandan R, Parameshwaran R, Prassanna J, Sekar KR (2019) A Study on Specific Computational Algorithms for VLSI Cell Partitioning Problems. International Journal on Emerging Technologies 10: 67-70. |
| [13] | Pavithra Guru R, Vaithianathan V (2020) Ant Colony Optimization Based Partition Model for VLSI Physical Design. Proceedings of Int. Conf. on Computer Communication and Informatics, 1-5. https://doi.org/10.1109/ICCCI48352.2020.9104175 |
| [14] |
Pavithra Guru R, Vaithianathan V (2020) An efficient VLSI circuit partitioning algorithm based on satin bowerbird optimization (SBO). J Comput Electron 19: 1232-1248. https://doi.org/10.1007/s10825-020-01491-9 doi: 10.1007/s10825-020-01491-9
|
| [15] |
Karthick R, Senthilselvi A, Meenalochini P, Senthil Pandi S (2023) An Optimal Partitioning and Floor Planning for VLSI Circuit Design Based on a Hybrid Bio-Inspired Whale Optimization and Adaptive Bird Swarm Optimization (WO-ABSO) Algorithm. J Circuit Syst Comp 32: 1-33. https://doi.org/10.1142/S0218126623502730 doi: 10.1142/S0218126623502730
|
| [16] |
Rahimi H, Jahanirad H (2021) An evolutionary approach to implement logic circuits on three dimensional FPGAs. Expert Syst Appl 174: 114780. https://doi.org/10.1016/j.eswa.2021.114780 doi: 10.1016/j.eswa.2021.114780
|
Figures(4) / Tables(6)
Velamala Pavan Kumar, Aravindhan Alagarsamy. A balanced computational approach for multilevel VLSI circuit partitioning strategy with bat algorithm[J]. AIMS Electronics and Electrical Engineering, 2025, 9(3): 390-404. doi: 10.3934/electreng.2025018
DownLoad: