Télécharger le fichier pdf d’un mémoire de fin d’études
Gestion des ressources d’une grille de calcul
La gestion de ressources distribuées est un domaine dans lequel de nombreuses recherches ont et menées. Qu’il s’agisse de machines massivement parallèles de type supercalculateur, ou bien de clusters, des outils de gestion efficaces ont et´ mis au point. Cependant, de tels outils ne sont pas adaptés a` des supports tels que les grilles de calcul.
Ce chapitre pr´esente le probl`eme de la gestion des ressources d’une grille de calcul. Il introduit les diff´erentes caract´eristiques propres a` ce domaine et d´etaille le fonctionnement de diff´erents gestionnaires de ressources existants. Une attention toute particuli`ere est port´ee au gestionnaire OAR, puisqu’il s’agit de celui utilis´e sur la plate-forme Grid’5000. D’autre part, ce chapitre permet de positionner le mod`ele d’ordonnancement propos´e dans le cadre de cette th`ese parmi l’offre d´ej`a existante, et ainsi de mettre en avant les contributions qu’il apporte.
Objectifs et challenges
Caractéristiques de l’ordonnancement sur grille
Les ressources présentes sur une grille de calcul possèdent des caractéristiques devant etre prises en charge par les systemes responsables de leur gestion. Le type de grille que l’on considere (grille de calcul, d’information, de stockage, etc.) conditionne le type de ressources a gerer. Concernant une grille de calcul, il s’agit principalement des processeurs fournissant la puissance de calcul, et du reseau reliant les differents nœuds.
Les syst`emes d’ordonnancement doivent prendre en consideration les caracteristiques suivantes [14, 17] :
• H´et´erog´en´eit´ des ressources : La grille est une interconnexion de ressources appartenant a` diff´erents domaines. Si les ressources peuvent ˆetre homog`enes au sein d’un mˆeme domaine, il en est tout autrement lorsque l’ensemble de la grille est consid´er´. De fortes diff´erences peuvent ˆetre constat´ees en termes d’architectures mat´erielles des machines partag´ees, de vitesse des processeurs, de syst`emes d’exploi-tation utilis´es, de bande-passante reliant les machines au r´eseau, etc. Ceci r´esulte en une diff´erenciation des capacit´es de calcul et d’acc`es aux donn´ees pour chaque ressource.
• Autonomie des sites : Les sites constituant la grilles appartiennent a` diff´erents do-maines d’administration, chacun poss´edant ses propres politiques d’acc`es, de s´ecurit´ et de gestion des ressources. Le gestionnaire de ressources doit savoir s’adapter a` ces sp´ecificit´es, et laisser une totale autonomie aux diff´erents sites.
• Diversit´ des applications : Une grande diversit´ d’utilisateurs venant de diff´e-rents horizons peuvent ˆetre amen´es a` utiliser la grille. Il en r´esulte une grande palette d’applications pouvant ˆetre ex´ecut´ees, et donc devant ˆetre prises en charge par les al-gorithmes d’ordonnancement. Il peut s’agir d’applications parall`eles communicantes qui poss`edent un nombre important de tˆaches ´echangeant une quantit´e variable de donn´ees, de mˆeme que des applications param´etriques, pour lesquelles diff´erentes instances ind´ependantes de l’application sont lanc´ees pour des param`etres diff´erents.
• Ressources non-d´edi´ees : Les ressources pr´esentes sur la grille ne sont g´en´erale-ment pas d´edi´ees a` celle-ci. Les utilisateurs des divers domaines peuvent utiliser les ressources leur appartenant sans passer par le gestionnaire de ressources de la grille, ce qui implique une diversit´ de nouveaux param`etres a` prendre en compte. Cependant, certaines grilles de calcul poss`edent des ressources d´edi´ees, comme les grilles orient´ees vers la prestation de services applicatifs (ASP pour Application Service Provider ) [18].
• Aspects dynamiques : Une des caract´eristiques des grilles de calcul est le compor-tement dynamique des ressources qui la composent. D’une part, la disponibilit´e de ces derni`eres peut varier fortement au cours du temps : une ressource peut rejoindre ou quitter la grille inopin´ement. De plus, les performances des ressources peuvent ´egalement fluctuer en fonction de l’importance de leur utilisation.
Les caract´eristiques ainsi mises en avant sont tr`es diff´erentes de celles que l’on retrouve dans les syst`emes traditionnels. Par exemple, les ressources d’un cluster sont g´en´eralement homog`enes, et peuvent ˆetre consid´er´ees comme stables. Il est par cons´equent n´ecessaire d’adapter les gestionnaires de ressources afin de prendre en compte l’ensemble de ces caract´eristiques [2, 19].
Missions d’un gestionnaire de ressources
Un gestionnaire de ressources regroupe un ensemble de composants, dont le rˆole principal est de fournir les services suivants [17, 20] :
• un service d’ordonnancement,
• un service d’information,
• un service d’ex´ecution et d’observation.
En pratique, la figure 2.1 montre les composants mis en jeu ainsi que leurs interactions [15, 17]. Le rˆole du gestionnaire de ressources de la grille est de s’interfacer avec les ges-tionnaires locaux, d’une part pour soumettre des applications aux ressources des domaines dont ceux-ci ont la responsabilit´e, et d’autre part pour collecter les informations provenant de ces mˆeme ressources. Ceci garantit ainsi l’autonomie des diff´erents domaines de la grille. De plus, au sein d’un domaine, les utilisateurs peuvent confier des tˆaches au gestionnaire de ressources local, mettant ainsi en avant l’aspect potentiellement non-d´edi´ de la grille.
L’ordonnancement sur une grille de calcul met en œuvre les trois ´etapes suivantes [21] :
1. D´ecouverte des ressources : L’utilisateur fournit au gestionnaire la description de l’application a` ex´ecuter. Le syst`eme doit alors d´eterminer quelles sont les ressources disponibles pour cet utilisateur. Pour cela, le service d’information est utilis´e afin d’identifier les ressources pr´esentes sur la grille. Un premier filtrage est alors op´er´ afin d’´eliminer celles que l’utilisateur n’a pas le droit d’utiliser. De plus, le gestion-naire calcule les besoins de l’application en ressources (leur nombre, leur puissance, le temps n´ecessaire, etc.). Un second filtrage peut alors ˆetre effectu´ pour ne retenir que les ressources pouvant satisfaire ces besoins.
2. S´election des ressources : Il s’agit de l’´etape d’ordonnancement. Etant donn´e un ensemble de ressources possibles pour ex´ecuter l’application de l’utilisateur, le ges-tionnaire doit choisir celles qui seront r´eellement utilis´ees. Il s’appuie pour cela sur une estimation des besoins en ressources de l’application, ainsi que sur une pr´ediction des performances des ressources. Divers algorithmes sont alors disponibles, permet-tant de choisir un ordonnancement en fonction des objectifs fix´es (´equilibrage de charge, temps d’ex´ecution minimal, etc.).
3. Ex´ecution de l’application : Cette derni`ere ´etape permet au gestionnaire de grille de se connecter a` un ou plusieurs gestionnaires locaux afin de leur confier l’application a` ex´ecuter. Un suivi de la progression de cette ex´ecution et de l’´etat des ressources employ´ees peut ´eventuellement ˆetre mis en place.
Ordonnancement sur une grille de calcul
Le probl`eme de l’ordonnancement sur une grille de calcul peut ˆetre repr´esent´ par la figure 2.2. Il s’agit d’attribuer les tˆaches de l’application a` ex´ecuter aux diff´erentes res-sources de la grille. Pour cela, l’ordonnanceur consid`ere d’une part les caract´eristiques de l’application, et d’autre part celles des ressources disponibles. L’ordonnancement est alors calcul´e de mani`ere a` satisfaire un objectif fix´e [22].
Applications
Diff´erentes caract´eristiques des applications candidates a` l’ex´ecution sur un support tel qu’une grille de calcul doivent ˆetre prises en compte par le gestionnaire de ressources de la grille [14, 23].
La premi`ere de ces caract´eristiques correspond aux exigences des applications li´ees aux calculs. Il s’agit ici de fournir a` l’ordonnanceur des donn´ees telles que le temps processeur n´ecessaire pour les ex´ecuter, ou encore l’espace m´emoire demand´. D’autres facteurs, tels que la date de d´ebut requise par l’application ou son coˆut maximal, peuvent ˆetre pris en consid´eration.
De plus, il est ´egalement possible de distinguer le cas des applications batch de celui des applications interactives. Les premi`eres ne n´ecessitent aucune intervention de la part de l’utilisateur au cours de leur ex´ecution. Elles sont ainsi parfaitement adapt´ees a` une ex´ecution sur grille, et leur ex´ecution peut ˆetre pr´eempt´ee et diff´er´ee si besoin. En revanche, les applications interactives dialoguent r´eguli`erement avec l’utilisateur. Dans ce cas, de telles pratiques sont difficilement envisageables.
Les besoins des applications en termes de r´eseau doivent ´egalement ˆetre pris en consid´era-tion. Par exemple, s’il s’agit d’applications parall`eles, les besoins en termes de bande-passante d´ependent du volume de donn´ees devant ˆetre transf´er´ees entre les tˆaches. Les applications param´etriques n’ont quant a` elles aucune exigence particuli`ere sur ce point. Ces caract´eristiques influenceront l’ordonnancement afin de ne pas p´enaliser ces applica-tions par un mauvais choix de ressources.
Enfin, il est possible de distinguer deux derniers cas : celui des applications temps r´eel, pour lesquelles les tˆaches sont soumises a` des contraintes de deadlines (dates buttoir), et les applications auxquelles un niveau de qualit´e de service est garanti. Pour ex´ecuter ce type d’applications dans les d´elais impartis, le gestionnaire de ressources doit s´electionner les ressources pour lesquelles les performances pr´edites sont fiables.
Ressources
Les ressources g´er´ees par les syst`emes etudi´es dans ce chapitre peuvent ˆetre fortement h´et´erog`enes. Ainsi, divers param`etres les concernant doivent ˆetre pris en compte lors de la phase d’ordonnancement [14].
La premi`ere caract´eristique que nous distinguons concerne les performances des res-sources. Pour des ressources de calcul (processeurs), il s’agit par exemple du nombre d’op´erations pouvant ˆetre r´ealis´ees a` la seconde. Dans le cas des r´eseaux, c’est la bande-passante qui est consid´er´ee. Dans tous les cas, les capacit´es des ressources constituent un param`etre important de l’ordonnancement.
Les capacit´es des ressources sont de plus modul´ees par leur charge. Le gestionnaire de ressources est alors responsable de la pr´ediction de performances des ressources, en se basant sur une estimation de cette charge. Plusieurs m´ethodes peuvent ˆetre utilis´ees pour ceci : l’´etablissement d’un mod`ele th´eorique, l’estimation bas´ee sur un historique, etc.
Une autre caract´eristique importante a` retenir est l’aspect d´edi´ des ressources. La ma-jorit´e des grilles fonctionne avec des ressources non-d´edi´ees aux activit´es g´en´er´ees par la grille. En d’autres termes, les applications soumises se partagent l’acc`es aux ressources avec des applications lanc´ees par les utilisateurs locaux de ces ressources. Dans de telles condi-tions, il est difficile de pr´edire leurs performances, ce qui peut avoir un impact significatif sur l’ordonnancement.
Enfin, de nombreux autres param`etres pourront ˆetre pris en compte, parmi lesquels le fonctionnement en temps partag´e, ou bien encore la possibilit´e de pr´eempter les applica-tions pr´esentes sur les ressources.
Fonctions objectifs
L’ordonnanceur choisit les ressources auxquelles les tˆaches des applications soumises seront associ´ees de mani`ere a` atteindre un objectif. Deux types d’objectifs sont principa-lement consid´er´es [14, 17] :
• Objectifs centr´es sur les applications : Ces objectifs tendent a` satisfaire au mieux les exigences de chacune des applications soumises. La fonction objectif a` minimiser pour trouver un ordonnancement peut inclure les param`etres suivants :
– Temps d’ex´ecution : le temps mis pour ex´ecuter l’application.
– Temps d’attente : le temps pass´e par l’application dans une file d’attente, avant son ex´ecution d’une part, et durant son ex´ecution si elle subit des interruptions.
– Temps de r´eponse : le temps total, correspondant a` la somme du temps d’ex´ecution et du temps d’attente.
– Ralentissement de l’application : le rapport entre le temps d’attente de r´eponse et le temps d’ex´ecution r´eel de l’application.
– Coˆut de l’application : si la gestion des ressources est r´ealis´ee a` l’aide de paradigmes ´economiques.
• Objectifs centr´es sur les ressources : Les objectifs appartenant a` cette cat´egorie favorisent un jeu de m´etriques li´ees au syst`eme, et non aux applications. Les pro-pri´et´es suivantes du syst`eme peuvent alors ˆetre consider´ees :
– Capacit´e de traitement : le nombre d’applications qui se terminent par unit´e de temps (par heure, par jour, etc.).
– Taux d’utilisation : le pourcentage de temps durant lequel la ressource est occup´ee.
– Performance moyenne des applications.
– Profits g´en´er´es : si la gestion des ressources est r´ealis´ee a` l’aide de paradigmes ´economiques.
Cat´egories d’ordonnancement
Des ´etudes ont et´ men´ees afin de parvenir a` d´efinir des cat´egories d’algorithmes d’or-donnancement [24, 15, 22, 17]. Nous choisissons de retenir les cat´egories pr´esent´ees en figure 2.3.
Placement statique et placement dynamique
Dans le cas du placement statique, la d´ecision de placement est prise hors-ligne, c’est-a`-dire avant l’ex´ecution du programme. Les informations concernant l’´etat des ressources ainsi que de l’application soumise sont suppos´ees disponibles au moment o`u l’ordonnan-cement est calcul´e. Ce type de placement est bien adapt´e aux applications d´eterministes dont le comportement est bien maˆıtris´e d’une part, et d’autre part aux grilles pour les-quelles l’´etat des ressources peut ˆetre pr´edit de fa¸con fiable, comme c’est le cas des grilles dont les ressources sont d´edi´ees.
Le placement dynamique repose sur le principe d’une allocation des tˆaches a` la vol´ee, lorsque l’application s’ex´ecute. Il s’agit ainsi d’un placement en-ligne. L’algorithme peut ´eventuellement s’adapter au cours de l’ex´ecution de l’application a` l’´etat des ressources, notamment a` la charge des processeurs, en choisissant de migrer certaines tˆaches d’une ressource a` une autre. Le placement dynamique est utile lorsqu’il est impossible, par exemple, de d´eterminer le temps d’ex´ecution de l’application a` ex´ecuter.
Placement centralis´e, d´ecentralis´ ou hi´erarchique
Une strat´egie d’ordonnancement centralis´ee concentre toutes les prises de d´ecisions a` un seul endroit : un ordonnanceur unique est responsable de calculer un placement des applications soumises sur l’ensemble des ressources disponibles de la grille.
Cette approche est optimale, puisque l’ordonnanceur a une connaissance de l’´etat de toutes les ressources. Cependant trois points n´egatifs se posent :
– le passage a` l’´echelle n’est pas facilit´e par une telle approche,
– ce syst`eme n’admet pas de tol´erance aux fautes,
– le goulot d’´etranglement ainsi cr´e´ peut engendrer une baisse importante des perfor-mances du syst`eme.
Le mod`ele d´ecentralis´e, ou distribu´e, confie la responsabilit´e de l’ordonnancement a` diff´erents ordonnanceurs, agissant de mani`ere coop´erative ou non. Enfin, la derni`ere strat´e-gie d’ordonnancement repose sur un mod`ele hi´erarchique, pour lequel les ordonnanceurs g`erent des entit´es de plus ou moins haut niveau selon leur position dans la hi´erarchie. Ce dernier mod`ele constitue une combinaison de l’approche statique et de l’approche dynamique.
Mod`ele coop´eratif et mod`ele non-coop´eratif
Dans le cas d’une strat´egie d’ordonnancement dynamique ou hi´erarchique, les diff´erents ordonnanceurs peuvent collaborer entre eux pour d´eterminer un placement, ou bien ils peuvent travailler de mani`ere totalement ind´ependante. Le mod`ele coop´eratif permet a` chaque ordonnanceur de calculer une partie du placement global d’une application, en communiquant avec les autres ordonnanceurs dans le but d’´evoluer vers un objectif com-mun.
Au contraire, les ordonnanceurs ´evoluant en mode non-coop´eratif sont des entit´es au-tonomes qui prennent des d´ecisions dans le but d’optimiser uniquement leurs propres objectifs, sans se soucier de la vue d’ensemble du syst`eme.
Strat´egies d’ordonnancement
Diff´erentes strat´egies d’ordonnancement, ´egalement qualifi´ees d’algorithmes de place-ment, peuvent ˆetre d´efinies d’apr`es les points cit´es pr´ec´edemment. Quelques exemples peuvent ˆetre cit´es :
• La politique de type FIFO (First In, First Out ) [25] : La strat´egie la plus simple consiste a` ex´ecuter les applications dans l’ordre o`u elles sont soumises. Dans sa version la plus stricte, les ressources ne fonctionnent pas en temps partag´e. Ce type de politique peut ainsi g´en´erer des probl`emes dus au fractionnement des ressources. En effet, si le nombre de ressources libres n’est pas suffisant pour ex´ecuter l’application en tˆete de la file d’attente, celle-ci bloquera les autres applications en attente.
• Le backfilling [26, 27] : Il s’agit d’une am´elioration de la politique FIFO. Lors-qu’une ou plusieurs applications sont bloqu´ees en tˆete de file d’attente pour cause de manque de ressources, les autres travaux en attente peuvent passer en tˆete de file s’ils n’interf`erent pas avec celles-ci. On distingue alors :
– Le conservative backfilling : les applications peuvent passer en tˆete de file si elles ne retardent aucun travail arriv´e avant.
– Le easy backfilling : les applications peuvent passer en tˆete de file si elles ne re-tardent pas le travail arriv´e en premier (en tˆete de file).
• Le gang scheduling [28, 29] : Les applications ´evoluent en temps partag´e sur les ressources. Chacune d’entre elles dispose d’un acc`es aux ressources pendant une quantit´e de temps fixe (on emploie le terme de quantum), puis elle est interrompue afin de lib´erer les ressources pour les autres applications, et reprendra son ex´ecution lors du prochain quantum qui lui sera allou´e. Notons que la pr´eemptibilit´ est un pr´erequis a` cette approche.
• La politique MET (Minimum Execution Time) : Cette strat´egie permet d’as-signer chacune des tˆaches au processeur qui minimise son temps d’ex´ecution, sans se pr´eoccuper de sa disponibilit´e. Chaque tˆache aura ainsi la ressource qui lui est en th´eorie la mieux adapt´ee. Cependant, cette approche r´esulte en pratique a` un fort d´es´equilibre de charge entre les ressources, et si le temps d’ex´ecution des tˆaches est minimal, leur temps de r´eponse (attente et ex´ecution) n’est en revanche pas optimal.
• La politique MCT (Minimum Completion Time) : Cette politique est iden-tique a` la politique MET, except´ que le temps pris en compte est le temps de r´eponse, c’est-a`-dire le cumul du temps d’attente et du temps d’ex´ecution. Cette strat´egie permet alors un meilleur ´equilibrage des charges sur l’ensemble des res-sources consid´er´ees.
• La politique MECT (Minimum Execution and Completion Time) : En pratique, les politiques MET et MCT peuvent ˆetre utilis´ees conjointement [30, 31]. L’algorithme de placement admet alors plusieurs entr´ees : l’ensemble des tˆaches Ti de l’application, et le temps d’ex´ecution ei,j de chaque tˆache i sur un processeur Pj . Pour chacune des tˆaches Ti de l’application, les ´etapes suivantes sont n´ecessaires afin de d´eterminer le processeur m qui l’ex´ecutera :
– Calcul du temps d’attente maximal : bmax = maxPj ∈P bi,j o`u bi,j d´esigne le temps d’attente de la tˆache Ti sur le processeur Pj .
– D´etermination de l’ensemble de ressources P ′ = {Pk \ci,k < bmax}
Il s’agit ainsi de d´eterminer les ressources pour lesquelles le temps de r´eponse sera inf´erieur au temps d’attente maximal.
– Si de telles ressources existent (|P ′| > 0), alors on choisit m tel que : ei,m = minPj′∈P ei,j c’est-a`-dire que le processeur ´elu est celui qui, parmi les ressources s´electionn´ees, minimise le temps d’ex´ecution de l’application.
– Dans le cas contraire, on choisit le processeur m minimisant le temps de r´eponse parmi toutes les ressources disponibles : ci,m = minPj ∈P ci,j
Il s’agit ainsi de faire une premi`ere s´election de ressources pour lesquelles le temps d’attente de la tˆache n’est pas p´enalisante. Dans ce cas, la politique MET peut ˆetre appliqu´ee. Si de telles ressources n’existent pas, on emploie alors la politique MCT.
• Le rescheduling [32] : Au cours de l’ex´ecution d’une application, il est possible que l’ordonnancement initialement calcul´e perde son optimalit´e en fonction des per-formances du syst`eme ou bien en raison du changement des besoins de l’application. Il peut ainsi ˆetre int´eressant de modifier l’ordonnancement afin de migrer les tˆaches vers des ressources plus a` mˆeme de les ex´ecuter. Cette strat´egie peut ´egalement ˆetre utilis´ee pour mettre en place un ´equilibrage de charge dynamique des ressources.
• Le placement avec qualit´e de service garantie [33] : Cet algorithme permet de placer des applications parall`eles sur un support orient´ vers la prestation de services applicatifs : les ressources sont d´edi´ees aux activit´es li´ees a` la grille, de telle sorte que leur charge est connue et pr´evisible a` tout moment. Quatre classes d’applications sont d´efinies, par ordre de priorit´e d´ecroissante (cf. figure2.4) :
– Applications avec deadline : une date buttoir est d´efinie pour chaque application, avant laquelle celle-ci doit se terminer. L’ex´ecution peut ˆetre imm´ediate ou diff´er´ee.
– Applications prioritaires : cette classe garantit que l’ex´ecution sera imm´ediate.
– Applications a` ressources non-partag´ees : chaque application sera seule a` utiliser les ressources qui lui sont attribu´ees durant son ex´ecution.
– Applications best effort : aucune contrainte n’est exprim´ee sur ces applications. Elles sont ex´ecut´ees le plus tˆot possible avec les ressources disponibles.
Ce type de placement soul`eve un probl`eme d’optimisation, pour lequel le crit`ere retenu permet d’optimiser l’utilisation des ressources du fournisseur. Ainsi, pour une application A donn´ee, l’ordonnancement s est choisi parmi tous les ordonnancements S(A) possibles d’apr`es le crit`ere suivant : min max Mu(m) tf (m, s) + tf (m, s) × Mf × Mt(m) s∈S(A)m
La date de lib´eration des ressources tf (m, s) est optimis´ee. De plus, un second crit`ere consiste a` int´egrer l’espace m´emoire utilis´e, de mani`ere a` p´enaliser les machines dont la m´emoire est d´ej`a satur´ee. Ainsi, le rapport Mu (m) repr´esente la quantit´e de Mt (m) m´emoire utilis´ee sur la machine m par rapport a` la m´emoire totale. Le coefficient Mf permet d’ajuster la pond´eration de cette partie du crit`ere, tandis qu’on multiplie par tf (m, s) afin de se ramener dans le mˆeme ordre de grandeur que la premi`ere partie du crit`ere.
Introduction aux mod`eles ´economiques
La grille de calcul est un lieu d’´echange de ressources : leurs propri´etaires les mettent a` disposition des utilisateurs de la grille pour que ces derniers puissent y ex´ecuter leurs applications. Dans un tel contexte, les fournisseurs de ressources et leurs consommateurs auront chacun leurs propres objectifs et strat´egies [34]. Une approche bas´ee sur les mod`eles ´economiques du march´e r´eel peut ainsi ˆetre employ´ee dans le cadre du calcul sur grille.
Les mod`eles ´economiques constituent une m´etaphore pour la gestion des ressources et le placement d’applications, permettant ainsi de r´eguler l’offre et la demande au niveau des ressources de la grille tout en garantissant une certaine qualit´e de service aux clients. Ils permettent ainsi d’inciter les producteurs a` partager leurs ressources, en leur fournissant une contrepartie, et ´egalement inciter les consommateurs a` r´efl´echir au compromis entre temps de calcul et coˆut selon la qualit´e de service d´esir´ee.
Historique
L’exp´erience d’Harvard en 1968
Le premier exemple d’utilisation de paradigmes ´economiques pour g´erer des ressources informatiques remonte a` la fin des ann´ees 60. Sutherland publie en 1968 un rapport d´etaillant l’utilisation d’un syst`eme d’ench`eres mis en place au sein de l’universit´ d’Har-vard pour r´eguler l’acc`es a` un ordinateur, le PDP-1 [35].
Cet ordinateur ´etait utilis´e par l’ensemble des ´etudiants de l’universit´e, ainsi que par les membres enseignants et chercheurs, afin d’ex´ecuter leurs exp´eriences. Celles-ci pouvaient durer de quelques minutes a` plusieurs heures, au cours desquelles les utilisateurs devaient rester devant la machine. En effet, les exp´eriences ´etaient pour la plupart interactives, et n´ecessitaient ainsi la pr´esence des utilisateurs. De plus, le PDP-1 ´etait mono-utilisateur. Par cons´equent, les utilisateurs ´etaient en comp´etition pour y acc´eder, et une demande tr`es importante ´etait constat´ee en journ´ee, a` des heures que l’on pourrait qualifier de “pratiques” pour les utilisateurs.
Un syst`eme d’ench`eres a alors et´ mis en place. Chaque personne se voyait remettre un certain montant d’une monnaie fictive, le yen, en fonction de la priorit´e de ses exp´eriences. Le temps ´etait divis´e en tranches de 15 minutes, et chaque utilisateur pouvait proposer une certaine somme, en yens par heure, pour obtenir l’acc`es a` la machine durant l’intervalle de temps d´esir´. Chaque utilisateur pouvait alors surench´erir en fonction de ses besoins, et de ses capacit´es a` le faire. La coordination des ench`eres ´etait r´ealis´ee en centralisant toutes les offres sur un tableau d’affichage unique.
Sutherland montre ainsi qu’un tel syst`eme ´etait parfaitement fonctionnel. Il ´etait en outre exempt de tout ph´enom`ene de famine, et ´etait auto-suffisant : les yens ´etaient au-tomatiquement revers´es aux utilisateurs aussitˆot apr`es les avoir consomm´es.
D`es lors, l’emploi de paradigmes ´economiques a et´ repris pour r´eguler l’utilisation de ressources informatiques [36]. Par exemple, Nielsen pr´esente dans [37] un mod`ele de tarification destin´ a` r´eguler la demande au sein d’une communaut´e de 200 physiciens du Stanford Linear Accelerator Center. Ces derniers ex´ecutaient la plupart du temps des applications batch. L’objectif ´etait alors de les inciter a` ´etaler les soumissions au cours du temps afin de ne pas saturer le syst`eme.
La facturation de l’utilisation des ressources pouvait ´egalement avoir d’autres objectifs [38, 39], tels que l’amortissement du coˆut du mat´eriel. Les strat´egies d’´etablissement des prix s’appuyaient alors sur l’optimisation du profit des fournisseurs de ressources.
L’arriv´ee des r´eseaux et du calcul distribu´e
A partir du milieu des ann´ees 80, la d´emocratisation des r´eseaux informatiques a chang´e la philosophie de l’utilisation de mod`eles ´economiques. La multiplicit´e des fournisseurs de ressources a compliqu´e la situation [40] : d´esormais, ces derniers sont en comp´etition pour vendre l’utilisation de leurs ressources. On se rapproche alors d’une r´eelle ´economie de march´e [41, 42, 43].
L’utilisation de mod`eles ´economiques permet alors de d´ecentraliser le processus d’al-location de ressources [41], limitant ainsi sa complexit´. Ceci implique une plus grande efficacit´ dans la prise de d´ecision, une meilleure tol´erance aux fautes dans le syst`eme et un passage a` l’´echelle plus ais´e.
Quelques exemples d’utilisation de mod`eles ´economiques
Ferguson et al. ont mis en place un algorithme d’´equilibrage de charge bas´e sur des concepts provenant de la micro-´economie [44]. Celui-ci est appliqu´e aux syst`emes distribu´es dans le but d’allouer et de partager les ressources de calcul et de communication. Ainsi, les processeurs vendent des ressources libres (lien r´eseau ou temps CPU), en utilisant un mod`ele de vente aux ench`eres. Chaque application d´etermine alors ses pr´ef´erences en termes de fournisseur : elle choisit ceux qui pourront lui fournir la meilleure prestation (selon ses besoins) en fonction du budget dont elle est dot´ee, et peut ainsi leur soumettre une offre. Les auteurs montrent que les performances de cette approche sont au moins aussi bonnes que celles des syst`emes traditionnels d’´equilibrage de charge.
Les auteurs de [45] d´ecrivent le syst`eme appel´ Spawn. Il s’agit d’un syst`eme de gestion de ressources permettant de g´erer un r´eseau de stations de travail hautes-performances. Il r´ecup`ere les ressources non-utilis´ees, et permet aux utilisateurs de les employer, ´evitant ainsi un gaspillage inutile. Un syst`eme de vente aux ench`res est alors mis en place pour vendre des quantums de temps CPU aux applications. Celles-ci peuvent ainsi disposer d’un acc`es d´edi´ a` la ressource durant les quantums acquis. Les applications consid´er´ees par Spawn sont des applications parall`eles a` gros grain, ou bien des applications param´etriques. Celles-ci ont la possibilit´es de soumettre des offres aux fournisseurs, une offre ´etant com-pos´ee du montant propos´e pour une dur´ee de temps sp´ecifi´ee. Il est a` noter que Spawn ne tol`ere pas la migration, ni la pr´eemption. Ainsi une application, qui ne se termine pas du-rant la p´eriode de temps qu’elle a achet´ee, a la priorit´e sur l’achat des quantums suivants, si toutefois son budget lui permet de suivre les prix du march´e.
De la mˆeme mani`ere, POPCORN [46] est un logiciel Java permettant de vendre aux ench`eres les cycles CPU d’ordinateurs reli´es a` l’Internet. La monnaie utilis´ee est acquise en partageant ses ressources, et est d´epens´ee lors de la consommation de celles disponibles.
Un exemple de gestion des ressources d’une grille compos´ee d’appareils mobiles est pr´esent´ dans [47]. Dans ce cas, les fournisseurs de ressources sont les appareils mobiles, tandis que les consommateurs sont les serveurs WAP qui leur confient des tˆaches a` ex´ecuter. L’objectif des auteurs a et´ de d´efinir un mod`ele de calcul de coˆut s’appuyant sur un jeu de n´egociation non-coop´eratif, qui soit juste et stable. Ce mod`ele a alors et´ utilis´e pour mettre en place un syst`eme d’ordonnancement d´ecentralis´e robuste a` ´equilibrage de charge.
Le dernier exemple que nous citerons est celui de Mariposa [40, 48]. Il s’agit d’une base de donn´ees distribu´ee utilisant une approche bas´ee sur les mod`eles ´economiques pour g´erer le stockage ainsi que l’ex´ecution des requˆetes. Chaque site contient un ensemble d’objets stock´es. Lorsqu’un client soumet une requˆete, celle-ci est d´ecompos´ee en sous-requˆetes, et un appel d’offres est op´er´ aupr`es des sites. En fonction du budget allou´e a` la requˆete, le client choisit les sites les plus adapt´es, et leur soumet alors un ensemble de sous-requˆetes. Lorsque celles-ci ont et´ trait´ees, les sites renvoient d’une part leur r´esultat, et d’autre part la facture correspondant. Il est a noter que si les sites mettent plus de temps a` ex´ecuter une requˆete que pr´evu, des pénalités leur sont imputées.
|
Table des matières
1 Introduction
1.1 Les grilles de calcul
1.1.1 Définition d’une grille de calcul
1.1.2 Caractéristiques d’une grille et de ses ressources
1.2 La plate-forme de recherche Grid’5000
1.2.1 Présentation générale
1.2.2 Architecture et réseau
1.2.3 Accès aux ressources
1.2.4 Principe d’utilisation de la grille
1.3 Problématique liée `a la gestion des ressources
1.4 Plan de la thèse
2 Gestion des ressources d’une grille de calcul
2.1 Objectifs et challenges
2.1.1 Caractéristiques de l’ordonnancement sur grille
2.1.2 Missions d’un gestionnaire de ressources
2.2 Ordonnancement sur une grille de calcul
2.2.1 Applications
2.2.2 Ressources
2.2.3 Fonctions objectifs
2.2.4 Catégories d’ordonnancement
2.2.4.1 Placement statique et placement dynamique
2.2.4.2 Placement centralis´e, d´ecentralis´e ou hiérarchique
2.2.4.3 Mod`ele coop´eratif et mod`ele non-coop´eratif
2.2.5 Strat´egies d’ordonnancement
2.2.6 Introduction aux mod`eles ´economiques
2.2.6.1 Historique
2.2.6.2 Quelques exemples d’utilisation de mod`eles ´economiques
2.2.6.3 Mod`eles ´economiques existants
2.3 Outils d’observation et de pr´ediction
2.3.1 MDS (Meta Directory Service)
2.3.2 NWS (Network Weather Service)
2.3.3 Ganglia
2.3.4 Monika et DrawOARGantt
2.4 Outils de placement et de gestion des ressources
2.4.1 Globus
2.4.2 AppLeS
2.4.3 Nimrod/G et le framework GRACE
2.4.4 Le gestionnaire de ressources OAR
3 Conception et implémentation d’un modèle économique
3.1 Introduction
3.1.1 Objectifs et contexte
3.1.2 Caract´eristiques du mod`ele propos´e
3.2 Mod`ele math´ematique
3.2.1 D´efinition des variables utilis´ees
3.2.1.1 Aspects temporels
3.2.1.2 Donn´ees du probl`eme
3.2.1.3 Inconnues recherch´ees
3.2.2 Mod´elisation sous forme de probl`eme d’optimisation
3.2.3 Equations r´egissant le mod`ele
3.2.3.1 Relations entre les inconnues recherch´ees et contraintes
3.2.3.2 Quantit´e de calculs d’une tˆache
3.2.3.3 Calcul du temps d’ex´ecution de l’application
3.2.3.4 Calcul du coˆut de l’application
3.2.3.5 Influence des applications soumises sur la charge de la grille
3.3 Impl´ementation du mod`ele ´economique propos´e par un algorithme g´en´etique
3.3.1 Choix d’impl´ementation
3.3.2 Les algorithmes g´en´etiques
3.3.3 Impl´ementation
3.3.3.1 Repr´esentation des individus
3.3.3.2 Op´erateurs de reproduction
3.3.4 Validation de l’algorithme mis en place
3.3.4.1 Etude comparative des r´esultats obtenus en mode statique
3.3.4.2 Etude des r´esultats obtenus en mode dynamique
3.3.5 Performances de l’algorithme
3.3.5.1 Convergence de l’algorithme
3.3.5.2 Temps de r´esolution
3.4 Int´egration du mod`ele ´economique au sein d’OAR
3.4.1 Etude pr´eliminaire
3.4.1.1 Sp´ecifications
3.4.1.2 Incompatibilit´es entre le fonctionnement actuel d’OAR et le mod`ele ´economique
3.4.2 Politiques d’ordonnancement
3.4.3 Soumission d’applications
3.4.3.1 Mise en place d’un nouveau client
3.4.3.2 Traitement des param`etres du mod`ele
3.4.4 M´ecanismes de placement des tˆaches
3.4.5 Vue d’ensemble du processus de soumission
3.4.6 Tests et validation
3.5 Conclusion
4 Etude de l’estimation du temps d’ex´ecution d’une application
4.1 Introduction
4.2 Travaux portant sur l’estimation du WCET d’une application
4.2.1 Objectifs et contexte
4.2.2 M´ethodes dynamiques d’analyse du WCET
4.2.3 M´ethodes statiques d’analyse du WCET
4.2.3.1 Analyse de flot
4.2.3.2 Analyse de bas niveau
4.2.3.3 Calcul du WCET
4.3 Pr´ediction bas´ee sur un historique d’ex´ecutions pass´ees
4.3.1 Principe g´en´eral
4.3.2 Etat de l’art
4.3.3 Apprentissage bas´e sur des instances
4.3.3.1 Principe
4.3.3.2 Terminologie utilis´ee
4.3.3.3 Notion de distance entre deux exp´eriences
4.3.3.4 Calcul de l’estimation du temps d’ex´ecution
4.4 Approche hybride de pr´ediction de temps d’ex´ecution d’une application
4.4.1 Principe g´en´eral
4.4.2 D´efinitions et hypoth`eses
4.4.2.1 Hypoth`eses sur le temps d’ex´ecution des blocs de base
4.4.2.2 Hypoth`eses sur le temps d’ex´ecution des fonctions
4.4.3 Mod`ele math´ematique
4.4.4 Mise en œuvre du mod`ele
4.5 Conclusion
5 D´détermination du temps d’exécution des blocs de base d’un programme
5.1 Introduction
5.1.1 Objectifs
5.1.2 Principe
5.2 Exemple trait´e et faisabilit´e
5.2.1 Evolution du temps d’ex´ecution du programme en fonction des entr´ees
5.2.2 Coh´erence des temps obtenus et reproductibilit´e
5.2.3 Influence de l’utilisation de gprof et gcov sur le temps d’ex´ecution du programme
5.3 R´esolution du syst`eme d’´equations `a l’aide d’outils et de m´ethodes standards129
5.3.1 Introduction
5.3.2 Calcul d’une estimation initiale de la solution
5.3.3 R´esolution du probl`eme sous la forme d’un syst`eme lin´eaire
5.3.3.1 Pr´esentation
5.3.3.2 R´esultats obtenus
5.3.4 R´esolution du probl`eme sous la forme d’un syst`eme non-lin´eaire
5.3.4.1 Pr´esentation
5.3.4.2 R´esultats obtenus
5.3.5 Conclusion
5.4 R´esolution it´erative du syst`eme d’´equations
5.4.1 Introduction
5.4.1.1 Positionnement du probl`eme
5.4.1.2 Caract´eristiques du syst`eme d’´equations `a r´esoudre
5.4.2 Reformulation du syst`eme
5.4.3 R´esolution du syst`eme par it´erations
5.4.3.1 D´efinition de la suite
5.4.3.2 Convergence de la suite
5.4.3.3 Lien entre le conditionnement du syst`eme initial et la convergence de la suite
5.4.4 R´esultats obtenus
5.5 Am´elioration de la convergence de la r´esolution it´erative du syst`eme d’´equations
5.5.1 Introduction d’une erreur ε dans le syst`eme `a r´esoudre
5.5.2 Reformulation du syst`eme `a r´esoudre en prenant en compte l’erreur introduite
5.5.3 R´esolution du nouveau syst`eme par it´erations
5.5.3.1 D´efinition de la suite
5.5.3.2 Convergence de la suite
5.5.3.3 Choix de la matrice d’erreur
5.5.4 R´esultats obtenus
5.6 Conclusion
6 Etude du comportement d’un programme
6.1 Introduction
6.2 M´ethode d’estimation du nombre d’exécutions des blocs de base d’un programme
6.2.1 Mod`ele math´ematique
6.2.2 Impl´ementation
6.2.2.1 Principe de fonctionnement
6.2.2.2 Phase d’apprentissage
6.2.2.3 Pr´ediction
6.2.3 Exemple trait´e
6.2.3.1 Pr´esentation g´en´erale de l’application
6.2.3.2 Structure du programme
6.2.3.3 Entr´ees du programme
6.2.4 R´esultats obtenus
6.2.4.1 Estimation du comportement du programme pour une requˆete donn´ee
6.2.4.2 Extension de l’estimation `a un ensemble de requˆetes
6.2.4.3 Influence du contenu de la base de connaissances
6.3 Prise en compte de l’impact relatif des entr´ees du programme sur le nombre d’ex´ecutions des blocs de base
6.3.1 Positionnement du probl`eme
6.3.2 Reformulation du mod`ele de pr´ediction
6.3.3 Annotations du code source d’un programme
6.3.3.1 Objectifs et principe
6.3.3.2 Mise en œuvre
6.3.4 R´esultats obtenus
6.4 Mod`ele complet de pr´ediction hybride de temps d’ex´ecution
6.4.1 Pr´eambule
6.4.2 Pr´ediction du temps d’ex´ecution d’un ensemble de requˆetes
6.4.3 Variation du nombre d’experiences contenues dans la base de connaissances
6.5 Conclusion
7 Conclusion
7.1 Prédiction de comportement d’applications parallèles
7.2 Placement `a l’aide de modeles économiques sur une grille de calcul
7.3 Vue d’ensemble
7.4 Perspectives
Annexes
Télécharger le rapport complet
