Peelsched: a Simple and Parallel Scheduling Algorithm for Static Taskgraphs

Abstract

We present a new algorithm, which we call P EELSCHED, to schedule a set of tasks with precedence constraints and communication costs onto a parallel computer with homogeneous processing units. The algorithm is deterministic and simple, and can be parallelized itself. The new algorithm is based on the usage of structural graph properties, in particular series-parallel or N-free graphs, but can be used on any DAG. We provide an implementation and validate it against a benchmark suite of task graphs. We find that the algorithm's scheduling results are comparable to strictly sequential schedulers.