Design and Analysis of a Novel Parallel Algorithm for Large Scale Graph Optimization with Dynamic Load Balancing in Heterogeneous Computing Environments
Keywords:
Parallel Graph Optimization, Dynamic Load Balancing, Heterogeneous Computing, Resource Utilization, ScalabilityAbstract
This research focuses on the design and evaluation of a novel parallel graph optimization algorithm incorporating dynamic load balancing (DLB) to address inefficiencies in heterogeneous computing environments. Large-scale graph optimization problems, such as those in social networks, bioinformatics, and transportation systems, often suffer from computational imbalances when using traditional static load balancing approaches, leading to underutilized resources and prolonged execution times. The primary objective of this research is to develop an algorithm that can dynamically adjust workload distribution across processors, enhancing computational efficiency and scalability. The proposed method combines heuristic techniques, including region expansion and multilevel partitioning, with diffusive load balancing strategies to minimize inter-processor communication overhead. Experimental results demonstrate that the proposed algorithm reduces execution time by up to 40% compared to static methods, with optimized resource utilization and more balanced workload distribution. The scalability of the algorithm is also evident, as it adapts effectively to increasing problem sizes and processor counts. These findings suggest that dynamic load balancing is crucial for improving parallel graph optimization in real-world applications. Future work will focus on further enhancing the algorithm’s responsiveness to rapidly changing workloads and expanding its applicability to additional domains.
References
[1] D. Yan, L. Yuan, A. Ahmad, and S. Adhikari, “Systems for Scalable Graph Analytics and Machine Learning: Trends and Methods,” in International Conference on Information and Knowledge Management, Proceedings, 2024, pp. 5547 – 5550. doi: 10.1145/3627673.3679101.
[2] J. Zawalska, M. Chung, K. Rycerz, L. Schulz, M. Schulz, and D. Kranzlmuller, “Leveraging Hybrid Classical-Quantum Methods for Efficient Load Rebalancing in HPC,” in Proceedings of SC 2024-W: Workshops of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2024, pp. 1713 – 1722. doi: 10.1109/SCW63240.2024.00214.
[3] R. Elshawi, O. Batarfi, A. Fayoumi, A. Barnawi, and S. Sakr, “Big graph processing systems: State-of-the-art and open challenges,” in Proceedings - 2015 IEEE 1st International Conference on Big Data Computing Service and Applications, BigDataService 2015, 2015, pp. 24 – 33. doi: 10.1109/BigDataService.2015.11.
[4] O. Batarfi et al., “Large scale graph processing systems: survey and an experimental evaluation,” Cluster Comput., vol. 18, no. 3, pp. 1189 – 1213, 2015, doi: 10.1007/s10586-015-0472-6.
[5] A. Barnawi et al., “On characterizing the performance of distributed graph computation platforms,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 8904, pp. 29 – 43, 2015, doi: 10.1007/978-3-319-15350-6_3.
[6] D. Danang, F. A. Prasetya, and E. Siswanto, “Design of Intelligent Street Lighting Systems Based on Motion and Ambient Light Sensors,” J. Multidiscip. Res. Technol., vol. 2, no. 1, pp. 65–79, 2026.
[7] D. Danang and Z. Mustofa, “Digital Forensics and Automated Incident Response Framework Leveraging Big Data Analytics and Real Time Network Traffic Profiling in Heterogeneous Cyber Environments,” Cyber Secur. Netw. Manag., vol. 1, no. 1, pp. 44–45, 2026.
[8] D. Danang and Z. Mustofa, “CLSTMNet Architecture: A CNN–LSTM-Based Hybrid Deep Learning Model for DDoS Attack Detection and Mitigation in Network Security,” J. Artif. Intell. Technol., 2026.
[9] N. Jansson, R. Bale, K. Onishi, and M. Tsubokura, “Dynamic load balancing for large-scale multiphysics simulations,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 10164 LNCS, pp. 13 – 23, 2017, doi: 10.1007/978-3-319-53862-4_2.
[10] M. Lieber, K. Gößner, and W. E. Nagel, “The potential of diffusive load balancing at large scale,” in ACM International Conference Proceeding Series, 2016, pp. 154 – 157. doi: 10.1145/2966884.2966887.
[11] O. Pearce, T. Gamblin, B. R. De Supinski, M. Schulz, and N. M. Amato, “Decoupled load balancing,” in Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP, 2015, pp. 267 – 268. doi: 10.1145/2688500.2688539.
[12] S. Chokri, S. Baroud, S. Belhaous, M. Bentaleb, M. Mestari, and M. El Youssfi, “Heuristics for dynamic load balancing in parallel computing,” in Proceedings of the 2018 International Conference on Optimization and Applications, ICOA 2018, 2018, pp. 1 – 5. doi: 10.1109/ICOA.2018.8370587.
[13] S. Smirnov and V. Voloshinov, “Integration of ParaSCIP solvers running on several clusters on the base of Everest cloud platform,” in Procedia Computer Science, 2019, pp. 13 – 18. doi: 10.1016/j.procs.2019.08.124.
[14] S. Almarzooq and N. Albishi, Mathematical modelling for transportation with application to airline transportation network. 2021. doi: 10.4018/978-1-7998-8040-0.ch002.
[15] R. V Ravi, P. K. Dutta, and S. B. Goyal, Graph data science: Applications and future. 2025. doi: 10.1016/B978-0-443-29654-3.00007-7.
[16] S. Srivastava, A. Tripathi, S. Bansal, and P. P. Vuppulur, Introduction to optimization: Techniques and applications in engineering. 2025. doi: 10.1201/9781003612858-1.
[17] W. Zheng, D. Wang, and F. Song, “OpenGraphGym: A parallel reinforcement learning framework for graph optimization problems,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 12141 LNCS, pp. 439 – 452, 2020, doi: 10.1007/978-3-030-50426-7_33.
[18] D. Danang, E. Siswanto, W. Aryani, and P. Wibowo, “Hybrid Federated Ensemble Learning Approach for Real-Time Distributed DDoS Detection in IIoT Edge Computing Environment,” J. Eng. Electr. Informatics, vol. 5, no. 1, pp. 9–17, 2025, doi: https://doi.org/10.55606/jeei.v5i1.5099.
[19] S. S. Bhattacharyya and M. C. Wolf, “Research challenges for heterogeneous cyberphysical system design,” Computer (Long. Beach. Calif)., vol. 53, no. 7, pp. 71 – 75, 2020, doi: 10.1109/MC.2020.2988953.
[20] B. Pervan and J. Knezovic, “A survey on parallel architectures and programming models,” in 2020 43rd International Convention on Information, Communication and Electronic Technology, MIPRO 2020 - Proceedings, 2020, pp. 999 – 1005. doi: 10.23919/MIPRO48935.2020.9245341.
[21] Y. Yang, Z. Ke, X. Jia, and L. Yan, “Intelligent Optimization Strategies for Hierarchical Cloud-Edge Computing in Heterogeneous Hardware Ecosystems,” in 2025 4th International Conference on Electronics, Integrated Circuits and Communication Technology, EICCT 2025, 2025, pp. 578 – 581. doi: 10.1109/EICCT65471.2025.11099973.
[22] D. Danang, A. B. Santoso, and M. U. Dewi, “CICA Framework: Harnessing CSR, AI, and Blockchain for Sustainable Digital Culture,” Int. J. Adv. Comput. Sci. & Appl., vol. 16, no. 11, 2025.
[23] Danang, T. Wahyono, I. Sembiring, T. Wellem, and N. H. Dzulkefly, “An Adaptive Framework Integrating ML Blockchain and TEE for Cloud Security,” in Proceeding - 2025 4th International Conference on Creative Communication and Innovative Technology: Empowering Transformative MATURE LEADERSHIP: Harnessing Technological Advancement for Global Sustainability, ICCIT 2025, 2025. doi: 10.1109/ICCIT65724.2025.11167152.
[24] D. Danang, H. Haryani, Q. Aini, F. A. Ramahdan, and J. Edwards, “Empowering Digital Literacy Through Blockchain Based Alphasign for Secure and Sustainable E-Governance,” 2025.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Programming and Algorithm Fundamentals
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
