Design and Analysis of a Novel Parallel Algorithm for Large Scale Graph Optimization with Dynamic Load Balancing in Heterogeneous Computing Environments

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.