Bounding the Response Time of DAG Tasks Using Long Paths

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

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

10 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 languageEnglish
Title of host publicationProceeding - 43rd IEEE Real-Time Systems Symposium, RTSS 2022
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages474-486
Number of pages13
ISBN (Electronic)9781665453462
DOIs
Publication statusPublished - Dec 2022
Event43rd IEEE Real-Time Systems Symposium, RTSS 2022 - Houston, United States
Duration: 5 Dec 20228 Dec 2022

Publication series

NameProceedings - Real-Time Systems Symposium
Volume2022-December
ISSN (Print)1052-8725

Conference

Conference43rd IEEE Real-Time Systems Symposium, RTSS 2022
Country/TerritoryUnited States
CityHouston
Period5/12/228/12/22

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Bounding the Response Time of DAG Tasks Using Long Paths'. Together they form a unique fingerprint.

Cite this