Back to Search Start Over

Timing-Anomaly Free Dynamic Scheduling of Conditional DAG Tasks on Multi-Core Systems

Authors :
Qingqiang He
Nan Guan
Xu Jiang
Weichen Liu
Peng Chen
School of Computer Science and Engineering
Source :
ACM Transactions on Embedded Computing Systems. 18:1-19
Publication Year :
2019
Publisher :
Association for Computing Machinery (ACM), 2019.

Abstract

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. Accepted version This work is supported by the Research Grants Council of Hong Kong (GRF 15204917 and 15213818) and National Natrual Science Foundation of China (Grant No. 61672140), and Nanyang Assistant Professorship (NAP) M4082282 and Start-Up Grant (SUG) M4082087 from Nanyang Technological University, Singapore.

Details

ISSN :
15583465 and 15399087
Volume :
18
Database :
OpenAIRE
Journal :
ACM Transactions on Embedded Computing Systems
Accession number :
edsair.doi.dedup.....f7f83903a35256a367373e6904d4f275
Full Text :
https://doi.org/10.1145/3358236