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 for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Citations (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.

Original language	English
Title of host publication	Algorithms and Architectures for Parallel Processing - 8th International Conference, ICA3PP 2008, Proceedings
Pages	18-29
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-540-69501-1_4
Publication status	Published - 2008
Externally published	Yes
Event	8th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2008 - , Cyprus Duration: Jun 9 2008 → Jun 11 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5022 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	8th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2008
Country/Territory	Cyprus
Period	6/9/08 → 6/11/08

ASJC Scopus Subject Areas

Theoretical Computer Science
General Computer Science

Keywords

Genetic algorithm
Parallel processing
Scheduling
Stochastic programming

Access to Document

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

Cite this

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

Yang, Jun ; Ma, Xiaochuan ; Hou, Chaohuan et al. / 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. 2008. pp. 18-29 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e5ee6474ac2e483e88d79667823e400b,

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)",

pages = "18--29",

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

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

}

Yang, J, Ma, X, Hou, C & Yao, Z 2008, A static multiprocessor scheduling algorithm for arbitrary directed task graphs in uncertain environments. in Algorithms and Architectures for Parallel Processing - 8th International Conference, ICA3PP 2008, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5022 LNCS, pp. 18-29, 8th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2008, Cyprus, 6/9/08. 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 et al.
Algorithms and Architectures for Parallel Processing - 8th International Conference, ICA3PP 2008, Proceedings. 2008. p. 18-29 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5022 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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

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

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

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

M3 - Conference contribution

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

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

Y2 - 9 June 2008 through 11 June 2008

ER -

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

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

Abstract

Publication series

Conference

ASJC Scopus Subject Areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this