Title
A performance study of multiprocessor task scheduling algorithms
Abbreviated Journal Title
J. Supercomput.
Keywords
task scheduling; parallel computing; Heuristic algorithms; communication; delay; PARALLEL GENETIC ALGORITHM; COMMUNICATION DELAYS; DUPLICATION; PROCESSORS; SYSTEMS; GRAPHS; OPTIMIZATION; HEURISTICS; CLUSTER; Computer Science, Hardware & Architecture; Computer Science, Theory &; Methods; Engineering, Electrical & Electronic
Abstract
Multiprocessor task scheduling is an important and computationally difficult problem. A large number of algorithms were proposed which represent various tradeoffs between the quality of the solution and the computational complexity and scalability of the algorithm. Previous comparison studies have frequently operated with simplifying assumptions, such as independent tasks, artificially generated problems or the assumption of zero communication delay. In this paper, we propose a comparison study with realistic assumptions. Our target problems are two well known problems of linear algebra: LU decomposition and Gauss-Jordan elimination. Both algorithms are naturally parallelizable but have heavy data dependencies. The communication delay will be explicitly considered in the comparisons. In our study, we consider nine scheduling algorithms which are frequently used to the best of our knowledge: min-min, chaining, A*, genetic algorithms, simulated annealing, tabu search, HLFET, ISH, and DSH with task duplication. Based on experimental results, we present a detailed analysis of the scalability, advantages and disadvantages of each algorithm.
Journal Title
Journal of Supercomputing
Volume
43
Issue/Number
1
Publication Date
1-1-2008
Document Type
Article
Language
English
First Page
77
Last Page
97
WOS Identifier
ISSN
0920-8542
Recommended Citation
"A performance study of multiprocessor task scheduling algorithms" (2008). Faculty Bibliography 2000s. 494.
https://stars.library.ucf.edu/facultybib2000/494
Comments
Authors: contact us about adding a copy of your work at STARS@ucf.edu