Résumé. Les dernières évolutions dans le calcul distribué ont conduit à l'apparition de nouvelles infrastructures appelées grilles de calcul. La gestion d'équilibrage de charge dans ce type d'infrastructure est complexe et exige donc des outils sophistiqués pour analyser les algorithmes avant de les appliquer aux vrais systèmes. Cependant une recherche étendue a été conduite dans le domaine de la simulation pour modéliser de tels systèmes et comprendre leur comportement. En conséquence, un nombre croissant d'outils de simulation ont été conçus et développés. Dans ce papier nous proposons un outil de simulation de grilles qui fournit des primitives pour la création et l'ordonnancement des tâches indépendantes. C'est un simulateur qui permet d'évaluer les performances d'un modèle distribué pour résoudre le problème d'équilibrage de charge dans les grilles de calcul. Mots-clés: Grilles de calcul, Équilibrage de charge, Simulateur de grilles, Tâches indépendantes, Modèle d'équilibrage de charge.
Dés les débuts de l’informatique, les scientifiques furent les plus gros
consommateurs de puissance de calcul. La dernière décennie a également vu
l’avènement des réseaux et d’Internet. De plus en plus de projets de recherche
impliquent de multiples partenaires pouvant être repartis aux quatre coins du globe. Il
devient alors nécessaire de disposer d’une infrastructure commune, facilitant les
partages d’informations mais aussi de ressources. C’est dans ce contexte, qu’est né le
concept de Grille de Calcul (Grid Computing): une infrastructure virtuelle constituée
d'un ensemble coordonné de ressources informatiques potentiellement partagées,
distribuées, hétérogènes et sans administration centralisée [
Lorsqu'il s'agit de comparer la performance de deux algorithmes, les conditions expérimentales doivent nécessairement être les mêmes. Or assurer la même évolution de multiples composants d'un environnement distribué dans le contexte de la grille est impossible: un trop grand nombre de phénomènes amène un non déterminisme de la plateforme de test. Il est d'usage de les simuler. Beaucoup d’outils standards et spécifiques à l'application ont été établis dans cette optique.
Cependant, ces outils de simulation ne permettent pas de tester facilement de nouveaux algorithmes de gestion d'équilibrage pour les grilles : ils leurs manquent les fonctionnalités permettant la mise en oeuvre de la politique d’informations nécessaire à tout système d’équilibrage. Cette information concerne aussi bien l’état de charge des ressources disponibles que la charge du réseau de communication à un instant donné.
Dans cet article nous proposons un simulateur de grilles nommé OrientéSim qui : (i) fournit des primitives pour la création et l'ordonnancement des tâches indépendantes, (ii) permet d'évaluer les paramètres de performance d'un modèle distribué pour résoudre le problème d'équilibrage de charge dans les grilles de calcul.
Le reste de cet article est organisé comme suit : Dans la deuxième section, nous présentons une taxonomie des outils de simulation. La troisième section cite quelques outils de simulation et propose un tableau de comparaison. La quatrième section présente le simulateur proposé. Dans la cinquième section, nous présenterons et discuterons quelques résultats expérimentaux relatifs au model développé. La sixième section conclut cet article et présente quelques perspectives futures de recherche.
Les outils de simulation sont nombreux et il est difficile d'en faire une présentation
détaillée. Pour cela, la nécessité d'avoir une taxonomie qui permet d'uniformiser les
terminologies pour une meilleure description est indispensable. Ainsi, Anthony
Sulistio, Chee Shin Yeo et Rajkumar Buyya [
Taxonomie des utilisateurs : l'outil de simulation peut être utilisé comme un simulateur ou comme un émulateur ; un simulateur est un outil qui représente un système réel par contre l'émulateur est un outil qui agie comme un système réel.
Taxonomie de simulation : en général, une simulation comporte trois propriétés :
Présence du temps: indique si la simulation d'un système prend en compte le facteur temps. Une simulation statique ne considère pas le temps en tant qu'élément de simulation, contrairement à une simulation dynamique.
Valeur de base: spécifie les valeurs que peut prendre une entité simulée. Une simulation discrète à des valeurs d’entités appartenant à un intervalle fini tandis qu’une simulation continue propose des valeurs d’entités appartenant à un intervalle infini.
Comportement: la simulation peut se dérouler d'une manière déterministe (sans événements aléatoires) ; Ainsi la répétition de la même simulation rendra toujours les mêmes résultats contrairement à une simulation probabiliste (avec événements aléatoires) ; la répétition de la même simulation rend souvent des résultats différents.
Taxonomie de conception : Cela consiste à classer les outils de simulations par catégories basées sur les composants et les dispositifs nécessaires à la simulation:
Moteur de simulation : la simulation peut être exécutée en mode séquentiel ou en mode parallèle ; Une simulation séquentielle est exécutée en utilisant un seul processeur, alors qu'une simulation parallèle ou distribuée est exécutée en utilisant plusieurs processeurs.
Environnement de conception : détermine comment l'utilisateur utilise l'outil pour concevoir des modèles de simulation. Un langage fournit un ensemble de constructions définies pour concevoir des modèles de simulation, alors qu'une bibliothèque fournit un ensemble de routines pour être utilisé avec un langage de programmation.
Interface utilisateur: détermine comment l'utilisateur agit avec l'outil de simulation. Une interface de conception visuelle permet à l'utilisateur de créer un modèle de simulation beaucoup plus facile et plus rapide. Alors qu'une interface de conception non-visuel exige à l'utilisateur d'écrire des codes de programme ce qui exige plus de temps et d'effort.
Supports système: fournit les dispositifs utiles et prêts à employer qui aident l'utilisateur à construire un modèle de simulation précis.
Dans la littérature beaucoup d’outils standards et spécifiques à l'application ont été établis parmi lesquels nous pouvons citer :
Bricks [
OptorSim [
MicroGrid [
Le tableau (Table 1) compare ces quatre simulateurs en respectant la taxonomie présentée dans la deuxième section.
La figure Fig. 1, présente les différents composants du simulateur que nous avons développé dans le but d’avoir un outil approprié à nos besoins, à savoir modéliser l’information de charge qui caractérise les ressources de calcul d’une grille, implémenter et évaluer les performances des stratégies d’équilibrage de charge dédiées aux environnements de grille de calcul.
Sites: fournit les ressources de calcul nécessaires à l’exécution des tâches soumises par l'ordonnanceur.
Gestionnaire d'équilibrage: chaque gestionnaire participe au maintien des informations de charge et à l'équilibrage de la charge globale des éléments de calcul de la grille. Les différents gestionnaires peuvent échanger leurs informations de charge.
Chaque ressource représente un élément de calcul, et se caractérise par : Hétérogénéité : sur le plan matériel (architecture des processeurs, nombre de processeurs, vitesse CPU mesurée en MIPS1, File d’attente) et sur le plan logiciel (système d'exploitation).
Période : durant laquelle, la ressource mesure sa charge courante.
Dans OrientéSim il n'existe pas des protocoles réseaux ou de normes qui doivent être suivies. Tous les éléments sont reliés en utilisant des liens logiques.
OrientéSim est écrit en Java, pour les raisons principales suivantes : Approche orientée objet : où il y a plusieurs composants distincts qui agissent les uns sur les autres par l'intermédiaire de méthodes bien définies.
Capacité d'exécuter des threads concourants : les threads sont assignés à chaque site et à chaque CE (élément de calcul), l'ordonnanceur et un thread simple.
Portabilité : permettant à la simulation d'être distribuée facilement sans avoir à recompiler le code pour les différents systèmes.
Extensibilité : Le code est structuré dans plusieurs packages, dont chacun traite une partie différente de la simulation.
La figure fig. 2, montre les différentes interactions entre les composants d’OrientéSim pendant la vie de la simulation, c'est un exemple de diagramme de séquence dans lequel le temps augmente de haut en bas.
Tout d'abord l'ordonnanceur affecte chaque tâche soumise par l’un des utilisateurs à un élément de calcul selon l’une des stratégies d'ordonnancement présentées cidessus. Les tâches sont insérées aux files d'attente de chaque élément de calcul. Quand l'élément de calcul est prêt à traiter la tâche il la dépile et l'exécute.
A chaque période de temps l'élément de calcul évalue sa charge courante, envoie son information de charge au gestionnaire d'équilibrage, ce dernier prend les décisions d'équilibrage de charge, la procédure se répète jusqu'à la fin de la simulation.
Pour valider notre simulateur nous avons implémenté un modèle distribué reposant sur une architecture hybride. Sur la base de ce modèle nous avons développé une stratégie d'équilibrage centralisée locale, intra-cluster, et une deuxième totalement distribuée, inter-clusters. L’ensemble des expériences ont été réalisées sur un PC Pentium DUAL CPU de 2.00 GHz, doté d’une mémoire de 1 Go et fonctionnant sous Windows XP.
Dans ce modèle, nous considérons qu’une grille de calcul est composée d’un ensemble de Clusters qui communiquent à travers un réseau WAN. Chaque cluster est à son tour composé d’un ensemble de Noeuds de calcul qui communiquent à travers un réseau LAN. Ces entités (noeuds de calcul, clusters et réseaux locaux) peuvent être hétérogènes. Nous pouvons représenter cette topologie par un modèle arborescent à deux niveaux (Fig. 3).
Niveau 1 : ce niveau est constitué d’un ensemble de noeuds qui représentent les clusters de la grille. Chaque noeud est appelé gestionnaire du cluster.
Niveau 2 : ce niveau est à son tour constitué d’un ensemble de noeuds, qui correspondent aux noeuds de calcul de chaque cluster.
Selon la structure arborescente du modèle proposé nous avons développés une stratégie d'équilibrage de charge à deux niveaux : Intra-cluster et Inter-clusters. Équilibrage intra-cluster : Dans cette première phase, chaque gestionnaire de cluster et selon les informations de charge transmises par ses éléments de calcul, décide de lancer une opération d’équilibrage de charge locale à son cluster. Équilibrage intra-grille cette deuxième phase est réalisée entre les clusters de la grille, elle est lancée par chaque gestionnaire de cluster qui ne parvient pas à équilibré sa charge localement.
Nous avons utilisé la stratégie aléatoire comme stratégie d'ordonnancement et nous avons varié le nombre de noeuds de calcul de 40 à 100, avec un nombre de tâches variant de 4000 à 8000.
Le tableau suivant, montre les gains obtenus en temps de reponse, temps d'attente et temps d'exécution. Nous pouvons constater à partir des résultats ci-dessus que pour parvenir à stabiliser le système et avoir de bons gains, il faut avoir, pour une charge de 4000 à 8000 tâches et un nombre de ressources variant de 60 à 100 noeuds.
Dans cet article nous avons proposé un outil de simulation de grille OrientéSim, qui dispose d’une architecture extensible et modulaire, il fournit des primitives pour la création et l'ordonnancement des tâches indépendantes et permet de tester les paramètres de performances d'un modèle distribué pour l'équilibrage de charge dans les grilles de calcul.
Comme perspectives, nous pensons à :
Etendre notre simulateur par un module de gestion de réplication. Nous avons implémenté deux stratégies d’équilibrage de charge basé essentiellement sur un placement de taches comme mécanisme de transfert. Nous aimerions élargir notre simulateur pour étudier l’équilibrage de charge avec une migration de taches qui s’avère une opération très complexe à réaliser.
Appliquer l'équilibrage de charge dans le cas ou les tâches sont dépendantes.
Nous avons vue que dans OrientéSim il n'existe pas des protocoles et des normes qui doivent être suivie on aimerait bien d'implémenter des protocoles réseau.