Title

A performance study of multiprocessor task scheduling algorithms

Authors

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