A static multiprocessor scheduling algorithm for arbitrary directed task graphs in uncertain environments

Jun Yang; Xiaochuan Ma; Chaohuan Hou; Zheng Yao

doi:10.1007/978-3-540-69501-1_4

A static multiprocessor scheduling algorithm for arbitrary directed task graphs in uncertain environments

Jun Yang^*, Xiaochuan Ma, Chaohuan Hou, Zheng Yao

^*Corresponding author af dette arbejde

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

4 Citationer (Scopus)

Abstract

The objective of a static scheduling algorithm is to minimize the overall execution time of the program, represented by a directed task graph, by assigning the nodes to the processors. However, sometimes it is very difficult to estimate the execution time of several parts of a program and the communication delays under different circumstances. In this paper, an uncertain intelligent scheduling algorithm based on an expected value model and a genetic algorithm is presented to solve the multiprocessor scheduling problem in which the computation time and the communication time are given by stochastic variables. In simulation examples, it shows that the algorithm performs better than other algorithms in uncertain environments.

Originalsprog	Engelsk
Titel	Algorithms and Architectures for Parallel Processing - 8th International Conference, ICA3PP 2008, Proceedings
Antal sider	12
Forlag	Springer
Publikationsdato	2008
Sider	18-29
ISBN (Trykt)	9783540695004
DOI	https://doi.org/10.1007/978-3-540-69501-1_4
Status	Udgivet - 2008
Udgivet eksternt	Ja
Begivenhed	8th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2008 - , Cypern Varighed: 9 jun. 2008 → 11 jun. 2008

Konference

Konference	8th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2008
Land/Område	Cypern
Periode	09/06/2008 → 11/06/2008

Navn	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vol/bind	5022 LNCS
ISSN	0302-9743

Adgang til dokumentet

10.1007/978-3-540-69501-1_4

Andre filer og links

Link to publication in Scopus

Citationsformater

Yang, J., Ma, X., Hou, C., & Yao, Z. (2008). A static multiprocessor scheduling algorithm for arbitrary directed task graphs in uncertain environments. I Algorithms and Architectures for Parallel Processing - 8th International Conference, ICA3PP 2008, Proceedings (s. 18-29). Springer. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Bind 5022 LNCS https://doi.org/10.1007/978-3-540-69501-1_4

A static multiprocessor scheduling algorithm for arbitrary directed task graphs in uncertain environments. / Yang, Jun; Ma, Xiaochuan; Hou, Chaohuan; Yao, Zheng.

Algorithms and Architectures for Parallel Processing - 8th International Conference, ICA3PP 2008, Proceedings. Springer, 2008. s. 18-29 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind 5022 LNCS).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Yang, J, Ma, X, Hou, C & Yao, Z 2008, A static multiprocessor scheduling algorithm for arbitrary directed task graphs in uncertain environments. i Algorithms and Architectures for Parallel Processing - 8th International Conference, ICA3PP 2008, Proceedings. Springer, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), bind 5022 LNCS, s. 18-29, 8th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2008, Cypern, 09/06/2008. https://doi.org/10.1007/978-3-540-69501-1_4

Yang J, Ma X, Hou C, Yao Z. A static multiprocessor scheduling algorithm for arbitrary directed task graphs in uncertain environments. I Algorithms and Architectures for Parallel Processing - 8th International Conference, ICA3PP 2008, Proceedings. Springer. 2008. s. 18-29. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind 5022 LNCS). https://doi.org/10.1007/978-3-540-69501-1_4

Yang, Jun ; Ma, Xiaochuan ; Hou, Chaohuan ; Yao, Zheng. / A static multiprocessor scheduling algorithm for arbitrary directed task graphs in uncertain environments. Algorithms and Architectures for Parallel Processing - 8th International Conference, ICA3PP 2008, Proceedings. Springer, 2008. s. 18-29 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind 5022 LNCS).

@inproceedings{94a3a79fc8194a77b0002bd2c93db44a,

title = "A static multiprocessor scheduling algorithm for arbitrary directed task graphs in uncertain environments",

abstract = "The objective of a static scheduling algorithm is to minimize the overall execution time of the program, represented by a directed task graph, by assigning the nodes to the processors. However, sometimes it is very difficult to estimate the execution time of several parts of a program and the communication delays under different circumstances. In this paper, an uncertain intelligent scheduling algorithm based on an expected value model and a genetic algorithm is presented to solve the multiprocessor scheduling problem in which the computation time and the communication time are given by stochastic variables. In simulation examples, it shows that the algorithm performs better than other algorithms in uncertain environments.",

keywords = "Genetic algorithm, Parallel processing, Scheduling, Stochastic programming",

author = "Jun Yang and Xiaochuan Ma and Chaohuan Hou and Zheng Yao",

year = "2008",

doi = "10.1007/978-3-540-69501-1_4",

language = "English",

isbn = "9783540695004",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "18--29",

booktitle = "Algorithms and Architectures for Parallel Processing - 8th International Conference, ICA3PP 2008, Proceedings",

address = "Switzerland",

note = "8th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2008 ; Conference date: 09-06-2008 Through 11-06-2008",

}

TY - GEN

T1 - A static multiprocessor scheduling algorithm for arbitrary directed task graphs in uncertain environments

AU - Yang, Jun

AU - Ma, Xiaochuan

AU - Hou, Chaohuan

AU - Yao, Zheng

PY - 2008

Y1 - 2008

N2 - The objective of a static scheduling algorithm is to minimize the overall execution time of the program, represented by a directed task graph, by assigning the nodes to the processors. However, sometimes it is very difficult to estimate the execution time of several parts of a program and the communication delays under different circumstances. In this paper, an uncertain intelligent scheduling algorithm based on an expected value model and a genetic algorithm is presented to solve the multiprocessor scheduling problem in which the computation time and the communication time are given by stochastic variables. In simulation examples, it shows that the algorithm performs better than other algorithms in uncertain environments.

AB - The objective of a static scheduling algorithm is to minimize the overall execution time of the program, represented by a directed task graph, by assigning the nodes to the processors. However, sometimes it is very difficult to estimate the execution time of several parts of a program and the communication delays under different circumstances. In this paper, an uncertain intelligent scheduling algorithm based on an expected value model and a genetic algorithm is presented to solve the multiprocessor scheduling problem in which the computation time and the communication time are given by stochastic variables. In simulation examples, it shows that the algorithm performs better than other algorithms in uncertain environments.

KW - Genetic algorithm

KW - Parallel processing

KW - Scheduling

KW - Stochastic programming

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

U2 - 10.1007/978-3-540-69501-1_4

DO - 10.1007/978-3-540-69501-1_4

M3 - Article in proceedings

AN - SCOPUS:46049096998

SN - 9783540695004

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 18

EP - 29

BT - Algorithms and Architectures for Parallel Processing - 8th International Conference, ICA3PP 2008, Proceedings

PB - Springer

T2 - 8th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2008

Y2 - 9 June 2008 through 11 June 2008

ER -