Load Balancing Algorithms for Parallel Computing: History
Please note this is an old version of this entry, which may differ significantly from the current revision.
Contributor: , , ,

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.

## 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]. However, with the development of research on heuristic algorithms, there is a great potential for their application to solve load-balancing problems. We 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 paper, 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.

This entry is adapted from the peer-reviewed paper 10.3390/biomimetics7040168

This entry is offline, you can click here to edit this entry!