Parallel real-time scheduling of DAGs

Abusayeed Saifullah, David Ferry, Jing Li, Kunal Agrawal, Chenyang Lu, Christopher D. Gill

Research output: Contribution to journalArticlepeer-review

143 Scopus citations


Recently, multi-core processors have become mainstream in processor design. To take full advantage of multi-core processing, computation-intensive real-time systems must exploit intra-task parallelism. In this paper, we address the problem of real-time scheduling for a general model of deterministic parallel tasks, where each task is represented as a directed acyclic graph (DAG) with nodes having arbitrary execution requirements. We prove processor-speed augmentation bounds for both preemptive and non-preemptive real-time scheduling for general DAG tasks on multi-core processors. We first decompose each DAG into sequential tasks with their own release times and deadlines. Then we prove that these decomposed tasks can be scheduled using preemptive global EDF with a resource augmentation bound of 4. This bound is as good as the best known bound for more restrictive models, and is the first for a general DAG model. We also prove that the decomposition has a resource augmentation bound of 4 plus a constant non-preemption overhead for non-preemptive global EDF scheduling. To our knowledge, this is the first resource augmentation bound for non-preemptive scheduling of parallel tasks. Finally, we evaluate our analytical results through simulations that demonstrate that the derived resource augmentation bounds are safe in practice.

Original languageEnglish (US)
Article number6714435
Pages (from-to)3242-3252
Number of pages11
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number12
StatePublished - Dec 1 2014
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


  • Multi-core processor
  • Parallel task
  • Real-time scheduling
  • Resource augmentation bound


Dive into the research topics of 'Parallel real-time scheduling of DAGs'. Together they form a unique fingerprint.

Cite this