A Heuristic Greedy Algorithm for Scheduling Out-Tree Task Graphs

Abstract

The scheduling of Out-Tree task graphs is one of the critical factors in implementing the compilers of parallel languages and improving the performance of parallel computing. Although there are a few heterogeneity based algorithms in the literature suitable for scheduling Out-Tree task graphs, they usually require significantly high scheduling costs and may not deliver good quality schedules with lower costs. This paper presents a heuristic greedy scheduling algorithm for Out-Tree task graphs with an objective to simultaneously meet high performance and fast scheduling time, which is based on list and task duplication, tries to find the best point between balancing loads and shortening the schedule length and improves the schedule performance without increasing the time complexity of the algorithm. The comparative study shows that the proposed algorithm surpasses previous approaches in terms of schedule length ratio, speedup and efficiency metrics.