Heterogeneous earliest finish time

Heterogeneous earliest finish time (HEFT) is a heuristic algorithm to schedule a set of dependent tasks onto a network of heterogenous workers taking communication time into account.[1] For inputs HEFT takes a set of tasks, represented as a directed acyclic graph, a set of workers, the times to execute each task on each worker, and the times to communicate the results from each job to each of its children between each pair of workers. It descends from list scheduling algorithms.

Algorithm

edit

HEFT executes in two phases.

Prioritizing tasks

edit

In the first phase each task is given a priority. The priority of each task   is usually designated to be its "upward rank" which is defined recursively as follows

 

where   represents the   task,   is an average computation cost of job i among all the processor,   is the set of all jobs that immediately depend on task  , and   is the average communication cost of the variables transferred between jobs   and   between all pairs of workers. Note that the computation of   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   different averages may provide different results.[2]

Assigning tasks to workers

edit

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.

Discussion

edit

HEFT is well respected among heuristic algorithms for this problem. But in complex situations it can easily fail to find the optimal scheduling. HEFT is essentially a greedy algorithm and incapable of making short-term sacrifices for long term benefits. Some improved algorithms based on HEFT look ahead to better estimate the quality of a scheduling decision can be used to trade run-time for scheduling performance.[3][4]

Code

edit

HEFT implementations are available on GitHub in the programming languages C++,[5] and Python.[6]

References

edit
  1. ^ Topcuoglu, Haluk; Hariri, Salim; Wu, M. (2002). "Performance-effective and low-complexity task scheduling for heterogeneous computing". IEEE Transactions on Parallel and Distributed Systems. 13 (3): 260–274. CiteSeerX 10.1.1.119.122. doi:10.1109/71.993206. S2CID 17773509.
  2. ^ Zhao, Henan; Sakellariou, Rizos (2003). "An Experimental Investigation into the Rank Function of the Heterogeneous Earliest Finish Time Scheduling Algorithm". Euro-Par 2003 Parallel Processing. Lecture Notes in Computer Science. Vol. 2790. pp. 189–194. CiteSeerX 10.1.1.329.9320. doi:10.1007/978-3-540-45209-6_28. ISBN 978-3-540-40788-1.
  3. ^ Bittencourt, Luiz F; Sakellariou, Rizos; Madeira, Edmundo R M (2010). DAG Scheduling Using a Lookahead Variant of the Heterogeneous Earliest Finish Time Algorithm. Euromicro Conference on Parallel, Distributed and Network-based Processing. CiteSeerX 10.1.1.703.3063. doi:10.1109/PDP.2010.56.
  4. ^ Arabnejad, Hamid; Barbosa, Jorge G. (2014). "List Scheduling Algorithm for Heterogeneous Systems by an Optimistic Cost Table". IEEE Transactions on Parallel and Distributed Systems. 25 (3): 682–694. doi:10.1109/TPDS.2013.57. ISSN 1045-9219.
  5. ^ Mishra, Yuvraj (VanillaBase1lb) (2021). "Implementation of Heterogenous Earliest FInish Time First scheduling in C++". GitHub.{{cite web}}: CS1 maint: numeric names: authors list (link)
  6. ^ Rocklin, Matthew (mrocklin) (2013). "A static scheduling heuristic". GitHub.