An Improved Prioritization Method for Task Scheduling in Heterogeneous Computing Systems

H. Yu (USA)


Task Scheduling, Parallel and Distributed Computing, Het erogeneous Computing, List Scheduling.


Scheduling the execution of computing tasks for heteroge neous computing systems is a widely studied problem in the field of parallel and distributed computing. Many algo rithms belong to list scheduling algorithms in which tasks are scheduled sequentially in the order of their pre-assigned priorities. The determination of task priorities is typically based on problem-specific heuristics, which is critical to the performance of a list scheduling algorithm. We de sign a list scheduling algorithm for heterogeneous com puting systems in which task priorities are determined by both the completion time and upward rank of a task. We extend the notion of upward ranks used in HEFT and our method of calculating a task’s upward rank improves over the method used in HEFT, with the inclusion of additional domain knowledge embedded in scheduling problems. As a result, more accurate estimation of the execution time of remaining tasks can be achieved. Experimental results on benchmark task graphs show that our algorithm consis tently outperforms HEFT with higher execution speedups.

Important Links:

Go Back