Response Time Analysis and Optimization of DAG Tasks Exploiting Mutually Exclusive Execution

Haochun Liang; Xu Jiang; Nan Guan; Qingqiang He; Wang Yi

doi:10.1109/DAC56929.2023.10247927

Response Time Analysis and Optimization of DAG Tasks Exploiting Mutually Exclusive Execution

Haochun Liang
, Xu Jiang^*
, Nan Guan
, Qingqiang He
, Wang Yi

^*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

8 Citations (Scopus)

Abstract

There is an increasing move towards implementing embedded real-time systems upon multiprocessors with parallel applications, which are usually modeled as Directed Acyclic Graphs (DAGs). Plentiful work has been presented to optimize the bound of Worst-Case Response Time (WCRT) since the cornerstone work proposed by Graham in 1969. However, all these works are developed on the basis of Graham's bound and failed to tackle the root of pessimism in it. In this work, we present a novel method to optimize the WCRT bound of a DAG task by designing mutually exclusive groups so that a sequential execution is enforced for some nodes, under which the problem of bounding WCRT becomes a problem of identifying a mutually exclusive path and thus does not suffer the pessimism in Graham's bound. Experiments are conducted to evaluate the performance of our method against other WCRT optimization approaches in the state-of-the-art. © 2023 IEEE.

Original language	English
Title of host publication	2023 60th ACM/IEEE Design Automation Conference (DAC)
Publisher	IEEE
Number of pages	6
ISBN (Electronic)	9798350323481
ISBN (Print)	9798350323498
DOIs	https://doi.org/10.1109/DAC56929.2023.10247927
Publication status	Published - 2023
Event	60th ACM/IEEE Design Automation Conference (DAC 2023) - San Francisco, United States Duration: 9 Jul 2023 → 13 Jul 2023 https://www.dac.com/About/Conference-Archive/60th-DAC-2023

Publication series

Name	Proceedings - Design Automation Conference
Volume	2023-July
ISSN (Print)	0738-100X

Conference

Conference	60th ACM/IEEE Design Automation Conference (DAC 2023)
Abbreviated title	60th DAC
Place	United States
City	San Francisco
Period	9/07/23 → 13/07/23
Internet address	https://www.dac.com/About/Conference-Archive/60th-DAC-2023

RGC Funding Information

RGC-funded

Access Output

10.1109/DAC56929.2023.10247927

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{d48ce8c1f1d24644b2dcf057a1018375,

title = "Response Time Analysis and Optimization of DAG Tasks Exploiting Mutually Exclusive Execution",

abstract = "There is an increasing move towards implementing embedded real-time systems upon multiprocessors with parallel applications, which are usually modeled as Directed Acyclic Graphs (DAGs). Plentiful work has been presented to optimize the bound of Worst-Case Response Time (WCRT) since the cornerstone work proposed by Graham in 1969. However, all these works are developed on the basis of Graham's bound and failed to tackle the root of pessimism in it. In this work, we present a novel method to optimize the WCRT bound of a DAG task by designing mutually exclusive groups so that a sequential execution is enforced for some nodes, under which the problem of bounding WCRT becomes a problem of identifying a mutually exclusive path and thus does not suffer the pessimism in Graham's bound. Experiments are conducted to evaluate the performance of our method against other WCRT optimization approaches in the state-of-the-art. {\textcopyright} 2023 IEEE.",

author = "Haochun Liang and Xu Jiang and Nan Guan and Qingqiang He and Wang Yi",

year = "2023",

doi = "10.1109/DAC56929.2023.10247927",

language = "English",

isbn = "9798350323498",

series = "Proceedings - Design Automation Conference",

publisher = "IEEE",

booktitle = "2023 60th ACM/IEEE Design Automation Conference (DAC)",

address = "United States",

note = "60th ACM/IEEE Design Automation Conference (DAC 2023), 60th DAC ; Conference date: 09-07-2023 Through 13-07-2023",

url = "https://www.dac.com/About/Conference-Archive/60th-DAC-2023",

}

Liang, H, Jiang, X, Guan, N, He, Q & Yi, W 2023, Response Time Analysis and Optimization of DAG Tasks Exploiting Mutually Exclusive Execution. in 2023 60th ACM/IEEE Design Automation Conference (DAC). Proceedings - Design Automation Conference, vol. 2023-July, IEEE, 60th ACM/IEEE Design Automation Conference (DAC 2023), San Francisco, California, United States, 9/07/23. https://doi.org/10.1109/DAC56929.2023.10247927

Response Time Analysis and Optimization of DAG Tasks Exploiting Mutually Exclusive Execution. / Liang, Haochun; Jiang, Xu; Guan, Nan et al.
2023 60th ACM/IEEE Design Automation Conference (DAC). IEEE, 2023. (Proceedings - Design Automation Conference; Vol. 2023-July).

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

TY - GEN

T1 - Response Time Analysis and Optimization of DAG Tasks Exploiting Mutually Exclusive Execution

AU - Liang, Haochun

AU - Jiang, Xu

AU - Guan, Nan

AU - He, Qingqiang

AU - Yi, Wang

PY - 2023

Y1 - 2023

N2 - There is an increasing move towards implementing embedded real-time systems upon multiprocessors with parallel applications, which are usually modeled as Directed Acyclic Graphs (DAGs). Plentiful work has been presented to optimize the bound of Worst-Case Response Time (WCRT) since the cornerstone work proposed by Graham in 1969. However, all these works are developed on the basis of Graham's bound and failed to tackle the root of pessimism in it. In this work, we present a novel method to optimize the WCRT bound of a DAG task by designing mutually exclusive groups so that a sequential execution is enforced for some nodes, under which the problem of bounding WCRT becomes a problem of identifying a mutually exclusive path and thus does not suffer the pessimism in Graham's bound. Experiments are conducted to evaluate the performance of our method against other WCRT optimization approaches in the state-of-the-art. © 2023 IEEE.

AB - There is an increasing move towards implementing embedded real-time systems upon multiprocessors with parallel applications, which are usually modeled as Directed Acyclic Graphs (DAGs). Plentiful work has been presented to optimize the bound of Worst-Case Response Time (WCRT) since the cornerstone work proposed by Graham in 1969. However, all these works are developed on the basis of Graham's bound and failed to tackle the root of pessimism in it. In this work, we present a novel method to optimize the WCRT bound of a DAG task by designing mutually exclusive groups so that a sequential execution is enforced for some nodes, under which the problem of bounding WCRT becomes a problem of identifying a mutually exclusive path and thus does not suffer the pessimism in Graham's bound. Experiments are conducted to evaluate the performance of our method against other WCRT optimization approaches in the state-of-the-art. © 2023 IEEE.

UR - https://www.scopus.com/pages/publications/85173071704

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

U2 - 10.1109/DAC56929.2023.10247927

DO - 10.1109/DAC56929.2023.10247927

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

SN - 9798350323498

T3 - Proceedings - Design Automation Conference

BT - 2023 60th ACM/IEEE Design Automation Conference (DAC)

PB - IEEE

T2 - 60th ACM/IEEE Design Automation Conference (DAC 2023)

Y2 - 9 July 2023 through 13 July 2023

ER -

Response Time Analysis and Optimization of DAG Tasks Exploiting Mutually Exclusive Execution

Abstract

Publication series

Conference

RGC Funding Information

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this