Multi-core real-time scheduling for generalized parallel task models

Abusayeed Saifullah, Jing Li, Kunal Agrawal, Chenyang Lu, Christopher Gill

Research output: Contribution to journalArticlepeer-review

123 Scopus citations


Multi-core processors offer a significant performance increase over single-core processors. They have the potential to enable computation-intensive real-time applications with stringent timing constraints that cannot be met on traditional single-core processors. However, most results in traditional multiprocessor real-time scheduling are limited to sequential programming models and ignore intra-task parallelism. In this paper, we address the problem of scheduling periodic parallel tasks with implicit deadlines on multi-core processors. We first consider a synchronous task model where each task consists of segments, each segment having an arbitrary number of parallel threads that synchronize at the end of the segment. We propose a new task decomposition method that decomposes each parallel task into a set of sequential tasks. We prove that our task decomposition achieves a resource augmentation bound of 4 and 5 when the decomposed tasks are scheduled using global EDF and partitioned deadline monotonic scheduling, respectively. Finally, we extend our analysis to a directed acyclic graph (DAG) task model where each node in the DAG has a unit execution requirement. We show how these tasks can be converted into synchronous tasks such that the same decomposition can be applied and the same augmentation bounds hold. Simulations based on synthetic workload demonstrate that the derived resource augmentation bounds are safe and sufficient.

Original languageEnglish (US)
Pages (from-to)404-435
Number of pages32
JournalReal-Time Systems
Issue number4
StatePublished - Jul 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Modeling and Simulation
  • Computer Science Applications
  • Computer Networks and Communications
  • Control and Optimization
  • Electrical and Electronic Engineering


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


Dive into the research topics of 'Multi-core real-time scheduling for generalized parallel task models'. Together they form a unique fingerprint.

Cite this