Efficient Response Time Bound for Typed DAG Tasks

Qingqiang He; Yongzheng Sun; Mingsong Lv; Weichen Liu

doi:10.1109/RTCSA58653.2023.00034

Efficient Response Time Bound for Typed DAG Tasks

Qingqiang He, Yongzheng Sun, Mingsong Lv, Weichen Liu

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

Abstract

Heterogeneous multi-core platforms have been used in many fields to meet the increasing requirement of computation. In this paper, we study the response time bound of typed DAG (directed acyclic graph) tasks on heterogeneous multi-core platforms. The existing bound has exponential time complexity. In this paper, we propose a new bound that can be computed with complexity O(|V| + |E|) and is only slightly larger than the state-of-the-art. Experiments demonstrate that the computation of our bound is significantly more efficient than the existing bound and our bound has almost the same tightness as the existing bound.

Original language	English
Title of host publication	Proceedings - 2023 IEEE 29th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2023
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	226-231
Number of pages	6
ISBN (Electronic)	9798350337860
DOIs	https://doi.org/10.1109/RTCSA58653.2023.00034
Publication status	Published - Aug 2023
Event	29th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2023 - Niigata, Japan Duration: 30 Aug 2023 → 1 Sept 2023

Publication series

Name	Proceedings - 2023 IEEE 29th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2023

Conference

Conference	29th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2023
Country/Territory	Japan
City	Niigata
Period	30/08/23 → 1/09/23

Keywords

heterogeneous multi-core
response time bound
typed DAG task

ASJC Scopus subject areas

Computer Networks and Communications
Computer Science Applications
Hardware and Architecture
Software

More information

10.1109/RTCSA58653.2023.00034

Cite this

He, Q., Sun, Y., Lv, M., & Liu, W. (2023). Efficient Response Time Bound for Typed DAG Tasks. In Proceedings - 2023 IEEE 29th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2023 (pp. 226-231). (Proceedings - 2023 IEEE 29th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2023). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/RTCSA58653.2023.00034

He, Qingqiang ; Sun, Yongzheng ; Lv, Mingsong et al. / Efficient Response Time Bound for Typed DAG Tasks. Proceedings - 2023 IEEE 29th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2023. Institute of Electrical and Electronics Engineers Inc., 2023. pp. 226-231 (Proceedings - 2023 IEEE 29th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2023).

@inproceedings{604442fab81142b285cc9ee508091200,

title = "Efficient Response Time Bound for Typed DAG Tasks",

abstract = "Heterogeneous multi-core platforms have been used in many fields to meet the increasing requirement of computation. In this paper, we study the response time bound of typed DAG (directed acyclic graph) tasks on heterogeneous multi-core platforms. The existing bound has exponential time complexity. In this paper, we propose a new bound that can be computed with complexity O(|V| + |E|) and is only slightly larger than the state-of-the-art. Experiments demonstrate that the computation of our bound is significantly more efficient than the existing bound and our bound has almost the same tightness as the existing bound.",

keywords = "heterogeneous multi-core, response time bound, typed DAG task",

author = "Qingqiang He and Yongzheng Sun and Mingsong Lv and Weichen Liu",

note = "Publisher Copyright: {\textcopyright} 2023 IEEE.; 29th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2023 ; Conference date: 30-08-2023 Through 01-09-2023",

year = "2023",

month = aug,

doi = "10.1109/RTCSA58653.2023.00034",

language = "English",

series = "Proceedings - 2023 IEEE 29th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2023",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "226--231",

booktitle = "Proceedings - 2023 IEEE 29th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2023",

}

He, Q, Sun, Y, Lv, M & Liu, W 2023, Efficient Response Time Bound for Typed DAG Tasks. in Proceedings - 2023 IEEE 29th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2023. Proceedings - 2023 IEEE 29th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2023, Institute of Electrical and Electronics Engineers Inc., pp. 226-231, 29th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2023, Niigata, Japan, 30/08/23. https://doi.org/10.1109/RTCSA58653.2023.00034

Efficient Response Time Bound for Typed DAG Tasks. / He, Qingqiang; Sun, Yongzheng; Lv, Mingsong et al.
Proceedings - 2023 IEEE 29th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2023. Institute of Electrical and Electronics Engineers Inc., 2023. p. 226-231 (Proceedings - 2023 IEEE 29th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2023).

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - Efficient Response Time Bound for Typed DAG Tasks

AU - He, Qingqiang

AU - Sun, Yongzheng

AU - Lv, Mingsong

AU - Liu, Weichen

PY - 2023/8

Y1 - 2023/8

N2 - Heterogeneous multi-core platforms have been used in many fields to meet the increasing requirement of computation. In this paper, we study the response time bound of typed DAG (directed acyclic graph) tasks on heterogeneous multi-core platforms. The existing bound has exponential time complexity. In this paper, we propose a new bound that can be computed with complexity O(|V| + |E|) and is only slightly larger than the state-of-the-art. Experiments demonstrate that the computation of our bound is significantly more efficient than the existing bound and our bound has almost the same tightness as the existing bound.

AB - Heterogeneous multi-core platforms have been used in many fields to meet the increasing requirement of computation. In this paper, we study the response time bound of typed DAG (directed acyclic graph) tasks on heterogeneous multi-core platforms. The existing bound has exponential time complexity. In this paper, we propose a new bound that can be computed with complexity O(|V| + |E|) and is only slightly larger than the state-of-the-art. Experiments demonstrate that the computation of our bound is significantly more efficient than the existing bound and our bound has almost the same tightness as the existing bound.

KW - heterogeneous multi-core

KW - response time bound

KW - typed DAG task

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

U2 - 10.1109/RTCSA58653.2023.00034

DO - 10.1109/RTCSA58653.2023.00034

M3 - Conference article published in proceeding or book

AN - SCOPUS:85175684229

T3 - Proceedings - 2023 IEEE 29th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2023

SP - 226

EP - 231

BT - Proceedings - 2023 IEEE 29th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2023

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 29th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2023

Y2 - 30 August 2023 through 1 September 2023

ER -

He Q, Sun Y, Lv M, Liu W. Efficient Response Time Bound for Typed DAG Tasks. In Proceedings - 2023 IEEE 29th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2023. Institute of Electrical and Electronics Engineers Inc. 2023. p. 226-231. (Proceedings - 2023 IEEE 29th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2023). doi: 10.1109/RTCSA58653.2023.00034

Efficient Response Time Bound for Typed DAG Tasks

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this