Resource-efficient scheduling of parallel DAG tasks on identical multiprocessors

Parallel real-time embedded applications can be modelled as directed acyclic graphs (DAGs) whose nodes represent subtasks and whose edges represent precedence constraints among subtasks. Scheduling such parallel tasks on a multicore platform with efficient use of its processing capacity can be challenging. To address this problem, we propose a new algorithm called Segmented-Flattened-and-Split (SFS) scheduling. SFS schedules high-utilisation tasks in dedicated groups of processors, called clusters, as in federated scheduling, but can also reclaim the processing capacity lost to fragmentation, by splitting the execution of parallel tasks over different existing clusters. Our approach is inspired by semi-partitioned C=D scheduling – an approach originally devised for scheduling non-parallel tasks. We prove that SFS dominates federated scheduling. Furthermore, in experiments with synthetic DAG task sets, it outperforms the best-performing variant of federated scheduling in terms of scheduling success ratio (by up to 49%) and weighted schedulability.