inria-00108518, version 2
Scheduling and data redistribution strategies on star platforms
Loris Marchal
1, 2Veronika Rehn 1, 2Yves Robert 1, 2Frédéric Vivien a, 1, 2
N° RR-6005 (2006)
Résumé : In this work we are interested in the problem of scheduling and redistributing data on master-slave platforms. We consider the case were the workers possess initial loads, some of which having to be redistributed in order to balance their completion times. We examine two different scenarios. The first model assumes that the data consists of independent and identical tasks. We prove the NP-completeness in the strong sense for the general case, and we present two optimal algorithms for special platform types. Furthermore we propose three heuristics for the general case. Simulations consolidate the theoretical results. The second data model is based on Divisible Load Theory. This problem can be solved in polynomial time by a combination of linear programming and simple analytical manipulations.
- a – INRIA
- 1 : GRAAL (INRIA Grenoble Rhône-Alpes / LIP Laboratoire de l'Informatique du Parallélisme)
- CNRS : UMR5668 – INRIA – École Normale Supérieure (ENS) - Lyon – Université Claude Bernard - Lyon I (UCBL) – Laboratoire d'informatique du Parallélisme
- 2 : Laboratoire de l'Informatique du Parallélisme (LIP)
- PRES Université de Lyon – CNRS : UMR5668 – INRIA – École Normale Supérieure (ENS) - Lyon – Université Claude Bernard - Lyon I (UCBL)
- Domaine : Informatique/Calcul parallèle, distribué et partagé
- Mots-clés : Master-slave platform – scheduling – data redistribution – one-port model – independent tasks – divisible load theory
- Référence interne : RR-6005
- Versions disponibles : v1 (23-10-2006) v2 (26-10-2006)
- inria-00108518, version 2
- http://hal.inria.fr/inria-00108518
- oai:hal.inria.fr:inria-00108518
- Contributeur : Rapport De Recherche Inria
- Soumis le : Jeudi 26 Octobre 2006, 15:46:01
- Dernière modification le : Jeudi 26 Octobre 2006, 15:46:57
Documents associés
Exporter