Load-balancing makes reference to the process of distributing a set of tasks over a set of resources which are the computing units, with the objective of making their overall processing more systematic. Load balancing software techniques can enhance the response time for each task, avoiding overloading compute nodes while the other compute nodes are left idle.
Characteristics of load balancing software
The algorithm of load balancing always tries to answer a specific problem. Among other things, the hardware architecture on which the algorithms will run the nature of the tasks, the algorithmic complexity, as well as required error tolerance must also be taken into account. For that reason, a compromise must be established to best meet application-specific requirements.
Nature of tasks
Load balancing algorithms’ efficiency critically depends on the nature of the tasks. Hence, the more information related to the tasks is available at the time of decision making, the greater the will be the potential for optimization.
Size of tasks
Perfect knowledge about the execution time of each task will allow us to reach an optimal load distribution. But, Knowing the exact execution time of each task is impossible. Therefore, there are many techniques to get an idea of the different execution times. First of all, in the favored scenario of having tasks of adequately homogeneous size, it is possible to take into account that each of them will need approximately the average execution time. On the other hand, if the execution time is very inconsistent, more sophisticated techniques should be used.
There are some cases where the tasks will depend on each other. These interdependencies can be demonstrated by a directed acyclic graph. Moreover, some tasks cannot begin until the existing tasks are fully completed.
Let us assume that the time required for each of the tasks is known in advance; an optimal execution order should lead to the minimization of the total execution time. There are algorithms, like job schedulers, that can calculate optimal task distributions with the help of metaheuristic methods.
Segregation of tasks
Another characteristic of the tasks that are critical for the design of a load balancing algorithm is their capability to be broken down into subtasks during the execution process. The “Tree-Shaped Computation” algorithm takes great advantage of this specificity.
Static and dynamic algorithms
Static
A load-balancing algorithm is conducted to be “static” when it does not take into consideration the state of the system for the distribution of tasks. Thereby, the system state comprises measures of certain processors such as the load level and sometimes even overload.
Alternatively, assumptions on the overall system are made in advances, such as the resource requirements of incoming tasks and arrival times. In addition to it, the number of processors, communication speeds, and their respective power are known. Therefore, the objective of static load balancing is to associate a known set of tasks with the available processors so as to minimize a certain performance function.
Static load balancing techniques are mostly centralized around a master or a router, which dispenses the loads and optimizes the performance function. This minimization can be taken into account when the information related to the tasks is distributed and derives an expected execution time.
The advantage of static algorithms is that they are extremely efficient in the case of fairly regular tasks and easy to set up. However, there are still a few statistical variances in the assignment of tasks that can lead to the weight downing of some computing units.
Dynamic
Unlike static load distribution algorithms, dynamic algorithms take into consideration the current load of each of the computing units, which are also called nodes, in the system. In this approach, tasks can be shifted dynamically from an overloaded node to an underloaded node so as to receive faster processing. While these algorithms are much more complicated to produce, they can give rise to excellent results, particularly when the execution time of the tasks varies greatly from one to another.
In dynamic load balancing software, the architecture can be more modular since it is not obligatory to have a specific node dedicated to the distribution of work. When tasks are distinctively assigned to a processor according to its state at a given moment, it is considered to be a unique assignment. On the other hand, if the tasks can be permanently reallocated according to the state of the system and its evolution, it is called a dynamic assignment.