Timing-anomaly free dynamic scheduling of conditional DAG tasks on multi-core systems
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 enfo...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/145468 |
| _version_ | 1826122861706739712 |
|---|---|
| author | Chen, Peng Liu, Weichen Jiang, Xu He, Qingqiang Guan, Nan |
| author2 | School of Computer Science and Engineering |
| author_facet | School of Computer Science and Engineering Chen, Peng Liu, Weichen Jiang, Xu He, Qingqiang Guan, Nan |
| author_sort | Chen, Peng |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T05:55:29Z |
| format | Journal Article |
| id | ntu-10356/145468 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T05:55:29Z |
| publishDate | 2020 |
| record_format | dspace |
| spelling | ntu-10356/1454682023-12-06T07:35:42Z Timing-anomaly free dynamic scheduling of conditional DAG tasks on multi-core systems Chen, Peng Liu, Weichen Jiang, Xu He, Qingqiang Guan, Nan School of Computer Science and Engineering Engineering::Computer science and engineering Timing Anomaly Dynamic Scheduling 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. 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. 2020-12-22T08:10:28Z 2020-12-22T08:10:28Z 2019 Journal Article Chen, P., Liu, W., Jiang, X., He, Q., & Guan, N. (2019). Timing-anomaly free dynamic scheduling of conditional DAG tasks on multi-core systems. ACM Transactions on Embedded Computing Systems, 18, 1-19. doi:10.1145/3358236 1539-9087 https://hdl.handle.net/10356/145468 10.1145/3358236 18 1 19 en Research Grants Council of Hong Kong (GRF 15204917 and 15213818) National Natrual Science Foundation of China (Grant No. 61672140) Nanyang Technological University, Singapore (M4082282, M4082087) ACM Transactions on Embedded Computing Systems doi:10.21979/N9/F5KN5M © 2019 Association for Computing Machinery (ACM). All rights reserved. This paper was published in ACM Transactions on Embedded Computing Systems and is made available with permission of Association for Computing Machinery (ACM). application/pdf |
| spellingShingle | Engineering::Computer science and engineering Timing Anomaly Dynamic Scheduling Chen, Peng Liu, Weichen Jiang, Xu He, Qingqiang Guan, Nan Timing-anomaly free dynamic scheduling of conditional DAG tasks on multi-core systems |
| title | Timing-anomaly free dynamic scheduling of conditional DAG tasks on multi-core systems |
| title_full | Timing-anomaly free dynamic scheduling of conditional DAG tasks on multi-core systems |
| title_fullStr | Timing-anomaly free dynamic scheduling of conditional DAG tasks on multi-core systems |
| title_full_unstemmed | Timing-anomaly free dynamic scheduling of conditional DAG tasks on multi-core systems |
| title_short | Timing-anomaly free dynamic scheduling of conditional DAG tasks on multi-core systems |
| title_sort | timing anomaly free dynamic scheduling of conditional dag tasks on multi core systems |
| topic | Engineering::Computer science and engineering Timing Anomaly Dynamic Scheduling |
| url | https://hdl.handle.net/10356/145468 |
| work_keys_str_mv | AT chenpeng timinganomalyfreedynamicschedulingofconditionaldagtasksonmulticoresystems AT liuweichen timinganomalyfreedynamicschedulingofconditionaldagtasksonmulticoresystems AT jiangxu timinganomalyfreedynamicschedulingofconditionaldagtasksonmulticoresystems AT heqingqiang timinganomalyfreedynamicschedulingofconditionaldagtasksonmulticoresystems AT guannan timinganomalyfreedynamicschedulingofconditionaldagtasksonmulticoresystems |