Yves Caniou

Eddy Caron

Aurélie Kong

Win Chang

Yves Robert

Budget-aware scheduling algorithms for scientific workflows with stochastic task weights on heterogeneous IaaS Cloud platforms

This paper introduces several budget-aware algorithms to deploy scientific workflows on IaaS Cloud platforms, where users can request Virtual 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 wellknown algorithms, MIN-MIN and HEFT, 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. Most of the time our budget-aware algorithms succeed in achieving efficient makespans while enforcing the given budget, despite (i) the uncertainty in task weights and (ii) the heterogeneity of VMs in both cost and speed values.

I. INTRODUCTION

IaaS (Infrastructure as a Service) Cloud platforms provide a convenient service to many users. Many vendors provide commercial offers with various characteristics and price policies. In particular, a large choice of VM (Virtual Machine) types is usually provided, that ranges from slow-but-cheap to powerfulto-expensive devices. When deploying a scientific workflow on an IaaS Cloud, the user is faced with a difficult decision: which VM type to select for which task? How many VMs to rent? The heterogeneity of VMs applies to both cost and speed values, and these values are not necessarily proportional. The mapping decisions clearly depend upon the budget allocated to execute the workflow, and are best taken when some knowledge on the task profiles in the workflow is available. The standard practice is to run a classical scheduling algorithm, whether MIN-MIN [START_REF] Braun | A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems[END_REF], [START_REF] Ezzatti | An efficient implementation of the min-min heuristic[END_REF] or HEFT [START_REF] Topcuoglu | Performance-effective and lowcomplexity task scheduling for heterogeneous computing[END_REF], with a VM type selected arbitrarily, and to hope for the best, i.e., that the budget will not be exceeded at the end. To remedy such an inefficient approach, this paper introduces several budget-aware algorithms to deploy scientific workflows on IaaS Clouds. The main idea is to revisit well-known algorithms such as MIN-MIN and HEFT and to make a decision for each task to be scheduled based upon both machine availability and remaining budget.

While several cost-aware algorithms have been introduced in the literature (see Section II for an overview), this paper makes new contributions along the following lines:

• A realistic application model, with stochastic task weights;

• A detailed yet tractable platform model, with a datacenter and multiple VM categories;

• Budget-aware algorithms that extend MIN-MIN and HEFT, two widely-used list-scheduling algorithms for heterogeneous platforms;

• Refined (but more costly) variants that squeeze the most of any leftover budget to further decrease total execution time. The refined versions aim at exploiting the opportunity to re-schedule 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.

The rest of the paper is organized as follows. Section II surveys related work. We introduce the performance model in Section III. We describe budget-aware scheduling algorithms in Section IV: Section IV-A presents the extensions to MIN-MIN and HEFT, while Section IV-B provides the refined versions. Section V is devoted to assessing their performance through extensive simulations, including comparisons of two previous budget-aware algorithms, namely BDT [START_REF] Arabnejad | Budget distribution strategies for scientific workflow scheduling in commercial clouds[END_REF] and CG/CG+ [START_REF] Wu | End-to-end delay minimization for scientific workflows in clouds under budget constraint[END_REF]. Finally, we provide concluding remarks and directions for future work in Section VI.

II. RELATED WORK

Many scientific applications from various disciplines are structured as workflows [START_REF] Bharathi | Characterization of scientific workflows[END_REF]. Informally, a workflow can be seen as the composition of a set of basic operations that have to be performed on a given input data set to produce the expected scientific result. The development of complex middleware with workflow engines [START_REF] Couvares | Workflow Management in Condor[END_REF], [START_REF] Deelman | Pegasus: a Framework for Mapping Complex Scientific Workflows onto Distributed Systems[END_REF], [START_REF] Caron | Workflow-based comparison of two distributed computing infrastructures[END_REF] has automated workflow management. IaaS Clouds raised a lot of interest recently, thanks to an elastic resource allocation and pay-asyou-go billing model. In a Cloud environment, there exist many solutions for scheduling workflows [START_REF] Lin | Scheduling scientific workflows elastically for cloud computing[END_REF], [START_REF] Smanchat | Taxonomies of workflow scheduling problem and techniques in the cloud[END_REF], some of which include data management strategies [START_REF] Yuan | A data placement strategy in scientific cloud workflows[END_REF]. Also [START_REF] Mao | Scaling and scheduling to maximize application performance within budget constraints in cloud workflows[END_REF] introduced two auto-scaling mechanisms to solve the resource allocation problem for unpredicted workflow jobs in a cost-efficient way. [START_REF] Zeng | SABA: A security-aware and budgetaware workflow scheduling strategy in clouds[END_REF] introduced a workflow scheduling in Clouds solutions with security and cost considerations. [START_REF] Alkhanak | Cost optimization approaches for scientific workflow scheduling in cloud and grid computing: A review, classifications, and open issues[END_REF] provides guidelines and analysis to understand cost optimization in scientific workflow scheduling by surveying existing approaches in Cloud computing. Although the multi-objective offline scheduling problem that consists in meeting deadlines and respecting a budget has been extensively studied for deterministic workflows ( [START_REF] Calheiros | Meeting deadlines of scientific workflows in public clouds with tasks replication[END_REF], [START_REF] Fard | A truthful dynamic workflow scheduling mechanism for commercial multicloud environments[END_REF], [START_REF] Abrishami | Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds[END_REF], for example), it has received much less attention in a stochastic context. In a provider-centered point of view, [START_REF] Ferguson | Jockey: Guaranteed job latency in data parallel clusters[END_REF] proposed a framework with the objective of meeting deadlines minimizing the impact of the execution of the workflow's execution on the cluster. In a slightly different context, e.g. with faults, preemptive tasks, from the provider point of view, [START_REF] Boutin | Apollo: Scalable and coordinated scheduling for cloud-scale computing[END_REF] targets a complicated multi-criteria objective, namely (i) minimizing each job's completion time, (ii) maximizing the global utilization of the platforl and (ii) dividing fairly the resources between all the users in a scalable manner.

To the best of our knowledge, the closest papers to this work are [START_REF] Arabnejad | Budget distribution strategies for scientific workflow scheduling in commercial clouds[END_REF], [START_REF] Wu | End-to-end delay minimization for scientific workflows in clouds under budget constraint[END_REF], which both propose workflow scheduling algorithms (BDT in [START_REF] Arabnejad | Budget distribution strategies for scientific workflow scheduling in commercial clouds[END_REF], CG/CG+ in [START_REF] Wu | End-to-end delay minimization for scientific workflows in clouds under budget constraint[END_REF]) under budget and deadline constraints, but with a simplified platform model. We extended BDT and CG/CG+ to enable a fair comparison with our algorithms, and present the corresponding results in Section V-D. Finally, [START_REF] Malawski | Algorithms for cost-and deadline-constrained provisioning for scientific workflow ensembles in iaas clouds[END_REF] also proposes workflow scheduling algorithms under budget and deadline constraints. Their platform model is similar to ours, although we allow for computation/transfer overlap and account for a startup delay t boot to boot a VM. However, their application framework and objective are different: they consider workflow ensembles, i.e., sets of workflows with priorities, that are submitted for execution simultaneously, and they aim at maximizing the number, or the cumulated priority value, of the workflows that complete successfully under the constraints. Still, we share the approach of partitioning the initial budget into chunks to be allotted to individual candidates (workflows in [START_REF] Malawski | Algorithms for cost-and deadline-constrained provisioning for scientific workflow ensembles in iaas clouds[END_REF], tasks in this paper).

Workflows n number of tasks in the workflow T i

The i th task of the workflow III. MODEL This section details the application and platform model used to assess the performance of the scheduling algorithms. Table I summarizes the main notations used in this paper.

w i , σ i weight of T i : mean, standard deviation size(d T i ,T j ) amount of data from T i to T j Platform k number of VM categories s 1 ≤ s 2 • • • ≤ s k VMs speeds s average speed c h,k , c ini,

A. Workflows

The model of workflows presented here is directly inspired by [START_REF] Juve | Characterizing and profiling scientific workflows[END_REF], [START_REF] Malawski | Algorithms for cost-and deadline-constrained provisioning for scientific workflow ensembles in iaas clouds[END_REF]. A task workflow is represented with a DAG (Directed Acyclic Graph) G = (V, E), where V is the set of tasks to schedule, and E is the set of dependencies between tasks. In this model, a dependency corresponds to a data transfer between two tasks. Tasks are not preemptive and must be executed on a single processor 1 . Most workflow scheduling algorithms use as starting assumption that the exact number of instructions constituting a task is known in advance, so that its execution time is given accurately. However, this hypothesis is not always realistic. The number of instructions for a given task may strongly depend on the current input data, such as in image processing kernels. In our model, we only know an estimation of the number of instructions for each task. For lack of knowledge about the origin of time variations, we assume that all the parameters which determine the number of instructions forming a task are independent. This resulting number is the task weight and follows a Gaussian law with mean w i and standard deviation σ i which can be estimated (for example by sampling).

To each dependency (T i , T j ) ∈ E is associated an amount of data of size size(d Ti,Tj ). We say that a task T is ready if either it does not have any predecessor in the dependency graph, or if all its predecessors have been executed and all the output data generated.

B. Platform

Our model of Cloud platform mainly consists of a datacenter and processing units. It is based to a great extent on the offers of three Cloud providers: Google Cloud2 , Amazon EC23 and OVH 4 . Given that Cloud providers propose a fault-tolerance service which ensures a very high availability of resources (in general over 99.97% 5 ) as well as sufficient data redundancy, the datacenter and processing units are considered reliable and not subject to faults.

There is only one datacenter, used by all processing units. It is the common crossing point for all the data exchanges between processing units: these units do not interact directly, because of security issues for example. When a task T is to be executed on a VM v, all input data of T generated by one predecessor T must be accessed from the datacenter, unless that this data has been produced on the same VM v (meaning that T had been scheduled on v too). The datacenter is also where the final generated data are stored before being transferred to the user. For simplicity, we consider that the datacenter bandwidth is large enough to feed all processing units, and to accommodate all submitted requests simultaneously, without any supplementary cost.

The processing units are VMs (Virtual Machines). They can be classified in different categories characterized by a set of parameters fixed by the provider. Some providers offer parameters of their own, such as the number of forwarding rules 6 . We only retain parameters common to the three providers Google, Amazon and OVH: A VM of category k has n k processors, one processor being able to process one task at a time; A VM has also a speed s k corresponding to the number of instructions it can process per time unit, a cost per time-unit c h,k and an initial cost c ini,k ; All these VMs take an initial, and uncharged, amount of time t boot to boot before being ready to process tasks. Already integrated in the schedule computing process, this starting time is thus not counted in the cost related to the use of the VM, which is presented in Section III-C. Without loss of generality, categories are sorted according to hourly costs, so that c h,1 ≤ c h,2 • • • ≤ c h,n k . We expect speeds to follow the same order, but do not make such an assumption.

The platform thus consists of a set of n VMs of k possible categories. Some simplifying assumptions make the model tractable while staying realistic: (i) We assume that the bandwidth is the same for every VM, in both directions, and does not change throughout execution; (ii) A VM is able to store enough data for the tasks assigned to it: in other words, a VM will not have any memory/space overflow problem, so that every increase of the total makespan will be because of the stochastic aspect of the task weights; (iii) Initialization time is the same for every VM; (iv) Data transfers take place independently of computations, hence do not have any impact on processor speeds to execute tasks.

We chose an "on-demand" provisioning system: it is possible to deploy a new VM during the workflow execution if needed. Hence VMs may have different start-up times. A VM v is started at time H start,v and does not stop until all the data created by its last computed task have been transferred to the datacenter, at time H end,v . VMs are allocated by continuous slots. If one wants discontinuous allocations, one may free the VM, then use a new one later, which at least requires sending all the data generated by the last processed task to the datacenter, and reloading all input data of the first task scheduled on that new VM before execution.

C. Workflow execution, cost and objective

Tasks are mapped to VMs and locally executed in the order given by the scheduling algorithm, such as those described in Section IV. Given a VM v, a task is launched as soon as (i) the VM is idle; (ii) all its predecessor tasks have been executed, and (iii) the output files of those predecessors mapped onto other VMs have been transferred to v via the datacenter.

a) Cost: The cost model is meant to represent generic features out of the existing offers from Cloud providers (Google, Amazon, OVH). The total cost of the whole workflow execution is the sum of the costs due to the use of the VMs and of the cost due to the use of the datacenter C DC . The cost C v of the use of a VM v of category k v is calculated as follows:

C v = (H end,v -H start,v ) × c h,kv + c ini,kv (1)
There is a start-up cost c ini,kv in Equation ( 1), and a term c h,kv proportional to usage duration H end,v -H start,v . The cost for the datacenter is based on a cost per time-unit c h,DC , to which we add a transfer cost. This transfer cost is computed with the amount of data transferred from the external world to the datacenter (size(d in,DC )), and from the datacenter to the outside world (size(d DC,out )). In other words, d in,DC corresponds to data that are input to entry tasks in the workflow, and d DC,out to data that are output from exit tasks. Letting H start,f irst be the moment when we book the first VM and H end,last be the moment when the data of the last processed task have entirely been sent to the datacenter, we have:

C DC = (size(d in,DC ) + size(d DC,out )) × c tsf +(H end,last -H start,f irst ) × c h,DC (2)
Altogether, the total cost is

C wf = v∈R V M C v +C DC ,
where R V M is the set of booked VMs during the execution. b) Objective: Given a deadline D and a budget B, the objective is to fulfil the deadline while respecting the budget:

D ≥ H end,last -H start,f irst and B ≥ C wf (3)
A more complicated objective would be to find the schedule that minimizes the makespan while respecting the budget, namely min(H end,last -H start,f irst ) where B ≥ C wf .

IV. SCHEDULING ALGORITHMS

This section introduces MIN-MINBUDG and HEFTBUDG, the budget-aware extensions to MIN-MIN [START_REF] Braun | A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems[END_REF], [START_REF] Ezzatti | An efficient implementation of the min-min heuristic[END_REF] and HEFT [START_REF] Topcuoglu | Performance-effective and lowcomplexity task scheduling for heterogeneous computing[END_REF], two reference scheduling algorithms widely used by the community. Section IV-A details the main algorithms, which assign a fraction of the remaining budget to the current task to be scheduled, while aiming at minimizing its completion time. Then Section IV-B provides refined versions of HEFTBUDG that squeeze the most of any leftover budget to re-map some tasks to more efficient VMs. This leads to an improvement in the makespan, at the price of a much larger CPU time of the scheduling algorithms. We did not consider the corresponding refinement of MIN-MINBUDG because HEFTBUDG turned out to be more efficient than MIN-MINBUDG in our simulations, always achieving a smaller makespan for the same budget.

A. MIN-MINBUDG and HEFTBUDG

The budget-aware extensions of MIN-MIN and HEFT need to account both for the task stochasticity and budget constraint, while aiming at makespan minimization. Coping with task stochasticity is achieved by adding a certain quantity to the average task weight so that the risk of under-estimating its execution time is reasonably low, while retaining an accurate value for most executions. We use a conservative value for the weight of a task T , namely w T + σ T .

As for the budget, given a workflow wf , we first reserve a fraction to cover the cost of the datacenter and VM initializations; we divide what remains into the workflow tasks. Let B ini denote the initial budget. To estimate the amount to be reserved:

• For the cost of the datacenter, we need to estimate the duration H end,last -H start,f irst of the whole execution (see Equation ( 2)). To this purpose, we consider an execution on a Algorithm 1 Dividing the budget into tasks. W max ← getMaxTotalWork(wf ) 3:

d max ← getMaxTotalTransfData (wf ) 4:
for each T of wf do

5: budgP T sk[T ] ← B T ← B calc × w T +σ T s + size(d pred,T ) bw Wmax s + dmax bw 6:
end for 7:

return budgP T sk 8: end function single VM of the first (cheapest) category, compute the total duration W max = T ∈wf (w T + σ T ) and let

H end,last -H start,f irst = Wmax s1 + size(d in,DC )+size(d DC,out ) bw (4)
Altogether, we pay the cost of input/output data several times: with factor c tsf for the outside world, with factor c h,DC for the usage of the datacenter (Equation ( 4)), and with factor c h,1 during the transfer of data to and from the unique VM. However, there is no communication internal to the workflow, since we use a single VM.

• For the initialization of the VMs, we assume a different VM of the first category per task, hence we budget the amount n × c ini,1 .

Combining these two choices is conservative: on the one hand, we consider a sequential execution, but account only for input and output data with the external world, eliminating all internal transfers during the execution; on the other hand, we reserve as many VMs as tasks, ready to pay the price for parallelism, at the risk of spending time and money due to data transfers during the execution. Altogether, we reserve the corresponding amount of budget and are left with B calc for the tasks.

This reduced budget B calc is shared among tasks in a proportional way (see Algorithm 1): we estimate how much time t calc,T is required to execute each task T , transfer times included, and allocate the corresponding part B T of the budget in proportion to the whole for execution of the entire workflow t calc,wf :

B T = t calc,T t calc,wf × B calc (5)
In Equation ( 5), we use

t calc,T = w T + σ T s + size(d pred,T ) bw , where size(d pred,T ) = (T ,T )∈E size(d T ,T ) (6)
is the volume of input data of T from all its predecessors. Similarly, we use t calc,wf = Wmax s + dmax bw , where d max = (Ti,Tj )∈E size(d Ti,Tj ) is the total volume of data within the workflow. Computed weights (w T + σ T and W max ) are divided by the mean speed s of VM categories, while data sizes (size(d pred,T ) and d max ) are divided by the bandwidth bw between VMs and the datacenter. Again, it is conservative to assume that all data will be transferred, because some of them will be stored in-place inside VMs, so there is here another source of over-estimation of the cost. On the contrary, using the average speed s in the estimation of the computing time may lead to an under-estimation of the cost when cheaper/slower VMs are selected.

This subdivided budget is then used to choose the best VM to host each ready task (see Algorithm 2): the best host for a task T on platform P will be the one providing the best EFT (Earliest Finish Time) for T , among those respecting the amount of budget B T allocated to T . The platform P is defined as the set of host candidates, which consists of already used VMs plus one fresh VM of each category. For each host candidate host, either already used (set Used VM ) or new candidate (set New VM ), we first evaluate the time t Exec,T,host needed to have T executed (i.e., transfer of input data and computations) on host:

t Exec,T,host = δ new × t boot + w T + σ task s k host + size(d in,T ) bw (7)
In Equation ( 7), we introduce the boolean δ new whose value is 1 if host ∈ New VM to account for its startup delay, and 0 otherwise. Also, some input data may already be present if host ∈ Used VM , thus we use size(d in,T ) instead of size(d pred,T ) (see Equation ( 6)), defining d in,T as those input data not already present on host.

To compute EF T T,host , the Earliest Finish Time of task T on host host, we account for its Earliest Begin Time t begin,host and add t Exec,T,host . Then t begin,host is simply the maximum of the following quantities: (i) availability of host; (ii) end of transfer to the datacenter of any input data of T . The latter includes all data produced by a predecessor of T executed on another host; these data have to be sent to the datacenter before being re-emitted to host, since VMs do not communicate directly. There is a cost associated to these transfers, which we add to t Exec,T,host × c h,host to compute the total cost c T,host incurred to execute T on host. We do not write down the equation defining t begin,host , as it is quite similar to previous ones. Since we already subtracted from the initial budget everything except the cost of the use of the VMs themselves, getBestHost() can safely use B T as the upper bound for the budget reserved for task T .

The algorithm reclaims any unused fraction of the budget consumed when assigning former tasks: this is the role of the variable pot, which records any leftover budget in previous assignments. Finally, MIN-MINBUDG (Algorithm 3) and HEFTBUDG (Algorithm 4) are the counterpart of the original MIN-MIN and HEFT algorithms, extended with the provisioning for the budget. For some tasks, getBestHost() will not return the host with the smallest ETF, but instead the host with the smallest ETF among those that respect the allotted budget. The complexity of MIN-MINBUDG and HEFTBUDG is O(n + e)p, where n is the number of tasks, e is the number of dependence edges, and p the number of enrolled VMs. This complexity is the same as for the baseline versions, except that p is not fixed a priori. In the worst case, p = O(max(n, k)) because for each task we try all used VMs, whose count is possibly O(n), and k new ones, one per category.

Algorithm 2 Choosing the best host for each ready task. for each host of (Used VM ∪ New VM ) do return LISTT, sched 15: end function design of the algorithm, it is very likely that not all the initial budget B ini will be spent by HEFTBUDG. In order to refine the solution returned from HEFTBUDG, we re-consider each decision taken and try to improve it. HEFTBUDG (just as HEFT) assigns priorities to the tasks based upon their bottom level [START_REF] Topcuoglu | Performance-effective and lowcomplexity task scheduling for heterogeneous computing[END_REF]. Let LISTT be the ordered list of tasks by non-decreasing priority, and let selSched denote the schedule returned by HEFTBUDG. The first variant HEFTBUDG+ (see Algorithm 5) processes the tasks in the order of LISTT, hence in the same order as HEFT and HEFTBUDG, while HEFTBUDG+INV uses the reverse order. For both variants, let T be the task currently considered: we then generate new schedules obtained by assigning T on each already used VM except the one given by selSched, and on a new one for each category. We compute c tot and t calc,wf for each of them, and keep the one which has the shortest makespan and respects the budget.

As mentioned in Section IV-A, HEFTBUDG (just as HEFT) has a complexity O(n + e)p, where p = O(max(n, k)) in the worst case. Both HEFTBUDG+ and HEFTBUDG+INV start with a full iteration of HEFTBUDG; then, for each task, they try a new host and generate the resulting schedule. Hence their complexity is O(n(n + e)p), where p = O(max(n, k)) in the worst case. This is an order of magnitude more CPU demanding than HEFTBUDG, which limits their usage to smaller-size workflows.

V. SIMULATIONS

This section provides all the simulation results. We first describe the experimental setup in Section V-A. Next in Section V-B, we assess the performance of the main algorithms MIN-MINBUDG and HEFTBUDG, using the standard MIN-MIN and HEFT heuristics as a baseline for comparison. Then in Section V-C, we proceed to the refined variants HEFTBUDG+ and HEFTBUDG+INV, and quantify their improvement in terms of makespan, as well as their additional cost in terms of CPU time. Finally, Section V-D is devoted to comparing our algorithms with (extensions of) two formerly published competitors, namely BDT [START_REF] Arabnejad | Budget distribution strategies for scientific workflow scheduling in commercial clouds[END_REF] and CG/CG+ [START_REF] Wu | End-to-end delay minimization for scientific workflows in clouds under budget constraint[END_REF]. B calc ← getBudgCalc(wf, B ini , P) Table II: Parameters of the IAAS Cloud platform.

A. Experimental methodology

We designed a simulator based on SimDag [START_REF] Simdag | Programming environment for DAG applications[END_REF], an extension of the discrete event simulator SimGrid [START_REF] Casanova | Versatile, scalable, and accurate simulation of distributed applications and platforms[END_REF], to evaluate all algorithms. The model described in Section III is instantiated with 3 VM categories and respective costs inspired from the offers by Amazon Cloud, Google Cloud and OVH (see Table II): the cost of our VMs is based on the mean of the prices of S3 when we made our experiments, and is linear with the speed of the VM. The VM is paid for each used second.

We used three types of workflow from the Pegasus benchmark suite [START_REF]Pegasus workflow generator[END_REF], [START_REF] Deelman | Pegasus, a workflow management system for science automation[END_REF]: CYBERSHAKE, LIGO and MONTAGE. Concerning LIGO, most input data have the same (large) size, only one of them is oversized compared with the others (by a ratio over 100). LIGO consists of a lot of parallel tasks sharing a link to some agglomerative tasks, one agglomerative task per little set; this scheme repeats twice since there is a second subdivision after the first agglomeration. In CYBERSHAKE, half the tasks have huge input data. The workflow itself consists of a first set of tasks generating data in parallel, data which will be used by a directly connected task (one calculating task per generating task). These parallel activities are all linked to two different agglomerative tasks. On the contrary, MONTAGE has plenty highly inter-connected tasks, rendering parallelization less easy. The number of instructions of its different tasks is balanced, as is the size of the exchanged data. For each workflow type, we used the simulator available on the Pegasus website to generate our benchmark, with five different instances per workflow type, and different numbers of tasks: 30, 60 and 90; this leads to 5 × 3 = 15 workflows per type.

Each generated workflow is then re-used to generate workflows having the same DAG structure, but with different values for task weights: to this purpose, we keep the original weight for a task T as the mean w T and use 25, 50, 75 and 100% of that mean number for the standard deviation σ T . In the figures, each simulation was repeated 25 times and we plot mean values; vertical bars represent standard deviations. Overall, 16500 experiments have been executed per workflow type and scheduling algorithm.

Then, to further assess the efficiency of the previous algorithms, we made some comparisons with two competitors: Budget Distribution with Trickling (BDT [START_REF] Arabnejad | Budget distribution strategies for scientific workflow scheduling in commercial clouds[END_REF]) and Critical Greedy (CG [START_REF] Wu | End-to-end delay minimization for scientific workflows in clouds under budget constraint[END_REF]). Both BDT and CG schedule deterministic workflows, and CG does not take into account communication costs. In [START_REF] Wu | End-to-end delay minimization for scientific workflows in clouds under budget constraint[END_REF], CG also comes with a refined version CG+. We extended BDT and CG/CG+ to fit our model, so as to enforce fair comparisons. We propose two scenarios, first with unrefined versions (MIN-MINBUDG and HEFTBUDG against BDT and CG), and then with refined ones (HEFTBUDG+ and HEFTBUDG+INV against CG+).

B. MIN-MINBUDG and HEFTBUDG

In this section, we report and compare results for MIN-MINBUDG and HEFTBUDG against those for the baseline algorithms MIN-MIN and HEFT. Due to lack of space, we report only results for 90 tasks. Results for 30 and 60 tasks are available in the extended version [START_REF] Caniou | Budgetaware scheduling algorithms for scientific workflows with stochastic task weights on IaaS cloud platform[END_REF]. Figure 1 has three rows, one per workflow type, and reports the results as a function of the initial budget: makespan in first column, total cost in second column, and number of VMs in third column. We record the number of used VMs as an indicator of some choices made by the budget-aware algorithms that trade-off increased usage of former VMs vs. enrolment of new ones. In the first column, the green dot labeled min_cost represents the mean of the cheapest solutions for the corresponding schedule, and is obtained by allocating all tasks to the same cheapest host.

The budget constraint is respected in almost all cases (see Figures 1b, 1e and1h; the black line draws the affine function of the initial budget). Exceptions are some instances of LIGO with a budget near the minimum needed to schedule all the tasks. The explanation is the following: we assumed that the bandwidth of the datacenter would be sufficient for all simultaneous transfers, but we observed that it became a bottleneck in that case. LIGO has a lot of parallel tasks running concurrently, that may well send huge data at the same time. In those very few cases, we underestimated the time needed to send these data.

Clearly, when given an infinite initial budget, MIN-MIN and HEFT give the same schedule as MIN-MINBUDG and HEFTBUDG respectively. We see that MIN-MIN and HEFT obtain similar makespans, but HEFT uses more VMs than MIN-MIN: for instance there is an average of 79 VMs for HEFT vs. 33 for MIN-MIN for CYBERSHAKE, 90 vs. 22 for LIGO and 90 vs. 56 for MONTAGE. The cost is thus smaller for more parallel workflows (LIGO), and larger for the other ones (CYBERSHAKE, MONTAGE).

We now discus the initial budget needed by the budget-aware algorithms to achieve the minimal makespan returned by the baseline version. HEFTBUDG needs a smaller initial budget than MIN-MINBUDG for MONTAGE (see Figure 1g), and a similar one for CYBERSHAKE and LIGO (see Figures 1a and1d). We refine this analysis in the extended version [START_REF] Caniou | Budgetaware scheduling algorithms for scientific workflows with stochastic task weights on IaaS cloud platform[END_REF]: the dif-ference in minimal budgets decreases sharply with the number of tasks for CYBERSHAKE and LIGO. This is due to the graph structure of these workflows: for CYBERSHAKE, increasing the number of tasks leads to workflows with a majority of parallel tasks; for LIGO, it leads to an increasing number of independent short workflows. In both cases, increasing the number of tasks renders the workflow closer to a Bag of Tasks, and the priority mechanism of HEFTBUDG becomes less useful. On the contrary, larger MONTAGE workflows keep numerous imbricated dependencies between tasks, and HEFTBUDG remains more efficient in terms of budget.

Regarding the behavior of our algorithms, increasing initial budget will lead to enrolling more VMs with an exception: in Figure 1i, we see that the number of VMs can rise for intermediate values of budgets until exceeding that of the baseline version, then decrease again. This corresponds to the moment when several tasks have enough budget to leave their mid- We have also assessed the impact of the amount of uncertainty in task weights, but because of space limitations, we refer to the extended version [START_REF] Caniou | Budgetaware scheduling algorithms for scientific workflows with stochastic task weights on IaaS cloud platform[END_REF]. Both HEFTBUDG and MIN-MINBUDG require a larger initial budget to achieve a given makespan, when σ increases; yet the budget constraint is respected, even in scenarios where task weights can be twice their mean value.

Finally we discuss the execution time of each algorithm. The experiments have been conducted on a computer with a Intel R Core TM i5-6200U CPU @ 2.30GHz × 4 processors. We recorded the time needed for each algorithm while calculating 5 continuous schedules, and executed 30 instances for each combination of parameters. We used three types of workflows (CYBERSHAKE, LIGO and MONTAGE) instantiated with 30, 60 and 90 tasks. As for the impact of the budget on the time needed to calculate a schedule, we used three characteristic values for each workflow, which we designate as "low", "high" and "medium". A "low" budget B min corresponds to the minimum budget needed to find a schedule, a "high" one to a budget large enough to enroll an unlimited number of VMs. The "medium" budget is chosen as follows: for each workflow, we empirically find the minimum budget B min best needed to obtain a makespan as good as the one found for baseline version of the algorithm, and take the average:

B med = Bmin best +Bmin 2
Table III shows CPU times needed to calculate a schedule for workflows of varying type and size. For example, for a MONTAGE workflow of 90 tasks, HEFTBUDG needs 2.87 ± 0.52 seconds to find a schedule when it only needs 0.60 ± 0.39 seconds for a CYBERSHAKE workflow or 0.72 ± 0.40 seconds for a LIGO workflow; such differences can be seen for the other algorithms as well.

Here is a concluding remark about MIN-MINBUDG and HEFTBUDG: To cope with uncertainty in task weights, we made a pessimistic estimation of the cost of data transfers, assuming they were always produced by another VM. This was safe but led to overestimating both the time and the budget for these transfers. Also the budget assignment is somewhat unfair to the first scheduled tasks, which have no access to any leftover resource (the pot). In the next section, we aim at improving the schedule by re-examining the assignment and budget allotted to each task. We do this for HEFTBUDG only, because it typically achieves a smaller makespan than MIN-MINBUDG for a prescribed budget. Of course, similar improvements could be designed for MIN-MINBUDG.

C. HEFTBUDG+ and HEFTBUDG+INV

Figure 2 is the counterpart of Figure 1 to compare HEFTBUDG+ and HEFTBUDG+INV against HEFT and HEFTBUDG. The schedules obtained for both refined algorithms HEFTBUDG+ and HEFTBUDG+INV have a shorter makespan than HEFTBUDG (see Figure 2a, 2d and 2g). Their makespan can be up to one third shorter than for HEFTBUDG, e.g., for MONTAGE.

Surprisingly the refined algorithms manage to achieve a smaller makespan using fewer VMs than HEFTBUDG. This is mostly because they succeed in assigning interdependent tasks onto the same VM. The initial budget needed to obtain the same makespan as HEFT is the same for HEFTBUDG, HEFTBUDG+ and HEFTBUDG+INV. Moreover, the budget is respected overall, as was already the case with HEFTBUDG.

To compare HEFTBUDG+ and HEFTBUDG+INV, we observe that their makespans are very similar, apart from the case where a budget near the minimum is needed to complete a schedule: in that case, HEFTBUDG+ obtains an average makespan twice shorter than HEFTBUDG+INV. This difference seen in this exact configuration may be due to the particular structure of MONTAGE and CYBERSHAKE workflows: they have a lot of initial tasks, and the amount of work for every kind of tasks is of the same magnitude. In the case of LIGO, there were few to none improvement, probably because of the structure near from a Bag of Tasks of these workflows. As for the overspent of the budget that we can sometimes see for very small initial budgets, it is likely due to the saturation of the bandwidth of the datacenter which is not taken into account. However, smaller makespans for HEFTBUDG+ and HEFTBUDG+INV are obtained at a much higher computa-

D. Comparison with BDT and CG/CG+

In this section, we compare our algorithms with two competitors, BDT [START_REF] Arabnejad | Budget distribution strategies for scientific workflow scheduling in commercial clouds[END_REF] and CG/CG+ [START_REF] Wu | End-to-end delay minimization for scientific workflows in clouds under budget constraint[END_REF]. Beforehand, we briefly describe them and explain how we have extended them to match our application/platform model. A word of caution: some of our choices may be seen as arbitrary, but we have tried to be as fair as possible to allow for a meaningful comparison.

1) BDT (Budget Distribution with Trickling): BDT is divided into three major steps: (i) traversing the graph and grouping tasks into levels, i.e., subgroups of independent tasks; (ii) sharing the budget across the different levels, according to one chosen strategy. We implemented the strategy leading to the best results in [START_REF] Arabnejad | Budget distribution strategies for scientific workflow scheduling in commercial clouds[END_REF], All in, which tentatively grants all the budget to the first task of the current level. That task is not expected to consume all the budget, and the leftover is given to the next task in the level; (iii) scheduling tasks level by level. Inside a level, tasks are sorted on their increasing Earliest Start Time. Then for each task, the best host host is selected to maximize the ratio T CT F host ECTmax-ECTmin . Here subBudg t is the budget fraction allocated to the task t, ECT t,host and c t,host are the Earliest Completion Time (ECT) and total cost of task t on host host respectively, and c min the minimal cost possible for the execution of t (cheapest VM). Finally, ECT min and ECT max are respectively the smallest and largest ECT possible for task t, when trying all possible VM choices for t.

We have extended this algorithm to match our model, using the same task weights as in our own propositions. BDT uses an eager scheduling strategy, aiming at a very low makespan but at the risk of overspending the budget. Also, it is better suited to DAGs that can be decomposed into independent levels of tasks with similar costs.

2) CG/CG+ (Critical Greedy): This algorithm is divided in two parts: generation of an initial schedule CG, then refinement into another schedule CG+. CG first defines a global value gbl = B-cmin cmax-cmin to be used later to partition the budget B across the tasks. Here c min is the minimal budget needed to execute the workflow (assigning all tasks to a single VM of the cheapest type), and c max is the maximal one (assigning all tasks to a VM of the most expensive type). Then for each task t of the workflow (the ordering is not specified in [START_REF] Wu | End-to-end delay minimization for scientific workflows in clouds under budget constraint[END_REF] so we used HEFT), the algorithm computes the quantity c t,min + (c t,max -c t,min ) × gbl which represents the budget fraction predetermined for task t, with c t,min being the minimal cost needed to compute the task t and c t,max the maximal possible cost to compute the task t. It then selects the VM category whose cost for task t has the smallest difference in absolute value with that quantity.

Once the first schedule has been obtained with CG, it is refined to spend any leftover budget. The tasks belonging to the critical path of the schedule are re-assigned to more efficient VMs. Among these tasks, CG+ selects the task and VM pair so that re-assigning that task to that VM provides the largest ratio δT δc , where δT is the time decrease and δc the cost increase when making the re-assignment. The refinement continues until all the budget is spent.

There are no data transfers in [START_REF] Wu | End-to-end delay minimization for scientific workflows in clouds under budget constraint[END_REF], so we had to extend CG/CG+ to include all transfer times and costs.

3) Results: Figure 3 reports several key results for MIN-MINBUDG, HEFTBUDG, BDT and CG, on CYBERSHAKE, LIGO and MONTAGE workflows. The first row represents the makespan for different initial budgets; the second row shows the percentage of executions for which each algorithm found a makespan enforcing the initial budget, and the third row shows the actual budget spent w.r.t. the given initial budget. We see that BDT often fails to find a valid schedule, i.e., a schedule enforcing the initial budget, especially for small budgets; however when a schedule is found, its makespan is smaller than those found by MIN-MINBUDG and HEFTBUDG. For example on a CYBERSHAKE workflow of 90 tasks, BDT needs three times the lowest required budget to find a schedule. As for CG, it returns schedules that are close to the cheapest possible schedule possible. This is due to the way the budget is shared between tasks: the sub-budget given to a task is, in general, enough to choose between different instances of the cheapest VM type, but does not allow to afford a better VM type. The schedule generated by HEFTBUDG or MIN-MINBUDG (which have benefited from the transmission of leftover budgets to the next tasks) have then a smaller makespan.

Furthermore, we see in Figure 4 that CG+ keeps finding schedules with high makespans. The main reason is probably the chosen heuristic: CG+ maximizes the ratio between the time decrease and the cost increase, one pair (task, VM) after the other on the critical path. If a newly found assignment has both a lower cost and a lower makespan, the δT δc ratio will be negative and thus the new assignment will not be selected. This happens for example in the case when a re-assignment removes a data transfer.

The CPU execution times of BDT and CG (see Table III) have the same order of magnitude as HEFT or MIN-MIN. The execution time of CG+ is huge, an order of magnitude higher than HEFTBUDG+, but we do not report precise values for fairness: we believe that part of the high execution time is due to a technical requirement within SimDag when running the simulations.

VI. CONCLUSION

In this paper, we have presented a model and several budgetaware algorithms to schedule scientific workflows with stochastic task weights onto IaaS Cloud platforms. These platforms allow to dynamically enroll VMs of several types, with different cost and speed parameters. The first two algorithms, MIN-MINBUDG and HEFTBUDG, are extensions of the wellknown MIN-MIN and HEFT heuristics. We show that they manage to find a solution whose makespan remains similar to the one of the baseline versions while enforcing the prescribed budget. We observe that for a given budget HEFTBUDG obtains a better makespan than MIN-MINBUDG, in particular for workflows with a non-trivial inter-dependency graph. We then propose two refined versions, HEFTBUDG+ and HEFTBUDG+INV, that achieve better makespans, but at a higher CPU time cost. We also extend and implement two previously published budget-aware algorithms, BDT and CG/CG+. While BDT returns the smallest makespans when it succeeds, it fails to enforce the initial budget most of the time. Globally our algorithms find better schedules than CG/CG+. Again, these comparisons must be made with caution, because the application/platform cost models of BDT and CG/CG+ were cruder than the detailed framework used in this paper.

Further work will be devoted to extending the approach to on-line schedules, whenever the target Cloud infrastructure would allow to interrupt and re-schedule tasks on the fly. Indeed, if we monitor the execution of the tasks, we can detect unlikely events such as very long durations, and in such cases, it could be beneficial to interrupt some tasks and re-schedule them onto faster VMs. Such dynamic decisions encompass risks in terms of both final makespan and budget. For instance, deriving execution timeouts is a challenging problem, but we hope to design on-line heuristics that, with high probability, will decrease the final makespan while respecting the initial budget constraint.

1 :

 1 function DIVBUDGET(wf, B calc , s, bw ) 2:

1 : 5 :

 15 function GETBESTHOST(T , budgP T sk[T ], P, pot) 2: B T ← budgP T sk[T ] + pot 3: // initialisation: new host of cheapest category: 4: bestHost ← v, where v ∈ New VM and k v = 1 minEF T ← EF T T,bestHost 6:

7 : 4 : 4 : 7 :

 7447 if ((EF T T,host < minEF T ) 8:and (c T,host <= B T )) then 9: minEF T ← EF T T,host 10: return bestHost, pot 15: end function Algorithm 3 MIN-MINBUDG 1: function MIN-MINBUDG(wf, B calc , P) budgP T sk ← divBudget(wf, B calc , s, bw ) readyT asks ← getReadyT asks(wf ) 11: for each T of wf do 12: host ← getBestHost(T, budgP T sk[T ], 13: P, newP ot) 14: f inishT ime ← EF T T,host 15: if ((minF T < 0) 16: or (f inishT ime < minF T )) then 17: minF T ← f inishT ime function B. HEFTBUDG+ and HEFTBUDG+INV This section details two refined versions of HEFTBUDG. Because of the many conservative decisions taken during the Algorithm 4 HEFTBUDG 1: function HEFTBUDG(wf, B calc , P) budgP T sk ← divBudget(wf, B calc , s, bw ) 5: LISTT ← getT asksSortedByRanks(wf, s, bw , lat) 6: pot, newP ot ← 0 for each T of LISTT do 8:host ← getBestHost(T, budgP T sk[T ], P, newP ot)

Algorithm 5 HEFTBUDG+ 1 :

 51 function HEFTBUDG+(wf, B ini , P) 2:

Figure 1 :

 1 Figure 1: MIN-MIN, HEFT, budget-aware extensions MIN-MINBUDG and HEFTBUDG for the three workflow types with 90 tasks.

Figure 2 :

 2 Figure 2: HEFTBUDG+, HEFTBUDG+INV compared to HEFT and HEFTBUDG for the three workflow types with 90 tasks.

Figure 3 :

 3 Figure 3: Makespan, percentage of valid schedules and cost for MIN-MINBUDG, HEFTBUDG, BDT and CG for CYBERSHAKE, LIGO and MONTAGE with 90 tasks.

Table I :

 I Summary of main notations.

3 :

 3 LISTT, selSched ← HEFTBUDG(wf, B calc , P) tot , t calc,wf ← simulate(wf, P, LISTT, selSched )

	4:
	5:	minT imeCalc ← t calc,wf
	6:	for each T of LISTT do
	7:	for each host of (Used VM \sched[T ]) ∪ New VM do
	8:	sched ← schedule(T, host)
	9:	c tot , t calc,wf ← simulate(wf, P, LISTT, sched)
	10:	if ((t calc,wf < minT imeCalc)
	11:	and (c tot < B)) then
	12:	selectedHost ← host
	13:	minT imeCalc ← t calc,wf
	14:	end if
	15:	end for
	16:	selSched [T ] ← selectedHost
	17:	update(Used VM )
	18:	end for
	19:	return LISTT, selSched
	20: end function
			VM parameters
		Categories	k = 3
		Setup delay	t boot = 10 min
		Setup cost	c ini, = $2 for 1 ≤ ≤ 3
		Category 1	Speed s 1 = 5.2297 Gflops
		(Slow)	Cost c h,1 = $0.145 per hour
		Category 2	Speed s 2 = 8.8925 Gflops
		(Medium)	Cost c h,2 = $0.247 per hour
		Category 3	Speed s 3 = 13.357 Gflops
		(Fast)	Cost c h,3 = $0.370 per hour
			Datacenter
		Cost per month	c h,DC = $0.022 per GB
		Data transfer cost c tsf = $0.055 per GB
			Bandwidth
		bw	125MBps

c

Table III :

 III Time to calculate a schedule, in seconds, in the form mean ± standard value, median: (a) MONTAGE workflow of 90 tasks and different budgets; (b): MONTAGE workflow with 30, 60, 90 and 400 tasks, and a high budget. efficient VM and migrate to a fastest category VM.

				MIN-MIN	HEFT	MIN-MINBUDG	HEFTBUDG		BDT	CG
		Low		2.89 ± 0.39 2.78 ± 0.33 3.13 2.99	2.06 ± 0.23 2.19	2.60 ± 0.31 2.79	1.88 ± 0.26 3.35 ± 0.71 1.74 2.88
	(a)	Medium	2.90 ± 0.37 2.76 ± 0.33 3.13 2.98	2.06 ± 0.21 2.19	2.59 ± 0.30 2.78	2.48 ± 0.43 3.34 ± 0.71 2.21 2.86
		High		2.90 ± 0.39 2.77 ± 0.33 3.14 2.98	2.07 ± 0.22 2.20	3.32 ± 0.39 3.60	2.47 ± 0.44 2.45 ± 0.42 2.22 2.19
				MIN-MIN	HEFT	MIN-MINBUDG	HEFTBUDG	BDT	CG
		30		0.13 ± 0.002 0.14	0.16 ± 0.02 0.17	0.10 ± 0.01 0.11	0.20 ± 0.003 0.22	0.13 ± 0.00 0.13	0.13 ± 0.00 0.13
	(b)	60		0.88 ± 0.01 0.88	0.90 ± 0.01 0.90	0.63 ± 0.00 0.63	1.11 ± 0.01 1.11	0.91 ± 0.00 0.91	0.90 ± 0.01 0.90
		90		2.90 ± 0.39 3.14	2.77 ± 0.33 2.98	2.07 ± 0.22 2.20	3.32 ± 0.46 3.60	2.47 ± 0.44 2.22	2.45 ± 0.42 2.19
		400	395.80 ± 15.83 294.96 ± 15.83 395.06 297.23	268.15 ± 12.41 269.54	341.00 ± 14.64 363.95 ± 65.21 452.73 ± 110.38 340.15 361.50 380.26

This assumption is only for the sake of the presentation; it is easy to extend the approach to parallel tasks.

https://cloud.google.com/compute/pricing

https://aws.amazon.com/ec2/pricing/on-demand/

https://www.ovh.com/fr/public-cloud/instances/tarifs/

https://cloudharmony.com/status

https://cloud.google.com/compute/pricing