Author(s): Subhrapratim Nath, Rana Majumdar, Subir Kumar Sarkar

Email(s): suvro.n@gmail.com , rana.majumdarwb@gmail.com , sksarkar@etce.jdvu.ac.in

DOI: 10.52711/2321-581X.2023.00003   

Address: Subhrapratim Nath1, Rana Majumdar2, Subir Kumar Sarkar3
1Department of CSE, Jadavpur University, Kolkata, West Bengal, India.
2Department of CS, Sister Nivedita University, Kolkata, West Bengal, India.
3Department of ETCE, Jadavpur University, Kolkata, West Bengal, India.
*Corresponding Author

Published In:   Volume - 14,      Issue - 1,     Year - 2023


ABSTRACT:
Interconnection of billion transistors in a single layer of a die with the advent of the nanometer regime imposes a great challenge to handle the increased complexity, particularly in the global routing of the Very Large-Scale Integration (VLSI) physical design phase which involves distinct optimization in the computation of overall interconnect wire-length. In classical graph theory, the VLSI global routing problem can be mapped as a Rectilinear Steiner Minimal Tree (RSMT) Problem, which in itself is an NP-complete problem. The use of metaheuristics in solving this problem plays a major role where Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO) proved to be efficient algorithms. Both algorithms face certain limitations and inconsistencies in determining maximum optimization. A new optimization algorithm with insight from the biological activity of microorganisms has been proposed in this paper which is based on the behavior of the unicellular organism Physarum Polycephalum aiming at minimizing the wire length of VLSI interconnects. The paper further explores a new hybridization technique employing the use of Physarum BioNetwork and Particle Swarm Optimization together where PSO generate better possible Steiner’s in the initial stage for the final process using Physarum BioNetwork to ensure better convergence. Complexity analysis of the proposed algorithm has been performed and the simulation results achieved greater efficiency when compared with the conventional PSO algorithm and available industry benchmark over-optimizing Global Routing problem in VLSI design.


Cite this article:
Subhrapratim Nath, Rana Majumdar, Subir Kumar Sarkar. A Very Large-Scale Integration Global Routing Optimization Model for Hybrid Physarum Bionetworks. Research Journal of Engineering and Technology. 2023; 14(1):25-0. doi: 10.52711/2321-581X.2023.00003

Cite(Electronic):
Subhrapratim Nath, Rana Majumdar, Subir Kumar Sarkar. A Very Large-Scale Integration Global Routing Optimization Model for Hybrid Physarum Bionetworks. Research Journal of Engineering and Technology. 2023; 14(1):25-0. doi: 10.52711/2321-581X.2023.00003   Available on: https://www.ijersonline.org/AbstractView.aspx?PID=2023-14-1-3


REFERENCES
1.    K. Sakai, K. Tsuji, T. Matsumoto, An efficient approximation algorithm for the Steiner tree problem in rectilinear graphs, IEEE International Symposium on Circuits and Systems, 1 (1989) 339-342, https://10.1109/ISCAS.1989.100360.
2.    D.M. Warme, P. Winter, M. Zachariasen, Exact Algorithms for Plane Steiner Tree Problems: A Computational Study, in: Advances in Steiner Trees Combinatorial Optimization, Springer, 6 (2000) 81-116. https://doi.org/10.1007/978-1-4757-3171-2_6.
3.    R. Novak, J. Rugelj, Distribution of constrained Steiner tree computation in shortest-delay networks, in: Mediterranean Electro technical Conference on Industrial Applications in Power Systems, Computer Science and Telecommunications, 2 (1996) 959-962, https://10.1109/MELCON.1996.551368.
4.    M. Fujimoto, D. Takafuji, T. Watanabe, Approximation algorithms for the rectilinear Steiner tree problem with obstacles, in: IEEE International Symposium on Circuits and Systems, 2 (2005) 1362-1365, https://10.1109/ISCAS.2005.1464849.
5.    Chin Lung Lu, Chuan Yi Tang, Richard, Chia-Tung Lee, The full Steiner tree problem, Theoretical Computer Science, 306 (1–3) (2003) 55-67, https://doi.org/10.1016/S0304-3975 (03)00209-3.
6.    S. Areibi, M. Xie, A. Vannelli, An efficient rectilinear Steiner tree algorithm for VLSI global routing, in: Canadian Conference on Electrical and Computer Engineering, 2 (2001) 1067-1072, https://10.1109/CCECE.2001.933950.
7.    G. Grewal, M. Xu, An efficient graph-based Steiner tree heuristic for the global routing of macro cells, in: Canadian Journal of Electrical and Computer Engineering, 31(4) (2006) 211-219, https://10.1109/CJECE.2006.259174.
8.    N. Maharjan, A. Shrestha, A. Tamrakar, S. P. Panday, Solving Minimum Steiner Tree based on behavior of ants, in: Third Asian Himalayas International Conference on Internet, (2012) 1-4, https://10.1109/AHICI.2012.6408443.
9.    Y. Shi, R. C. Eberhart, Empirical study of particle swarm optimization, in: 1999 Congress on Evolutionary Computation-CEC99, 3 (1999) 1945-1950, https://10.1109/CEC.1999.785511.
10.    M. Clerc, J. Kennedy, The particle swarm - explosion, stability, and convergence in a multidimensional complex space, IEEE Transactions on Evolutionary Computation, 6(1) (2002) 58-73, https://10.1109/4235.985692.
11.    S. Nath, S. Ghosh, S. K. Sarkar, A novel approach to discrete Particle Swarm Optimization for efficient routing in VLSI design, in: International Conference on Reliability, Infocom Technologies and Optimization, (2015) 1-4, https://10.1109/ICRITO.2015.7359375.
12.    A.Tero, R. Kobayashi, T. Nakagaki, A mathematical model for adaptive transport network in path finding by true slime mold, J. Theoret. Biol., 244(4) (2007) 553–564, https://doi.org/10.1016/j.jtbi.2006.07.015.
13.    T. Miyaji, I. Ohnishi, Physarum can solve the shortest path problem on Riemannian surface mathematically rigorously, Int. J. Pure Appl. Math., 47(3) (2008) 353–369.
14.    A Tero, T Nakagaki, K. Toyabe, K. Yumiki, R. Kobayashi, A method inspired by Physarum for solving the Steiner problem, International Journal of Unconventional Computing, 6(1) (2010) pp. 109–123.
15.    S. Tsuda, K. P. Zauner, Y.-P. Gunji, Robot control with biological cells, Biosystems, 87(2-3) (2007) 215–223, https://doi.org/10.1016/j.biosystems.2006.09.016.
16.    H. Wang, K. Li, W. Pedrycz, An Elite Hybrid Meta-Heuristic Optimization Algorithm for Maximizing Wireless Sensor Networks Lifetime with a Sink Node, IEEE Sensors Journal, 20(10) (2020) 5634-5649, https://10.1109/JSEN.2020.2971035.
17.    J. Pasha, M. A. Dulebenets, M. Kavoosi, O. F. Abioye, H. Wang, W. Guo, An Optimization Model and Solution Algorithms for the Vehicle Routing Problem with a “Factory-in-a-Box”, IEEE Access, 8 (2020) 134743-134763, https://10.1109/ACCESS.2020.3010176.
18.    V. F. Yu, H. Susanto, P. Jodiawan, T. -W. Ho, S. -W. Lin, Y. -T. Huang, A Simulated Annealing Algorithm for the Vehicle Routing Problem with Parcel Lockers, IEEE Access, 10 (2022) 20764-20782, https://10.1109/ACCESS.2022.3152062.
19.    X. Gong, N. Geng, Y. Zhu, A. Matta, E. Lanzarone, A Meta-Heuristic Approach for the Home Care Scheduling Problem with Chargeable Overtime and Preference Matching, IEEE Transactions on Automation Science and Engineering, vol. 18 (1) (2021) 282-298, https://10.1109.20/TASE 20.3026484.
20.    B. Rana, Y. Singh, H. Singh, Meta-heuristic Routing: A Taxonomy and Energy-Efficient Framework for Internet of Things, IEEE Access, 9 (2021) 155673-155698, https://10.1109/ACCESS.2021.3128814.
21.    E. K. Teh, M. A. M. Zawawi, M. F. P. Mohamed, N. A. M. Isa, Practical Full Chip Clock Distribution Design with a Flexible Topology and Hybrid Meta-Heuristic Technique, IEEE Access, vol. (9) (2021) 14816- 14835, https://10.1109/ACCESS.2021.3053052.
22.    W. Lan, Z. Ye, P. Ruan, J. Liu, P. Yang, X. Yao, Region-Focused Memetic Algorithms with Smart Initialization for Real-World Large-Scale Waste Collection Problems, IEEE Transactions on Evolutionary Computation, 26(4) (2022) 704-718, https://10.1109/TEVC.2021.3123960.
23.    M. Caleffi, I. F. Akyildiz, L. Paura, On the Solution of the Steiner Tree NP-Hard Problem via Physarum BioNetwork, IEEE/ACM Transactions on Networking, 23(4) (2015) 1092-1106, https://10.1109/TNET.2014.2317911.
24.    Y. Sun, D. Rehfeldt, M. Brazil, D. Thomas, S. Halgamuge, A Physarum-Inspired Algorithm for Minimum- Cost Relay Node Placement in Wireless Sensor Networks, IEEE/ACM Transactions on Networking, 28(2) (2020) 681-694, https://10.1109/TNET.2020.2971770.
25.    M. Asvial, M. A. Laagu, New Development of Physarum Routing Algorithm with Adaptive Power Control, IEEE Access, (9) (2021) 74868-74878, https://10.1109/ACCESS.2021.3065036.
26.    H. Zhang, F. Qi, X. Liu, A Physarum-based Boost Algorithm for Network Optimization in Dense Wireless Sensor Networks, in: International Conference on Computer Communications and Networks, (2021) 1-9, https://10.1109/ICCCN52240.2021.9522232.
27.    H. DeVoe, N. Gilmet, H. ElAarag, A Novel Routing Protocol for Wireless Ad Hoc Networks Based on the Behavior of Slime Mold Physarum Polycephalum, in: Annual Modeling and Simulation Conference (ANNSIM), (2021) 1-12, https://10.23919/ANNSIM52504.2021.9552175.
28.    O. Elek, J. N. Burchett, J. X. Prochaska, A. G. Forbes, Monte Carlo Physarum Machine: Characteristics of Pattern Formation in Continuous Stochastic Transport Networks, Artificial Life, 28(1) (2022), 22-57, https://10.1162/artl_a_00351.
29.    Y Sun, Solving the Steiner Tree Problem in Graphs using Physarum-inspired Algorithm, (2019) arXiv:1903.08926v2. https://doi.org/10.48550/arXiv.1903.08926
30.    Hsu, S., Massolo, F. I. S., Schaposnik, L. P, A Physarum-inspired approach to the Euclidean Steiner tree problem, Scientific Reports, 12(1) (2022) 1-13, https://doi.org/10.1038/s41598-022-18316-3.
31.    D.M. Warme, P. Winter, M. Zachariasen, Exact Algorithms for Plane Steiner Tree Problems: A Computational Study, Advances in Steiner Trees. Combinatorial Optimization, Springer, 6 (2000) 81-116, https://doi.org/10.1007/978-1-4757-3171-2_6.
32.    D. M. Warme, P. Winter, M. Zacharisen, The GeoSteiner 5.0.1 package. [Online]. Available: http://www.geoSteiner.net/geoSteiner-5.0.1.tar.gz.
33.    C. J. Alpert, The ISPD98 Circuit Benchmark Suite, in: International Symposium on Physical Design, (1998), http://dx.doi.org/10.1145/274535.274546.
34.    R. Sardar, R. Mondal, T. Samanta, Geometry Independent Wirelength Estimation Method in VLSI Routing, in: International Conference on VLSI Design and International Conference on Embedded Systems, (2013), 257-261, https://10.1109/VLSID.2013.197.
35.    Subhrapratim Nath, Rana Majumdar,” Multiple Criteria Decision Analysis using VLSI global routing”, Predictive Analytics: Modelling and Optimization by CRC Pres-A Taylor & Francis Group, USA, 2021.
36.    Subhrapratim Nath, Rana Majumdar, Subir Kumar Sarkar, “ Metaheuristic Optimization in Routing Protocol for Cluster -based Wireless Sensor Network and Wireless Ad-Hoc Network, ICT and Data Sciences” CRC Press , 2021.
37.    Poonam Yadav. A taxonomy review of Nature Inspired Algorithms on cyber security for communication and networking. Int. J. Tech. 2020; 10(1):47-52.
38.    Swathypriyadharsini P, K Premalatha. Particle Swarm Optimization for Triclustering High Dimensional Microarray Gene Expression Data.
39.    Antim Bala Sharma, T. Vigneswaran, Ajay Sharma, Fanibhushan Sharma, Nirmala Sharma. Design of High Performance Digital Fir Filter Using Distributed Arithmetic Algorithm with Residue Number System. Research J. Engineering and Tech. 2(1): Jan.-Mar. 2011 page 21-25.
40.    Satish Garg. Data Security using Multi-Level Encryption. Research Journal of Engineering and Technology. 2022; 13(4):100-6. doi: 10.52711/2321-581X.2022.00015
41.    Shelly Gandhi, Rajnish Verma. Review on various Edutainment techniques of Mathematics pedagogy. Research Journal of Engineering and Technology. 2022; 13(4):112-6. doi: 10.52711/2321-581X.2022.00017
42.    Satish Garg. Cryptography Using Modern Ciphers (Xor and Transposition). Research Journal of Engineering and Technology. 2022; 13(3):86-0. doi: 10.52711/2321-581X.2022.00012
43.    Gouri Ganesh Padgal, Shruti Oza. An Efficient Viterbi Algorithm for Communication System. Research Journal of Engineering and Technology. 2022;13(1):10-6. doi: 10.52711/2321-581X.2022.00002
44.    Nitu Singh Gahlawat, Praveen Kantha. A Review on Intrusion Detection System. Research Journal of Engineering and Technology. 2021;12(3):66-4. doi: 10.52711/2321-581X.2021.00011
45.    Gouri Ganesh Padgal, Shruti Oza. An Efficient Viterbi Algorithm for Communication System. Research Journal of Engineering and Technology. 2022;13(1):10-6. doi: 10.52711/2321-581X.2022.00002
46.    Sheetal S. Patil, S.H. Patil. Study of Various Forecasting Models for time series data, using Stochastic Processes. Research Journal of Engineering and Technology. 2021;12(4):99-4. doi: 10.52711/2321-581X.2021.00017

Recomonded Articles:

Author(s): Thangavel S, Sujin David Rajan S., Kevin B.C.

DOI:         Access: Open Access Read More

Author(s): Sahil Angaria, P. S. Rao, S. S. Dham

DOI: 10.5958/2321-581X.2017.00046.0         Access: Open Access Read More

Author(s): Subhrapratim Nath, Rana Majumdar, Subir Kumar Sarkar

DOI: 10.52711/2321-581X.2023.00003         Access: Closed Access Read More

Research Journal of Engineering and Technology (RJET) is an international, peer-reviewed, research journal aiming at promoting and publishing original high quality research in all disciplines of engineering sciences and technology....... Read more >>>

RNI: Not Available                     
DOI: 10.5958/2321-581X 


Recent Articles




Tags