Load Balancing Algorithms for Parallel Computing

Computational fluid dynamics (CFD) is a discipline that solves and analyzes fluid dynamics problems through computer and numerical simulation methods. In the process of CFD numerical simulations, the complexity of the problem is gradually increasing, the accuracy of the numerical simulation is becoming more and more demanding, and the network size is continuously expanding. Load-balancing algorithms for CFD parallel computing are being gradually and extensively researched in the world.

firefly algorithm;bio-inspired design;hybrid methods

1. Introduction

Computational fluid dynamics (CFD) [1] is a discipline that solves and analyzes fluid dynamics problems through computer and numerical simulation methods. In the process of CFD numerical simulations, the complexity of the problem is gradually increasing, the accuracy of the numerical simulation is becoming more and more demanding, and the network size is continuously expanding. In the process of numerical simulations, the computational area is discretized into multiple grid blocks of different sizes, and these blocks are assigned to different processors for parallel computation. Therefore, how to make the load task of each processor reasonably balanced is the main problem to be solved, and it is also an important technology to improve the processing efficiency. As the scale of computation increases, the impact of the communication overhead of the processors is also gradually increasing on the parallel processing efficiency. The mismatch between the number of grid blocks and the number of processes, as well as the mismatch between the computational capacity of grid blocks and the computational capacity of processes, makes the traditional partitioning or combination strategies unable to meet the demand of load balancing well [2]. Therefore, the research on algorithms for large-scale load balancing is crucial.
At present, load-balancing algorithms for CFD parallel computing are being gradually and extensively researched in the world. For example, the load-balancing algorithm of greedy method and the recursive pairwise edge splitting load-balancing algorithm proposed by Streng [3] and Ytterström [4] are classical load-balancing algorithms based on a geometric level. In addition, Hendrickson et al. [5] proposed a multi-level algorithm for partitioning graphs, which is a method of mapping to a refined graph by coarsening the graph dissection. In recent years, heuristic algorithms have also been increasingly used in the research of load-balancing algorithms. Most of them are swarm intelligence algorithms that imitate natural bodies, such as firefly algorithm, ant colony algorithm, and bee colony algorithm. They are applied to solve various optimization scheduling problems and are widely used in industry [6], network transmission [7], biology [8] and cloud computing [9]. Among them, the combination of neural networks and other algorithms has achieved considerable research success in image capture and retrieval [10][11][12][13][10,11,12,13]. With the development of parallel computing, the improvement and optimization of heuristic algorithms to solve the load-balancing problem of parallel computing have also achieved considerable results. For example, Kernighan et al. [14] proposed a heuristic algorithm for graph segmentation. The hybrid load-balancing algorithm proposed by Yang Chengfu et al. [15] and the ant colony optimization based MrLBA algorithm proposed by Arfa Muteeh [16] are typical methods of heuristic algorithms applied to load balancing. However, swarm intelligence algorithms generally easily fall into local optimum, and the optimization effect is uneven. This rpapesearchr uses the multi-level graph segmentation algorithm of a structural grid to obtain a network coarsening graph and proposes a FaCO algorithm based on the firefly and ant colony algorithm to subdivide the coarsening graph. Based on the fusion of the two in the optimization rule, a new optimization rule is established to adjust the position update, which avoids falling into the local optimal situation to a certain extent.

2. Load Balancing Algorithms for Parallel Computing

In order to solve the time and cost problems of large-scale computation, parallel computing decomposes complex problems into several parts with certain regularity and assigns each part to a separate processor for simultaneous computation of multiple instructions. It not only reduces the time cost but also improves the overall computational performance. With the development of CFD numerical simulation research, the scale of computation is increasing, and parallel computing becomes an effective method to solve this problem. With the wide application of CFD numerical simulations, such as point cloud sampling [17], multi-view image retrieval [18], etc., the research on load-balancing algorithms for CFD parallel computing can be basically divided into two main categories: geometry-based and graph-based [3][4][5][3,4,5]. However, with the development of research on heuristic algorithms, there is a great potential for their application to solve load-balancing problems. RWesearchers mainly focus on the improvement of heuristic algorithms and their graph-based optimization applications to load-balancing problems for parallel computing. Kannan et al. proposed a multi-objective load-balancing method using a bio-inspired algorithm [19]. It solves the pre-convergence problem by a micro-genetic algorithm and proposed a stable method of combining cat swarm optimization for process load distribution (MG-CSO). Better results are obtained on the time cost problem of load balancing for cloud computing. The hybrid discrete artificial bee colony algorithm (ABC) proposed by Junqing Li and Yunqi Han investigated and solved the task scheduling problem in cloud computing systems [20]. It designs an improved scout bee using different local search methods to obtain the best food source or waste solution that can improve the convergence of the proposed algorithm. Ahmad M. Manasrah et al. proposed a hybrid algorithm based on genetic algorithm (GA) and particle swarm optimization (PSO) to solve the multitask scheduling problem [21]. In the field of multitask scheduling, this algorithm converges to the optimal solution much faster and with higher quality. The firefly load-balancing algorithm was proposed by Manisha et al. It reduces the computational cycles and the degree of load imbalance while exhibiting better working performance [22]. Both the genetic ant colony algorithm proposed by Cheng Cheng et al. [23] and the ACO focusing algorithm proposed by Skinderowicz Rafał [24] improved the ant colony algorithm to a new level and obtained better computational performance. Tang Bo et al. proposed the idea of applying genetic algorithms to the mapping process of grid blocks and processors and then performing intelligent allocation [2], but genetic algorithms have more space for optimization than other algorithms. In the optimization process of a series of heuristic algorithms, although they also solve the load-balancing problem to a certain extent, they have the limitation of a single mechanism of finding the best and the tendency to fall into the local optimum. In this respapearchr, the proposed FaCO algorithm based on the fusion of firefly algorithm and ant colony algorithm with merit-seeking mechanism is free from the constraints of a single mechanism. Additionally, the previous heuristic algorithm is introduced to fuse the allocation mapping process of parallel computing, and the innovative FaCO algorithm is applied to solve the simple tsp graph structure after multi-level graph dissection. The load-balancing problem of massively parallel computing is solved with the goal of optimal allocation.
Top
Feedback