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.
Original language | English |
---|---|
Article number | 91 |
Pages (from-to) | 1-19 |
Journal | ACM Transactions on Embedded Computing Systems |
Volume | 18 |
Issue number | 5s |
DOIs | |
Publication status | Published - Oct 2019 |
Keywords
- Conditional DAG
- Dynamic scheduling
- Response time analysis
- Timing anomaly
ASJC Scopus subject areas
- Software
- Hardware and Architecture