An Improved Heterogeneous Dynamic List Schedule Algorithm

Scheduling algorithm impacts system substantially in terms of throughput and load balance. Traditional methods rely on static criteria, such as earliest finishing time, critical path, and the importance of the nodes, to prioritise workloads towards various hardware settings. In practice, however, a global static scheduling method often works suboptimally given the dependence complexity among tasks and the performance diversity on separate hardware configurations. To cope with such issue, in this paper, we propose an improved heterogeneous dynamic list scheduling algorithm (IHDSA) to balance workload across heterogeneous cores and optimize communication overhead adaptively. The proposed algorithm performs three steps. First, it transforms the DAG task graph into a list and marks job status. Then, it calculates the shortest completion time of three distinctive scheduling schemes and selects the best solution among the three. Finally, it sets up thresholds for computing units and monitors the status to balance the usage of those cores. In our experiment, the IHDSA adaptive scheduling improves the performance significantly over the static counterpart.