WSCOM: Online task scheduling with data transfers

Abstract : In our paper we consider the on-line problem of tasks scheduling with communication. All information on tasks and communication are not available in advance except the DAG of task topology. We take a novel approach by considering the bi-objective problem where we try to minimize both completion time and the number of data transmissions. We propose a new variation of the work-stealing algorithm: WSCOM. We try here to take advantage of the information of the DAG topology, and improve locality by clustering the tasks together. We propose several variants designed to overlap communication or optimize the graph decomposition. Performance is evaluated by simulation and we compare our algorithms with off-line list-scheduling algorithms from the literature. These experiments validate the different design choices taken. In particular we show that WSCOM is able to achieve performance closes to off-line algorithms in most cases and is even able to achieve better performance in the event of congestion due to less data transfer.
Type de document :
Rapport
[Research Report] RR-7792, INRIA. 2011, pp.15
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00639922
Contributeur : Jean-Noel Quintin <>
Soumis le : jeudi 10 novembre 2011 - 10:59:27
Dernière modification le : mercredi 11 avril 2018 - 01:55:42
Document(s) archivé(s) le : jeudi 30 mars 2017 - 19:02:13

Fichier

RR-7792.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00639922, version 1

Citation

Jean-Noel Quintin, Frédéric Wagner. WSCOM: Online task scheduling with data transfers. [Research Report] RR-7792, INRIA. 2011, pp.15. 〈hal-00639922〉

Partager

Métriques

Consultations de la notice

262

Téléchargements de fichiers

220