S. Jin, G. Schiavone, and D. Turgut. A Performance Study of Multiprocessor Task Scheduling Algorithms. Journal of Supercomputing, Springer, 43(1):77–97, January 2008.
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.
@article{Jin-2008-JoS,
author = "S. Jin and G. Schiavone and D. Turgut",
title = "A Performance Study of Multiprocessor Task Scheduling Algorithms",
journal = "Journal of Supercomputing, Springer",
volume = "43",
number = "1",
pages = "77-97",
month = "January",
year = "2008",
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.
},
}
Generated by bib2html.pl (written by Patrick Riley, Lotzi Boloni ) on Sun Mar 03, 2024 18:41:15