On Task Scheduling Accuracy: Evaluation Methodology and Results

Authors: Sinnen O.¹; Sousa L.²

Source: The Journal of Supercomputing, Volume 27, Number 2, February 2004 , pp. 177-194(18)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

Abstract:

Many heuristics based on the directed acyclic graph (DAG) have been proposed for the static scheduling problem. Most of these algorithms apply a simple model of the target system that assumes fully connected processors, a dedicated communication sub-system and no contention for the communication resources. Only a few algorithms consider the network topology and the contention for the communication resources. This article evaluates the accuracy of task scheduling algorithms and thus the appropriateness of the applied models. An evaluation methodology is proposed and applied to a representative set of scheduling algorithms. The obtained results show a significant inaccuracy of the produced schedules. Analyzing these results is important for the development of more appropriate models and more accurate scheduling algorithms.

Keywords: task scheduling; DAG; scheduling accuracy; scheduling model

Document Type: Research article

DOI: http://dx.doi.org/10.1023/B:SUPE.0000009321.92150.64

Affiliations: 1: INESC-ID, Rua Alves Redol, 9, 1000 Lisboa, Portugal, Email: oliver.sinnen@inesc-id.pt 2: INESC-ID, Rua Alves Redol, 9, 1000 Lisboa, Portugal, Email: las@inesc-id.pt

Publication date: 2004-02-01