S. Jin, G. Schiavone, and D. Turgut

A Performance Study of Multiprocessor Task Scheduling Algorithms


Cite as:

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.

Download:

Download 

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.

BibTeX:

@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