Outils et algorithmes pour gérer l'incertitude lors de l'ordonnancement d'application sur plateformes distribuées, Tools and Algorithms for Coping with Uncertainty in Application Scheduling on Distributed Platforms

Louis-Claude Canon

Description

Sous la direction de Emmanuel Jeannot
Thèse soutenue le 18 octobre 2010: Nancy 1
Cette thèse traite de l'ordonnancement dans les systèmes distribués. L'objectif est d'étudier l'impact de l'incertitude sur les ordonnancements et de proposer des techniques pour en réduire les effets sur les critères à optimiser. Nous distinguons plusieurs aspects de l'incertitude en considérant celle liée aux limites des méthodes employées (e.g., modèle imparfait) et celle concernant la variabilité aléatoire qui est inhérente aux phénomènes physiques (e.g., panne matérielle). Nous considérons aussi les incertitudes qui se rapportent à l'ignorance portée sur les mécanismes en jeu dans un système donné (e.g., soumission de tâches en ligne dans une machine parallèle). En toute généralité, l'ordonnancement est l'étape qui réalise une association ordonnée entre des requêtes (dans notre cas, des tâches) et des ressources (dans notre cas, des processeurs). L'objectif est de réaliser cette association de manière à optimiser des critères d'efficacité (e.g., temps total consacré à l'exécution d'un application) tout en respectant les contraintes définies. Examiner l'effet de l'incertitude sur les ordonnancements nous amène à considérer les aspects probabilistes et multicritères qui sont traités dans la première partie. La seconde partie repose sur l'analyse de problèmes représentatifs de différentes modalités en terme d'ordonnancement et d'incertitude (comme l'étude de la robustesse ou de la fiabilité des ordonnancements)
-Ordonnancement
-Incertitude
-Systèmes distribués
-Optimisation
This thesis consists in revisiting traditional scheduling problematics in computational environments, and considering the adjunction of uncertainty in the models. We adopt here a wide definition of uncertainty that encompasses the intrinsic stochastic nature of some phenomena (e.g., processor failures that follow a Poissonian distribution) and the imperfection of model characteristics (e.g., inaccuracy of the costs in a model due to a bias in measurements). We also consider uncertainties that stem from indeterminations such as the user behaviors that are uncontrolled although being deterministic. Scheduling, in its general form, is the operation that assigns requests to resources in some specific way. In distributed environments, we are concerned by a workload (i.e., a set of tasks) that needs to be executed onto a computational platform (i.e., a set of processors). Therefore, our objective is to specify how tasks are mapped onto processors. Produced schedules can be evaluated through many different metrics (e.g., processing time of the workload, resource usage, etc) and finding an optimal schedule relatively to some metric constitutes a challenging issue. Probabilistic tools and multi-objectives optimization techniques are first proposed for tackling new metrics that arise from the uncertainty. In a second part, we study several uncertainty-related criteria such as the robustness (stability in presence of input variations) or the reliability (probability of success) of a schedule
Source: http://www.theses.fr/2010NAN10097/document

Sujets

• Ordonnancement
• Incertitude
• Calcul distribué
• Optimisation

Informations

• Publié par: Thesee
• Nombre de lectures: 36
• Langue: Français
• Poids de l'ouvrage: 3 Mo

Extrait

AVERTISSEMENT

Ce document est le fruit d'un long travail approuvé par le
jury de soutenance et mis à disposition de l'ensemble de la
communauté universitaire élargie.

Il est soumis à la propriété intellectuelle de l'auteur. Ceci
implique une obligation de citation et de référencement lors
de l’utilisation de ce document.

D’autre part, toute contrefaçon, plagiat, reproduction
illicite encourt une poursuite pénale.


➢ Contact SCD Nancy 1 : [e-mail]




LIENS


Code de la Propriété Intellectuelle. articles L 122. 4
Code de la Propriété Intellectuelle. articles L 335.2- L 335.10
http://www.cfcopies.com/V2/leg/leg_droi.php
http://www.culture.gouv.fr/culture/infos-pratiques/droits/protection.htm Département de formation doctorale en informatique École doctorale IAEM Lorraine
UFR STMIA
Outils et algorithmes pour gérer l’incertitude lors de
l’ordonnancement d’application sur plateformes
distribuées
THÈSE
date de soutenance envisagée le 18 octobre 2010
pour l’obtention du
Doctorat de l’Université Henri Poincaré – Nancy 1
(spécialité informatique)
par
Louis-Claude Canon
Composition du jury
Rapporteurs : Bruno Gaujal, Directeur de recherche, Laboratoire d’Informatique de Grenoble
Pierre Sens, Professeur, Université de Paris 6
Examinateurs : Emmanuel Jeannot, Chargé de recherche, INRIA-Bordeaux (Directeur de thèse)
Arnold Rosenberg, Professeur, Université du Colorado
René Schott, Professeur, Université Henri Poincaré
Laboratoire Lorrain de Recherche en Informatique et ses Applications — UMR 7503Remerciements
Ce mémoire de thèse représente l’aboutissement de trois années de recherche, de découvertes
et d’égarement. Derrière les contributions scientifiques qui y sont présentées, se dissimule un
investissement humain qu’il m’aurait été impossible d’assumer sans la direction éclairée de mon
directeur de thèse. Je lui exprime donc ma plus vive reconnaissance pour son encadrement d’ex-
ception. Je tiens en particulier à souligner sa disponibilité, la pertinence de ses critiques ainsi
que son soutien et l’en remercie sincèrement.
Jesouhaiteraiégalementadresserunremerciementparticulieràmesparentsquionteuunrôle
significatifdansl’élaborationdecedocument.Leurintérêtpourcetteréalisationm’aspécialement
touché.
Mes derniers remerciements vont à l’ensemble des personnes que j’ai côtoyé pendant ces
dernières années, ce qui inclut les membres des équipes AlGorille et Runtime qui m’ont accueilli
pendant ma thèse, les membres de ma famille et enfin mes amis.
iiiTable des matières
Remerciement i
Introduction 1
Notations 7
I Outils 9
1 Évaluation de graphes stochastiques 11
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2 Modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3 État de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4 Complexité du problème général . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.5 Méthodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.6 Validation empirique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2 Ordonnancement bicritère 47
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.2t multicritère . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.3 Agrégation des critères . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.4 Algorithmes évolutionnaires multicritères . . . . . . . . . . . . . . . . . . . . . . . 59
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
II Algorithmes 69
3 Ordonnancer des tâches à durée aléatoire 71
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.2 Modèles et définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.3 Mesures de robustesse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.4 Plan d’expérience . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.5 Comparaison des mesures de robustesse . . . . . . . . . . . . . . . . . . . . . . . 81
3.6 Méthodes d’ordonnancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.7 des méthodes d’ordonnancement . . . . . . . . . . . . . . . . . . . 93
3.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
iiiiv TABLE DES MATIÈRES
4 Évaluer la fiabilité des ordonnancements 99
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.2 État de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.3 Modèles et définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.4 Évaluer un ordonnancement général . . . . . . . . . . . . . . . . . . . . . . . . . 107
4.5 Évaluer unement strict . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.6 Évaluer un ordonnancement d’une chaîne de tâches . . . . . . . . . . . . . . . . . 119
4.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
5 Caractériser la fiabilité des ressources 129
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
5.2 État de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
5.3 Modèles et définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.4 Caractérisation des fautes collectives . . . . . . . . . . . . . . . . . . . . . . . . . 138
5.5 Validation empirique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
Conclusion 155
Publications scientifiques 159
Bibliographie 161
Résumé 171Introduction
Cette thèse traite de l’ordonnancement dans les systèmes distribués. Notre objectif est d’étu-
dier l’impact de l’incertitude sur les ordonnancements et de proposer des techniques pour en
réduire les effets sur les critères à optimiser.
Danscetteintroduction,nousprésentonslecontexteducalculdistribué,quelquesconceptsre-
latifsàl’incertitudeetledomained’étudeliéàl’ordonnancement.Nouspoursuivonsenprésentant
le plan et les principaux axes autour desquelles s’articule cette thèse, ainsi que les collaborations
que nous avons menées.
Contexte
Calcul distribué
Une plateforme de calcul distribué est composée d’un ensemble de processeurs (ou plus gé-
néralement de ressources calculatoires) interconnectés par un réseau de communication. Comme
ces systèmes sont complexes, leur étude requiert des modèles puissants et utiles. Si les ressources
de calcul sont séquentielles, un modèle couramment utilisé est l’architecture de type SISD (Single
Instruction, Single Data) de la taxonomie de Flynn [67], ce qui correspond à l’architecture de
Von Neumann. Les modèles des réseaux de communication ont quant à eux considérablement
évolués depuis le modèle PRAM [110] avec par exemple le modèle un-port [22] ou encore les
modèles de communications point à point comme LogP [46].
Du coté logiciel, un modèle d’application spécifie l’ensemble des calculs à réaliser. Une ap-
plication peut se décomposer en plusieurs tâches, le calcul de chaque tâche produisant alors un
résultat. Le calcul d’une tâche peut par ailleurs être conditionné par l’accessibilité et la disponi-
bilité des données produites par d’autres tâches. La structure de l’application définit ainsi dans
quel ordre les tâches peuvent être exécutées.
Nous nous intéressons à l’exécution efficace d’une application parallèle sur une plateforme de
calcul distribué. À cet égard, l’ensemble des modèles de calcul distribué mentionnés plus haut
sont déterministes. Or l’incertitude est une composante essentielle à toute science. En particulier,
l’échelle et la complexité importante (et grandissante) des systèmes distribués sont des sources
d’indétermination. Par exemple, la disponibilité d’une ressource particulière à un moment donné
ou bien encore la nature précise des calculs parallèles ne sont pas toujours