For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Experimental Evaluation of Task Scheduling Accuracy: Implications for the Scheduling Model
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2003/09/01
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Parallel and Distributed Computing, Applications and Technologies)
Category: Algorithms and Applications
task scheduling, DAG, scheduling accuracy, enhanced scheduling model,
Full Text: PDF>>
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.