Load balancing in parallel computing: an evolutionary approach
Simona Dinu, Gabriel Raicu · 2023
The assignment of work uniformly, across an available group of processors, represent an important problem in parallel computing. The efficiency of the workload balancing is obtained by a proper partitioning strategy, which is a challenging task. Partitioning is an important concept connected to various other problems in modern computing field and also an extensively-studied problem in graph-based analysis. The computational graph in parallel computing model defines units of computations (or tasks) as nodes and data dependencies (or communications) between units as edges. A k-way graph balanced partitioning algorithm is proposed, with the objectives of partitioning the graph nodes into k equal sized disjoint components, while minimizing the number of edges crossing between components. This edge partition model is suggestive for mapping computations to processors, while reducing the interprocessors communications. The partitioning problem turned out to be a NP-hard problem of combinatorial optimization, so we proposed a Genetic Algorithm with fuzzy adaptation of parameters for determining optimal partitions within a reasonable amount of time. The performance of the partitions was assessed based on two performance metrics, namely density and conductance. Based on randomly generated application workflows, experiments with different values of k were performed to demonstrate computational capabilities of the proposed algorithm.