Idle regulation in non-clairvoyant scheduling of parallel jobs

Abstract : The optimization of parallel applications is difficult to achieve by classical optimization techniques because of their diversity and the variety of actual parallel and distributed platforms and/or environments. Adaptive algorithmic schemes, capable of dynamically changing the allocation of jobs during the execution to optimize global system behavior, are the best alternatives for solving this problem. In this paper, we focus on non-clairvoyant scheduling of parallel jobs with known resource requirements but unknown running times, with emphasis on the regulation of idle periods in the context of general list policies. We consider a new family of scheduling strategies based on two phases which successively combine sequential and parallel execution of jobs. We generalize known worst-case performance bounds by considering two extra parameters, in addition to the number of processors and maximum processor requirements considered in the literature, namely, job parallelization penalty and idle regulation factor. Furthermore, we prove that under certain conditions of idle regulation, the performance guarantee of parallel job scheduling in space-sharing mode can be improved.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2009, 157, pp.364-376. 〈10.1016/j.dam.2008.03.005〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00800416
Contributeur : Grégory Mounié <>
Soumis le : mercredi 13 mars 2013 - 16:30:46
Dernière modification le : jeudi 11 janvier 2018 - 06:22:01

Identifiants

Collections

Citation

Andrei Tchernykh, Denis Trystram, C. Brizuela, Isaac Scherson. Idle regulation in non-clairvoyant scheduling of parallel jobs. Discrete Applied Mathematics, Elsevier, 2009, 157, pp.364-376. 〈10.1016/j.dam.2008.03.005〉. 〈hal-00800416〉

Partager

Métriques

Consultations de la notice

153