Laboratoire des Sciences de l'Image de l'Informatique et

Arnaud Giersch

Description

Niveau: Supérieur, Doctorat, Bac+8
Laboratoire des Sciences de l'Image, de l'Informatique et de la Télédétection UMR CNRS-ULP 7005 Équipe Image et Calcul Parallèle Scientifique Thèse présentée pour obtenir le grade de Docteur de l'Université Louis Pasteur Strasbourg I Discipline : informatique par Arnaud Giersch TitreOrdonnancement sur plates-formes hétérogènes de tâches partageant des données Soutenue publiquement le 22 décembre 2004 Membres du jury Directeur : M. Guy-René Perrin, professeur Université Louis Pasteur de Strasbourg Rapporteur interne : M. Jean-Jacques Pansiot, professeur Université Louis Pasteur de Strasbourg Rapporteurs externes : M. Denis Trystram, professeur Institut national polytechnique de Grenoble M. Henri Casanova, Research Scientist University of California, San Diego Examinateur : M. Hervé Guyennet, professeur Université de Franche-Comté Co-encadrants (membres invités) : M. Stéphane Genaud, maître de conférences Université Robert Schuman de Strasbourg M. Frédéric Vivien, chargé de recherche Inria École normale supérieure de Lyon

• tâches partageant des données


• intermédiaire de frédéric


• membres du jury directeur


• merci


• maître de conférence des université


• jury de thèse

Sujets

• Université de Franche-Comté
• Casanova
• Vivien
• Louis Pasteur University
• Alsace
• Perrin
• Schuman

Informations

• Publié par: profil-zyak-2012
• Publié le: 01 décembre 2004
• Nombre de lectures: 86
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

Thèse présentée pour obtenir le grade de
Laboratoire des Sciences
de l’Image, de l’Informatique et Docteur de l’Université Louis Pasteur
de la Télédétection
UMR CNRS ULP 7005 Strasbourg I
Équipe Image et
Calcul Parallèle Scientifique
Discipline : informatique
par Arnaud Giersch
OrdonnancementTitre
sur plates formes hétérogènes
de tâches partageant des données
Soutenue publiquement le 22 décembre 2004
Membres du jury
Directeur : M. Guy René Perrin, professeur
Université Louis Pasteur de Strasbourg
Rapporteur interne : M. Jean Jacques Pansiot, professeur
Université Louis Pasteur de Strasbourg
Rapporteurs externes : M. Denis Trystram, professeur
Institut national polytechnique de Grenoble
M. Henri Casanova, Research Scientist
University of California, San Diego
Examinateur : M. Hervé Guyennet, professeur
Université de Franche Comté
Co encadrants (membres invités) :M. Stéphane Genaud, maître de conférences
Université Robert Schuman de Strasbourg
M. Frédéric Vivien, chargé de recherche Inria
École normale supérieure de LyonACe documment a été composé avec LT X.EÀ Fatima,
Gabriel, Brahim et Joachim.Remerciements
Alors Papa, tu as fini ta thèse?
Gabriel, juillet–décembre 2004.
Eh oui, j’ai finalement terminé cette thèse. Je voudrais maintenant remercier
tous ceux qui m’ont accompagné, soutenu et aidé pendant ces quatre années.
D’abord Guy-René Perrin, mon directeur de thèse, qui a su m’aider à me
réorienter lorsque, au bout de la première année, je ne savais plus trop où j’allais.
Ensuite Stéphane, qui a alors accepté d’encadrer mon travail. C’est grâce à lui,
et au projet TAG, que je me suis mis à jouer avec des problèmes de grilles, ce qui
a finalement aboutit à cette thèse.
Puis Frédéric qui s’est joint a nous, même s’il a fallu attendre qu’il s’éloigne
1d’environ 486 km avant de commencer à faire de la recherche ensemble! C’est
vrai que ça aurait été trop facile et moins drôle en partageant le même bureau...
EtenfinYves,quiaacceptédeconsacrerdesontempspourtravailleravecmoi,
alors qu’on ne se connaissait même pas – sauf par l’intermédiaire de Frédéric!
Merci à vous qui, par votre disponibilité, vos remarques, vos conseils et votre
aide, m’ont permis de mener à bien ce
travail.
JevoudraiségalementremercierceuxquisesontdéplacéenAlsacedanslafroidure d’un 22 décembre ( 10 °C), en particulier mes rapporteurs : Henri Casanova,
Jean-Jacques Pansiot et Denis Trystram, ainsi que Hervé Guyennet qui a présidé
mon jury de thèse.
Merci à Benjamin (Ouaf?), Benoît, Catherine, Guillaume, Philippe, Romaric
(Plop!), Vincent et – toujours par ordre alphabétique – les autres membres de
l’ICPS avec qui j’ai partagé bureau, repas, cafés, canoës, discussions plus ou moins
scientifiques, etc., et qui ont contribué à rendre notre cadre de travail si agréable.
Merci Fatima. Ta présence quotidienne, ton soutien et ton aide (et tout le reste
aussi)mesontprécieux.MerciGabriel,BrahimetJoachim,votreprésenceetvotre
joie de vivre me sont tout autant précieux.
1. Distance approximative, par la route, entre le Pôle API à Illkirch et l’ENS à Lyon.
vvi
Je ne manquerai pas bien sûr de remercier également mes parents, famille et
amis qui m’accompagnent depuis de nombreuses années.
Je tiens enfin à remercier le laboratoire LIP et le CINES qui m’ont permis
d’utiliser leurs gros ordinateurs, sans lesquels je n’aurais pas pu mener toutes mes
expériences et simulations. Merci aussi à tous les acteurs du logiciel libre car c’est
aussi un peu grâce à eux que ce travail a pu être effectué.
Finalement, Merci à toutes celles et tous ceux (sans compter les autres) que
j’aurais pu oublier de citer.Table des matières
1 Introduction 1
2 Maître-esclave 5
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.1 Exemple d’application en tomographie sismique . . . . . . . 6
2.2.2 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.3 Modèle de communication . . . . . . . . . . . . . . . . . . . 8
2.3 Équilibrage statique . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.1 Modèles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.2 Une solution exacte . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.3 Une heuristique garantie . . . . . . . . . . . . . . . . . . . . 15
2.3.4 Choix du processeur maître . . . . . . . . . . . . . . . . . . 17
2.4 Résolution par tâches divisibles . . . . . . . . . . . . . . . . . . . . 17
2.4.1 Durée d’exécution . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4.2 Terminaisons simultanées. . . . . . . . . . . . . . . . . . . . 19
2.4.3 Politique pour l’ordre des processeurs . . . . . . . . . . . . . 20
2.4.4 Conséquences pour le cas général . . . . . . . . . . . . . . . 24
2.5 Validation expérimentale . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5.1 Environnement . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5.2 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.6 Travaux connexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3 Avec des données partagées 35
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2 Modèles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2.1 Tâches et données . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2.2 Graphe de plate-forme . . . . . . . . . . . . . . . . . . . . . 38
3.2.3 Fonction objectif . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
viiviii TABLE DES MATIÈRES
3.3.1 Avec un seul esclave . . . . . . . . . . . . . . . . . . . . . . 40
3.3.2 Avec plusieurs esclaves . . . . . . . . . . . . . . . . . . . . . 45
3.4 Heuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.4.1 Heuristiques de référence . . . . . . . . . . . . . . . . . . . . 50
3.4.2 Structure des nouvelles heuristiques . . . . . . . . . . . . . . 52
3.4.3 Les fonctions objectifs . . . . . . . . . . . . . . . . . . . . . 53
3.4.4 Politiques additionnelles . . . . . . . . . . . . . . . . . . . . 55
3.4.5 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.5 Évaluation par simulations . . . . . . . . . . . . . . . . . . . . . . . 57
3.5.1 Plates-formes simulées . . . . . . . . . . . . . . . . . . . . . 58
3.5.2 Graphes d’application . . . . . . . . . . . . . . . . . . . . . 59
3.5.3 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4 Avec plusieurs serveurs 69
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.2 Modèles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2.1 Tâches et données . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2.2 Graphe de plate-forme . . . . . . . . . . . . . . . . . . . . . 70
4.2.3 Fonction objectif . . . . . . . . . . . . . . . . . . . . . . . . 72
4.2.4 Déroulement de l’exemple . . . . . . . . . . . . . . . . . . . 73
4.2.5 Discussion du modèle . . . . . . . . . . . . . . . . . . . . . . 75
4.3 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.4 Adaptation du min-min. . . . . . . . . . . . . . . . . . . . . . . . . 84
4.4.1 Principe du min-min . . . . . . . . . . . . . . . . . . . . . . 84
4.4.2 Ordonnancement des communications . . . . . . . . . . . . . 85
4.4.3 Le min-min adapté . . . . . . . . . . . . . . . . . . . . . . . 90
4.5 Heuristiques moins coûteuses. . . . . . . . . . . . . . . . . . . . . . 92
4.5.1 Heuristiques statiques . . . . . . . . . . . . . . . . . . . . . 92
4.5.2 Variantes des heuristiques statiques . . . . . . . . . . . . . . 94
4.5.3 Heuristiques dynamiques . . . . . . . . . . . . . . . . . . . . 98
4.6 Évaluation par simulations . . . . . . . . . . . . . . . . . . . . . . . 102
4.6.1 Plates-formes simulées . . . . . . . . . . . . . . . . . . . . . 102
4.6.2 Graphes d’application . . . . . . . . . . . . . . . . . . . . . 103
4.6.3 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5 Conclusion et perspectives 113
5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114TABLE DES MATIÈRES ix
Bibliographie 119
A Notatio