Experimental Evaluation of Task Scheduling Accuracy: Implications for the Scheduling Model

Oliver SINNEN  Leonel SOUSA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E86-D   No.9   pp.1620-1627
Publication Date: 2003/09/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Parallel and Distributed Computing, Applications and Technologies)
Category: Algorithms and Applications
Keyword: 
task scheduling,  DAG,  scheduling accuracy,  enhanced scheduling model,  

Full Text: PDF(698.4KB)>>
Buy this Article




Summary: 
Most heuristics for the task scheduling problem employ a simple model of the target system, assuming fully connected processors, a dedicated communication subsystem and no contention for communication resources. A small number of algorithms is aware of the contention, using an undirected graph model of the communication network. Although, many scheduling algorithms have been compared in the literature, little is known about the accuracy and appropriateness of the employed models. This article evaluates the accuracy of task scheduling algorithms on generic parallel systems. The performed experiments show a significant inaccuracy of the schedules produced. In an extensive analysis, the reasons for these results are identified and the implications for the scheduling model are discussed.