Back to Search
Start Over
Timing-Anomaly Free Dynamic Scheduling of Conditional DAG Tasks on Multi-Core Systems
- 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.
- Subjects :
- Multi-core processor
Schedule
Theoretical computer science
Computer science
0206 medical engineering
Response time
Timing Anomaly
02 engineering and technology
Dynamic priority scheduling
020601 biomedical engineering
Upper and lower bounds
020202 computer hardware & architecture
Scheduling (computing)
Hardware and Architecture
Dynamic Scheduling
0202 electrical engineering, electronic engineering, information engineering
Key (cryptography)
Computer science and engineering [Engineering]
Time complexity
Software
Subjects
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