Tài liệu Workflows scientifiques sur plusieurs clouds (stage effectué à l’ens de lyon laboratoire de l’informatique du parallélisme (lip) pour l’obtention du diplôme de master informatique option système et réseaux)

Workflows scientifiques sur plusieurs clouds Mémoire de fin d’études Stage effectué à l’ENS de Lyon Laboratoire de l’Informatique du Parallélisme (LIP) pour l’obtention du diplôme de Master Informatique option Système et Réseaux Par DAO Van Toan [email protected] [email protected] Encadrants : Frédéric DESPREZ (INRIA - Avalon) [email protected] Jonathan ROUZAUD-CORNABAS (CNRS - CC-IN2P3/LIP - Avalon) [email protected] Lyon, Novembre 2013 Remerciements Je tiens à remercier tous ceux qui m’ont aidé à la réalisation de ce travail. Mes premiers remerciements vont à mes encadrants Fédéric DESPREZ et Jonathan ROUZAUD-CORNABAS à l’École Normale Supérieure de Lyon pour m’avoir donné de nombreux conseils ainsi que des orientations importantes dans l’approche académique et scientifique. J’ai obtenu des connaissances inestimables et de très bonnes compétences dans le domaine de la recherche. De plus, j’aimerais remercier Laurent LEFEVRE qui a présenté ce stage sur son site. J’aimerais remercier tous les membres de l’équipe AVALON du LIP, pour leur amitié et leur soutien. Je tiens à remercier ensuite tout le personnel et enseignants de l’Institut de la Francophonie pour l’Informatique (IFI) à Hanoi pour leur conseil et le suivi qu’ils m’ont accordé pendant mes études de master. Je tiens également à remercier mes camarades étudiants de l’IFI avec qui j’ai passé de bons moments pendant les périodes de stress et des cours. J’aimerais remercier mes amis de Lyon. J’adresse un merci particulier à toute ma famille qui malgré la distance n’a cessé de me prêter main forte. Résumé Les calculs scientifiques sont compliqués et les données manipulées sont très grandes alors ils nécessitent un grand ensemble de ressources de calcul et de stockage ainsi qu’une méthode pour les utiliser efficacement. La technique dite workflow scientifique est devenue l’un des principaux choix dans la communauté scientifique pour formaliser et structurer les calculs scientifiques. Le but premier du workflow scientifique est de maximiser la performance. De plus, le concept de cloud computing amène une nouvelle dimension dans la technologie de l’information, grâce à ses avantages, on peut augmenter les ressources disponibles avec celles provenent de clouds privés et publiques. De plus, le cloud privé peut facilement renforcer sa performance en tirant parti des clouds publiques, hybride cloud computing. Les workflows ont tout intérêt à tirer parti des environnements multi-clouds. Dans ce rapport, nous nous intéressons aux algorithmes d’ordonnancement pour les workflows scientifiques dans les environnements multi-clouds de type IaaS pour maximiser leurs performances d’exécution tout en minimisant son coût et son temps d’exécution. Pour cela, nous proposons notre solution qui se compose de 3 phases : découpage d’un graphe en sous-graphes (cutting-graph), faire l’allocation des ressources, faire l’ordonnancement des tâches et des données. Après, notre proposition est validé via simulateur grâce à SimGrid Cloud Broker du projet ANR INFRA SONGS 1 qui a été construit pour simuler Amazon Web Service 2 . Les résultats expérimentaux montrent une corrélation entre le temps d’exécution, la distribution des tâches dans des clusters et le coût du workflow, révélant ainsi la nécessité d’algorithmes qui s’adaptent aux demandes de l’utilisateur. Mots-clés : Le cloud computing, le modèle IaaS, l’environnement multi-clouds, le workflow scientifique, l’algorithme d’ordonnancement, le coût et le makespan, SimGrid Cloud Broker, le simulateur Amazon Web Service. 1. http ://infra-songs.gforge.inria.fr/ 2. http ://aws.amazon.com/fr/ Abstract The scientific applications are complex and manipulated very large datasets. So they require a large set of computing resources and storage as well as a method to use them effectively. The scientific workflow technique has become one of the main choice in the scientific community to formalize and structure scientific computations. The main goal of scientific workflow is to maximize performance. Furthermore, the cloud computing is a new dimension in the information of technology, thank to its advantages, you can increase the available resources with those coming from private and public cloud computing. In addition, the private cloud computing can easily enhance its performance or its infrastructure through the public cloud computing, hybrid cloud computing. Scientific workflows must take adavantage of multi-clouds environment. In this report, we focus on the scheduling algorithms for the scientific workflows in the IaaS multi-clouds environments to maximize runtime performance while minimizing its costs and execution time. For this, we propose our solution consists of three phases : cutting a graph into subgraphs, resource provisioning, task allocation. Finally, our proposal is validated via the simulator with SimGrid Cloud Broker of the project ANR INFRA SONGS that was built to simulate Amazon Web Service. Experimental results show a correlation between the execution time, the distribution of the tasks in the clusters and the cost of workflow, revealing that algorithms needs to adapt to user’s requirements. Key-words : The cloud computing, the model IaaS, the multi-clouds environment, the scientific workflow, the scheduling algorithm, the cost and the performance, SimGrid Cloud Broker, the simulator Amazon Web Service. Table des matières 1 INTRODUCTION 1.1 Motivations . . . . . . . . . . . . . . . . . 1.2 Objectifs et Domaines d’application . . . . 1.3 Structure du document . . . . . . . . . . . 1.4 Présentation de l’environnement de travail 2 LE 2.1 2.2 2.3 . . . . 5 5 5 6 7 CLOUD COMPUTING ET LE WORKFLOW SCIENTIFIQUE LE CLOUD COMPUTING . . . . . . . . . . . . . . . . . . . . . . . . . LE WORKFLOW SCIENTIFIQUE . . . . . . . . . . . . . . . . . . . . . SGCB : Simulation d’environnement multi-Clouds avec SimGrid . . . . . 8 8 12 15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 DES ALGORITHMES D’ORDONNANCEMENT DES TÂCHES DU WORKFLOW 16 4 SOLUTION ET RÉLIASATION PRATIQUE 21 4.1 LA SOLUTION PROPOSÉE . . . . . . . . . . . . . . . . . . . . . . . . 21 4.2 LE TRAVAIL PRATIQUE . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5 EXPÉRIMENTATIONS ET ANALYSES DES RÉSULTATS 31 6 CONCLUSION 39 A La taille de données dans un cluster 44 B Des autres expérimentations 46 1 Table des figures 2.1 2.2 2.3 2.4 2.5 2.6 La convergence des avantages du cloud computing. . Les types de cloud computing. . . . . . . . . . . . . . Des structures simples du workflow. . . . . . . . . . . Un workflow simple par DAG. . . . . . . . . . . . . . Des types de découpage des tâches dans le workflow. L’architecture du broker de cloud SIMGRID. . . . . . . . . . . . 9 11 12 13 14 15 3.1 Un exemple des workflows dans plusieurs clouds. . . . . . . . . . . . . . . 17 4.1 4.2 4.3 4.4 4.5 Des étapes de l’algorithme de l’ordonnancement dans mon étude. Un processus avec des étapes de faire l’ordonnancement. . . . . . Le workflow Montage. . . . . . . . . . . . . . . . . . . . . . . . . Le workflow Epigenomics. . . . . . . . . . . . . . . . . . . . . . . Le workflow Inspiral. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 29 30 30 30 5.1 5.2 5.3 5.4 5.5 5.6 La distribution des tâches dans des clusters avec Inspiral. . . . . . . . . . La distribution des tâches dans des clusters avec Montage. . . . . . . . . La distribution des tâches dans des clusters avec Epigenomics. . . . . . . Le prix total, le temps total d’exécution et ratio entre eux du Montage 25 Le prix total, le temps total d’exécution et ratio entre eux du Inspiral 30 Le prix total, le temps total d’exécution et ratio entre eux du Epigenomics 24 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 33 33 35 36 A.1 La taille de données dans des clusters avec Inspiral. . . . . . . . . . . . . A.2 La taille de données dans des clusters avec Montage. . . . . . . . . . . . A.3 La taille de données dans des clusters avec Epigenomics. . . . . . . . . . 44 45 45 B.1 B.2 B.3 B.4 B.5 46 46 47 47 47 Le Le Le Le Le prix prix prix prix prix total, total, total, total, total, le le le le le temps temps temps temps temps d’exécution d’exécution d’exécution d’exécution d’exécution et et et et et 2 ratio ratio ratio ratio ratio entre entre entre entre entre eux eux eux eux eux . . . . . . du du du du du . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Montage 50 . . . Inspiral 50 . . . Epigenomics 46 . Montage 100 . . Inspiral 100 . . . 37 DAO Van Toan, Promotion 16, Réseaux et Systèmes Communicants, IFI. B.6 B.7 B.8 B.9 Le Le Le Le prix prix prix prix total, total, total, total, le le le le temps temps temps temps d’exécution d’exécution d’exécution d’exécution et et et et 3 ratio ratio ratio ratio entre entre entre entre eux eux eux eux du du du du Epigenomics 100 Montage 1000 . Inspiral 1000 . . Epigenomics 997 47 48 48 48 Liste des tableaux 2.1 Types de VMs du cloud computing . . . . . . . . . . . . . . . . . . . . . 10 3.1 3.2 Étude des algorithmes de l’ordonnancement du workflow . . . . . . . . . Une comparaison des algorithmes en basant sur les facteurs différents . . 19 20 5.1 La relation entre le numéro de clusters et le temps d’exécution. . . . . . . 31 4 Chapitre 1 INTRODUCTION 1.1 Motivations Dans la réalité, les organismes scientifiques ont besoin d’un système informatique pour exécuter leurs calculs, leurs applications scientifiques et stocker leurs données et ceci dans un grand nombre de domaine scientifique comme : l’astronomie, la bioinformatique, la génétique, la physique, la physique nucléaire, etc. Ces calculs et ces applications sont très grands, s’exécutent de manière concurrente et peuvent tirer parti des ressources fournies par les clouds. Pour cela, il y a plusieurs solutions pour construire un environnement multi-cloud : – Construire un nouveau système ou reconstruire sur un système existant (le cloud privé a été construit localement en utilisant un logiciel ouvert comme : OpenStack, OpenNebula, Eucalyptus, StratusLab, etc.). – Si l’organisme scientifique a un propre cloud privé, il est alors possible de créer une liaison avec des autres organismes scientifiques, ayant également des clouds privés (federated cloud) ou une combinaison de plusieurs cloud publics (cloud hybrid ). – Utiliser directement plusieurs cloud publics via un logiciel ou une interface commune entre eux. Le workflow scientifique est une méthode pour formaliser et structurer les calculs scientifiques. Le but du workflow scientifique est de maximiser la performance, un budget minimale, la sécurité, etc. Pour le moment, il n’est pas aisé d’utiliser ces workflows dans le cadre du cloud computing, en particulierement dans l’environnement multi-clouds alors qu’ils ont tout intérêt à en tirer parti. 1.2 Objectifs et Domaines d’application L’objectif du stage est d’étudier des algorithmes d’ordonnancement pour les workflows scientifiques dans les environnements multi-clouds de type IaaS. Nous proposons 5 DAO Van Toan, Promotion 16, Réseaux et Systèmes Communicants, IFI. des algorithmes qui sont meilleurs selon différents objectifs comme maximiser la performance, minimiser le coût et minimiser le temps d’exécution, etc. et ainsi que nous présentons notre solution. Les workflows scientifiques sont utilisés dans un grand nombre de projets qui travaillent sur des grands ensembles de données comme : Montage, Epigenomics, LHC Atlas, etc. Dans ce rapport, nous proposons des algorithmes d’ordonnancement pour les workflows dans un environnement multi-clouds pour maximiser la performance, minimiser le coût et le temps d’exécution, etc. C’est-à-dire, nous présentons des solutions pour améliorer l’exécution de calculs scientifiques qui nécessitent un grand emsemble avec de ressources qui proviennent d’un environnement dynamique et distribué comme le cloud computing. 1.3 Structure du document Le contenu du rapport se compose de 6 chapitres : – Dans le premier, nous présentons brièvement notre sujet et notre motivation. – Le chapitre 2 présente un état de l’art des travaux en liaison avec notre travail. Tout d’abord, ce rapport revient sur les définitions du cloud computing, un cloud computing IaaS et hybride, le workflow scientifique et ses problèmes comme la structure, ses caractéristiques, le système de gestion du workflow. De plus, nous présenterons des stratégies pour découper un workflow. Enfin, nous présentons brièvement l’outil de simulation, SIMGRID Cloud Broker (SGCB). – Dans le chapitre 3, nous présenterons une recherche bibliographique contenant une synthèse et une analyse critique combinée des algorithmes d’ordonnancement optimiser pour l’utilisation des clouds par les workflows scientifiques. Ce rapport présente les algorithmes existants et leurs paramètres particuliés (répondre au problème du temps, du coût, de la performance, etc). – Après, dans le chapitre 4, nous donnons un modèle des étapes de notre algorithme et une considération des stratégies et des algorithmes qui peuvent utiliser pour chacune des étapes. – Ensuite, le chapitre 5, nous introduisons notre extension à SGCB pour supporter les workflows scientifiques. Puis, nous présentons l’expérimentation et donnons notre analyse des résultats. – Enfin dans la dernière partie du rapport, le chapitre 6, nous résumerons les points faibles et forts de notre algorithmes et concluons notre étude. 6 DAO Van Toan, Promotion 16, Réseaux et Systèmes Communicants, IFI. 1.4 Présentation de l’environnement de travail Mon stage de fin d’études de Master a été effectué à l’Ecole Normale Supérieure de Lyon (ENS de Lyon) sous encadrants M. Fédéric DESPREZ et M. Jonathan ROUZAUDCORNABAS dans l’équipe de recherche AVALON du laboratoire de l’Informatique du Parallélisme (LIP). Le LIP est associé à l’Institut National de Recherche en Informatique et en Automatique (INRIA), le Centre national de la recherche scientifique (CNRS) et l’Université de Lyon 1. L’équipe AVALON 1 est grande avec environ de 30 membres, est un groupe commun entre l’INRIA, le CNRS, le LIP, l’université Claude Bernard Lyon 1 et l’université de Lyon. Les sous-projets dans l’équipe contient : les algorithmes distribuées, les modèles de programmation, le déploiement de services, la composition de service et l’orchestration, la gestion des donées à grande échelle, etc. Mon stage est une partie dans le sous-projet des algorithmes distribuées. Nous proposons des algorithmes d’ordonnancement par les workflows scientifiques dans les clouds computing qu’ils vont tester par simulation via le projet ANR INFRA SONGS. 1. http ://avalon.ens-lyon.fr/ 7 Chapitre 2 LE CLOUD COMPUTING ET LE WORKFLOW SCIENTIFIQUE 2.1 LE CLOUD COMPUTING L’idée d’Utility computing dont est fortement inspiré le concept de Cloud computing a été présentée par M. John McCarthy en 1961 dans sa thèse. De plus, l’architecture du cloud computing est issue de la recherche sur la grille de calcul, le calcul distribué, la virtualisation, l’utility computing, etc. Grâce à ces avantages, le cloud computing est un nouveau modèle de calcul pour les applications scientifiques, l’entreprise et l’utilisateur lambda. Le cloud computing 1 est un concept qui consiste à déporter sur des serveurs distants le stockage et les traitements informatiques traditionnellement localisés sur des serveurs locaux ou sur le poste de l’utilisateur. D’après la définition de l’Institut des sciences et techniques de l’ingénieur de Lyon, le cloud computing : "C’est un concept qui fait référence à l’utilisation d’un "cloud" de serveurs et d’ordinateurs répartis dans le monde entier et liés par un réseau, tel Internet. Le concept du Cloud Computing est comparable à celui de la distribution de l’énergie électrique. L’hébergeur fournit une plateforme technique capable d’accueillir à peu près tout type d’application et facture son service en fonction de la consommation des ressources", [11]. Différentes définitions ont été présentées mais elles ne sont pas des définitions standards et officielles. L’Institut National des Normes et de la Technologie des États-Unis (NIST) a donné une définition officielle : "Le cloud computing est un modèle qui apparaît partout et permet d’accèder facilement via Internet aux services qui permettent de partager des ressources informatiques (par exemple : des ressources de calcul, réseaux, serveurs, stockages, applications et services)". De plus, "Une infrastructure du 1. http ://fr.wikipedia.org/wiki/Cloud_computing 8 DAO Van Toan, Promotion 16, Réseaux et Systèmes Communicants, IFI. cloud est la collection du logiciel et du matériel qui respectent 5 caractères essentiels du cloud computing (on-demand self service, broad network access, resource pooling, rapid elasticity, measured service). Il peut être considéré comme un système qui contient deux couches : la physique et l’abstraction. La couche physique contient des ressources matériels (serveurs, stockages, composants de réseau) et autres services du cloud. La couche abstraite qui se trouve au-dessus la couche physique, contient des logiciels qui s’exécutent sur le cloud et manifestent des caractères essentielles du cloud", [37]. D’après ces définitions, on voit que le cloud computing est un modèle de services et n’est pas une technologie. C’est une combinaison complexe de matériels et logiciels mais aussi de techniques d’ingénieurie. On peut décrire les spécificités du cloud computing par un modèle visuel présenté dans la Figure 2.1. Selon [38], le cloud computing est une convergence des points forts des systèmes, des méthodes scientifiques, des technologies modernes et des nouvelles techniques. En pratique, il devient une nouvelle dimension de la technologie. Le cloud computing permet d’augmenter les profits et la rentabilité des consommateurs et des fournisseurs du service d’informatique. Toutes les ressources du cloud computing sont fournies comme des services (as a service) à l’utilisateur comme : les ressources de calcul, les ressources réseau, les ressources virtuelles, les ressources logiciel, les nouvelles technologies, etc. Le cloud computing se présente comme un modèle de service allant de l’infrastructure à la plate-forme et au logiciel comme une machine universelle. Un client lambda peut facilement l’utiliser ou l’exploiter. Il garantit la qualité de service (QoS), la sécurité, etc. Figure 2.1 – La convergence des avantages du cloud computing. 9 DAO Van Toan, Promotion 16, Réseaux et Systèmes Communicants, IFI. En pratique, il n’est pas seulement un nouveau système générique pour une organisation quelconque (l’entreprise, l’institut de la recherche, l’université, etc.) comme les systèmes précédents mais encore il est un produit des services qui permet de tirer un bénéfice. LE CLOUD COMPUTING IAAS ET HYBRIDE Le IaaS signifie Infrastructure as a Service, est un cloud de service d’infrastructure, la plus basse des 3 couches du cloud computing. Pour le modèle IaaS, NIST a donné la définition suivante : "Le IaaS fournit du calcul, stockage, réseau au consommateur pour qu’il puisse déployer des logiciels, faire fonctionner des applications (incluant le système d’exploitation). Le consommateur ne peut pas gérer ou contrôler l’infrastructure du cloud computing mais il peut contrôler le système d’exploitation et ses applications", [37]. L’Institut des sciences et techniques de l’ingenieur de Lyon a donné sa définition suivante : "L’Infrastructure-as-a-Service (IaaS) apporte la possibilité pour l’utilisateur de bénéficier, à la demande, d’une infrastructure matérielle lui fournissant une capacité de traitement, sans avoir à gérer le réseau en tant que tel", [11]. Nous présentons brièvement un tableau des types de VMs dans des clusters. Dans notre travail, nous utilisons les types de Amazon 1 . Type ArchitectureVCPUsMémoire Stockage t1. micro 32/64 bits m1.small 32/64 bits m1.xlarge 64 bits m1.tiny m1.small m1.xlarge N/A N/A N/A t1.micro m1.small m1.xlarge N/A N/A N/A Prix Linux Windows Amazon EC2 0.60 Go 0 Go $0.02/h $0.02/h 1.70 Go 1 x 160 Go$0.06/h $0.09/h 15 Go 4 x 420 Go$0.48/h $0.73/h OpenStack 1 512 Mo 0 Go N/A N/A 1 2 Go 10 Go N/A N/A 8 16 Go 10 Go N/A N/A StratusLab 1 128 Mo 0 Go N/A N/A 1 128 Mo N/A N/A N/A 2 1 Go N/A N/A N/A 1 1 4 Table 2.1 – Types de VMs du cloud computing Selon moi, le IaaS est un modèle de service du cloud qui fournit une infrastructure d’informatique comme un service en permettant de créer ou installer, intégrer, gérer et superviser des services et de construire un système virtuel complet sur un système 1. http ://aws.amazon.com/fr/ec2/pricing/ 10 DAO Van Toan, Promotion 16, Réseaux et Systèmes Communicants, IFI. réel aussi que l’administrer, etc. Différentes techniques de virtualisation peuvent être utilisées : KVM, VirtualBox, Xen, OpenVZ, VMWare, HyperV, etc. Maintenant, il existe beaucoup d’IaaSs différents en incluant les publics et les privés. Les offres de cloud publique, les plus connues sont Amazon EC2 1 , VMware vCloud Suite 2 , GoGrid 3 , Microsoft Azure 4 , etc. De plus, des logiciels qui permettent de construire un cloud sur ses propres ressources ont été proposés : Openstack 5 , OpenNebula 6 , StratusLab 7 , etc. Dans la Table 2.1, nous présentons brièvement des types différents de VMs disponibles dans plusieurs clouds : Amazon EC2, OpenStack, StratusLab. Figure 2.2 – Les types de cloud computing. La combinaison entre deux ou plus types différents de cloud (privé, communautaine ou public) s’appelle hybride, [37]. La Figure 2.2 donne une explication synthétique, des différents types de cloud, [33]. Un cloud hybride n’est qu’un ensemble de clouds séparés par contre il garantit l’unité étroite, le standard commun, la correspondance de la technologie, la flexibilité d’applications entre le cloud privé et le cloud public. De plus, il limite les inconvénients du cloud privé et public en tirant parti des points forts du cloud privé et public en concernant : la sécurité, le stockage de données, le coût, la QoS, etc. En d’autres mots, le cloud privé peut facilement renforcer sa performance grâce au cloud public quand il en a besoin en prenant en compte le coût des ressources provenant d’un ou plusieurs clouds public. Grâce à cela, le cloud privé économise le coût d’acheter du matériel, le temps pour étendre le système, etc. Aujourd’hui, il existe beaucoup des logiciels facilitant cette hybridation : VMware vCloud Hybrid, etc. 1. 2. 3. 4. 5. 6. 7. http http http http http http http ://aws.amazon.com/fr/ec2/ ://www.vmware.com/products/datacenter-virtualization/vcloud-suite/overview.html ://www.gogrid.com ://www.windowsazure.com ://www.openstack.org/ ://opennebula.org/start ://stratuslab.eu/ 11 DAO Van Toan, Promotion 16, Réseaux et Systèmes Communicants, IFI. 2.2 LE WORKFLOW SCIENTIFIQUE Le concept du workflow est originaire du commerce pour faire l’organisation et la gestion commerciale, selon le WFMC (est signe de "workflow management coalition") a défini un workflow comme : "l’automatisation d’un processus, en totalité ou en partie, au cours laquelle des documents, des informations ou des tâches sont transmises d’un participant à l’autre pour l’action, selon un ensemble de règles de procédure", [30][33][42]. Maintenant, on l’utilise dans le domain scientifique. Il existe beaucoup d’applications scientifiques qui utilisent le workflow : Montage, Ligo [13][31][39]. Le workflow (flux de travail en français) est une façon de réorganiser, de gérer et d’exécuter automatiquement des tâches compliquées ou des grands calculs dans un système comme le cloud computing par un ensemble d’étapes. La notation workflow scientifique dans mon étude parle de l’utilisation d’un workflow pour l’application ou le calcul scientifique. Un workflow scientifique est un modèle qui contient des tâches, des éléments de données, des contraints entre des tâches, des séquences de contrôle. On utilise un graphe orienté acyclique (directed acyclic graph - DAG) pour représenter un workflow scientifique, qui est composé d’un ensemble de sommets V et d’un ensemble d’arcs E avec E ⊆ VxV alors on a G = (V, E). Les sommets représentent les tâches calculs et les arcs représentent des dépendances de données et des contrôles entre les sommets correspondants comme : le poids d’arc, la dépendance hiérarchique parentenfant ou la flèche ou l’ordre d’exécution, [13][39]. Le coût de communication entre deux noeuds est déterminé par le poids (une valeur ou un ensemble de valeurs différentes) de l’arc. Le coût de calcul de la tâche est déterminé par le poids du sommet. Chaque DAG a seulement un sommet entré et un sommet sorti. D’après [20], on a une classification du workflow selon son architecture comme : séquentiel, paralléle ou conditionnel. Selon [39], il y a 5 structures simples du workflow, il contient : le processus, le pipeline, la distribution de données, l’agrégation de données, la redistribution de données dans la Figure 2.3. Grâce à ces structures, on facilite de construire un grand workflow compliqué. Figure 2.3 – Des structures simples du workflow. 12 DAO Van Toan, Promotion 16, Réseaux et Systèmes Communicants, IFI. Dans le workflow, le type de communication entre des tâches le plus utilisé se fait via des fichiers. Le fichier sorti de la tâche précédente est le fichier entré de la tâche suivante. Les fichiers sont stockés dans un système de fichiers partagés (NFS, GlusterFS, cluster storage, pvfs, etc) ou transférer d’un noeud à une autre, [14]. En effet, on a un seul fichier entré, un seul fichier sorti et beaucoup de fichiers intermédiaires qui sont créés par les noeuds intermédiaires du workflow. On a une illustration d’un workflow simple dans la Figure 2.4 avec deux fichiers entré et sorti : f1in, f7out et des fichiers intermédiaires : f1out, f2out, f3out, f4out, f5out, f6out. Chaque sommet a une valeur wi avec i=1, 7 qui représente son coût en MIPs 1 , chaque arc représente une relation entre deux sommets ainsi que les données à transférer de l’un vers l’autre. Par l’utilisation du DAG, quand une tâche finit son travail alors il envoie sa sortie à son enfant, dans ce moment-là, son enfant peut commencer son travail avec la donnée sortie comme une entrée. Si un noeud parent n’a pas encore fini son travail alors un noeud enfant ne peut pas commencer jusqu’à ce qu’il reçoive les données d’entrée. Dans le cloud computing, un DAG correspond à un ensemble de machines virtuels et leurs liaisions qui sont des tâches d’un job entrée et transmettent des données correspondants entre eux. Figure 2.4 – Un workflow simple par DAG. Le cloud computing peut exécuter plusieurs DAGs différents en paralléle, on appelle cela multi-DAGs, [19][38]. [17] présente des stratégies pour changer un multi-DAGs en un DAG. Le problème d’ordonnancement est une partie ou une module du Workflow Engine(s), [36][42] qui permet l’exécuter de workflows sur une plate-forme. 1. http ://en.wikipedia.org/wiki/Instructions_per_second 13 DAO Van Toan, Promotion 16, Réseaux et Systèmes Communicants, IFI. LE DÉCOUPAGE DES TÂCHES DANS LE WORKFLOW Comme dit précédemment les tâches d’un workflow sont interdépendantes concernant les données, l’ordre d’exécution, les contraintes. Afin de faciliter son ordonnancement la première étape consiste à découper les tâches (le découpage permet de minimiser le déplacement des données entre des tâches). Le but est de minimiser l’utilisation des ressources et le budget alloué des ressources, par exemple : un workflow a 400 Go de données alors on choisit 3 x m1.small plutôt que 1 x m1.xlarge parce qu’on considère le budget alloué et l’utilisation des ressources dans l’environnement présenté dans la Table 2.1. Comme plusieurs tâches et/ou workflows demandent des ressources, il n’est pas optimal de réserver toutes les ressources pour exécuter toutes les tâches en même temps car ce problème va entraîner du gaspillage de temps, d’argent, etc. Le découpage va permettre de créer des sous-graphes ou sous-workflows qui correspondent aux ressources d’exécution, s’appelle un groupe ou un cluster. Figure 2.5 – Des types de découpage des tâches dans le workflow. Plusieurs méthodes existent pour découper un workflow en sous-workflows. La Figure 2.4 montre 3 approches : level-based/cut-horizon [10], label-based [10], triplet [6] ; "minimum k-way cut" [25], décomposition en composantes fortement connexes ; le hasard, etc. 14