Bounding the Response Time of DAG Tasks Using Long Paths

Qingqiang He; Nan Guan; Mingsong Lv; Xu Jiang; Wanli Chang

doi:10.1109/RTSS55097.2022.00047

Bounding the Response Time of DAG Tasks Using Long Paths

Qingqiang He, Nan Guan^*, Mingsong Lv, Xu Jiang, Wanli Chang

^*Corresponding author for this work

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

17 Citations (Scopus)

Abstract

In 1969, Graham developed a well-known response time bound for a DAG task using the total workload and the longest path of the DAG, which has been widely applied to solve many scheduling and analysis problems of DAG-based task systems. This paper presents a new response time bound for a DAG task using the total workload and the lengths of multiple long paths of the DAG, instead of the longest path in Graham's bound. Our new bound theoretically dominates and empirically outperforms Graham's bound. We further extend the proposed approach to multi-DAG task systems. Our schedulability test theoretically dominates federated scheduling and outperforms the state-of-the-art by a considerable margin.

Original language	English
Title of host publication	Proceedings - 43rd IEEE Real-Time Systems Symposium (RTSS 2022)
Publisher	IEEE
Pages	474-486
ISBN (Electronic)	978-1-6654-5346-2
DOIs	https://doi.org/10.1109/RTSS55097.2022.00047
Publication status	Published - 2022
Event	43rd IEEE Real-Time Systems Symposium, RTSS 2022 - Houston, United States Duration: 5 Dec 2022 → 8 Dec 2022

Publication series

Name	Proceedings - Real-Time Systems Symposium
Volume	2022-December
ISSN (Print)	1052-8725

Conference

Conference	43rd IEEE Real-Time Systems Symposium, RTSS 2022
Place	United States
City	Houston
Period	5/12/22 → 8/12/22

Bibliographical note

Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).

Funding

This work is supported by the Research Grants Council of Hong Kong (GRF 11208522, 15206221) and the National Natural Science Foundation of China (NSFC 62102072). The authors also thank the anonymous reviewers for their helpful comments

RGC Funding Information

RGC-funded

Access Output

10.1109/RTSS55097.2022.00047

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{5919ba89878b42a7af9fbd37417fee8b,

title = "Bounding the Response Time of DAG Tasks Using Long Paths",

abstract = "In 1969, Graham developed a well-known response time bound for a DAG task using the total workload and the longest path of the DAG, which has been widely applied to solve many scheduling and analysis problems of DAG-based task systems. This paper presents a new response time bound for a DAG task using the total workload and the lengths of multiple long paths of the DAG, instead of the longest path in Graham's bound. Our new bound theoretically dominates and empirically outperforms Graham's bound. We further extend the proposed approach to multi-DAG task systems. Our schedulability test theoretically dominates federated scheduling and outperforms the state-of-the-art by a considerable margin.",

author = "Qingqiang He and Nan Guan and Mingsong Lv and Xu Jiang and Wanli Chang",

note = "Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).; 43rd IEEE Real-Time Systems Symposium, RTSS 2022 ; Conference date: 05-12-2022 Through 08-12-2022",

year = "2022",

doi = "10.1109/RTSS55097.2022.00047",

language = "English",

series = "Proceedings - Real-Time Systems Symposium",

publisher = "IEEE",

pages = "474--486",

booktitle = "Proceedings - 43rd IEEE Real-Time Systems Symposium (RTSS 2022)",

address = "United States",

}

He, Q, Guan, N, Lv, M, Jiang, X & Chang, W 2022, Bounding the Response Time of DAG Tasks Using Long Paths. in Proceedings - 43rd IEEE Real-Time Systems Symposium (RTSS 2022). Proceedings - Real-Time Systems Symposium, vol. 2022-December, IEEE, pp. 474-486, 43rd IEEE Real-Time Systems Symposium, RTSS 2022, Houston, United States, 5/12/22. https://doi.org/10.1109/RTSS55097.2022.00047

Bounding the Response Time of DAG Tasks Using Long Paths. / He, Qingqiang; Guan, Nan; Lv, Mingsong et al.
Proceedings - 43rd IEEE Real-Time Systems Symposium (RTSS 2022). IEEE, 2022. p. 474-486 (Proceedings - Real-Time Systems Symposium; Vol. 2022-December).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Bounding the Response Time of DAG Tasks Using Long Paths

AU - He, Qingqiang

AU - Guan, Nan

AU - Lv, Mingsong

AU - Jiang, Xu

AU - Chang, Wanli

N1 - Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).

PY - 2022

Y1 - 2022

N2 - In 1969, Graham developed a well-known response time bound for a DAG task using the total workload and the longest path of the DAG, which has been widely applied to solve many scheduling and analysis problems of DAG-based task systems. This paper presents a new response time bound for a DAG task using the total workload and the lengths of multiple long paths of the DAG, instead of the longest path in Graham's bound. Our new bound theoretically dominates and empirically outperforms Graham's bound. We further extend the proposed approach to multi-DAG task systems. Our schedulability test theoretically dominates federated scheduling and outperforms the state-of-the-art by a considerable margin.

AB - In 1969, Graham developed a well-known response time bound for a DAG task using the total workload and the longest path of the DAG, which has been widely applied to solve many scheduling and analysis problems of DAG-based task systems. This paper presents a new response time bound for a DAG task using the total workload and the lengths of multiple long paths of the DAG, instead of the longest path in Graham's bound. Our new bound theoretically dominates and empirically outperforms Graham's bound. We further extend the proposed approach to multi-DAG task systems. Our schedulability test theoretically dominates federated scheduling and outperforms the state-of-the-art by a considerable margin.

UR - http://www.scopus.com/inward/record.url?scp=85146122561&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85146122561&origin=recordpage

U2 - 10.1109/RTSS55097.2022.00047

DO - 10.1109/RTSS55097.2022.00047

M3 - RGC 32 - Refereed conference paper (with host publication)

T3 - Proceedings - Real-Time Systems Symposium

SP - 474

EP - 486

BT - Proceedings - 43rd IEEE Real-Time Systems Symposium (RTSS 2022)

PB - IEEE

T2 - 43rd IEEE Real-Time Systems Symposium, RTSS 2022

Y2 - 5 December 2022 through 8 December 2022

ER -

Bounding the Response Time of DAG Tasks Using Long Paths

Abstract

Publication series

Conference

Bibliographical note

Funding

RGC Funding Information

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

GRF: Managing Information Synchronicity in Real-Time Systems

GRF: Building a Theoretical Foundation for Real-time ROS

Cite this

Bounding the Response Time of DAG Tasks Using Long Paths

Abstract

Publication series

Conference

Bibliographical note

Funding

RGC Funding Information

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Projects

GRF: Managing Information Synchronicity in Real-Time Systems

GRF: Building a Theoretical Foundation for Real-time ROS

Cite this