Ordonnancement d’Applications Parallèles (Workflows Scientifiques) sur les ressources IaaS du Cloud Computing

Résumé

Aujourd’hui de nombreuses applications scientifiques nécessitent d’être parallélisées. Cette parallélisation permet d’exécuter simultanément plusieurs tâches indépendantes d’une même application sur des cœurs de processeurs différents. Ainsi on peut considérablement réduire le temps d’exécution (makespan) d’une telle application par rapport à sa version séquentielle (où toutes les tâches s’exécutent sur un même cœur de processeur l’une après l’autre). Les applications parallélisables sont aussi diverses que variées. On trouve de nombreuses applications de calcul scientifique dans les domaines de la recherche de médicaments, de la simulation nucléaire, de la simulation des propriétés mécaniques des engins, de la recherche astronomique, de la simulation bancaire, du traitement d’images, etc. De nombreuses applications sont modélisables sous forme de workflows scientifiques, c’est-à-dire que ces applications peuvent être représentées par des graphes orientés acycliques où les nœuds représentent les différentes tâches de l’application à exécuter. Les arcsreprésentent, quant à eux, les contraintes de dépendances entre les tâches (une tâche ne peut commencer son exécution que lorsque toutes les tâches parentes de cette tâche ont terminé leur exécution). Dans les workflows scientifiques, certaines tâches chargent des fichiers en entrée et/ou produisent des fichiers en sortie lors de leurs exécutions. Un fichier en sortie d’une tâche peut être réutilisé en entrée d’une autre tâche. Il se pose donc la problématique de l’ordonnancement de ces tâches et de ces fichiers afin de réduire l’impact des transferts de fichiers sur le réseau et de minimiser le makespan et/ou le coût d’exécution de l’application parallèle, surtout lorsque les différents cœurs de processeurs sollicités ne se trouvent pas nécessairement sur la même machine. Les workflows scientifiques s’exécutaient principalement sur les grappes de calcul (clusters). Aujourd’hui les offres IaaS (Infrastrure as a Services) des fournisseurs de cloud computing représentent un nouvel environnement d’exécution de ce type d’applications parallèles. Toutefois, cette migration vers le cloud computing entraîne de nouveaux défis d’ordonnancement à relever. En effet, puisque sur les plateformes IaaS, les ressources paraissent virtuellement illimitées et que chaque utilisateur qui souhaite y exécuter son application est facturé en fonction des ressources utilisées, le problème majeur qui se pose est comment trouver un bon compromis entre le temps d’exécution de son application et le coût d’utilisation des ressources. Nous proposons ainsi une solution pour ce problème d’optimisation bi-critères de recherche de compromis entre le makespan des workflows scientifiques et le coût d’utilisation des ressources du cloud, en menant cette étude en plusieurs étapes. La première étape consiste à proposer un algorithme d’optimisation monocritère qui tente de minimiser le makespan des workflows lorsque les ressources à utiliser sont fixées. Cet algorithme a été comparé au très populaire algorithme HEFT. Ensuite, dans une autre étude nous montrons que pour un même nombre total de cœurs de processeurs souhaité, utiliser moins de machines virtuelles contenant de nombreux cœurs de processeurs chacune est plus bénéfique qu’utiliser plus de machines virtuelles contenant chacune moins de cœurs de processeurs. En effet, cela permet de réduire considérablement le makespan des workflows scientifiques. Nous avons aussi proposé une méthode plus rapide de génération d’un front de Pareto à partir de l’algorithme proposé précédemment et en lançant les simulations sur un nombre réduit de plateformes par rapport à l’approche concurrente qui est l’algorithme MOHEFT. MOHEFT étant le meilleur algorithme de la littérature pour la résolution du problème bicritère sus-énoncé. Il faut rappeler qu’un front de Pareto représente les points optimaux obtenus à l’issu de l’exécution d’un algorithme d’optimisation multicritères. Les résultats obtenus montrent que l’approche proposée donne de meilleurs fronts de Pareto par rapport à MOHEFT en plus de donner plus de points (donc plus de choix à l’utilisateur) dans ces fronts de Pareto par rapport à ceux de MOHEFT, et de sortir les fronts de Pareto en des temps très inférieurs à ceux de MOHEFT. Enfin dans une dernière contribution, nous avons proposé une procédure par recherche dichotomique pour suggérer moins de points que ceux qui sont sur le front de Pareto complet afin de faciliter le choix à l’utilisateur. Cette approche élimine des points du front de Pareto qui ne sont pas intéressants en pratique, bien qu’étant des points optimaux théoriquement car non dominés par les autres points.

Citer ce document

Accès au document

Ce document est hébergé sur son dépôt institutionnel d'origine.

Auteur(s)

Statistiques

Consultations : 4

Téléchargements : 0