Editing Load balancing (computing) (section)

===Static distribution with full knowledge of the tasks: [[prefix sum]]===
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|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.{{citation needed|date=October 2022}}

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"/>

Most of the time, the execution time of a task is unknown and only rough approximations are available. This algorithm, although particularly efficient, is not viable for these scenarios.