Title

A Performance Study Of Multiprocessor Task Scheduling Algorithms

Keywords

Communication delay; Heuristic algorithms; Parallel computing; Task scheduling

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. © 2007 Springer Science+Business Media, LLC.

Publication Date

1-1-2008

Publication Title

Journal of Supercomputing

Volume

43

Issue

1

Number of Pages

77-97

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/s11227-007-0139-z

Socpus ID

37649004659 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/37649004659

This document is currently not available here.

Share

COinS