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