Timing-anomaly free dynamic scheduling of conditional DAG tasks on multi-core systems

Peng Chen, Weichen Liu, Xu Jiang, Qingqiang He, Nan Guan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

7 Citations (Scopus)


In this paper, we propose a novel approach to schedule conditional DAG parallel tasks, with which we can derive safe response time upper bounds significantly better than the state-of-the-art counterparts. The main idea is to eliminate the notorious timing anomaly in scheduling parallel tasks by enforcing certain order constraints among the vertices, and thus the response time bound can be accurately predicted off-line by somehow “simulating” the runtime scheduling. A key challenge to apply the timing-anomaly free scheduling approach to conditional DAG parallel tasks is that at runtime it may generate exponentially many instances from a conditional DAG structure. To deal with this problem, we develop effective abstractions, based on which a safe response time upper bound is computed in polynomial time. We also develop algorithms to explore the vertex orders to shorten the response time bound. The effectiveness of the proposed approach is evaluated by experiments with randomly generated DAG tasks with different parameter configurations.

Original languageEnglish
Article number91
Pages (from-to)1-19
JournalACM Transactions on Embedded Computing Systems
Issue number5s
Publication statusPublished - Oct 2019


  • Conditional DAG
  • Dynamic scheduling
  • Response time analysis
  • Timing anomaly

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture

Cite this