Evaluating DAG scheduling algorithms for maximum parallelism

Wei Zheng; Zhaobin Chen; Rizos Sakellariou; Lu Tang; Jinjun Chen

doi:10.1109/ISPA-BDCloud-SocialCom-SustainCom51426.2020.00033

Evaluating DAG scheduling algorithms for maximum parallelism

Wei Zheng
, Zhaobin Chen
, Rizos Sakellariou
, Lu Tang
, Jinjun Chen

Information Management

Xiamen University
Chinese University of Hong Kong
Swinburne University of Technology

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

Abstract

In practical distributed computing systems, one of the challenges is to schedule efficiently and effectively complex computations composed of interdependent tasks, commonly represented by a Directed Acyclic Graph (DAG). One element of this challenge is that the availability of resources and the precise execution time of different computations are often difficult to predict. Given this unpredictability, the priority based (PB) scheduling scheme aims at maximizing the parallelism of ready tasks. In this paper, the PB scheduling scheme is investigated in detail with respect to its efficiency and performance. Our results suggest that for various experimental settings, the PB scheme outperforms other popular existing solutions in overall execution time, with an acceptable running overhead as well as a wider usability as it can be applied to arbitrary DAG structure.

Original language	English
Title of host publication	Proceedings - 2020 IEEE International Symposium on Parallel and Distributed Processing with Applications, 2020 IEEE International Conference on Big Data and Cloud Computing, 2020 IEEE International Symposium on Social Computing and Networking and 2020 IEEE International Conference on Sustainable Computing and Communications, ISPA-BDCloud-SocialCom-SustainCom 2020
Editors	Jia Hu, Geyong Min, Nektarios Georgalas, Zhiwei Zhao, Fei Hao, Wang Miao
Place of Publication	Danvers, MA
Publisher	IEEE
Pages	49-56
Number of pages	8
ISBN (Electronic)	9781665414852
ISBN (Print)	9781665430517
DOIs	https://doi.org/10.1109/ISPA-BDCloud-SocialCom-SustainCom51426.2020.00033
Publication status	Published - 4 Jun 2021
Event	18th IEEE International Symposium on Parallel and Distributed Processing with Applications, 10th IEEE International Conference on Big Data and Cloud Computing, 13th IEEE International Symposium on Social Computing and Networking and 10th IEEE International Conference on Sustainable Computing and Communications, ISPA-BDCloud-SocialCom-SustainCom 2020 - Virtual, Online, United Kingdom Duration: 17 Dec 2020 → 19 Dec 2020

Conference

Conference	18th IEEE International Symposium on Parallel and Distributed Processing with Applications, 10th IEEE International Conference on Big Data and Cloud Computing, 13th IEEE International Symposium on Social Computing and Networking and 10th IEEE International Conference on Sustainable Computing and Communications, ISPA-BDCloud-SocialCom-SustainCom 2020
Country/Territory	United Kingdom
City	Virtual, Online
Period	17/12/20 → 19/12/20

Keywords

directed Acyclic Graph
heterogeneous Systems
parallelism
scheduling

Access to Document

10.1109/ISPA-BDCloud-SocialCom-SustainCom51426.2020.00033

Cite this

Zheng, W., Chen, Z., Sakellariou, R., Tang, L., & Chen, J. (2021). Evaluating DAG scheduling algorithms for maximum parallelism. In J. Hu, G. Min, N. Georgalas, Z. Zhao, F. Hao, & W. Miao (Eds.), Proceedings - 2020 IEEE International Symposium on Parallel and Distributed Processing with Applications, 2020 IEEE International Conference on Big Data and Cloud Computing, 2020 IEEE International Symposium on Social Computing and Networking and 2020 IEEE International Conference on Sustainable Computing and Communications, ISPA-BDCloud-SocialCom-SustainCom 2020 (pp. 49-56). IEEE. https://doi.org/10.1109/ISPA-BDCloud-SocialCom-SustainCom51426.2020.00033

Zheng, Wei ; Chen, Zhaobin ; Sakellariou, Rizos et al. / Evaluating DAG scheduling algorithms for maximum parallelism. Proceedings - 2020 IEEE International Symposium on Parallel and Distributed Processing with Applications, 2020 IEEE International Conference on Big Data and Cloud Computing, 2020 IEEE International Symposium on Social Computing and Networking and 2020 IEEE International Conference on Sustainable Computing and Communications, ISPA-BDCloud-SocialCom-SustainCom 2020. editor / Jia Hu ; Geyong Min ; Nektarios Georgalas ; Zhiwei Zhao ; Fei Hao ; Wang Miao. Danvers, MA : IEEE, 2021. pp. 49-56

@inproceedings{dbd5c99424654f3cb938c27d27731600,

title = "Evaluating DAG scheduling algorithms for maximum parallelism",

abstract = "In practical distributed computing systems, one of the challenges is to schedule efficiently and effectively complex computations composed of interdependent tasks, commonly represented by a Directed Acyclic Graph (DAG). One element of this challenge is that the availability of resources and the precise execution time of different computations are often difficult to predict. Given this unpredictability, the priority based (PB) scheduling scheme aims at maximizing the parallelism of ready tasks. In this paper, the PB scheduling scheme is investigated in detail with respect to its efficiency and performance. Our results suggest that for various experimental settings, the PB scheme outperforms other popular existing solutions in overall execution time, with an acceptable running overhead as well as a wider usability as it can be applied to arbitrary DAG structure.",

keywords = "directed Acyclic Graph, heterogeneous Systems, parallelism, scheduling",

author = "Wei Zheng and Zhaobin Chen and Rizos Sakellariou and Lu Tang and Jinjun Chen",

note = "Publisher Copyright: {\textcopyright} 2020 IEEE.; 18th IEEE International Symposium on Parallel and Distributed Processing with Applications, 10th IEEE International Conference on Big Data and Cloud Computing, 13th IEEE International Symposium on Social Computing and Networking and 10th IEEE International Conference on Sustainable Computing and Communications, ISPA-BDCloud-SocialCom-SustainCom 2020 ; Conference date: 17-12-2020 Through 19-12-2020",

year = "2021",

month = jun,

day = "4",

doi = "10.1109/ISPA-BDCloud-SocialCom-SustainCom51426.2020.00033",

language = "English",

isbn = "9781665430517",

pages = "49--56",

editor = "Jia Hu and Geyong Min and Nektarios Georgalas and Zhiwei Zhao and Fei Hao and Wang Miao",

booktitle = "Proceedings - 2020 IEEE International Symposium on Parallel and Distributed Processing with Applications, 2020 IEEE International Conference on Big Data and Cloud Computing, 2020 IEEE International Symposium on Social Computing and Networking and 2020 IEEE International Conference on Sustainable Computing and Communications, ISPA-BDCloud-SocialCom-SustainCom 2020",

publisher = "IEEE",

address = "United States",

}

Zheng, W, Chen, Z, Sakellariou, R, Tang, L & Chen, J 2021, Evaluating DAG scheduling algorithms for maximum parallelism. in J Hu, G Min, N Georgalas, Z Zhao, F Hao & W Miao (eds), Proceedings - 2020 IEEE International Symposium on Parallel and Distributed Processing with Applications, 2020 IEEE International Conference on Big Data and Cloud Computing, 2020 IEEE International Symposium on Social Computing and Networking and 2020 IEEE International Conference on Sustainable Computing and Communications, ISPA-BDCloud-SocialCom-SustainCom 2020. IEEE, Danvers, MA, pp. 49-56, 18th IEEE International Symposium on Parallel and Distributed Processing with Applications, 10th IEEE International Conference on Big Data and Cloud Computing, 13th IEEE International Symposium on Social Computing and Networking and 10th IEEE International Conference on Sustainable Computing and Communications, ISPA-BDCloud-SocialCom-SustainCom 2020, Virtual, Online, United Kingdom, 17/12/20. https://doi.org/10.1109/ISPA-BDCloud-SocialCom-SustainCom51426.2020.00033

Evaluating DAG scheduling algorithms for maximum parallelism. / Zheng, Wei; Chen, Zhaobin; Sakellariou, Rizos et al.
Proceedings - 2020 IEEE International Symposium on Parallel and Distributed Processing with Applications, 2020 IEEE International Conference on Big Data and Cloud Computing, 2020 IEEE International Symposium on Social Computing and Networking and 2020 IEEE International Conference on Sustainable Computing and Communications, ISPA-BDCloud-SocialCom-SustainCom 2020. ed. / Jia Hu; Geyong Min; Nektarios Georgalas; Zhiwei Zhao; Fei Hao; Wang Miao. Danvers, MA: IEEE, 2021. p. 49-56.

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Evaluating DAG scheduling algorithms for maximum parallelism

AU - Zheng, Wei

AU - Chen, Zhaobin

AU - Sakellariou, Rizos

AU - Tang, Lu

AU - Chen, Jinjun

PY - 2021/6/4

Y1 - 2021/6/4

N2 - In practical distributed computing systems, one of the challenges is to schedule efficiently and effectively complex computations composed of interdependent tasks, commonly represented by a Directed Acyclic Graph (DAG). One element of this challenge is that the availability of resources and the precise execution time of different computations are often difficult to predict. Given this unpredictability, the priority based (PB) scheduling scheme aims at maximizing the parallelism of ready tasks. In this paper, the PB scheduling scheme is investigated in detail with respect to its efficiency and performance. Our results suggest that for various experimental settings, the PB scheme outperforms other popular existing solutions in overall execution time, with an acceptable running overhead as well as a wider usability as it can be applied to arbitrary DAG structure.

AB - In practical distributed computing systems, one of the challenges is to schedule efficiently and effectively complex computations composed of interdependent tasks, commonly represented by a Directed Acyclic Graph (DAG). One element of this challenge is that the availability of resources and the precise execution time of different computations are often difficult to predict. Given this unpredictability, the priority based (PB) scheduling scheme aims at maximizing the parallelism of ready tasks. In this paper, the PB scheduling scheme is investigated in detail with respect to its efficiency and performance. Our results suggest that for various experimental settings, the PB scheme outperforms other popular existing solutions in overall execution time, with an acceptable running overhead as well as a wider usability as it can be applied to arbitrary DAG structure.

KW - directed Acyclic Graph

KW - heterogeneous Systems

KW - parallelism

KW - scheduling

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

U2 - 10.1109/ISPA-BDCloud-SocialCom-SustainCom51426.2020.00033

DO - 10.1109/ISPA-BDCloud-SocialCom-SustainCom51426.2020.00033

M3 - Conference contribution

AN - SCOPUS:85108024229

SN - 9781665430517

SP - 49

EP - 56

BT - Proceedings - 2020 IEEE International Symposium on Parallel and Distributed Processing with Applications, 2020 IEEE International Conference on Big Data and Cloud Computing, 2020 IEEE International Symposium on Social Computing and Networking and 2020 IEEE International Conference on Sustainable Computing and Communications, ISPA-BDCloud-SocialCom-SustainCom 2020

A2 - Hu, Jia

A2 - Min, Geyong

A2 - Georgalas, Nektarios

A2 - Zhao, Zhiwei

A2 - Hao, Fei

A2 - Miao, Wang

PB - IEEE

CY - Danvers, MA

T2 - 18th IEEE International Symposium on Parallel and Distributed Processing with Applications, 10th IEEE International Conference on Big Data and Cloud Computing, 13th IEEE International Symposium on Social Computing and Networking and 10th IEEE International Conference on Sustainable Computing and Communications, ISPA-BDCloud-SocialCom-SustainCom 2020

Y2 - 17 December 2020 through 19 December 2020

ER -

Zheng W, Chen Z, Sakellariou R, Tang L, Chen J. Evaluating DAG scheduling algorithms for maximum parallelism. In Hu J, Min G, Georgalas N, Zhao Z, Hao F, Miao W, editors, Proceedings - 2020 IEEE International Symposium on Parallel and Distributed Processing with Applications, 2020 IEEE International Conference on Big Data and Cloud Computing, 2020 IEEE International Symposium on Social Computing and Networking and 2020 IEEE International Conference on Sustainable Computing and Communications, ISPA-BDCloud-SocialCom-SustainCom 2020. Danvers, MA: IEEE. 2021. p. 49-56 doi: 10.1109/ISPA-BDCloud-SocialCom-SustainCom51426.2020.00033

Evaluating DAG scheduling algorithms for maximum parallelism

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this