A performance study of multiprocessor task scheduling algorithms

    Authors

    S. Y. Jin; G. Schiavone;D. Turgut

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    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

    WOS:000251972500005

    ISSN

    0920-8542

    Share

    COinS