Effective K-way Partitioning of VLSI Circuits with Hetero-Homo Status Based Models using Evolutionary Computation
Effective K-way Partitioning of VLSI Circuits with Hetero-Homo Status Based Models using Evolutionary Computation |
||
 |
 |
|
| © 2023 by IJETT Journal | ||
| Volume-71 Issue-5 |
||
| Year of Publication : 2023 | ||
| Author : P. Rajeswari, Theodore S Chandra, Manoj Kumar Singh |
||
| DOI : 10.14445/22315381/IJETT-V71I5P225 | ||
How to Cite?
P. Rajeswari, Theodore S Chandra, Manoj Kumar Singh, "Effective K-way Partitioning of VLSI Circuits with Hetero-Homo Status Based Models using Evolutionary Computation," International Journal of Engineering Trends and Technology, vol. 71, no. 5, pp. 240-250, 2023. Crossref, https://doi.org/10.14445/22315381/IJETT-V71I5P225
Abstract
In this paper, the circuit-level partitioning problem in VLSI has been considered. The concern objectives of partitioning have been considered in terms of minimizing the number of interconnections between partitions as well as satisfying the desired area of each partition. The need for k-way partitioning has also been satisfied without further computational cost. The problem has been solved through the heuristic approach. Based on the natural process, the new approach in the standard Genetic Algorithm has been included to define the selection process of parents. The proposed model presented the concept of hetero-homo status-based group formation to define parent selection. This model eliminates the biased nature of the standard tournament selection process. Based on the natural extinction process, an extinction operator has also been introduced. The proposed model has shown the relative benefit of the extinction operator against the standard genetic algorithm. The presented hetero-homo status-based group mechanism, along with the extinction operator, has shown benefits in terms of faster convergence with better solution exploration. Comparison of performances of proposed hetero-homo group model in association with extinction operator has shown against the dynamic weighted particle swarm optimization as well as different variation of standard genetic algorithm, and supremacy observed.
Keywords
VLSI circuit partitioning, VLSI physical design, K-way partitioning, Genetic algorithm, Extinction operator.
References
[1] Y. Yodtean, and P. Chantngarm, “Hybrid Algorithm for Bisection Circuit Partitioning,” Proceedings of IEEE Region 10 Conference, vol.4, 2004.
[CrossRef] [Google Scholar] [Publisher Link]
[2] G.-F. Nan, and M.-Q. Li, “Two Novel Encoding Strategies Based Genetic Algorithms for Circuit Partitioning,” Proceedings of the 3rd IEEE International Conference on Machine Learning, vol. 4, pp. 2182–2188, 2005.
[CrossRef] [Google Scholar] [Publisher Link]
[3] G. C. Sipakoulis, I. Karafyllidis, and A. Thanailkis, “Genetic Partition and Placement for VLSI Circuits,” Proceedings of the 6th IEEE Conference on Electronics Circuits and Systems, vol. 3, pp. 1647–1650, 1999.
[CrossRef] [Google Scholar] [Publisher Link]
[4] C. J. Augeri, and H. H. Ali, “New Graph-Based Algorithms for Partitioning VLSI Circuits,” Proceedings of the IEEE International Symposium on Circuits and Systems, pp. V-521–V-524, 2004.
[CrossRef] [Google Scholar] [Publisher Link]
[5] A. Cincotti, V. Cuttelo, and M. Pavone, “Graph Partitioning Genetic Algorithms With OPDX,” Proceedings of IEEE World Congress on Computational Intelligence, pp. 402–406, 2002.
[CrossRef] [Publisher Link]
[6] I. Hameem Shanavas, and R. K. Gnanamurthy, “Evolutionary Algorithmical Approach on VLSI Floor Planning Problem,” International Journal of Computer Theory and Engineering, vol.1, no. 4, pp. 461–464, 2009.
[CrossRef] [Google Scholar] [Publisher Link]
[7] N. Krasnogor, and J. Smith, “A Tutorial for Competent Memetic Algorithms: Model, Taxonomy, and Design Issues,” IEEE Transactionson Evolutionary Computation, vol. 9, no. 5, pp. 474–488, 2005.
[CrossRef] [Google Scholar] [Publisher Link]
[8] Jianhua Li, and L. Behjat, “A Connectivity Based Clustering Algorithm with Application to VLSI Circuit Partitioning,” IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 53, no. 5, pp. 384 - 388, 2006.
[CrossRef] [Google Scholar] [Publisher Link]
[9] N. Selvakkumaran, and G. Karypis, “Multiobjective Hypergraph-Partitioning Algorithms for Cut and Maximum Subdomain-Degree Minimization ,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp. 504 – 517, 2005.
[CrossRef] [Google Scholar] [Publisher Link]
[10] Shao-Jun Peng, Guo-Long Chen, and Wen-Zhong Guo,” A Discrete PSO for Partitioning in VLSI Circuit,” 2009 International Conference on Computational Intelligence and Software Engineering, pp. 1- 4, 2009.
[CrossRef] [Google Scholar] [Publisher Link]
[11] I. Hameem Shanavas et al., “A Novel Approach to Find the Best Fit for VLSI Partitioning - Physical Design,” Advances in Recent Technologies in Communication and Computing (ARTCOM), pp. 330 – 332, 2010.
[CrossRef] [Google Scholar] [Publisher Link]
[12] Roman Bazylevych, and Lubov Bazylevych,” The Methodology and Algorithms for Solving the Very Large-Scale Physical Design Automation Problems: Partitioning, Packaging, Placement and Routing,” 2013 2nd Mediterranean Conference on Embedded Computing (MECO), pp. 1 - 2, 2013.
[CrossRef] [Google Scholar] [Publisher Link]
[13] Aarti Patel, and Prashant K.Shah, "Semi-Custom Design of Functional Unit Block Using Data Path Methodology in Data Cache Unit," SSRG International Journal of VLSI & Signal Processing, vol. 4, no. 2, pp. 34-38, 2017.
[CrossRef] [Google Scholar] [Publisher Link]
[14] Pradip Kumar Sharma, and Maninder Kaur, “A Discrete Firefly Algorithm for VLSI Circuit Partitioning,” Electronics and Communication Systems (ICECS), pp. 1-4, 2014.
[CrossRef] [Google Scholar] [Publisher Link]
[15] Bhargab Sinha et al., “Heuristics in Physical Design Partitioning: A Review,” International Conference on Innovations in Information, Embedded and Communication Systems, pp. 1-5, 2015.
[CrossRef] [Google Scholar] [Publisher Link]
[16] Sadiq M. Sait et al., “Design Partitioning and Layer Assignment for 3D Integrated Circuits Using Tabu Search and Simulated Annealing,” Journal of Applied Research and Technology, vol. 14, no. 1, pp. 67-76, 2016.
[CrossRef] [Google Scholar] [Publisher Link]
[17] Prabhakar R, Sreenivasa Murhthy K E, and Soundara Rajan K, "Incremental Detailed Placement for VLSI Design," SSRG International Journal of VLSI & Signal Processing, vol. 2, no. 3, pp. 7-12, 2015.
[CrossRef] [Publisher Link]
[18] Linquan Lyu, and Takeshi Yoshimura, “A Force Directed Partitioning Algorithm for 3D Floorplanning,” 2017 IEEE 12th International Conference on ASIC (ASICON)
[CrossRef] [Google Scholar] [Publisher Link]
[19] Robin Andre, Sebastian Schlag, and Christian Schulz, “Memetic Multilevel Hypergraph Partitioning,” Arxiv:1710.01968v2 [Cs.DS], 2018.
[CrossRef] [Google Scholar] [Publisher Link]
[20] Ghasem Pasandi, and Massoud Pedram, “A Graph Partitioning Algorithm with Application in Synthesizing Single Flux Quantum Logic Circuits,” Arxiv.Org > Cs > Arxiv:1810.00134, 2018.
[CrossRef] [Google Scholar] [Publisher Link]
[21] Xia Lei et al., “A New Multilevel Circuit Partitioning Algorithm Based on the Improved KL Algorithm,” 2019 IEEE 5th Intl Conference on Big Data Security on Cloud (Bigdatasecurity), IEEE International Conference on High Performance and Smart Computing, (HPSC) and IEEE International Conference on Intelligent Data and Security (IDS).
[CrossRef] [Google Scholar] [Publisher Link]
[22] P. Rajeswari et al., “An Investigation on Basic Concepts of Particle Swarm Optimization Algorithm for VLSI Circuits,” International Journal of Engineering and Technique, vol. 4, no. 1, pp. 144-149, 2018.
[Publisher Link]
[23] P. Rajeswari, Theodore S. Chandra, and Amith Kiran Kumar, “Synthesis of VLSI Structural Cell Partitioning Using Genetic Algorithm” Springer Nature Proceedings, vol. 1270, pp. 279-287, 2020.
[CrossRef] [Publisher Link]
[24] P. Rajeswari, and Theodore S Chandra, "Partitioning of VLSI Circuits on the Basis of Standard Genetic Algorithm and Comparative Analysis of Partitioning Algorithms," SSRG International Journal of Electrical and Electronics Engineering, vol. 9, no. 12, pp. 126-133, 2022.
[CrossRef] [Publisher Link]
[25] Ajoy Kumar Khan et al., “A New Efficient Layer Assignment Algorithm for Partitioning in 3D VLSI Physical Design,” 2013 1st International Conference on Emerging Trends and Applications in Computer Science, pp. 203 - 207, 2013.
[CrossRef] [Google Scholar] [Publisher Link]
[26] P. Rajeswari, and S Theodore Chandra, “A Survey on An Optimal Solution for VLSI Circuit Partitioning in Physical Design Using DPSO & DFFA Algorithms,” 2017 International Conference on Intelligent Sustainable Systems (ICISS), pp. 868-872, 2017.
[CrossRef] [Google Scholar] [Publisher Link]