<figure><img src="image_1.png" /></figure>

HAL
open science

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

Yves Caniou, Eddy Caron, Aurélie Kong Win Chang, Yves Robert

► To cite this version:

Yves Caniou, Eddy Caron, Aurélie Kong Win Chang, Yves Robert. Budget-aware scheduling algorithms for scientific workflows with stochastic task weights on IaaS Cloud platforms *. Concurrency and Computation: Practice and Experience, In press. hal-03029318

HAL Id: hal-03029318

https://inria.hal.science/hal-03029318

Submitted on 30 Nov 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
# Budget-aware scheduling algorithms for scientific workflows with stochastic task weights on IaaS Cloud platforms*

Yves Caniou, Eddy Caron, Aurélie Kong Win Chang and Yves Robert

ROMA team, Inria Grenoble Rhône-Alpes, France
LIP laboratory, ENS Lyon, France
Innovative Computing Laboratory, Knoxville, TN, USA
CCPE, to appear

## Abstract

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 computing resources. We use a realistic application/platform model with stochastic task weights, and VMs communicating through a Cloud storage. We extend two well-known algorithms, *MINMIN* and *HEFT*, and make scheduling decisions based upon machine availability and remaining budget. During the mapping process, the budget-aware algorithms make conservative assumptions to avoid exceeding the initial budget; we further improve the 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, and this despite the uncertainty in task weights.

## 1 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 powerful-but-expensive devices. When deploying a scientific workflow on an IaaS Cloud, the

<footnote>*A preliminary version of this work has appeared in the proceedings [7] of the HCW workshop co-located with IPDPS, Vancouver, May 2018, and has been deposited on the HAL-Inria archive server as an Inria research report [6].</footnote>
user is faced with a difficult decision: which VM type to select for which task?
How many VMs to rent? These decisions clearly depend upon the budget al-
located 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, either MINMIN [5, 13] or HEFT [27], 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 improve upon such an inefficient approach,
this paper introduces several budget-aware algorithms to deploy scientific work-
flows on IaaS Clouds. The main idea is to revisit well-known algorithms such
as MINMIN 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 2 for an overview), this paper makes contributions along the fol-
lowing lines:

* A realistic application model, with stochastic task weights;

* A detailed yet tractable platform model, with a Cloud storage and multiple VM categories;

* Budget-aware algorithms MINMINBUDG and HEFTBUDG that extend MINMIN and HEFT, two widely-used list-scheduling algorithms for heterogeneous platforms;

* Refined (but more costly) variants HEFTBUDG+ and HEFTBUDG+INV that squeeze some of the leftover budget to further decrease total execution time (also called makespan). The refined versions aim at exploiting the opportunity to re-schedule some tasks onto faster VMs, thereby spending most of the budget fraction left over 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;

* A trade-off version HEFTBUDGMULT, which finds less good makespans than HEFTBUDG+ but with a time complexity close to HEFTBUDG.

The rest of the paper is organized as follows. Section 2 surveys related work. We introduce the performance model in Section 3. We describe budget-aware scheduling algorithms in Section 4: Section 4.1 presents the extensions to MINMIN and HEFT, while Section 4.2 provides the refined versions and Section 4.3 introduces the trade-off version. Section 5 is devoted to assessing their performance through extensive simulations, including comparisons with two previous budget-aware algorithms, namely BDT [2] and CG/CG+ [28]. Finally, we provide concluding remarks and directions for future work in Section 6.

## 2 Related work

Many scientific applications from various disciplines are structured as work-
flows [3]. 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 pro-
duce the expected scientific result. The development of complex middleware
with workflow engines [8, 10, 11] has automated workflow management. IaaS
Clouds raised lots of interest recently, thanks to an elastic resource allocation
and pay-as-you-go billing model. In a Cloud environment, there exist many
solutions for scheduling workflows [18, 26], some of which include data manage-
ment strategies [29]. Also [20] introduced two auto-scaling mechanisms to solve
the problem of the resource allocation in a cost-efficient way for unpredicted workflow jobs. [30] introduced a workflow scheduling in Cloud solutions with security and cost considerations. [1] provides guidelines and analysis to understand cost optimization in scientific workflow scheduling by surveying existing approaches in Cloud computing.

To the best of our knowledge, the closest papers to this work are [2, 28], which both propose workflow scheduling algorithms (BDT in [2], CG/CG+ in [28]) under budget and deadline constraints, but with a simplified platform model. In this work, we have extended BDT and CG/CG+ to enable a fair comparison with our algorithms, and we present the corresponding results in Section 5.2. Finally, [19] 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 [19], tasks in this paper).

<table><caption>Table 1: Summary of main notations.</caption><thead><tr><th colspan="2">Workflows</th></tr></thead><tbody><tr><td>$n$</td><td>number of tasks in the workflow</td></tr><tr><td>$T_i$</td><td>$i^{th}$ task of the workflow</td></tr><tr><td>$\overline{w_i}, \sigma_i \overline{w_i}$</td><td>mean and standard deviation of weight of $T_i$</td></tr><tr><td>$size(d_{T_i,T_j})$</td><td>amount of data from $T_i$ to $T_j$</td></tr></tbody><thead><tr><th colspan="2">Platform</th></tr></thead><tbody><tr><td>$k$</td><td>number of VM categories</td></tr><tr><td>$s_1 \le s_2 \le \dots \le s_k$</td><td>VMs speeds</td></tr><tr><td>$\overline{s}$</td><td>average speed</td></tr><tr><td>$c_{h,k}, c_{ini,k}$</td><td>per time-unit cost and initial cost for category $k$</td></tr><tr><td>$c_{tsf}$</td><td>per time-unit cost of I/O operations</td></tr><tr><td>$c_{h,CS}$</td><td>per time-unit cost of Cloud storage usage</td></tr><tr><td>$bw$</td><td>bandwidth between VMs and the Cloud storage</td></tr></tbody></table>

# 3 Model

This section details the application and platform model used to assess the performance of the scheduling algorithms. Table 1 summarizes main notations.

## 3.1 Workflows

The model of workflows presented here is directly inspired by [14, 19]. 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<fnref n="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 for 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 weight $w_i$ of task $T_i$ and follows a truncated Normal law with mean $\overline{w_i}$ and standard deviation $\sigma_i \overline{w_i}$:

$$w_i \sim \mathcal{N}(\overline{w_i}, \sigma_i \overline{w_i}) \qquad (1)$$

Here $\sigma_i$ is a parameter to control the standard deviation. To truncate, we draw randomly from the normal law until the result falls in the interval $[\overline{w_i} - \sigma_i \overline{w_i}, \overline{w_i} + \sigma_i \overline{w_i}]$. The value of $\overline{w_i}$ can be estimated (for example by sampling). Normal laws are ubiquitous in scientific applications [15] and therefore natural candidates to model the distribution of task weights. We truncate them to avoid negative values, as well as too large values. Note that the Pegasus generator also uses truncated normal laws [23].

To each dependency $(T_i, T_j) \in E$ is associated an amount of data of size $size(d_{T_i, T_j})$. 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.

## 3.2 Platform

Our model of Cloud platform mainly consists of a Cloud storage and processing units. To a great extent, it is based upon the offers of three big Cloud providers: Google Cloud<fnref n="2" />, Amazon EC2³ and OVH<fnref n="4" />. Given that Cloud providers propose a fault-tolerance service which ensures a very high availability of resources (in general over 99.97%<fnref n="5" />) as well as sufficient data redundancy, the Cloud storage 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. This model covers our needs in resilience and allows for the traceability of workflow execution. 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 Cloud storage, unless this data has been produced on the same VM $v$ (meaning that $T'$ had also been scheduled on $v$). The Cloud storage is also where the final generated data are stored before being transferred to the user. For simplicity, we consider that the Cloud storage bandwidth is large enough to feed all processing units, and to accommodate all submitted requests simultaneously, without any supplementary cost.

<footnote n="1">¹This assumption is only for the sake of the presentation; it is easy to extend the approach to parallel tasks.</footnote>

<footnote n="2">²https://cloud.google.com/compute/pricing</footnote>

<footnote n="3">³https://aws.amazon.com/ec2/pricing/on-demand/</footnote>

<footnote n="4">⁴https://www.ovh.com/fr/public-cloud/instances/tarifs/</footnote>

<footnote n="5">⁵https://cloudharmony.com/status</footnote>
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<fnref n="6" />. We only retain parameters common to the three providers Google, Amazon and OVH: a VM of category *k* has *n*<sub>*k*</sub> processors, one processor being able to process one task at a time; a VM has also a speed *s*<sub>*k*</sub> corresponding to the number of instructions that it can process per time unit, a cost per time-unit *c*<sub>*h*,*k*</sub> and an initial cost *c*<sub>ini,*k*</sub>; all these VMs take an initial, and uncharged, amount of time *t*<sub>boot</sub> 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 3.3. Without loss of generality (even if the VM is paid for each used second), categories are sorted according to hourly costs, so that *c*<sub>*h*,1</sub> ≤ *c*<sub>*h,2*</sub> · · · ≤ *c*<sub>*h,n*<sub>*k*</sub></sub>. We expect speeds to follow the same order, but do not make such an assumption.

Altogether, the platform 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 all 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; (v) a VM executes at most one task at every time-step, but this task can be parallel and enroll many computing resources (hence the execution time for the task strongly depends upon the VM type).

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 startup times. A VM *v* is started at time *H*<sub>start,*v*</sub> and does not stop until all the data created by its last computed task have been transferred to the Cloud storage, at time *H*<sub>end,*v*</sub>. 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 Cloud storage, and reloading all input data of the first task scheduled on that new VM before execution.

## 3.3 Workflow execution, cost and objective

Tasks are mapped to VMs and locally executed in the order given by the schedul-
ing algorithm, such as those described in Section 4. 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 Cloud storage.

**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 Cloud storage $C_{CS}$. The cost $C_v$ of the use of a VM

<footnote n="6">⁶https://cloud.google.com/compute/pricing</footnote>
$v$ of category $k_v$ is calculated as follows:

$$C_v = (H_{end,v} - H_{start,v}) \times c_{h,k_v} + c_{ini,k_v} \quad (2)$$

There is a startup cost $c_{ini,k_v}$ in Equation (2), and a term $c_{h,k_v}$ proportional to usage duration $H_{end,v} - H_{start,v}$.

The cost for the Cloud storage is based on a cost per time-unit $c_{h,CS}$, to which we add a transfer cost. This transfer cost is computed with the amount of data transferred from the external world to the Cloud storage (size($d_{in,CS}$)), and from the Cloud storage to the outside world (size($d_{CS,out}$)). In other words, $d_{in,CS}$ corresponds to data that are input to entry tasks in the workflow, and $d_{CS,out}$ to data that are output from exit tasks. Letting $H_{start,first}$ 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 Cloud storage, we define $H_{usage} = H_{end last} - H_{start,first}$ as the total platform usage during the whole execution. We have:

$$C_{CS} = (size(d_{in,CS}) + size(d_{CS,out})) \times c_{tsf} + H_{usage} \times c_{h,CS} \quad (3)$$

Altogether, the total cost is $C_{wf} = \sum_{v \in R_{VM}} C_v + C_{CS}$, where $R_{VM}$ is the set of booked VMs during the execution.

**Objective** Given a deadline $D$ and a budget $B$, the objective is to fulfill the deadline while respecting the budget:

$$D \geq H_{usage} \quad \text{and} \quad B \geq C_{wf} \quad (4)$$

# 4 Scheduling algorithms

This section introduces MINMINBUDG and HEFTBUDG, the budget-aware extensions to MINMIN [5, 13] and HEFT [27], two reference scheduling algorithms widely used by the community. Section 4.1 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 4.2 provides two refined versions of HEFTBUDG, namely HEFTBUDG+ and HEFTBUDG+INV. These versions squeeze some 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 MINMINBUDG because HEFTBUDG turned out to be more efficient than MINMINBUDG in our simulations, always achieving a smaller makespan for the same budget. Finally, Section 4.3 presents HEFTBUDGMULT, which constitutes a trade-off version between HEFTBUDG and HEFTBUDG+. Instead of refining an existing schedule, this last version uses information obtained from an execution of another algorithm to create a new schedule. More precisely, it uses the leftover budget from a first execution of HEFTBUDG to redo a sharing of the initial budget, with a bias in favor of the firsts tasks of the workflow. The obtained makespans are better than the ones found with HEFTBUDG, and with a lower complexity than HEFTBUDG+.
## 4.1 MINMINBUDG and HEFTBUDG

The budget-aware extensions of MINMIN and HEFT need to account both for task stochasticity and budget constraints, 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 $\bar{w}_T + \sigma_T \bar{w}_T$.

<caption>**Algorithm 1** Dividing the budget into tasks.</caption>

1: **function** DIVBUDGET(wf, $B_{calc}$, $\bar{s}$, bw)
2:     $W_{max}$ ← getMaxTotalWork(wf)
3:     $d_{max}$ ← getMaxTotalTransfData(wf)
4:     **for** each T of wf **do**
5:         $budgPTsk[T]$ ← $B_{calc}$ × $\frac{\bar{w}_T + \sigma_T \bar{w}_T + \frac{size(d_{pred,T})}{bw}}{\frac{W_{max}}{\bar{s}} + \frac{d_{max}}{bw}}$
6:         **end for**
7:         **return** $budgPTsk$
8: **end function**

Let us detail Algorithm 1: given the workflow $wf$, we first get the maximum of total work ($getMaxTotalWork(wf)$) and the total amount of data transfers ($getMaxTotalTransfData(wf)$) required to execute the workflow, and we reserve a fraction of the budget to cover the cost of the Cloud storage and VM initialization; then we divide what remains, $B_{calc}$, into the workflow tasks. To estimate the fraction of budget to be reserved, assuming that $B_{ini}$ denotes the initial budget:

* For the cost of the Cloud storage, we need to estimate the duration $H_{usage} = H_{end last} - H_{start first}$ of the whole execution (see Equation (3)). To this purpose, we consider an execution on a single VM of the first (cheapest) category, compute the total duration $W_{max} = \sum_{T \in wf} (\bar{w}_T + \sigma_T)$ and let

$$H_{usage} = \frac{W_{max}}{s_1} + \frac{size(d_{in,CS}) + size(d_{CS,out})}{bw} \quad (5)$$

Altogether, we pay the cost of input/output data several times: with factor $c_{tsf}$ for the outside world, with factor $c_{h,CS}$ for the usage of the Cloud storage (Equation (5)), 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 \times 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: we estimate how much time $t_{calc,T}$ is required to execute each task $T$, transfer times included, and allocate the corresponding part of the budget in proportion to the whole for execution of the entire workflow $t_{calc,wf}$:

$$budgPTsk[T] = \frac{t_{calc,T}}{t_{calc,wf}} \times B_{calc} \qquad (6)$$

In Equation (6), we use $t_{calc,T} = \frac{\overline{w_T} + \sigma_T}{\overline{s}} + \frac{size(d_{pred,T})}{bw}$, where

$$size(d_{pred,T}) = \sum_{(T',T) \in E} size(d_{T',T}) \qquad (7)$$

is the volume of input data of $T$ from all its predecessors. Similarly, we use $t_{calc,wf} = \frac{W_{max}}{\overline{s}} + \frac{d_{max}}{bw}$, where $d_{max} = \sum_{(T_i,T_j) \in E} size(d_{T_i,T_j})$ is the total volume of data within the workflow. Computed weights $(\overline{w_T} + \sigma_T)$ and $W_{max}$) are divided by the mean speed $\overline{s}$ of VM categories, while data sizes ($size(d_{pred,T})$ and $d_{max}$) are divided by the bandwidth $bw$ between VMs and the Cloud storage. 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 $\overline{s}$ in the estimation of the computing time may lead to an under-estimation of the cost when cheaper/slower VMs are selected.

**Algorithm 2 Choosing the best host for each ready task.**

1: **function** GETBESTHOST(T, budgPTsk[T], P, pot)

2: $B_T \leftarrow budgPTsk[T] + pot$

3: // initialisation: new host of cheapest category:

4: bestHost $\leftarrow v$, where $v \in New_{VM}$ and $k_v = 1$

5: minEFT $\leftarrow EFT_{T,bestHost}$

6: **for each host of** (Used$_{VM}$ $\cup$ New$_{VM}$) **do**

7: **if** $((EFT_{T,host} < minEFT) \text{ and } (c_{T,host} \leq B_T))$ **then**

8: minEFT $\leftarrow EFT_{T,host}$

9: bestHost $\leftarrow host$

10: pot $\leftarrow B_T - c_{T,host}$

11: **end if**

12: **end for**

13: **return** bestHost, pot

14: **end function**

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} = \delta_{new} \times t_{boot} + \frac{\overline{w_T} + \sigma_T \overline{w_T}}{s_{k_{host}}} + \frac{size(d_{in,T})}{bw} \qquad (8)$$
In Equation (8), we introduce the boolean $\delta_{new}$ whose value is 1 if $host \in New_{VM}$ to account for its startup delay, and 0 otherwise. Also, some input data may already be present if $host \in Used_{VM}$, thus we use $size(d_{in,T})$ instead of $size(d_{pred,T})$ (see Equation (7)), defining $d_{in,T}$ as those input data not already present on host.

To compute $EFT_{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 Cloud storage 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 Cloud storage 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} \times 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 very 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.

<caption>**Algorithm 3 MINMINBUDG.**</caption>

1: **function** MINMINBUDG(wf, $B_{calc}$, $\mathcal{P}$)
2:     $\bar{s} \leftarrow calcMeanSpeed(\mathcal{P})$
3:     bw $\leftarrow$ getBw($\mathcal{P}$)
4:     budgPTsk $\leftarrow$ divBudget(wf, $B_{calc}$, $\bar{s}$, bw)
5:     pot, newPot $\leftarrow$ 0
6:     **while** ! areEveryTasksSched(wf) **do**
7:         selectedHost $\leftarrow$ null
8:         selectedTask $\leftarrow$ null
9:         minFT $\leftarrow$ -1
10:        readyTasks $\leftarrow$ getReadyTasks(wf)
11:        **for** each $T$ **of** wf **do**
12:            host $\leftarrow$ getBestHost(T, budgPTsk[T], $\mathcal{P}$, newPot)
13:            finishTime $\leftarrow$ EFT$_{T,host}$
14:            **if** (($minFT$ < 0) or (finishTime < minFT)) **then**
15:                minFT $\leftarrow$ finishTime
16:                selectedTask $\leftarrow$ T
17:                selectedHost $\leftarrow$ host
18:                pot $\leftarrow$ newPot
19:            **end if**
20:        **end for**
21:        sched[$selectedTask$] $\leftarrow$ selectedHost
22:        schedule[$selectedTask$, selectedHost)
23:        update(Used$_{VM}$)
24:    **end while**
25:    return sched
26: **end function**

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, MINMINBUDG (Algorithm 3)
**Algorithm 4 HEFTBUDG.**

1: **function** HEFTBUDG(wf, $\mathcal{B}_{calc}, \mathcal{P}$)
2:     $\bar{s} \leftarrow calcMeanSpeed(\mathcal{P})$
3:     bw $\leftarrow getBw(\mathcal{P})$
4:     budgPTsk $\leftarrow divBudget(wf, \mathcal{B}_{calc}, \bar{s}, bw)$
5:     LISTT $\leftarrow getTasksSortedByRanks(wf, \bar{s}, bw, \bar{lat})$
6:     pot, newPot $\leftarrow 0$
7:     **for each** T **of** LISTT **do**
8:         host $\leftarrow getBestHost(T, budgPTsk[T], \mathcal{P}, newPot)$
9:         pot $\leftarrow newPot$
10:        sched[T] $\leftarrow host$
11:        schedule(T, host)
12:        update(Used<sub>VM</sub>)
13:    **end for**
14:    **return** LISTT, sched
15: **end function**

and HEFTBUDG (Algorithm 4) are the counterpart of the original MINMIN 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 MINMINBUDG 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 5 HEFTBUDG+**.

1: **function** HEFTBUDG+(wf, $\mathcal{B}_{ini}, \mathcal{P}$)
2:     $\mathcal{B}_{calc} \leftarrow getBudgCalc(wf, \mathcal{B}_{ini}, \mathcal{P})$
3:     LISTT, selSched $\leftarrow$ HEFTBUDG(wf, $\mathcal{B}_{calc}, \mathcal{P}$)
4:     $c_{tot}, t_{calc,wf} \leftarrow$ simulate(wf, $\mathcal{P}$, LISTT, selSched)
5:     minTimeCalc $\leftarrow t_{calc,wf}$
6:     **for each** T **of** LISTT **do**
7:         **for each** host **of** $((Used_{VM} \setminus sched[T]) \cup New_{VM})$ **do**
8:             sched $\leftarrow schedule(T, host)$
9:             $c_{tot}, t_{calc,wf} \leftarrow$ simulate(wf, $\mathcal{P}$, LISTT, sched)
10:          **if** $((t_{calc,wf} < minTimeCalc) \text{ and } (c_{tot} < \mathcal{B}))$ **then**
11:            selectedHost $\leftarrow host$
12:            minTimeCalc $\leftarrow t_{calc,wf}$
13:        **end if**
14:        **end for**
15:        selSched[T] $\leftarrow$ selectedHost
16:        update(Used<sub>VM</sub>)
17:    **end for**
18:    **return** LISTT, selSched
19: **end function**
## 4.2 HEFTBUDG+ and HEFTBUDG+INV

This section details two refined versions of HEFTBUDG. Because of the many conservative decisions taken during the 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 (like HEFT) assigns priorities to the tasks based upon their bottom level [27]. 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 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 4.1, HEFTBUDG (like 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.

## 4.3 HEFTBUDGMULT

<caption>**Algorithm 6 HEFTBUDGMULT.**</caption>

1: **function** HEFTBUDGMULT(wf, $B_{calc}$, $\mathcal{P}$)
2:     $B_{calc} \leftarrow \text{getBudgCalc}(wf, $B_{ini}$, $\mathcal{P}$)
3:     LISTT, $\text{selSched} \leftarrow$ HEFTBUDG(wf, $B_{calc}$, $\mathcal{P}$)
4:     $c_{tot}$, $t_{calc,wf} \leftarrow$ simulate(wf, $\mathcal{P}$, LISTT, $\text{selSched}$)
5:     $l = B_{calc} - c_{tot}$
6:     $\bar{s} \leftarrow \text{calcMeanSpeed}(\mathcal{P})$
7:     $bw \leftarrow \text{getBw}(\mathcal{P})$
8:     budgPTsk $\leftarrow$ divBudget(wf, $c_{tot}$, $\bar{s}$, bw)
9:     budgPTsk[$T_1$] = budgPTsk[$T_1$] + $l$
10:    LISTT $\leftarrow$ getTasksSortedByRanks(wf, $\bar{s}$, bw, $\bar{\text{lat}}$)
11:    pot, newPot $\leftarrow$ 0
12:    **for each** $T$ **of** LISTT **do**
13:        host $\leftarrow$ getBestHost($T$, budgPTsk[$T$], $\mathcal{P}$, newPot)
14:        pot $\leftarrow$ newPot
15:        sched[$T$] $\leftarrow$ host
16:        schedule($T$, host)
17:        update(Used$_{VM}$)
18:    **end for**
19:    **return** LISTT, sched
20: end function

The schedules found by HEFTBUDG+ are far better than the ones found
by HEFTBUDG, but at the price of a higher complexity. We thus propose HEFTBUDGMULT, a trade-off algorithm which uses the leftover that remains after HEFTBUDG. Because the budget left after an assignation is given to the next task all along the allocation process, HEFTBUDG is unfair with the first tasks, which cannot benefit from a larger share. As detailed in Algorithm 6, the idea here is to bias the initial repartition of the budget to correct this imbalance.

We first estimate the leftover $l$ that would be found after executing a pass of HEFTBUDG. Note that this estimation is done with a simulation using expected durations for tasks, which are different due to the stochasticity from the actual ones (which could only be measured after their respective and effective completion, i.e., post-mortem):

$$l = B_{ini} - c_{tot}$$

The amount of used money calculated earlier with HEFTBUDG, $c_{tot}$, is shared between the tasks of the workflow in the same way as HEFTBUDG shared $B_{ini}$. Hence the total amount of budget to allocate is not exceeded, and each task is allocated a smaller amount than with HEFTBUDG. We add $l$ to the amount of money dedicated to the first task:

$$budgPTsk[T_{first}] = budgPTsk[T_{first}] + l$$

For each task taken in the same priority order as in HEFTBUDG, we then choose the best host using Algorithm 2. The complexity is thus twice the complexity of HEFTBUDG, i.e., $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.

# 5 Simulations

In order to compare the different algorithms under study, we conducted a reproducible and extensive set of experiments, involving different scientific workflow types and varying many application and platform parameters. We describe the experimental methodology in Section 5.1, and assess the impact of the key parameters in Section 5.2.

## 5.1 Experimental methodology

### 5.1.1 Simulation setup

We designed a publicly available simulator [16] based on SimDag [25], an extension of the discrete event simulator SimGrid [9], to evaluate all algorithms. The model described in Section 3 is instantiated with 3 VM categories and respective costs based upon the offers by Amazon Cloud, Google Cloud and OVH (see Table 2): the cost of the VMs is based on the mean of the prices of EC2 at the time we made our experiments, and is linear with the speed of the VM. The VM is paid for each second used, with a startup cost.

### 5.1.2 Workflows

Our experiments rely on four different types of workflow from the Pegasus benchmark suite [12, 22], mostly selected because of their structural differences:
<table><caption>Table 2: Parameters of the IAAS Cloud platform.</caption><thead><tr><th colspan="2">VM parameters</th></tr></thead><tbody><tr><td>Categories</td><td>k = 3</td></tr><tr><td>Setup delay</td><td>t<sub>boot</sub> = 10 min</td></tr><tr><td>Setup cost</td><td>c<sub>ini,l</sub> = $2 for 1 ≤ l ≤ 3</td></tr><tr><td>Category 1<br>(Slow)</td><td>Speed s<sub>1</sub> = 5.2297 Gflops<br>Cost c<sub>h,1</sub> = $0.145 per hour</td></tr><tr><td>Category 2<br>(Medium)</td><td>Speed s<sub>2</sub> = 8.8925 Gflops<br>Cost c<sub>h,2</sub> = $0.247 per hour</td></tr><tr><td>Category 3<br>(Fast)</td><td>Speed s<sub>3</sub> = 13.357 Gflops<br>Cost c<sub>h,3</sub> = $0.370 per hour</td></tr><tr><th colspan="2">Cloud storage</th></tr><tr><td>Cost per month</td><td>c<sub>h,CS</sub> = $0.022 per GB</td></tr><tr><td>Data transfer cost</td><td>c<sub>tsf</sub> = $0.055 per GB</td></tr><tr><th colspan="2">Bandwidth</th></tr><tr><td>bw</td><td>125MBps</td></tr></tbody></table>

CYBERSHAKE, MONTAGE, LIGO and EPIGENOMICS. As for the fifth workflow offered in the Pegasus workflow generator, SIPHT, we felt its structure made it off-topic: SIPHT has more than half of its tasks ready to launch from its beginning, alongside a very short and simple DAG. In this particular case, using an algorithm designed to deal with bags of tasks would be far more appropriated. We nevertheless made some simulations with SIPHT, whose results are available in [16].

Concerning LIGO (Figure 1c), most input data have the same (large) size, only one of them is oversized compared with the others (by a ratio over 100). LIGO may be composed of numerous sub-workflows and consists of a lot of parallel tasks sharing a link to some agglomerative tasks, one agglomerative task per sub-workflow; this scheme repeats twice since there is a second subdivision after the first agglomeration. In CYBERSHAKE (Figure 1a), half the tasks have huge input data (around 20 Gigabytes). 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 (Figure 1b) has many highly inter-connected tasks, making parallelization less easy. The number of instructions of its different tasks is balanced, as is the size of the exchanged data. EPIGENOMICS (Figure 1d) consists of an early fork followed by a join at the end of the workflow. The tasks between these two structures are organized as chains of tasks. Huge data files are shared between tasks, and there is a high imbalance in the amount of work among tasks: the ones in the second half of the workflow can be more than 50 times longer than the ones at the beginning. We also point out that some chains of tasks are also imbalanced in the other workflows.

For each workflow type, we used the generator available on the Pegasus website to generate our benchmark, with five different instances per workflow type, and different numbers of tasks: 30, 60, 90 and 400; this leads to 5 × 3 = 15 workflows per type. The generated workflows and the platform files used for the experiments are available in [16]. To obtain task execution times, we use the deterministic task weight provided by these workflows as a basis for a random
<figure><img src="image_2.png" /><figcaption>Figure 1: Examples of 1a) CYBERSHAKE, 1b) MONTAGE, 1c) LIGO and 1d) EPIGENOMICS ([4])</figcaption></figure>

draw following a truncated Gaussian law (see Equation (1)):

$$w_{T,\text{simulated}} \sim \mathcal{N}(\bar{w}_T, \sigma_T \bar{w}_T), \quad \text{with } \sigma_T \in \{0.25, 0.5, 0.75, 1.0\} \quad (9)$$

### 5.1.3 Adaptations made to our competitors

To further assess the efficiency of our algorithms, we make comparisons with two competitors: Budget Distribution with Trickling (BDT [2]) and Critical Greedy (CG [28]). Both BDT and CG schedule deterministic workflows, and CG does not take communication costs into account. CG comes as a two-pass algorithm: first an affectation, then a refinement, which we will name respectively CG and CG+. We extended BDT and CG/CG+ to fit our model, so as to enforce fair comparisons. 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.

**BDT (Budget Distribution with Trickling) adaptation** 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 [2], 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 $TCTF_t^{host} = \frac{Time_t^{host}}{Cost_t^{host}}$ where $Cost_t^{host} = \frac{subBudg_t-c_{t,host}}{subBudg_t-c_{min}}$ and $Time_t^{host} = \frac{ECT_{max}-ECT_{t,host}}{ECT_{max}-ECT_{min}}$. 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.

**CG/CG+ (Critical Greedy) adaptation** 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 = \frac{B-c_{min}}{c_{max}-c_{min}}$ 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 [28] so we used that of HEFT), the algorithm computes the quantity $c_{t,min} + (c_{t,max} - c_{t,min}) \times 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 $\delta T / \delta c$, where $\delta T$ is the time decrease and $\delta c$ the cost increase when making the re-assignment. The refinement continues until all the budget is spent.

There are no data transfers in [28], so we had to extend CG/CG+ to include all transfer times and costs.

### 5.1.4 Collected data

Our objective here is to show data that best represent results obtained by the tested algorithms. Each simulation is characterized by a workflow, a degree of uncertainty regarding the real duration of its tasks, the tested algorithm and a budget. We computed the mean values on 25 runs per value of $\sigma_T$ (see 5.1.2). Overall, 16,500 experiments have been executed per workflow type
and scheduling algorithm. Given the high number of algorithms studied in the following, Table 3 provides a quick reminder description for each of them.

<table><caption>Table 3: Summary of algorithms under comparison.</caption><thead><tr><th colspan="2">Algorithms</th></tr></thead><tbody><tr><td>BDT (5.1.3)</td><td>Shares the budget between each level of the workflow.</td></tr><tr><td>CG (5.1.3)</td><td>Distribution of the budget per task, in one pass.</td></tr><tr><td>CG/CG+ (5.1.3)</td><td>First distribution via CG, then refinement along the critical path until no budget leftover remains unspent.</td></tr><tr><td>HEFT</td><td>No consideration of the budget. Ranks tasks and follows this ranking to allocate them to VM.</td></tr><tr><td>HEFTBUDG (4.1)</td><td>Ranks tasks as in HEFT, makes a first attribution of budget for each task, then allocates each task to a VM as in HEFT, but with respect to the budget. Forwards any budget leftover to the next task.</td></tr><tr><td>HEFTBUDG+ (4.2)</td><td>As in HEFTBUDG, but once a first allocation has been made, tries to shift the allocated task to a better VM using the budget leftover of the previous allocation. Reiterates until no leftover is left.</td></tr><tr><td>HEFTBUDG+INV (4.2)</td><td>Same as in HEFTBUDG+, but uses the opposite order for the ranking during reallocation.</td></tr><tr><td>HEFTBUDGMULT (4.3)</td><td>A first HEFTBUDG is ran and simulated, then a new allocation is done like in HEFTBUDG, but adding leftovers found to the budget of the first task.</td></tr><tr><td>MINMIN</td><td>No consideration of the budget. Allocates the couple &lt;task, VM &gt; with the earliest EFT until all tasks have been allocated.</td></tr><tr><td>MINMINBUDG (4.1)</td><td>Same as in MINMIN, but attributing a part of the budget to each task as in HEFTBUDG and using it for the allocation. Same mechanism of forwarding budget leftover as in HEFTBUDG.</td></tr></tbody></table>

## 5.2 Data analysis

### 5.2.1 General observations

We first present some general trends from the data collected in the simulations concerning the valid schedules found. We consider that a schedule is not valid if its cost, obtained during a simulation, exceeds the allocated budget. All graphics have been drawn with R [24]. Given the number of variables to analyze and their mixed nature, we use a graphical method for displaying multivariate data: the FAMD (Factor Analysis of Mixed Data) [21], performed with the FactoMineR package [17]. In a nutshell, for a given dataset containing variables that can be continuous and/or categorical, FAMD aims at extracting the axes structuring the dataset in the most reliable way. It makes possible to represent the correlation coefficient of the variables, and provides a graphical way to show how meaningful those coefficients are in the considered axes (correlation circle), as well as a summary of the dataset in the form of its projection on these axes (graph of individuals). All the results of the performed FAMD cannot be presented here due to lack of space, but the script to generate them is publicly available, with all raw results [16].

Correlation circles and graphs of individuals have a percentage written on the axis label which indicates how much of the total inertia of the point cloud is summarized by the selected axes. While parameters defining the workflow structure explain unsurprisingly most of the inertia (more than 50%), this first dimension had no correlation with the algorithms. Since we are using this method to summarize our results, we chose to represent only the dimensions correlated to the algorithms. The name of the variables contributing to the axes is shown next to this percentage. In the correlation circle, the arrows represent the different considered variables, and the angle between two arrows represent their correlation. The closest to 90° an angle between two arrows is, the less correlated the corresponding variables are. On the contrary, two opposite or overlapping arrows represent very correlated variables. The length
<figure><img src="image_3.png" /><figcaption>Figure 2: Impact of the number of tasks and of the value of σ(T): a) correlation circle and b) graph of individuals for schedules obtained for MONTAGE.</figcaption></figure>

of the arrows shows how much of the variability of the variables is represented in the selected plan, the maximum length possible being the length of the radius of the circle of correlation. The graph of individuals represents the projection of all schedules in the plan composed of the two dimensions obtained by the FAMD. The distance between two points represents how different they are, the difference growing with the distance. The boxes, when drawn, are just a visual help to more clearly discriminate the different algorithms and represent the convex hull of the corresponding points.

FAMD has been performed for each workflow type (CYBERSHAKE, MONTAGE, EPIGENOMICS and LIGO). For clarity, we report only detailed data for 30, 60 and 90 tasks; we only summarize results for 400 tasks: they are quite similar and available in [16]. The following variables were included in the datasets: type of the workflow, number of tasks, scheduling algorithm, schedule cost, percentage of uncertainty about the duration of the tasks, percentage of reserved VMs actually used (as opposed to the idle time), initial budget, number of reserved VMs. In order to remove as much as possible the impact of the each workflow characteristics, makespans and costs are shown relative to a reference value, namely the makespan and cost obtained using a unique cheap VM. Thereby, $IndMakespan = I_{tExec,tot} = \frac{t_{Exec,tot}}{t_{Exec,tot,ref}}$ and $IndCost = I_{cwf} = \frac{c_{wf}}{c_{wref}}$.

Figure 2a shows the impact of the number of tasks and standard deviation. A first observation is that the number of tasks in the scheduled workflow is not correlated with any of the other variables since the angle between the corresponding arrows is close to 90°. In other words, a comparison made between different algorithms concerning all selected criteria will lead to the same outcome, if the shape of the workflow is similar, regardless of the number of tasks. This is graphically confirmed in Figure 2b where we can see, for each different number of tasks, a similar positioning between the algorithms. This outcome has been found for the four workflow types. As a consequence, this paper only includes figures for workflows for 60 tasks, but similar observations can thus be made with a different number of tasks [16]. This similarity related to shape is observed for all experiments presented here. However, note that a LIGO of 30 tasks is either a single workflow or two sub-workflows, while a LIGO of 400
<figure><img src="image_4.png" /><figcaption>Figure 3: Correlation circle and graph of individuals for schedules obtained for MONTAGE workflows of 60 tasks</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Figure 4: Correlation circle and graph of individuals for schedules obtained for LIGO workflows of 60 tasks</figcaption></figure>

tasks is actually a big set of independent little sub-workflows, thus of a different shape.

Figure 3 displays the results of a similar FAMD made on MONTAGE work-
flows of 60 tasks (but the observations here are similar for CYBERSHAKE and
EPIGENOMICS), projecting the point cloud on a plane with an x-axis (Dim1)
based on a composition of *IndMakespan*, *IndCost*, number of VMs used and
algorithms, and a y-axis (Dim2) based on a composition of % VM used, sd dura-
tion and algorithms. It shows that our scheduling algorithms are bounded to the
left by CG and CG+ (less expensive money-wise, but with larger makespans),
and to the right by BDT and HEFT (shorter makespans, more expensive).
Schedules proposed by *MINMIN* and *MINMINBUDG* are distinguished by a dif-
ferent use of reserved VMs. This is further investigated in Section 5.2.5.

Figure 4 presents the case of LIGO, since this type of workflow is a bit distinc-
tive, as it is made of independent sub-workflows. The second most structuring
axis (Dim2) is here compounded of a combination of which algorithm is mak-
ing the schedule and how many VMs have been allocated. Here we observe
3 different behaviors: all budget-aware algorithms propose very similar schedules concerning the axes summarizing the cost, makespan and percentage of reserved VMs actually used to execute tasks; standing out from the ones that do not (MINMIN and HEFT) or fail to (BDT). Where all the other algorithms use reserved VMs equally, we observe that MINMIN stands apart, forming a very distinct block on the left in Figure 4b. Its stretched form comes from the fact that the tuple <IndMakespan, IndCost, % VM used> takes values on a wider range than the other algorithms. This behavior will be further analyzed in Section 5.2.5.

Finally, we provide an overview of results for workflows with 400 tasks. Globally, the observed behaviors are similar to their counterparts with 90 tasks when we have similar workflow shapes. More precisely, the observations are exactly the same as for Ligo and Cybershake with 90 tasks. In Epigenomics, we see a trend to overspend the budget which is similar to what we had with 90 tasks, but more often. This is probably related to the shape of the generated workflow for 400 tasks: Epigenomics gets numerous small forks-joins instead of the few big ones when it has 90 tasks. Besides, it creates a new task dedicated to merge all intermediate data, with a very high amount of data transfers. This can explain why we can see an accentuation of the observed behavior with fewer tasks. For Montage workflows of 400 tasks, our algorithms have a behavior very similar to the one observed for Epigenomics with 90 tasks. Here too, it can be explained by the shape of the generated workflow for 400 tasks. When a Montage workflow is composed of 400 tasks, the final fork-join becomes the place of a very large amount of data transfers. It seems to create two contention points at the end of the workflow. This would explain why the observed behavior is closer to the one observed with Epigenomics workflow of 90 tasks than to a Montage workflow of 90 tasks. Again, all results are available in [16].

5.2.2 Validity of proposed schedules

As mentioned earlier, we study the characteristics of the valid schedules found by
the algorithms. For all σT values, similar trends appear. To compute Figure 5,
we used the global mean obtained with all of them (i.e., σT ∈ (0.25, 0.5, 0.75, 1.0)),
and we drew the corresponding standard deviation for MONTAGE workflows of
60 tasks.

Unsurprisingly, HEFT and MINMIN only propose valid solutions for high budgets. It is the case for BDT too, which aims at a small makespan, taking the risk of spending too much money. On the contrary, CG, CG+, and our algorithms, which create schedules with the allocated budget in mind (MINMINBUDG, HEFTBUDG, HEFTBUDGMULT) have a better budget management. MINMINBUDG may fail for some initial budgets: for a budget of 0.12$, 99.68% of the proposed solutions were valid. As displayed in Figure 6k, this phenomenon increases for CYBERSHAKE workflows with 60 tasks, where the percentage of valid schedules can fall to a value of 90.65% for a budget of 0.31$. The algorithms which calculate schedules through multiple passes (HEFTBUDG+ and HEFTBUDG+INV) find a valid schedule about 97.5% of the time. Given the importance of the percentage of valid schedules in the comparison, we display this information, for each initial budget and workflow, in Figures 6 and 7.

A possible reason why some algorithms overspend their budget can be an
<figure><img src="image_6.png" /><figcaption>Figure 5: Percentage of valid schedules found by all algorithms for MONTAGE, 60 tasks, $\sigma_T \in (0.25, 0.5, 0.75, 1.0)$. (The error bars represent the standard deviation.)</figcaption></figure>

underestimation of the time needed to send data from a VM to another. When HEFT algorithms only use the rank of each task to decide which VM to pick, `MINMIN` selects the couple (task, VM) that achieves the best EFT under the budget constraint. This estimation is impacted by the estimation of the time needed to send data to the allocated VM, hence an underestimation would have more impact on `MINMIN` algorithms than on HEFT algorithms. This would explain the higher percentage of invalid schedules for `HEFTBUDG+` and `HEFTBUDG+INV`, which both cut down generously on leftovers to achieve a shorter makespan. The margin being narrower than expected, the algorithms sometimes overspend their budget.

This further explains results obtained with the FAMD, more particularly with Figure 3: HEFT and BDT give better makespan with more expensive schedules, but at the cost of a low percentage of valid schedules.

### 5.2.3 Execution time

We ran sequential simulations on a Intel® Core™ i5-6200U CPU @ 2.30GHz × 4 processors. We recorded the time needed for each algorithm while calculating 5 continuous schedules, and executing 30 instances for each combination of parameters. We use three types of workflows (CYBERSHAKE, LIGO and MONTAGE) instantiated with 30, 60 and 90 tasks. For each workflow, we use three characteristic values, "low", "high" and "medium", to characterize the impact of the budget on the time needed to compute a schedule. A "low" budget $B_{min}$ corresponds to the minimum budget needed to find a schedule, a "high" one is 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_{minbest}$ needed to obtain a makespan as good as the one found by the baseline version of the algorithm, and take the average: $B_{med} = \frac{B_{minbest} + B_{min}}{2}$.

<table><caption>(a)</caption><thead><tr><th></th><th>BDT</th><th>CG</th><th>HEFT</th><th>HEFTBUDG</th><th>HEFTBUDG+</th></tr></thead><tbody><tr><th>Low</th><td>1.88 ± 0.24<br>1.74</td><td>3.35 ± 0.71<br>2.88</td><td>2.78 ± 0.33<br>2.99</td><td>2.60 ± 0.31<br>2.79</td><td>6.20 ± 0.87<br>6.71</td></tr><tr><th>Medium</th><td>2.48 ± 0.43<br>2.21</td><td>3.34 ± 0.71<br>2.86</td><td>2.76 ± 0.33<br>2.98</td><td>2.59 ± 0.30<br>2.78</td><td>11.16 ± 1.76<br>12.04</td></tr><tr><th>High</th><td>2.47 ± 0.44<br>2.22</td><td>2.45 ± 0.42<br>2.19</td><td>2.77 ± 0.33<br>2.98</td><td>3.32 ± 0.39<br>3.60</td><td>115.80 ± 19.51<br>123.59</td></tr></tbody></table>

<table><caption>(b)</caption><thead><tr><th></th><th>HEFTBUDG+INV</th><th>HEFTBUDGMULT</th><th>MINMIN</th><th>MINMINBUDG</th></tr></thead><tbody><tr><th>Low</th><td>6.21 ± 0.88<br>6.73</td><td>2.74 ± 0.43<br>2.45</td><td>2.89 ± 0.39<br>3.13</td><td>2.06 ± 0.23<br>2.19</td></tr><tr><th>Medium</th><td>14.70 ± 2.14<br>15.75</td><td>3.28 ± 0.60<br>2.94</td><td>2.90 ± 0.37<br>3.13</td><td>2.06 ± 0.21<br>2.19</td></tr><tr><th>High</th><td>115.48 ± 17.99<br>124.30</td><td>3.91 ± 0.71<br>3.49</td><td>2.90 ± 0.39<br>3.14</td><td>2.07 ± 0.22<br>2.20</td></tr></tbody></table>

<table><thead><tr><th></th><th>BDT</th><th>CG</th><th>HEFT</th><th>HEFTBUDG</th><th>HEFTBUDG+</th></tr></thead><tbody><tr><th>30</th><td>0.13 ± 0.00<br>0.13</td><td>0.13 ± 0.00<br>0.13</td><td>0.16 ± 0.02<br>0.17</td><td>0.20 ± 0.03<br>0.22</td><td>3.27 ± 0.51<br>4.18</td></tr><tr><th>60</th><td>0.91 ± 0.00<br>0.91</td><td>0.90 ± 0.01<br>0.90</td><td>0.90 ± 0.01<br>0.90</td><td>1.11 ± 0.01<br>1.11</td><td>23.20 ± 0.51<br>23.10</td></tr><tr><th>90</th><td>2.47 ± 0.44<br>2.22</td><td>2.45 ± 0.42<br>2.19</td><td>2.77 ± 0.33<br>2.98</td><td>3.32 ± 0.46<br>3.60</td><td>115.80 ± 19.51<br>123.59</td></tr><tr><th>400</th><td>363.95 ± 65.21<br>361.50</td><td>452.73 ± 110.38<br>380.26</td><td>294.96 ± 15.83<br>297.23</td><td>341.00 ± 14.64<br>340.15</td><td>22979.44 ± 976.41<br>22381.89</td></tr></tbody></table>

<table><caption>Table 4: Time to compute 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 additional results for larger workflows (400 tasks), and a high budget.</caption><thead><tr><th></th><th>HEFTBUDG+INV</th><th>HEFTBUDGMULT</th><th>MINMIN</th><th>MINMINBUDG</th></tr></thead><tbody><tr><th>30</th><td>3.29 ± 1.56<br>4.20</td><td>0.25 ± 0.03<br>0.25</td><td>0.13 ± 0.02<br>0.14</td><td>0.10 ± 0.01<br>0.11</td></tr><tr><th>60</th><td>23.15 ± 0.60<br>22.98</td><td>1.55 ± 0.06<br>1.58</td><td>0.88 ± 0.01<br>0.88</td><td>0.63 ± 0.00<br>0.63</td></tr><tr><th>90</th><td>115.48 ± 17.99<br>124.30</td><td>3.91 ± 0.71<br>3.49</td><td>2.90 ± 0.39<br>3.14</td><td>2.07 ± 0.22<br>2.20</td></tr><tr><th>400</th><td>25090.96 ± 1086.20<br>24419.84</td><td>394.96 ± 98.35<br>364.35</td><td>395.80 ± 15.83<br>395.06</td><td>268.15 ± 12.41<br>269.54</td></tr></tbody></table>

Table 4 shows CPU times needed to compute a schedule for workflows of varying types and sizes. For example, for a MONTAGE workflow of 90 tasks, HEFTBUDG needs 3.32±0.46 seconds to find a schedule (Not represented here, but data [16] shows that 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). One can see a difference of behavior between MINMIN-type algorithms and HEFT-type algorithms. Indeed, when adding a budget constraint to the initial algorithm, the former see their execution time decrease when the later ones increase (for the most striking case, MINMIN on a MONTAGE workflow of 400 tasks will take on average 395.80 ± 15.83 seconds when MINMINBUDG will only take an average of 268.15 ± 12.41 seconds). This
is probably caused by a lower number of temporary selected couples (task, VM) induced by the budget constraint, thus lowering the number of intermediate steps.

On the contrary HEFT-type algorithms see their execution time increase with the addition of the budget constraint, the lower number of selections of couples (task, VM) during the creation of schedules being not enough to compensate for the additional operations introduced by the budget awareness. HEFTBUDG+ and HEFTBUDG+INV are by far the slowest algorithms among HEFT-type ones (for a MONTAGE of 90 tasks, they take respectively, on average, 115.80 ± 19.51 seconds and 115.48 ± 17.99 seconds to propose a schedule when HEFTBUDG only take 3.32 ± 0.46 seconds). Thus, while the FAMD presented in Section 5.2.1 suggested that HEFTBUDG+ and HEFTBUDG+INV propose schedules closer to what would create HEFT than to single-pass algorithms such as HEFTBUDG or HEFTBUDGMULT, their execution time can be prohibitive enough to persuade a user to prefer the latter rather than the former.

### 5.2.4 Efficiency

Concerning the valid schedules proposed by the different considered algorithms, as seen in the FAMD (Section 5.2.1), our competitors and the algorithms that do not take into account the budget form boundaries of the area where our budget-aware algorithms lie.

Figures 6 and 7 illustrate the performance details of valid schedules. In Figure 6, the first row represents the costs of valid schedules for various budgets in MONTAGE, CYBERSHAKE and EPIGENOMICS workflows. The second row shows their makespan for the same budgets. The third row displays the effective CPU time taken on the VMs (as opposed to idle). The fourth row reports, for each value of the budget, the proportion of valid schedules, i.e., the ratio of valid schedules among the 25 runs that have been used to compute the mean and standard deviation represented on all graphs. Figure 7 displays the same results for LIGO workflows.

CG creates the cheapest schedules (Figures 6a, 6b, 6c, 7a), but also the ones with the largest makespan (Figures 6d, 6e, 6f, 7b). On the contrary BDT creates schedules close to what HEFT would achieve: very short makespans, at the expense of high costs, with low proportions of valid schedules where budget is limited. MINMIN has a similar behavior in terms of short makespans, high costs and low proportion of valid schedules for limited budget, but tends to use fewer VMs.

Among the algorithms which schedule tasks within a single pass, HEFTBUDG and MINMINBUDG propose schedules whose efficiency in terms of makespan and cost tends to be closer to those obtained with HEFT and MINMIN as the allocated budget increases. With a lower budget, the efficiency depends on the workflow: In the case of LIGO, the schedules proposed by HEFTBUDG and MINMINBUDG are equivalent, either for makespan or for cost. With CYBERSHAKE, MINMINBUDG schedules achieve lower makespans than HEFTBUDG at a similar cost. But for MONTAGE workflows, as soon as HEFTBUDG has a budget large enough to reserve more VMs, it proposes schedules whose makespan is lower than those obtained by MINMINBUDG at a higher cost.

HEFTBUDG+ and HEFTBUDG+INV create schedules which are almost all
<figure><img src="image_7.png" /><figcaption>Figure 6: Cost, makespan, percentage of VMs reserved actually used to execute tasks, and percentage of valid schedules for MONTAGE, CYBERSHAKE and EPIGENOMICS workflows of 60 tasks.</figcaption></figure>

valid and whose makespan is far lower than HEFTBUDG and MINMINBUDG, for a cost sometimes over twice as high. In general, HEFTBUDGMULT proposes solutions halfway between the ones from HEFTBUDG+ and the ones from HEFTBUDG, whether it is for cost or for makespan. An interesting phenomenon appears in the case of EPIGENOMICS: the distinctive shape of this workflow, with very long tasks in its second half, makes the readjustment of the budget made by HEFTBUDGMULT irrelevant. Too much budget is used by
<figure><img src="image_8.png" /><figcaption>Figure 7: Cost, makespan, percentage of VMs reserved actually used to execute tasks, and percentage of valid schedules for LIGO workflows of 60 tasks.</figcaption></figure>

early tasks, dooming the last ones. This leads to a situation where HEFTBUDG and MINMINBUDG perform better than HEFTBUDGMULT, and even at least as well as HEFTBUDG+ and HEFTBUDG+INV. Those trends are confirmed in the percentage of valid schedules graph, getting lower with the higher values of the budget.

In summary, there is an opposition between algorithms creating schedules with a larger makespan in a single pass (HEFTBUDG, MINMINBUDG) and algorithms enforcing a reallocation of the estimated leftover budget after a first attribution (HEFTBUDG+, HEFTBUDG+INV). The latter schedules are more expensive and take longer to execute. HEFTBUDGMULT seems to emerge as a promising trade-off for most situations, with schedules whose makespan and cost are between the ones from HEFTBUDG and HEFTBUDG+/HEFTBUDG+INV and with an execution time closer to HEFTBUDG. However, in the case where early tasks need far less budget than subsequent ones, HEFTBUDG and MINMINBUDG perform better than HEFTBUDGMULT and at least as well as HEFTBUDG+ and HEFTBUDG+INV.

### 5.2.5 Flexibility

The FAMD of Section 5.2.1 showed that there was a difference in the actual use of CPU time of the VMs reserved by the algorithms. Figures 6g, 6h, 6i and 7c suggest the following: the more interdependent the tasks composing a workflow, the more different the behavior of the compared algorithms. For LIGO, regardless of the budget, all algorithms almost fully use the allocated VMs for the execution of tasks, apart from MINMIN, which always uses about 78%, and CG+ which seems to enroll all VMs only for high values of budget. On the contrary, in MONTAGE workflows, for low budgets, HEFTBUDG+, HEFTBUDG+INV and HEFTBUDGMULT are the ones that use their reserved VMs the least (about 80% vs. almost 100% for the other ones); while for
higher budgets, MINMINBUDG uses its reserved VMs the least (about 80% vs. between 88 to almost 100% for the other ones). CYBERSHAKE is blurrier, with very high variance and CG+ which differentiates itself from the other ones for high budgets. Interestingly, in EPIGENOMICS, the algorithms with low makespans use far less their reserved VMs than the other ones (about 60% for HEFTBUDG+, HEFTBUDG+INV and HEFTBUDG, 40% for MINMINBUDG versus almost 100% for CG and HEFTBUDGMULT). This is probably related to the large amount of exchanged data which highlights the differences in budget use among those algorithms. This leads to the possibility for the most efficient algorithms to reserve more VMs, thus spending more reserved time in sending and receiving data than executing tasks.

In a context of limited resources with uncertainty about the exact duration of tasks, allocating all free VMs can be an advantage, allowing for some possible rearrangements such as re-launching a task unexpectedly long on the least used VM without having to re-calculate a brand new schedule. This flexibility makes parsimonious algorithms such as MINMINBUDG shine for highly interdependent tasks and high budgets, despite having slightly higher makespans.

# 6 Conclusion

In this paper, we have presented a model and several budget-aware algorithms to schedule scientific workflows with stochastic task weights onto IaaS Cloud platforms. These algorithms are summarized in Table 3. Through experiments conducted with four types of scientific workflows, we have shown their respective merits and defaults, and we have compared them to two previously published budget-aware algorithms, BDT and CG/CG+. These experiments showed that, depending on the type of the workflow and the given budget, different algorithms shine in specific domains. If the workflow is close to LIGO (the one with the least interdependency among tasks), all budget-aware algorithms performed similarly. The only difference is that, for high budgets, CG/CG+ gave more flexibility but at the expense of a higher makespan. For workflows with highly interdependent tasks, with limited budget, if the amount of time needed to find a schedule is not important, HEFTBUDG+ and HEFTBUDG+INV propose the best schedules in terms of makespan, with even a bit of flexibility for very low budgets, but at the expense of a higher cost and huge amount of time to calculate the schedule. Schedules proposed by MINMINBUDG are in general cheaper than those produced by HEFT, but with a higher makespan. However, if the user wants to keep some flexibility to reschedule tasks during the execution of the workflow, the schedules proposed by MINMINBUDG with moderate budgets might be an interesting choice. HEFTBUDG is interesting for its short execution time, and it always respects the given budget. And it is, with MINMINBUDG, the best algorithm whenever there is a need of higher budget for the latest tasks. But it is otherwise superseded by the refined algorithms for the makespan. HEFTBUDGMULT is an interesting tradeoff between HEFTBUDG and HEFTBUDG+, achieving makespans between those found by HEFTBUDG and those found by HEFTBUDG+ or HEFTBUDG+INV, but with a CPU time close to HEFTBUDG. These comparisons must be made with caution, because the original 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 sched-
ules, 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 prob-
lem, but we hope to design on-line heuristics that, with high probability, will
decrease the final makespan while respecting the initial budget constraint.

Acknowledgments

We would like to thank the reviewers for their comments and suggestions, which
greatly helped improve the final version of the paper.

References

[1] E. N. Alkhanak, S. P. Lee, R. Rezaei, and R. M. Parizi. Cost optimization approaches for scientific workflow scheduling in cloud and grid computing: A review, classifications, and open issues. Journal of Systems and Software, 113:1–26, 2016.

[2] V. Arabnejad, K. Bubendorfer, and B. Ng. Budget distribution strategies for scientific workflow scheduling in commercial clouds. In 2016 IEEE 12th International Conference on e-Science (e-Science), pages 137–146, Oct 2016.

[3] S. Bharathi, A. Chervenak, E. Deelman, G. Mehta, M.-H. Su, and K. Vahi. Characterization of scientific workflows. In SC'08 Workshop: The 3rd Workshop on Workflows in Support of Large-scale Science (WORKS08) web site, Austin, TX, Nov. 2008. ACM/IEEE.

[4] S. Bharathi, A. Chervenak, E. Deelman, G. Mehta, M.-H. Su, and K. Vahi. Characterization of scientific workflows. In Workflows in Support of Large-Scale Science (WORKS), pages 1–10. IEEE, 2008.

[5] T. Braun, H. Siegel, N. Beck, L. Bölöni, M. Maheswaran, A. Reuther, J. P. Robertson, M. Theys, B. Yao, D. Hensgen, and R. F. Freund. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. Journal of Parallel and Distributed Computing, 61(6):810–837, 2001.

[6] Y. Caniou, E. Caron, A. K. W. Chang, and Y. Robert. Budget-aware scheduling algorithms for scientific workflows with stochastic task weights on IaaS cloud platforms. Research Report 9128, INRIA, Nov. 2017.

[7] Y. Caniou, E. Caron, A. K. W. Chang, and Y. Robert. Budget-aware scheduling algorithms for scientific workflows with stochastic task weights on heterogeneous iaas cloud platforms. In 27th International Heterogeneity in Computing Workshop HCW 2013. IEEE Computer Society Press, 2018.
[8] E. Caron, F. Desprez, T. Glatard, M. Ketan, J. Montagnat, and D. Reimert. Workflow-based comparison of two distributed computing infrastructures. In *Workflows in Support of Large-Scale Science (WORKS10)*, New Orleans, November 14 2010. In Conjunction with Supercomputing 10 (SC'10), IEEE. hal-00677820.

[9] H. Casanova, A. Giersch, A. Legrand, M. Quinson, and F. Suter. Versatile, scalable, and accurate simulation of distributed applications and platforms. *J. Parallel Distributed Computing*, 74(10):2899-2917, 2014.

[10] P. Couvares, T. Kosar, A. Roy, J. Weber, and K. Wenger. Workflow Management in Condor. In *I. Taylor, E. Deelman, D. Gannon, and M. Shields, editors, Workflows for e-Science*, pages 357-375. Springer, 2007.

[11] E. Deelman, G. Singh, M.-H. Su, J. Blythe, Y. Gil, C. Kesselman, G. Mehta, K. Vahi, G. B. Berriman, J. Good, A. Laity, J. Jacob, and D. Katz. Pegasus: a Framework for Mapping Complex Scientific Workflows onto Distributed Systems. *Scientific Programming Journal*, 13(3):219-237, 2005.

[12] E. Deelman, K. Vahi, G. Juve, M. Rynge, S. Callaghan, P. J. Maechling, R. Mayani, W. Chen, R. Ferreira da Silva, M. Livny, and K. Wenger. Pegasus, a workflow management system for science automation. *Future Generation Computer Systems*, 46(0):17-35, 2015.

[13] P. Ezzatti, M. Pedemonte, and A. Martín. An efficient implementation of the min-min heuristic. *Comput. Oper. Res.*, 40(11), 2013.

[14] G. Juve, A. L. Chervenak, E. Deelman, S. Bharathi, G. Mehta, and K. Vahi. Characterizing and profiling scientific workflows. *Future Generation Comp. Syst.*, 29(3):682-692, 2013.

[15] K. Kim and G. Shevlyakov. Why gaussianity? *IEEE Signal Processing Magazine*, 25(2):102-113, 2008.

[16] A. Kong Win Chang. http://graal.ens-lyon.fr/~yrobert/budget-aware-scheduling.zip.

[17] S. Lê, J. Josse, and F. Husson. FactoMineR: A package for multivariate analysis. *Journal of Statistical Software*, 25(1):1-18, 2008.

[18] C. Lin and S. Lu. Scheduling scientific workflows elastically for cloud computing. In *Cloud Computing (CLOUD), 2011 IEEE International Conference on*, pages 746-747. IEEE, 2011.

[19] M. Malawski, G. Juve, E. Deelman, and J. Nabrzyski. Algorithms for cost-and deadline-constrained provisioning for scientific workflow ensembles in iaas clouds. *Future Generation Computer Systems*, 48:1-18, 2015.

[20] M. Mao and M. Humphrey. Scaling and scheduling to maximize application performance within budget constraints in cloud workflows. In *Parallel and Distributed Processing (IPDPS), 2013 IEEE 27th International Symposium on*, pages 67-78. IEEE, 2013.

[21] J. Pagès. Analyse factorielle de données mixtes. *Revue de statistique appliquée*, 52(4):93-111, 2004.
[22] Pegasus. Pegasus workflow generator. https://confluence.pegasus.isi.edu/display/pegasus/WorkflowGenerator, 2014.

[23] Pegasus. Code for the Pegasus generator. https://github.com/pegasus-isi/WorkflowGenerator, 2020.

[24] R Core Team. R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria, 2019.

[25] SimDag. Programming environment for DAG applications. http://simgrid.gforge.inria.fr/simgrid/3.13/doc/group__SD__API.html, 2017.

[26] S. Smanchat and K. Viriyapant. Taxonomies of workflow scheduling problem and techniques in the cloud. Future Generation Computer Systems, 52:1–12, 2015.

[27] H. Topcuoglu, S. Hariri, and M. Y. Wu. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans. Parallel Distributed Systems, 13(3):260–274, 2002.

[28] C. Q. Wu, X. Lin, D. Yu, W. Xu, and L. Li. End-to-end delay minimization for scientific workflows in clouds under budget constraint. IEEE Transactions on Cloud Computing, 3(2):169–181, April 2015.

[29] D. Yuan, Y. Yang, X. Liu, and J. Chen. A data placement strategy in scientific cloud workflows. Future Generation Comp. Syst, 26(8):1200–1214, 2010.

[30] L. Zeng, B. Veeravalli, and X. Li. SABA: A security-aware and budget-aware workflow scheduling strategy in clouds. J. Parallel Distrib. Comput, 75:141–151, 2015.