Les grilles de calcul [1] sont des architectures en plein développement. Elles consistent en un réseau d'ordinateurs faiblement couplés et ont pour but d'offrir une très grande puissance de calcul à leurs utilisateurs de la façon la plus transparente possible. Ces ordinateurs peuvent être des supercalculateurs, des clusters ou des stations de travail ordinaires. Ils sont reliés par un réseau à très grande échelle, le plus souvent Internet. De ce fait, une grille est un ensemble de logiciels permettant de répartir et d'exécuter des applications extrêmement coûteuses en calcul sur un parc de machines hétérogènes et placées sous des autorités administratives différentes.
Ainsi, un problème crucial à résoudre est la gestion et le partage des ressources multiples dans le but d'augmenter les performances du système. Des tâches sont générées par un ensemble d'utilisateurs, et attendent que des ressources soient libres pour pouvoir être traitées. Il semble alors naturel d'avoir les situations où certaines ressources soient surchargés tandis que d'autres soient sous chargées ou complètement libres. Grâce au réseau de communication, on peut envisager de pallier de telles situations en transférant une partie de la charge d'une ressource surchargée vers une ressource sous-chargée. C'est à ce problème que l'équilibrage de charge apporte une solution à travers un ensemble de technique [2] permettant une distribution équitable de la charge de travail sur les ressources disponibles d'un système. L'équilibrage de la charge de travail sur les diverses ressources disponibles d'une grille de calcul s'avère être un véritable défi dont les objectifs peuvent être de trois types: (i) Minimisation du temps moyen de réponse des applications, (ii)Maximisation du degré d'occupation des ressources, et (iii) réduction des coûts de communication.
Dans une grille de calcul, une application est toujours décomposée en plusieurs ensembles de tâches parmi lesquelles il existe des relations de précédences. De telles relations deviennent un nouveau défi pour le problème d'équilibrage de charge. Actuellement, la plupart des travaux de recherche se sont concentrés sur l'équilibrage de charge des tâches indépendantes (sans relations de précédence) [3] [4]. Bien que de tels efforts de recherches puissent résoudre le problème de l'hétérogénéité et de la dynamicité des ressources de la grille, ils ne sont pas adaptables au problème d'équilibrage des tâches dépendantes. Dans le domaine des tâches avec contraintes de précédences, plusieurs travaux ont été dédiés au problème d'ordonnancement des tâches [5] [6]. Bien qu'ils visent à minimiser le temps de réponses des tâches soumises à la grille, ces travaux de recherches se révèlent utiles uniquement si on peut injecter suffisamment de connaissances dans le processus d'ordonnancement et d'application. En d'autres termes, si les caractéristiques de la plate-forme cible (vitesses des processeurs et capacités des liens) et de l'application cible (coût des calculs et des communications associés à chaque tâche) sont connues avec suffisamment de précision, alors un excellent niveau de performance peut être atteint par le biais de stratégies statiques [7]. Toutefois, nous nous intéressons à des systèmes fortement dynamique et très hétérogènes du point de vue plate-forme et applications, ces caractéristiques compliquent toute estimation préalable de cette connaissance, ce qui rend ces travaux de recherche inapplicable à ce type d'infrastructure.
Dans cet article nous proposons un modèle hybride à deux niveaux (sous forme d'une forêt d'arbres) pour résoudre le problème d'équilibrage de charge dans les grilles de calcul. Sur la base de ce modèle, nous définissons dans la troisième section une stratégie d'équilibrage dédiée aux tâches indépendantes. La quatrième section de ce papier vise à améliorer la stratégie proposée de façon a l'adapter à la classe des tâches dépendantes. Par ce travail, nous nous intéressons à : (i) La réduction du temps de réponse global des tâches soumises à la grille, (ii) La réduction des coûts de communication induits par le transfert des tâches. A chaque cluster nous associons un arbre à deux niveaux (Fig. 2) :
• Le niveau 0 représente le gestionnaire du cluster dont le rôle est de gérer la charge local de ce dernier. • Le second niveau, correspond aux éléments de calcul qui constituent le cluster. Les arbres à deux niveaux associés aux divers clusters sont agrégés pour former une forêt d'arbres, représentant la grille toute entière (Fig. 3) [8]. A chaque niveau nous associons une fonction :
• Niveau 0 : Ce niveau, contient G gestionnaires de clusters, chaque noeud à deux fonctions principales : (i) gère la charge locale de son cluster associé ;
(ii) Participe à l'équilibrage de la charge globale de la grille.
• Niveau 1 : À ce niveau, nous trouvons les éléments de calcul de la grille connectés à leurs clusters respectifs. Chaque élément de calcul de ce niveau a pour rôle de :
(i) Collecter son information de charge ;
(ii) Envoyer cette information au gestionnaire de cluster associé ;
(iii) Exécuter les décisions d'équilibrage prises par le gestionnaire.
Le modèle d'équilibrage de charge proposé est caractérisé par:
La stratégie d'équilibrage de charge proposée est dédiée à la classe des tâches indépendantes et composée des trois étapes suivantes [9]: Étape 1 : Estimation de la charge courante du cluster (resp. de la grille) Sachant que N représente le nombre d'éléments de calcul du cluster (resp. le nombre de cluster de la grille), Chaque gestionnaire du cluster exécute les étapes suivantes :
Estime la charge courante (LOD) du cluster (resp. de la grille) en se basant sur les informations de charge envoyées par ses éléments de calcul (resp. par les gestionnaires de clusters de la grille).
• Estime la capacité (SAT) et la vitesse (SPD) du cluster (resp. de la grille). , • Estime le temps d'exécution moyen du cluster (resp. de la grille).
• Calcul l'écart type (σ) sur les charges de travail de ses éléments de calcul (resp. de l'ensemble des clusters de la grille) dans le but de mesurer l'étendue des variations de charge entre le cluster et ses noeuds (resp. entre les différents clusters).
• Envoie son information de charge de travail à l'ensemble des clusters de la grille.
Etape
Pour expérimenter la stratégie d'équilibrage proposée, nous avons utilisé un PC Pentium IV de 1.7GHz, doté d'une mémoire de 512 Mo et fonctionnant sous Linux. Les expérimentations ont étaient faites a l'aide du simulateur GridSim [10]. Pour obtenir des résultats fiables, nous avons réitéré les mêmes expériences plus de cinq fois.
Les meilleurs résultats ont été obtenus pour ε = 1500,ρ = 0.75, et δ = 0.8. A l'aide de ces expériences faites avant (sans exécution de l'algorithme d'équilibrage) et après (en exécutant l'algorithme d'équilibrage). Nous considérons différents nombre de clusters comportant 30 éléments de calcul chacun et nous varions le nombre de tâches de 4000 à 1000. Fig. 4 illustre la variation du temps de réponse, obtenue par notre stratégie d'équilibrage de charge. A travers ces résultats, nous constatons que :
• Tous les gains sont supérieurs à 22%. Etant donnée la nature des applications traitées par les grilles, il nous semble que ce gain est important et pourra, éventuellement, être amélioré.
• Les meilleurs gains ont été obtenus pour un nombre de clusters compris entre 2 et 8 et pour un nombre de tâches supérieur à 6000 (grille est dans un état stable).
• Les gains les plus faibles ont été obtenus lorsque le nombre de clusters a été fixé à 16. On peut justifier cela par l'instabilité de l'état de la grille (la plupart des noeuds sont sous chargés ou complètement libres).
Les dépendances de tâches permettent de déterminer le moment où une tâche peut débuter. En fait, une tâche peut être associée à un ou plusieurs prédécesseurs qui doivent être complétés avant de pouvoir débuter la tâche en question. De plus, un temps d'attente peut être défini entre les prédécesseurs et les successeurs correspondant au temps de transfert des paramètres requis par les successeurs.
On appelle une contrainte de précédence entre la tâche t i et la tâche t j ou t i précède t j si t j doit attendre la fin d'exécution de t i pour commencer sa propre exécution [11].
Le graphe de précédence associé est schématisé sur la Fig. 7. La tâche T1 s'exécutera en premier puisqu'elle n'a pas de contraintes à satisfaire, et les tâches T5 et T6 s'exécuteront en derniers. Fig. 7. Graphe de précédence associé.
Un graphe de précédence peut être divisé en plusieurs sous graphes, comportant chacun un certain nombre de tâches dépendantes appelés méta-tâches (Fig. 8). Notons qu'il n'existe pas de relations de précédence entre les méta-tâches. Cet article propose un modèle et une stratégie d'équilibrage de charge pour résoudre le problème d'équilibrage de charge dans les grilles de calcul. Nous avons, tout d'abord conçu un modèle représentant une grille de calcul, qui prend en compte les caractéristique d'une grille de calcul, à savoir l'hétérogénéité et la dynamicité des ressources et des réseaux de communications, ainsi que le passage à l'échelle.
Nous avons ensuite développé sur ce modèle une stratégie d'équilibrage de charge qui vise dans un premier temps les tâches indépendante ou sans contraintes de précédences. Les résultats obtenus par l'implémentation de la stratégie sous le simulateur GridSim sont pour le moment très satisfaisant.
Nous avons ensuite apporté quelques améliorations à la stratégie présentée afin de supporter les tâches avec contraintes de précédences qui présentent un réel chalenge pour l'équilibrage de charge dans les grilles de calcul.
Comme perspectives, nous visons à expérimenter notre stratégie sous le simulateur GridSim et sur un simulateur développé selon nos propores besoin. Nous nous intéressons a distribué le modèle pour éviter le recours a des procédures de tolérance aux pannes et de goulot d'étranglement causés par les gestionnaires de clusters. Enfin et une fois la stratégie maitrisée nous voulons l'intégrer au middleware GLOBUS [12].