Editing Load balancing (computing) (section)

===Nature of tasks===
The efficiency of load balancing algorithms critically depends on the nature of the tasks. Therefore, the more information about the tasks is available at the time of decision making, the greater the potential for optimization.

====Size of tasks====
Perfect knowledge of the [[execution time]] of each of the tasks allows to reach an optimal load distribution (see algorithm of [[prefix sum]]).<ref name="Sequential and parallel algorithms">{{cite book |last1=Sanders |first1=Peter |last2=Mehlhorn |first2=Kurt |last3=Dietzfelbinger |first3=Martin |last4=Dementiev |first4=Roman |title=Sequential and parallel algorithms and data structures : the basic toolbox |date=11 September 2019 |publisher=Springer |isbn=978-3-030-25208-3}}</ref> Unfortunately, this is in fact an idealized case. Knowing the exact [[execution time]] of each task is an extremely rare situation.

For this reason, there are several techniques to get an idea of the different execution times. First of all, in the fortunate scenario of having tasks of relatively homogeneous size, it is possible to consider that each of them will require approximately the average execution time. If, on the other hand, the execution time is very irregular, more sophisticated techniques must be used. One technique is to add some [[metadata]] to each task. Depending on the previous execution time for similar metadata, it is possible to make inferences for a future task based on statistics.<ref>{{cite journal |last1=Liu |first1=Qi |last2=Cai |first2=Weidong |last3=Jin |first3=Dandan |last4=Shen |first4=Jian |last5=Fu |first5=Zhangjie |last6=Liu |first6=Xiaodong |last7=Linge |first7=Nigel |title=Estimation Accuracy on Execution Time of Run-Time Tasks in a Heterogeneous Distributed Environment |journal=Sensors |date=30 August 2016 |volume=16 |issue=9 |pages=1386 |doi=10.3390/s16091386|pmid=27589753 |pmc=5038664 |bibcode=2016Senso..16.1386L |s2cid=391429 |doi-access=free }}</ref>

====Dependencies====
In some cases, tasks depend on each other. These interdependencies can be illustrated by a [[directed acyclic graph]]. Intuitively, some tasks cannot begin until others are completed.

Assuming that the required time for each of the tasks is known in advance, an optimal execution order must lead to the minimization of the total execution time. Although this is an [[NP-hard]] problem and therefore can be difficult to be solved exactly. There are algorithms, like [[job scheduler]], that calculate optimal task distributions using [[metaheuristic]] methods.

====Segregation of tasks====
Another feature of the tasks critical for the design of a load balancing algorithm is their ability to be broken down into subtasks during execution. The "Tree-Shaped Computation" algorithm presented later takes great advantage of this specificity.