Evaluation de précision et vitesse de simulation pour des systèmes de calcul distribué à large échelle, Accurate and Fast Simulations of Large-Scale Distributed Computing Systems

Pedro Antonio Madeira De Campos Velho

Description

Sous la direction de Jean-françois Mehaut
Thèse soutenue le 04 juillet 2011: Grenoble
De nos jours, la grande puissance de calcul et l'importante capacité de stockage fournie par les systèmes de calcul distribué à large échelle sont exploitées par des applications dont les besoins grandissent continuellement. Les plates-formes de ces systèmes sont composées d'un ensemble de ressources reliées entre elles par une infrastructure de communication. Dans ce type de système, comme dans n'importe quel environnement de calcul, il est courant que des solutions innovantes soient étudiées. Leur adoption nécessite une phase d'expérimentation pour que l'on puisse les valider et les comparer aux solutions existantes ou en développement. Néanmoins, de par leur nature distribuée, l'exécution d'expériences dans ces environnements est difficile et coûteuse. Dans ces systèmes, l'ordre d'exécution dépend de l'ordre des événements, lequel peut changer d'une exécution à l'autre. L'absence de reproductibilité des expériences rend complexe la conception, le développement et la validation de nouvelles solutions. De plus, les ressources peu- vent changer d'état ou intégrer le système dynamiquement ; les architectures sont partagées et les interférences entre applications, ou même entre processus d'une même application, peuvent affecter le comportement général du système. Enfin, le temps d'exécution d'application à large échelle sur ces sys- tèmes est souvent long, ce qui empêche en général l'exploration exhaustive des valeurs des éventuels paramètres de cette application. Pour toutes ces raisons, les expérimentations dans ce domaine sont souvent basées sur la simulation. Diverses approches existent actuellement pour simuler le calcul dis- tribué à large-échelle. Parmi celles-ci, une grande partie est dédiée à des architectures particulières, comme les grappes de calcul, les grilles de calcul ou encore les plates-formes de calcul bénévole. Néan- moins, ces simulateurs adressent les mêmes problèmes : modéliser le réseau et gérer les ressources de calcul. De plus, leurs besoins sont les même quelle que soit l'architecture cible : la simulation doit être rapide et passer à l'échelle. Pour respecter ces exigences, la simulation de systèmes distribués à large échelle repose sur des techniques de modélisation pour approximer le comportement du système. Cependant, les estimations obtenues par ces modèles peuvent être fausses. Quand c'est le cas, faire confiance à des résultats obtenus par simulation peut amener à des conclusions aléatoires. En d'autres mots, il est nécessaire de connaître la précision des modèles que l'on utilise pour que les conclusions basées sur des résultats de simulation soient crédibles. Mais malgré l'importance de ce dernier point, il existe très rarement des études sur celui-ci. Durant cette thèse, nous nous sommes intéressés à la problématique de la précision des modèles pour les architectures de calcul distribué à large-échelle. Pour atteindre cet objectif, nous avons mené une évaluation de la précision des modèles existants ainsi que des nouveaux modèles conçus pendant cette thèse. Grâce à cette évaluation, nous avons proposé des améliorations pour atténuer les erreurs dues aux modèles en utilisant SimGrid comme cas d'étude. Nous avons aussi évalué les effets des ces améliorations en terme de passage à l'échelle et de vitesse d'exécution. Une contribution majeure de nos travaux est le développement de modèles plus intuitifs et meilleurs que l'existant, que ce soit en termes de précision, vitesse ou passage à l'échelle. Enfin, nous avons mis en lumière les principaux en- jeux de la modélisation des systèmes distribuées à large-échelle en montrant que le principal problème provient de la négligence de certains phénomènes importants.
-Simulation
-Modèles réseaux
-Evaluation de performance
-Calcul distribué
Large-Scale Distributed Computing (LSDC) systems are in production today to solve problems that require huge amounts of computational power or storage. Such systems are composed by a set of computational resources sharing a communication infrastructure. In such systems, as in any computing environment, specialists need to conduct experiments to validate alternatives and compare solutions. However, due to the distributed nature of resources, performing experiments in LSDC environments is hard and costly. In such systems, the execution flow depends on the order of events which is likely to change from one execution to another. Consequently, it is hard to reproduce experiments hindering the development process. Moreover, resources are very likely to fail or go off-line. Yet, LSDC archi- tectures are shared and interference among different applications, or even among processes of the same application, affects the overall application behavior. Last, LSDC applications are time consuming, thus conducting many experiments, with several parameters is often unfeasible. Because of all these reasons, experiments in LSDC often rely on simulations. Today we find many simulation approaches for LSDC. Most of them objective specific architectures, such as cluster, grid or volunteer computing. Each simulator claims to be more adapted for a particular research purpose. Nevertheless, those simulators must address the same problems: modeling network and managing computing resources. Moreover, they must satisfy the same requirements providing: fast, accurate, scalable, and repeatable simulations. To match these requirements, LSDC simulation use models to approximate the system behavior, neglecting some aspects to focus on the desired phe- nomena. However, models may be wrong. When this is the case, trusting on models lead to random conclusions. In other words, we need to have evidence that the models are accurate to accept the con- clusions supported by simulated results. Although many simulators exist for LSDC, studies about their accuracy is rarely found. In this thesis, we are particularly interested in analyzing and proposing accurate models that respect the requirements of LSDC research. To follow our goal, we propose an accuracy evaluation study to verify common and new simulation models. Throughout this document, we propose model improvements to mitigate simulation error of LSDC simulation using SimGrid as case study. We also evaluate the effect of these improvements on scalability and speed. As a main contribution, we show that intuitive models have better accuracy, speed and scalability than other state-of-the art models. These better results are achieved by performing a thorough and systematic analysis of problematic situations. This analysis reveals that many small yet common phenomena had been neglected in previous models and had to be accounted for to design sound models.
-Simulation
-Network Models
-Performance Evaluation
-Distributed Computing
Source: http://www.theses.fr/2011GRENM027/document

Sujets

• Calcul distribué

Informations

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

Extrait

THÈSE
Pour obtenir le grade de
DOCTEURDEL’UNIVERSITÉDEGRENOBLE
Spécialité : Informatique
Arrêté ministérial : 123123
Présentée par
PedroVelho
Thèse dirigée parM.Jean-FrançoisMéhaut
et codirigée parM.ArnaudLegrand
préparée au sein duLIG,Laboratoired’InformatiquedeGrenoble
et de l’École Doctorale Mathématiques, Sciences et Technologies de
l’Information,Informatique
Accurate and Fast Simulations of Large-
ScaleDistributedComputingSystems
Thèse soutenue publiquement ledateàdéfinir,
devant le jury composé de :
Mme. IsabelleGuérinLassous
Professeur, Université Lyon I, Rapporteur
M.OlivierDalle
Maître de Conférence, Université de Nice, Rapporteur
Mme. FrançoiseBaude
Professeur, Université de Nice, Examinatrice
M.FrédéricDesprez
Directeur de Recherche, INRIA Rhône-Alpes, Examinateur
M.HermesSenger
Professor Adjunto, Universidade de São Carlos,
M.Jean-FrançoisMéhaut
Professeur, Université de Grenoble, Directeur de thèse
M.ArnaudLegrand
Chargé de Recherche, CNRS, Co-Directeur de thèse
tel-00625497, version 1 - 21 Sep 2011tel-00625497, version 1 - 21 Sep 2011“Essentially, all models are wrong, but some are useful.”
GeorgeE.P.Box
“The Devil is in the details.”
tel-00625497, version 1 - 21 Sep 2011tel-00625497, version 1 - 21 Sep 2011Acknowledgement
tel-00625497, version 1 - 21 Sep 2011tel-00625497, version 1 - 21 Sep 2011Résumé
De nos jours, la grande puissance de calcul et l’importante capacité de stockage fournie par les
systèmes de calcul distribué à large échelle sont exploitées par des applications dont les besoins
grandissent continuellement. Les plates-formes de ces systèmes sont composées d’un ensemble de
ressources reliées entre elles par une infrastructure de communication. Dans ce type de système,
commedansn’importequelenvironnementdecalcul, ilestcourantquedessolutionsinnovantessoient
étudiées. Leur adoption nécessite une phase d’expérimentation pour que l’on puisse les valider et les
comparer aux solutions existantes ou en développement.
Néanmoins, de par leur nature distribuée, l’exécution d’expériences dans ces environnements est
difficile et coûteuse. Dans ces systèmes, l’ordre d’exécution dépend de l’ordre des événements, lequel
peut changer d’une exécution à l’autre. L’absence de reproductibilité des expériences rend complexe
la conception, le développement et la validation de nouvelles solutions. De plus, les ressources peu-
vent changer d’état ou intégrer le système dynamiquement ; les architectures sont partagées et les
interférences entre applications, ou même entre processus d’une même application, peuvent affecter le
comportementgénéraldusystème. Enfin,letempsd’exécutiond’applicationàlargeéchellesurcessys-
tèmes est souvent long, ce qui empêche en général l’exploration exhaustive des valeurs des éventuels
paramètres de cette application. Pour toutes ces raisons, les expérimentations dans ce domaine sont
souvent basées sur la simulation. Diverses approches existent actuellement pour simuler le calcul dis-
tribué à large-échelle. Parmi celles-ci, une grande partie est dédiée à des architectures particulières,
commelesgrappesdecalcul,lesgrillesdecalculouencorelesplates-formesdecalculbénévole. Néan-
moins, ces simulateurs adressent les mêmes problèmes : modéliser le réseau et gérer les ressources
de calcul. De plus, leurs besoins sont les même quelle que soit l’architecture cible : la simulation doit
être rapide et passer à l’échelle. Pour respecter ces exigences, la simulation de systèmes distribués à
largeéchellereposesurdestechniquesdemodélisationpourapproximerlecomportementdusystème.
Cependant, les estimations obtenues par ces modèles peuvent être fausses. Quand c’est le cas, faire
confianceàdesrésultatsobtenusparsimulationpeutameneràdesconclusionsaléatoires. End’autres
mots, il est nécessaire de connaître la précision des modèles que l’on utilise pour que les conclusions
basées sur des résultats de simulation soient crédibles. Mais malgré l’importance de ce dernier point, il
existe très rarement des études sur celui-ci.
Durant cette thèse, nous nous sommes intéressés à la problématique de la précision des modèles
pour les architectures de calcul distribué à large-échelle. Pour atteindre cet objectif, nous avons mené
une évaluation de la précision des modèles existants ainsi que des nouveaux modèles conçus pendant
cette thèse. Grâce à cette évaluation, nous avons proposé des améliorations pour atténuer les erreurs
dues aux modèles en utilisant SimGrid comme cas d’étude. Nous avons aussi évalué les effets des ces
améliorations en terme de passage à l’échelle et de vitesse d’exécution. Une contribution majeure de
nos travaux est le développement de modèles plus intuitifs et meilleurs que l’existant, que ce soit en
termesdeprécision,vitesseoupassageàl’échelle. Enfin,nousavonsmisenlumièrelesprincipauxen-
jeux de la modélisation des systèmes distribuées à large-échelle en montrant que le principal problème
provient de la négligence de certains phénomènes importants.
tel-00625497, version 1 - 21 Sep 2011tel-00625497, version 1 - 21 Sep 2011Abstract
Large-Scale Distributed Computing (LSDC) systems are in production today to solve problems that
require huge amounts of computational power or storage. Such systems are composed by a set of
computational resources sharing a communication infrastructure. In such systems, as in any computing
environment, specialists need to conduct experiments to validate alternatives and compare solutions.
However, due to the distributed nature of resources, performing experiments in LSDC environments is
hard and costly. In such systems, the execution flow depends on the order of events which is likely
to change from one execution to another. Consequently, it is hard to reproduce experiments hindering
the development process. Moreover, resources are very likely to fail or go off-line. Yet, LSDC archi-
tectures are shared and interference among different applications, or even among processes of the
same application, affects the overall application behavior. Last, LSDC applications are time consuming,
thus conducting many experiments, with several parameters is often unfeasible. Because of all these
reasons, experiments in LSDC often rely on simulations.
Today we find many simulation approaches for LSDC. Most of them objective specific architectures,
such as cluster, grid or volunteer computing. Each simulator claims to be more adapted for a particular
research purpose. Nevertheless, those simulators must address the same problems: modeling network
and managing computing resources. Moreover, they must satisfy the same requirements providing:
fast, accurate, scalable, and repeatable simulations. To match these requirements, LSDC simulation
use models to approximate the system behavior, neglecting some aspects to focus on the desired phe-
nomena. However, models may be wrong. When this is the case, trusting on models lead to random
conclusions. In other words, we need to have evidence that the models are accurate to accept the con-
clusions supported by simulated results. Although many simulators exist for LSDC, studies about their
accuracy is rarely found.
Inthisthesis, weareparticularlyinterestedinanalyzingandproposingaccuratemodelsthatrespect
the requirements of LSDC research. To follow our goal, we propose an accuracy evaluation study to
verifycommonandnewsimulationmodels. Throughoutthisdocument,weproposemodelimprovements
tomitigatesimulationerrorofLSDCsimulationusingSimGridascasestudy. Wealsoevaluatetheeffect
of these improvements on scalability and speed. As a main contribution, we show that intuitive models
have better accuracy, speed and scalability than other state-of-the art models. These better results
are achieved by performing a thorough and systematic analysis of problematic situations. This analysis
revealsthatmanysmallyetcommonphenomenahadbeenneglectedinpreviousmodelsandhadtobe
accounted for to design sound models.
tel-00625497, version 1 - 21 Sep 2011tel-00625497, version 1 - 21 Sep 2011