On the Efficiency of Several VM Provisioning Strategies for Workflows with Multi-threaded Tasks on Clouds

Cloud computing promises the delivery of on-demand pay-per-use access to unlimited resources. Using these resources requires more than a simple access to them as most clients have certain constraints in terms of cost and time that need to be fulfilled. Therefore certain scheduling heuristics have been devised to optimize the placement of client tasks on allocated virtual machines. The applications can be roughly divided in two categories: independent bag-of-tasks and workflows. In this paper we focus ourselves on the latter and investigate a less studied problem, i.e., the effect the virtual machine allocation policy has on the scheduling outcome. For this we look at how workflow structure, execution time, virtual machine instance type affect the efficiency of the provisioning method when cost and makespan are considered. To aid our study we devised a mathematical model for cost and makespan in case single or multiple instance types are used. While the model allows us to determine the boundaries for two of our extreme methods, the complexity of workflow applications requires a more experimental approach to determine the general relation. For this we considered simulations of real application workflows and synthetic ones, covering most of the possible cases. Results have shown the need for probabilistic selection methods in case small and heterogeneous execution times are used, while for large homogeneous ones the best algorithm is clearly noticed. Several other conclusions regarding the efficiency of powerful instance types as compared to weaker ones, and of dynamic methods against static ones are also made.Le cloud computing ouvre la perspective de ressources illimitées sur la base d'un paiement à l'utilisation. L'utilisation de ces ressources exige cependant plus que les primitives de base de gestion des machines virtuelles proposées à l'utilisateur, car elles ne prennent pas en compte les contraintes de coût et de temps d'exécution. Par conséquent, des heuristiques d'ordonnancement doivent être proposées pour optimiser le placement des tâches des clients sur les machines virtuelles allouées. Les applications peuvent être divisées en deux catégories principales~: celles composées de tâches indépendantes et les workflows. Dans cet article nous nous focalisons sur les workflows, et nous nous concentrons sur le problème assez peu étudié de l'effet de la politique d'allocation des machines virtuelles sur l'ordonnancement. Pour cela, nous examinons comment la structure, le temps d'exécution, et le type d'instance de machine virtuelle influencent l'efficacité de la méthode d'allocation et d'ordonnancement. L'étude s'appuye sur un modèle mathématique modélisant le coût et le temps de fin dans le cas ou on utilise un seul type d'instance, ou différent types d'instance de machines virtuelles. Bien que le modèle permette de déterminer des bornes pour deux des méthodes extrêmes, la complexité des workflows nécessite une approche expérimentale basée sur des cas variés pour déterminer une relation générale entre les paramètres. Les résultats montrent la nécessité de méthodes probabilistes de sélection dans le cas où les temps d'exécution des tâches sont courts et hétérogènes, tandis que pour des temps d'exécution homogènes le meilleur algorithme est clairement identifié. Plusieurs autres conclusions sont également tirées concernant l'efficacité de l'utilisation de types d'instance plus ou moins puissantes, ou de l'emploi de méthodes statiques ou au contraire dynamiques