AN IMPROVED PRIORITIZATION METHOD FOR TASK SCHEDULING IN HETEROGENEOUS COMPUTING SYSTEMS

摘要

Scheduling the execution of computing tasks for heterogeneous computing systems is a widely studied problem in the eld of parallel and distributed computing. Many algorithms 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-speci c heuristics, which is critical to the performance of a list scheduling algorithm. We design a list scheduling algorithm for heterogeneous computing 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 consistently outperforms HEFT with higher execution speedups.