Algorithmes d’ordonnancement avec contrainte de budget pour l’exécution de workflows scientifiques sur plates-formes de type IaaS cloud

This report introduces several budget-aware algorithms to deploy scientific workflows on IaaS cloud platforms, where users can requestVirtual Machines (VMs) of different types, each with specific cost and speed parameters. We use a realistic application/platform model with stochastic task weights, and VMs communicating through a datacenter. We extend two well-knownalgorithms, HEFT and \MinMin, and make scheduling decisions based upon machine availability and available budget. During the mapping process, the budget-aware algorithms make conservative assumptions to avoid exceeding the initial budget; we further improve our results with refined versions that aim at re-scheduling some tasks onto faster VMs, thereby spending any budget fraction leftover by the first allocation. These refined variants are much more time-consuming than the former algorithms, so there is a trade-off to find in terms of scalability. We report an extensive set of simulations with workflows from the Pegasus benchmark suite. Budget-aware algorithms generally succeed in achieving efficient makespans while enforcing the given budget, and despite the uncertainty in task weights.Ce rapport présente plusieurs algorithmes prenant en compte le budget pour déployer des workflows scientifiques sur des plateformes de Cloud de type IaaS, sur lesquelles les utilisateurs peuvent utiliser des machines virtuelles (ou Virtual Machines , VMs) de différentstypes, ces dernières étant caractérisées par un coût et une vitesse qui leur sont propres. Nous utilisons un modèle de plateforme et de workflow réalistes avec des tâches de taille stochastique et des VMs communiquant par le biais d’un datacenter. Nous étendons deux algorithmesconnus, HEFT et Min-Min, et effectuons l’ordonnancement en nous basant à la fois sur la disponibilité des machines et le budget disponible. Pendant le processus d’attribution des VMs aux tâches, les algorithmes prenant le budget en compte se basent sur des hypothèsesconservatives afin d’éviter de dépasser le budget initial ; nous améliorons nos résultats en proposant des algorithmes raffinant ces solutions en tentant de ré-assigner certaines taches à des VMs plus rapides, en utilisant pour ce faire la part de budget restant suite à l’ordonnancement initial. Ces versions raffinées demandent plus de temps que les algorithmes proposés plus tôt,il y a donc un compromis à faire en termes de scalabilité. Nous présentons un vaste ensemble de simulations effectuées sur des workflows obtenus à l’aide d’un logiciel de benchmark de Pegasus. Les algorithmes prenant en compte le budget réussissent en général à obtenir desmakespans efficaces tout en respectant le budget accordé, et ce malgré l’incertitude concernant la taille des tâche