On the Degree of Parallelism in Real-Time Scheduling of DAG Tasks

Qingqiang He; Nan Guan; Mingsong Lv; Zonghua Gu

doi:10.23919/DATE56975.2023.10137259

On the Degree of Parallelism in Real-Time Scheduling of DAG Tasks

Qingqiang He, Nan Guan, Mingsong Lv, Zonghua Gu

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

4 Citations (Scopus)

Abstract

Real-time scheduling and analysis of parallel tasks modeled as directed acyclic graphs (DAG) have been intensively studied in recent years. The degree of parallelism of DAG tasks is an important characterization in scheduling. This paper revisits the definition and the computing algorithms for the degree of parallelism of DAG tasks, and clarifies some misunderstandings regarding the degree of parallelism which exist in real-time literature. Based on the degree of the parallelism, we propose a real-time scheduling approach for DAG tasks, which is quite simple but rather effective and outperforms the state-of-the-art by a considerable margin.

Original language	English
Title of host publication	2023 Design, Automation and Test in Europe Conference and Exhibition, DATE 2023 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1-6
ISBN (Electronic)	9783981926378
DOIs	https://doi.org/10.23919/DATE56975.2023.10137259
Publication status	Published - Jun 2023
Event	2023 Design, Automation and Test in Europe Conference and Exhibition, DATE 2023 - Antwerp, Belgium Duration: 17 Apr 2023 → 19 Apr 2023

Publication series

Name	Proceedings -Design, Automation and Test in Europe, DATE
Volume	2023-April
ISSN (Print)	1530-1591

Conference

Conference	2023 Design, Automation and Test in Europe Conference and Exhibition, DATE 2023
Country/Territory	Belgium
City	Antwerp
Period	17/04/23 → 19/04/23

ASJC Scopus subject areas

General Engineering

More information

10.23919/DATE56975.2023.10137259

Cite this

He, Q., Guan, N., Lv, M., & Gu, Z. (2023). On the Degree of Parallelism in Real-Time Scheduling of DAG Tasks. In 2023 Design, Automation and Test in Europe Conference and Exhibition, DATE 2023 - Proceedings (pp. 1-6). (Proceedings -Design, Automation and Test in Europe, DATE; Vol. 2023-April). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.23919/DATE56975.2023.10137259

@inproceedings{28b577587dba46efad8b778ed54f07d5,

title = "On the Degree of Parallelism in Real-Time Scheduling of DAG Tasks",

abstract = "Real-time scheduling and analysis of parallel tasks modeled as directed acyclic graphs (DAG) have been intensively studied in recent years. The degree of parallelism of DAG tasks is an important characterization in scheduling. This paper revisits the definition and the computing algorithms for the degree of parallelism of DAG tasks, and clarifies some misunderstandings regarding the degree of parallelism which exist in real-time literature. Based on the degree of the parallelism, we propose a real-time scheduling approach for DAG tasks, which is quite simple but rather effective and outperforms the state-of-the-art by a considerable margin.",

author = "Qingqiang He and Nan Guan and Mingsong Lv and Zonghua Gu",

note = "Funding Information: This work is partially supported by Research Grants Council of Hong Kong (GRF 11208522, 15206221). Publisher Copyright: {\textcopyright} 2023 EDAA.; 2023 Design, Automation and Test in Europe Conference and Exhibition, DATE 2023 ; Conference date: 17-04-2023 Through 19-04-2023",

year = "2023",

month = jun,

doi = "10.23919/DATE56975.2023.10137259",

language = "English",

series = "Proceedings -Design, Automation and Test in Europe, DATE",

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

pages = "1--6",

booktitle = "2023 Design, Automation and Test in Europe Conference and Exhibition, DATE 2023 - Proceedings",

}

He, Q, Guan, N, Lv, M & Gu, Z 2023, On the Degree of Parallelism in Real-Time Scheduling of DAG Tasks. in 2023 Design, Automation and Test in Europe Conference and Exhibition, DATE 2023 - Proceedings. Proceedings -Design, Automation and Test in Europe, DATE, vol. 2023-April, Institute of Electrical and Electronics Engineers Inc., pp. 1-6, 2023 Design, Automation and Test in Europe Conference and Exhibition, DATE 2023, Antwerp, Belgium, 17/04/23. https://doi.org/10.23919/DATE56975.2023.10137259

On the Degree of Parallelism in Real-Time Scheduling of DAG Tasks. / He, Qingqiang; Guan, Nan; Lv, Mingsong et al.
2023 Design, Automation and Test in Europe Conference and Exhibition, DATE 2023 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2023. p. 1-6 (Proceedings -Design, Automation and Test in Europe, DATE; Vol. 2023-April).

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

TY - GEN

T1 - On the Degree of Parallelism in Real-Time Scheduling of DAG Tasks

AU - He, Qingqiang

AU - Guan, Nan

AU - Lv, Mingsong

AU - Gu, Zonghua

PY - 2023/6

Y1 - 2023/6

N2 - Real-time scheduling and analysis of parallel tasks modeled as directed acyclic graphs (DAG) have been intensively studied in recent years. The degree of parallelism of DAG tasks is an important characterization in scheduling. This paper revisits the definition and the computing algorithms for the degree of parallelism of DAG tasks, and clarifies some misunderstandings regarding the degree of parallelism which exist in real-time literature. Based on the degree of the parallelism, we propose a real-time scheduling approach for DAG tasks, which is quite simple but rather effective and outperforms the state-of-the-art by a considerable margin.

AB - Real-time scheduling and analysis of parallel tasks modeled as directed acyclic graphs (DAG) have been intensively studied in recent years. The degree of parallelism of DAG tasks is an important characterization in scheduling. This paper revisits the definition and the computing algorithms for the degree of parallelism of DAG tasks, and clarifies some misunderstandings regarding the degree of parallelism which exist in real-time literature. Based on the degree of the parallelism, we propose a real-time scheduling approach for DAG tasks, which is quite simple but rather effective and outperforms the state-of-the-art by a considerable margin.

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

U2 - 10.23919/DATE56975.2023.10137259

DO - 10.23919/DATE56975.2023.10137259

M3 - Conference article published in proceeding or book

AN - SCOPUS:85162675057

T3 - Proceedings -Design, Automation and Test in Europe, DATE

SP - 1

EP - 6

BT - 2023 Design, Automation and Test in Europe Conference and Exhibition, DATE 2023 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2023 Design, Automation and Test in Europe Conference and Exhibition, DATE 2023

Y2 - 17 April 2023 through 19 April 2023

ER -

On the Degree of Parallelism in Real-Time Scheduling of DAG Tasks

Abstract

Publication series

Conference

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this