An Adaptive Task Granularity Based Scheduling for Task-centric Parallelism

Different from data parallel model, task parallel computing model is very important for complex analysis and data mining. Task granularity is a key factor that significantly affects the performance of task-centric parallel programs. However, current task-granularity based solutions either only work well for regular task-parallel programs or are difficult to use. As a result, for irregular task-parallel programs, these solutions may suffer from inappropriate task granularity. To meet this challenge, in this paper, we propose an adaptive task-granularity based scheduling strategy, called ATG. It not only can adaptively switch between help-first and serialization scheduling policies to control task granularity, but also can prevent fine-grained tasks from being executed in parallel to reduce the task-creation overhead. Experiment results show that compared with manual cut-off strategy, the performance of irregular task parallel applications can be improved by ATG strategy up to 19% with low overhead. Meanwhile, for the regular task-parallel applications ATG strategy can even get almost the same performance of the optimal manual cut-off scheme as well.