Budget Constrained Resource Allocation for Non-Deterministic Workflows on a IaaS Cloud

Eddy Caron; Frédéric Desprez; Adrian Muresan; Frédéric Suter

hal-00697032, version 2

Budget Constrained Resource Allocation for Non-Deterministic Workflows on a IaaS Cloud

Eddy Caron (, )^a^, 1, 2, Frédéric Desprez ()^b^, 1, 2, Adrian Muresan ( Auteur à contacter de préférence , ) ^1, 2, Frédéric Suter (, )^c^, 2, 3

N° RR-7962 (2012)

Résumé : Many scientific applications are described through workflow structures. Due to the increasing level of parallelism offered by modern computing infrastructures, workflow applications now have to be composed not only of sequential programs, but also of parallel ones. Cloud platforms bring on-demand resource provisioning and pay-as-you-go payment charging. Then the execution of a workflow corresponds to a certain budget. The current work addresses the problem of resource allocation for non-deterministic workflows under budget constraints. We present a way of transforming the initial problem into sub-problems that have been studied before. We propose two new allocation algorithms that are capable of determining resource allocations under budget constraints and we present ways of using them to address the problem at hand.

a – Ecole Normale Supérieure de Lyon - ENS Lyon
b – INRIA
c – CNRS
1 : Laboratoire de l'Informatique du Parallélisme (LIP)
Université de Lyon – CNRS : UMR5668 – INRIA – École Normale Supérieure - Lyon – Université Claude Bernard - Lyon I
2 : AVALON (LIP Lyon / Inria Grenoble Rhône-Alpes)
CNRS : UMR5668 – INRIA – École Normale Supérieure - Lyon – Laboratoire d'informatique du Parallélisme – Université Claude Bernard - Lyon I
3 : Centre de Calcul de l'inst. national de phy. nucléaire et de phy. des particules (CC IN2P3)
CNRS : USR6402 – IN2P3

hal-00697032, version 2
http://hal.inria.fr/hal-00697032
oai:hal.inria.fr:hal-00697032
Contributeur : Adrian Muresan <>
Soumis le : Dimanche 20 Mai 2012, 17:05:43
Dernière modification le : Lundi 26 Novembre 2012, 15:09:09

Voir la fiche détaillée

Documents associés

PDF :

Exporter

Bibtex EndNote TEI RefWorks

%F hal-00697032, version 2
%0 Report
%U http://hal.inria.fr/hal-00697032
%2 INFO:INFO_DC
%T Budget Constrained Resource Allocation for Non-Deterministic Workflows on a IaaS Cloud
%A Caron, Eddy
%A Desprez, Frédéric
%A Muresan, Adrian
%A Suter, Frédéric
%+ Laboratoire de l'Informatique du Parallélisme - LIP , AVALON - LIP Lyon / Inria Grenoble Rhône-Alpes , Centre de Calcul de l'inst. national de phy. nucléaire et de phy. des particules - CC IN2P3
%X Many scientific applications are described through workflow structures. Due to the increasing level of parallelism offered by modern computing infrastructures, workflow applications now have to be composed not only of sequential programs, but also of parallel ones. Cloud platforms bring on-demand resource provisioning and pay-as-you-go payment charging. Then the execution of a workflow corresponds to a certain budget. The current work addresses the problem of resource allocation for non-deterministic workflows under budget constraints. We present a way of transforming the initial problem into sub-problems that have been studied before. We propose two new allocation algorithms that are capable of determining resource allocations under budget constraints and we present ways of using them to address the problem at hand.
%2 De nombreuses applications scientifiques sont décrites sous la forme de workflows. Du fait de l'accroissement du niveau de parallélisme offert par les infrastructures de calcul modernes, de telles applications doivent désormais être composées non seulement de programmes séquentiels mais aussi de programmes parallèles. Les Clouds offrent le provisionnement de ressources à la demande ainsi qu'une facturation à l'utilisation. L'exécution d'un workflow correspond alors à un certain budget. Dans cet article, nous considérons le problème de l'allocation de ressources à un workflow non déterministe en présence de contraintes de budget. Nous présentons une façon de transformer le problème initial en une série de sous-problèmes qui ont été largement étudiés. Nous proposons deux algorithmes originaux qui peuvent déterminer des allocations de ressources sous contrainte de budget. Nous détaillons également comment les utiliser pour résoudre le problème initial.
%G Anglais
%2 Rapport de recherche
%P 30
%8 2012-05-14
%K resource allocation; scheduling; PTG; workflow
%Z RR-7962

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Rapports</head>
<biblStruct type="report" xml:id="hal-00697032"><monogr>
<author><persName><forename>Eddy</forename><surname>Caron</surname></persName>
<affiliation>
<orgName type="laboratory">LIP</orgName>
<orgName type="team">Laboratoire de l'Informatique du Parallélisme</orgName>
<country>FR</country>
<orgName type="institution">Université de Lyon</orgName>
<orgName type="institution">CNRS : UMR5668</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">École Normale Supérieure - Lyon</orgName>
<orgName type="institution">Université Claude Bernard - Lyon I</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LIP Lyon / Inria Grenoble Rhône-Alpes</orgName>
<orgName type="team">AVALON</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5668</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">École Normale Supérieure - Lyon</orgName>
<orgName type="institution">Laboratoire d'informatique du Parallélisme</orgName>
<orgName type="institution">Université Claude Bernard - Lyon I</orgName>
</affiliation>
</author>
<author><persName><forename>Frédéric</forename><surname>Desprez</surname></persName>
<affiliation>
<orgName type="laboratory">LIP</orgName>
<orgName type="team">Laboratoire de l'Informatique du Parallélisme</orgName>
<country>FR</country>
<orgName type="institution">Université de Lyon</orgName>
<orgName type="institution">CNRS : UMR5668</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">École Normale Supérieure - Lyon</orgName>
<orgName type="institution">Université Claude Bernard - Lyon I</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LIP Lyon / Inria Grenoble Rhône-Alpes</orgName>
<orgName type="team">AVALON</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5668</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">École Normale Supérieure - Lyon</orgName>
<orgName type="institution">Laboratoire d'informatique du Parallélisme</orgName>
<orgName type="institution">Université Claude Bernard - Lyon I</orgName>
</affiliation>
</author>
<author><persName><forename>Adrian</forename><surname>Muresan</surname></persName>
<affiliation>
<orgName type="laboratory">LIP</orgName>
<orgName type="team">Laboratoire de l'Informatique du Parallélisme</orgName>
<country>FR</country>
<orgName type="institution">Université de Lyon</orgName>
<orgName type="institution">CNRS : UMR5668</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">École Normale Supérieure - Lyon</orgName>
<orgName type="institution">Université Claude Bernard - Lyon I</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LIP Lyon / Inria Grenoble Rhône-Alpes</orgName>
<orgName type="team">AVALON</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5668</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">École Normale Supérieure - Lyon</orgName>
<orgName type="institution">Laboratoire d'informatique du Parallélisme</orgName>
<orgName type="institution">Université Claude Bernard - Lyon I</orgName>
</affiliation>
</author>
<author><persName><forename>Frédéric</forename><surname>Suter</surname></persName>
<affiliation>
<orgName type="laboratory">LIP Lyon / Inria Grenoble Rhône-Alpes</orgName>
<orgName type="team">AVALON</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5668</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">École Normale Supérieure - Lyon</orgName>
<orgName type="institution">Laboratoire d'informatique du Parallélisme</orgName>
<orgName type="institution">Université Claude Bernard - Lyon I</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">CC IN2P3</orgName>
<orgName type="team">Centre de Calcul de l'inst. national de phy. nucléaire et de phy. des particules</orgName>
<country>FR</country>
<orgName type="institution">CNRS : USR6402</orgName>
<orgName type="institution">IN2P3</orgName>
</affiliation>
</author>
<title type="main" level="m">Budget Constrained Resource Allocation for Non-Deterministic Workflows on a IaaS Cloud</title><title type="main" level="m">Budget Constrained Resource Allocation for Non-Deterministic Workflows on a IaaS Cloud</title><imprint><biblScope type="publicationDate">2012-05-14</biblScope><biblScope type="pp">30</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/hal-00697032</idno><idno type="HALFile">http://hal.inria.fr/hal-00697032/PDF/RR-7962.pdf</idno></biblStruct>
</listBibl>
</listBibl>