Prioritizing tasks

In the first phase each task is given a priority. The priority of each task ${\displaystyle n_{i}}$ is usually designated to be its "upward rank" which is defined recursively as follows

${\displaystyle rank_{u}(n_{i})={\overline {w_{i}}}+\max _{n_{j}\in succ(n_{i})}({\overline {c_{i,j}}}+rank_{u}(n_{j}))}$

where ${\displaystyle n_{i}}$ represents the ${\displaystyle i^{th}}$ task, ${\displaystyle {\overline {w_{i}}}}$ is an average computation cost of job i among all the processor, ${\displaystyle succ(n_{i})}$ is the set of all jobs that immediately depend on task ${\displaystyle n_{i}}$, and ${\displaystyle {\overline {c_{i,j}}}}$ is the average communication cost of the variables transferred between jobs ${\displaystyle n_{i}}$ and ${\displaystyle n_{j}}$ between all pairs of workers. Note that the computation of ${\displaystyle rank_{u}(n_{i})}$ depends on the computation of the rank of all its children. The upward rank is meant to represent the expected distance of any task from the end of the computation. For averaged quantities like ${\displaystyle {\overline {w_{i}}}}$ different averages may provide different results.^[2]

Assigning tasks to workers

In the second phase tasks are assigned to workers. Now that all tasks are prioritized we consider and schedule each one, starting with the highest priority. The task with the highest priority for which all dependent tasks have finished is scheduled on the worker which will result in the earliest finish time of that task. This finish time depends on the communication time to send all necessary inputs to the worker, the computation time of the task on the worker, and the time when that processor becomes available (it may be busy with another task). HEFT uses an insertion-based policy that fills sufficiently sized gaps between already scheduled tasks.