Load balancing (computing): Difference between revisions

Revision as of 12:08, 17 August 2023

Revision as of 03:34, 1 November 2023

Line 1:

{{short description|Set of techniques to improve the distribution of workloads across multiple computing resources}}

[[File:Elasticsearch Cluster August 2014.png|thumb|400px|Diagram illustrating user requests to an [[Elasticsearch]] cluster being distributed by a load balancer. (Example for [[Wikipedia]].)]]

In [[computing]], '''load balancing''' is the process of distributing a set of [[Task (computing)|tasks]] over a set of [[System resource|resources]] (computing units), with the aim of making their overall processing more efficient. Load balancing can optimize the response time and avoid unevenly overloading some compute nodes while other compute nodes are left idle.

Line 72:

If the tasks are independent of each other, and if their respective execution time and the tasks can be subdivided, there is a simple and optimal algorithm.

[[File:Load_Balancing_divisible_tasks.png|thumb|370px|Load balancing algorithm depending on divisibility of tasks]]

By dividing the tasks in such a way as to give the same amount of computation to each processor, all that remains to be done is to group the results together. Using a [[prefix sum]] algorithm, this division can be calculated in [[logarithmic time]] with respect to the number of processors.{{fact|date=October 2022}}

By dividing the tasks in such a way as to give the same amount of computation to each processor, all that remains to be done is to group the results together. Using a [[prefix sum]] algorithm, this division can be calculated in [[logarithmic time]] with respect to the number of processors.{{fact|date=October 2022}}

[[File:Load_Balancing_divisible_tasks.png|thumb|370px|Load balancing algorithm depending on divisibility of tasks]]

If, however, the tasks cannot be subdivided (i.e., they are [[Linearizability|atomic]]), although optimizing task assignment is a difficult problem, it is still possible to approximate a relatively fair distribution of tasks, provided that the size of each of them is much smaller than the total computation performed by each of the nodes.<ref name="Sequential and parallel algorithms"/>