#  Scheduling Bag-of-Tasks in Clouds using Spot and Burstable Virtual Machines

Luan Teylo  Institute of Computing
Fluminense Federal University
Niterói, Brasil 24210-346
Email<EMAIL_ADDRESS>
Luciana Arantes  LIP6
Sorbonne Univ., CNRS, Inria
Paris, France
Email<EMAIL_ADDRESS>Pierre Sens  LIP6
Sorbonne Univ., CNRS, Inria
Paris, France
Email<EMAIL_ADDRESS>Lúcia Maria de A. Drummond  Institute of Computing
Fluminense Federal University
Niterói, Brasil 24210-346
Email<EMAIL_ADDRESS>
###### Abstract

Leading Cloud providers offer several types of Virtual Machines (VMs) in
diverse contract models, with different guarantees in terms of availability
and reliability. Among them, the most popular contract models are the on-
demand and the spot models. In the former, on-demand VMs are allocated for a
fixed cost per time unit, and their availability is ensured during the whole
execution. On the other hand, in the spot market, VMs are offered with a huge
discount when compared to the on-demand VMs, but their availability fluctuates
according to the cloud’s current demand that can terminate or hibernate a spot
VM at any time. Furthermore, in order to cope with workload variations, cloud
providers have also introduced the concept of burstable VMs which are able to
burst up their respective baseline CPU performance during a limited period of
time with an up to 20% discount when compared to an equivalent non-burstable
on-demand VMs. In the current work, we present the Burst Hibernation-Aware
Dynamic Scheduler (Burst-HADS), a framework that schedules and executes tasks
of Bag-of-Tasks applications with deadline constraints by exploiting spot and
on-demand burstable VMs, aiming at minimizing both the monetary cost and the
execution time. Based on ILS metaheuristics, Burst-HADS defines an initial
scheduling map of tasks to VMs which can then be dynamically altered by
migrating tasks of a hibernated spot VM or by performing work-stealing when
VMs become idle. Performance results on Amazon EC2 cloud with different
applications show that, when compared to a solution that uses only regular on-
demand instances, Burst-HADS reduces the monetary cost of the execution and
meet the application deadline even in scenarios with high spot hibernation
rates. It also reduces the total execution time when compared to a solution
that uses only spot and non-burstable on-demand instances.

###### Index Terms:

Cloud Computing, BoT Scheduling, Burstable VMs, Spot VM Hibernation

##  I Introduction

In the past few years, cloud computing has emerged as an attractive option to
execute different applications due to several advantages that it brings
compared with dedicated infrastructure. Clouds provide a significant reduction
in operational costs, besides offering rapid elastic provisioning of computing
resources like virtual machines (VMs) and storage. However, in cloud
environments, besides the usual goal of minimizing the application’s execution
time, it is also essential to reduce the monetary cost of using its resources,
i.e., there is a trade-off between performance and budget.

Most cloud platforms enable users to dynamically acquire computational
resources wrapped as virtual machines (VMs). The users can reserve the VMs
depending on their application requirements (CPU, memory, I/O, etc.) in a pay-
as-you-use price model. Furthermore, cloud providers offer VMs in different
contract models, with different guarantees in terms of availability and
volatility. For instance, in Amazon EC2, there are three main contract models
(also call markets): i) reserved market, where the user pays an upfront price,
guaranteeing long-term availability; ii) on-demand market which is allocated
for specific periods of time, and incurs a fixed cost per unit time of use,
ensuring the availability of the instance during this period; iii) spot market
in which unused resources are available up to 90% discount when compared to
the on-demand model.

In the three markets, there exist a wide range of VM types that suit different
user requirements. According to Amazon Web Service (AWS), “Instance types
comprise varying combinations of virtual CPUs (vCPUs), memory, storage, and
networking capacity and give you the flexibility to choose the appropriate mix
of resources for your applications. Each instance type includes one or more
instance sizes, allowing you to scale your resources to the requirements of
your target workload”111https://aws.amazon.com/ec2/instance-types. Instances
types are grouped into families based on their use case. For example, the
compute-optimized instances (C3, C4, and C5) are ideal for compute-bound
applications that require high-performance processors.

Regarding the spot market, the availability of its VMs fluctuates according to
the cloud’s current demand. If there are not enough resources to meet clients’
requests, the cloud provider can interrupt a spot VM (temporarily or
definitively). Despite the risk of unavailability, the main advantage of spot
VMs is that their costs are much lower than on-demand VMs since the user
requests unused instances at steep discounts. An interrupted spot VM instance
can either terminate or hibernate. If the VM will be terminated, the cloud
provider warns the user two minutes before its interruption. On the other
hand, hibernated VM instances are frozen immediately after noticing the user.
In this case, EC2 saves the VM instance memory and context in the root of EC2
Block Storage (EBS) volume, and during the VM’s interruption period, the user
is only charged for the EBS storage use. EC2 resumes the hibernated spot
instance, reloading the saved memory and context, only when there is enough
available resource whose price is lower than the maximum one, which the user
agreed to be charged.

Beside the markets, all leading cloud providers introduced in the last years
the concept of burstable VM that can sprint its performance during a limited
period of time to cope with sudden workload variations. By operating on a CPU
credit regime that controls the processing power offered to users, burstable
VM instances can use 100% of the VM’s processing power (burst mode) or only a
fraction of that processing power (baseline mode), depending on such credits.
They accumulate CPU credits per hour, whose amount depends on the instance
type. If a burstable instance uses fewer CPU resources than required for
baseline performance (for example, when it is idle), the unspent CPU credits
are accrued in the CPU credit balance of the instance. If a burstable VM needs
to burst above the baseline performance level, it spends the accrued credits.
The more credits that a burstable performance instance has accrued, the longer
it can burst beyond its baseline when higher performance is required.
Burstable instances have two main advantages: i) they are offered with an up
to 20% discount compared to non-burstable on-demand instances with equivalent
computational resources, and ii) contrarily to spot VMs, they are not prone to
revocation. On the other hand, to obtain monetary advantages of burstable
instances, the user has to control their respective CPU credit usage by
monitoring their baseline performance and bursting during their entire
running. In Amazon EC2, a burstable VMs are of type T3, T3a, or T2.

This paper presents a scheduler for Bag-of-Tasks applications with deadline
constraints, exploring hibernate-prone spot instances and on-demand burstable
instances aiming at minimizing both the monetary cost and the execution time
of applications. The proposed scheduler, denoted Burst Hibernation-Aware
Dynamic Scheduler (Burst-HADS), is an event-driven scheduling framework built
in a modular way with two main scheduling modules: i) the Primary Scheduling
Module that defines an initial scheduling map of tasks to VMs; and ii) a
Dynamic Scheduling Module responsible for task migration or task rollback
recovering to/in idle VMs. It also provides a Fault Tolerance Module that
takes checkpoints periodically, enabling that a task, when migrated, re-starts
from the last checkpoint.

In a previous work [1], we had already explored the use of hibernation-prone
spot instances to minimize the monetary cost of BoT applications execution,
respecting their respective deadline constraints. To meet such a deadline,
even in the presence of multiple hibernations, new on-demand VMs, not
allocated in the initial mapping, might be dynamically launched. In this case,
tasks of the hibernated spot instances and those not executed yet are migrated
to on-demand instances. Although the strategy can significantly reduce the
monetary costs, always respecting the application deadline, if VM spots
hibernate, the application’s total execution time might considerably increase
when compared with a solution that uses only on-demand instances. To tackle
such a problem, in this article, we are interested in investigating how
burstable instances can be used to reduce the impact in the execution time of
the application and the corresponding monetary costs. Several scenarios are
studied and evaluated, showing that the proposed burstable instance approach
can be very advantageous, guaranteeing the application’s deadline without
degrading application execution time, even in the presence of hibernations,
and still optimizing the monetary costs.

The main contributions of the paper are:

  * •

A mathematical formulation of the static scheduling problem;

  * •

An Iterated Local Search (ILS) based metaheuristic that defines an initial
scheduling map aiming to minimize both application execution time and monetary
cost. We point out that ILS [2] belongs to a class of local search algorithms
proposed in the literature that efficiently investigates the solution space of
combinatorial problems;

  * •

A spot and on-demand burstable instance-based dynamic scheduler;

  * •

Validation of Burst-HADS by presenting evaluation results from experiments
conducted in a real cloud provider environment, Amazon EC2, considering
synthetic applications [3] as well as NAS benchmark application in different
scenarios subject to spot VM hibernations and resuming events.

Performance results from the experiments confirm the effectiveness of Burst-
HADS in terms of monetary costs and execution times compared to an approach
based only on Amazon EC2 on-demand VMs. Concerning the comparison with our
previous work [1], results show that the new proposed ISL-based primary
scheduler and the use of burst instances can reduce the impact in the
execution time of using hibernate-probe instances.

The remaining of this paper is organized as follows. Section II discusses some
related work. Section III-A defines the system and application models, while
Section III-B presents the main modules of Burst-HADS. Evaluation results from
experiments on EC2 cloud are presented in Section IV. Finally, Section V
concludes the paper and introduces some future directions.

##  II Related Work

Since AWS introduced the concept of burstable VM, many works exploring its
features have been proposed. Many of them focus on evaluating the burstable
approach and the improvement in computational performance that it can induce.
In [4], Leitner and Scheuner present a first empirical and analytical study
about the second generation of AWS burstable instances (T2 family). They
specifically considered T2.micro, T2.small, and T2.medium instances. Their
article aimed at answering if, in terms of monetary cost and performance,
these instance types are more efficient than other instance ones. Results show
that compared to general-purpose and computed-optimized instances (2015
generation), the evaluated T2 instances provide a higher CPU performance-cost
ratio as long as the average utilization of instances is below 40%.

In order to figure out CPU usage limits on-the-fly, according to the dynamic
variation of the workloads, Ali et al. proposed in [5] an autonomic framework
that combines light-weight profiling and an analytical model The objective is
to maximize the amount of work done using the burstable capacity of T2 VM
instances. The authors state that the framework extends the CPU credits
depletion period. Similarly to t Leitner and Scheuner’s work [4], their
results also confirm the benefits from active CPU usage control when burstable
instances are exploited. However, they do not discuss the impact in the total
execution time when such an approach is applied. Jiang et al. [6] analytically
modeled the performance of burstable VMs, considering their respective
configuration, such as CPU, memory, and CPU credits parameters. They also show
that providers can maximize their total revenue by finding the optimal prices
for burstable instances. Although their work, contrarily to ours, does not
focus on application performance, its contribution is extremely interesting
since it states that providers can offer burstable instances for low prices
without losing revenue while meeting QoS parameters, including burst mode’s
performance.

Mehta and Chandy [7] conducted a series of experiments in EC2 to evaluate the
performance of a job executing in instances T1.micro and T2.micro. The article
shows it is possible to overcome performance penalty due to lack of CPU
credits by a simple checkpoint and migration approach. On the one hand, the
latter is very similar to the Burst-HADS migration procedure. On the other
hand, it differs from Burst-HADS and its previous versions [1] since it does
not exploit spot VMs to minimize monetary cost.

Some scheduling and scaling problems also take advantage of burstable
instances features. In [8], for example, Baarzi et al. propose an autoscale
tool denoted BurScale, which uses burstable instances, together with on-demand
instances, to handle transient queuing which arises due to traffic
variability. They also present how burstable instances can mask VM
startup/warmup costs when autoscaling, to handle flash crowds, takes place.
Using two distinct workloads, a stateless web server cluster and a stateful
Memcached caching cluster, the authors show that a careful combination of
burstable and regular instances ensured similar performance for applications
as traditional autoscaling systems while reducing up to 50% of the monetary
cost.

In [9], Wang et al. combined on-demand, spot, and burstable instances
proposing an in-memory distributed storage solution. Burstable instances are
used as a backup to overcome performance degradation resulting from spot
instance revocations. According to the authors, those instances’ burst
capacity makes them ideal candidates for such a backup. Performance results
show that the backup that uses burstable instances presents a latency, which
is 25% lower than the latency of backup based on regular instances, inducing,
therefore, significant monetary cost saving.

To deal with spot VM revocations, we proposed in [10] a static heuristic that
creates pre-defined backup maps before the execution of the job tasks
themselves. It was the first attempt to cope with spot VMs hibernation, and
results from simulation showed that the hibernation problem is better handled
with a dynamic approach. Thus, in [1] we present a dynamic scheduler, denoted
HADS that uses both spot and regular (non-burstable) on-demand VMs to execute
BoT applications. It aims at minimizing the execution’s monetary cost
respecting application deadline On the other hand, in the current work, Burst-
HADS exploits hibernation-prone spot VMs and burstable VMs. It also applies
new heuristics to reduce not only the monetary cost of the execution but also
the execution time of the application, while meeting the deadline defined by
the user.

To the best of our knowledge, the hibernation mechanism of the spot VMs is
only discussed in our previous works [10, 1] and in Fabra et al. [11]. In the
latter, the authors consider a scenario where hibernation-prone spot VMs can
is used and then they show that deadline constraints add complexity to the
problem of resource provisioning. However, no practical solution is presented
neither discussed. Moreover, that work does not concern the task scheduling
problem, but a resource provisioning one.

##  III Scheduling with Hibernation-prone Spot and Burstable On-demand
Instances

###  III-A System and Application Models

Table I: Notation used in the application and system models. Name |  Description
---|---
$B$ |  Set of tasks
$M$ |  Set of VMs
$M^{s}$ |  Set of VMs spots
$M^{o}$ |  Set of VMs on-demand
$M^{b}$ |  Set of VMs burstable on-demand VMs
$T$ |  Discretized time set
$D$ |  Deadline defined by the user
$D_{spot}$ |  Estimated time limit which ensures that there will be enough spare time to migrate tasks of a hibernated spot VM to other VMs no matter when hibernations take place
$\omega$ |  Overhead of initialization of a VM
$vm_{j}$ |  Virtual machine
$m_{j}$ |  Memory capacity of $vm_{j}$ in gigabytes
$c_{j}$ |  Cost per period of time of $vm_{j}$
$vcpu_{k}$ |  A Virtual Core of $vm_{j}$
$VC_{j}$ |  Set of vCPUs of $vm_{j}$
$cc_{j}$ |  CPU credits of $vm_{j}$
$t_{i}$ |  a task of the BoT application
$rm_{i}$ |  Amount of memory required by a task $t_{i}$
$e_{ij}$ |  Time required to execute task $t_{i}$ in a $vm_{j}$

Let $M=M^{s}\cup M^{o}\cup M^{b}$ be the user-provided set of VMs that can be
used to execute the BoT application, where $M^{s}\subset M$ is the set of spot
instances, $M^{o}\subset M$ is the set of non burstable on-demand ones and
$M^{b}\subset M$ is the set of burstable on-demand VMs. Let $D$ be the
application deadline, defined by the user, and $T=\\{1,\ldots,D\\}$ be a
discrete set of time periods. Each $vm_{j}\in M$ has a memory capacity of
$m_{j}$ gigabytes, $|VC_{j}|$ virtual cores (vCPU), and a current CPU credit
amount $cc_{j}$ (in the case of $vm_{j}\not\in M^{b}$, i.e., non-burstable
VMs, $cc_{j}=\infty$).

By default, Amazon EC2 does not allow more than five VMs of similar types and
markets to run simultaneously. Thus, if the user decides, for example, to use
only on-demand VMs of type $C5.xlarge$, spot VMs of type $C5.2xlarge$, and
burstable VMs of type $T3.xlarge$, there will be a maximum of five VMs of each
type at each set $M^{o}$, $M^{s}$ and $M^{b}$.

When the user requests a new VM, there exists a time delay for using it which
due to the launch of the VM by the provider plus its operating system booting.
Therefore, in this work, we consider the same overhead initialization time
cost $\omega$ for all VMs, which comprises these waiting times. When a new
$vm_{j}$ is launched, after $\omega$ periods of time, the user is charged
$c_{j}$ for each period of time. When the VM terminates, the user’s charge for
this VM immediately stops.

Let $B$ be the set of tasks of a BoT application. We assume that each task
$t_{i}\in B$ requires a known amount of memory $rm_{i}$, and it is executed in
only one $vcpu_{k}\in VC_{j}$ of $vm_{j}$. A multi-core $vm_{j}$
($|VC_{j}|>1$) can execute more than one task simultaneously (one task per
core) only when there is enough main memory to allocate them in the VM. We
also consider that the execution time $e_{ij}$ of each task $t_{i}$ in any
$vm_{j}\in M$ is known beforehand. In the case of a burstable $vm_{j}\in
M^{b}$, $e_{ij}$ is the execution time of task $t_{i}$ in $vm_{j}$ in burst
mode (100% of the $vm_{j}$ processing power).

All variables and parameters defined in this section are summarized in Table
I.

###  III-B Burst Hibernation-Aware Dynamic Scheduler Framework

The Burst Hibernation-Aware Dynamic Scheduler (Burst-HADS) that we propose has
two main scheduling modules: i) the Primary Scheduling Module, that defines an
initial scheduling map; and ii) a Dynamic Scheduling Module responsible for
migrating tasks or executing task rollback recovering in idle VMs. Note that
each of the modules can be easily changed or extended adopting a new approach.
For instance, a new heuristic or metaheuristic can be included in the Primary
Scheduling Module. The source code of Burst-HADS is available at
https://github.com/luanteylo/Burst-HADS.

###  III-C Primary Scheduling Module

It is worth remembering that the problem of scheduling tasks to distributed
computing resources is an NP-complete one [12], even in simple scenarios.
Furthermore, some features of clouds render it more difficult. We thus model
the primary scheduling problem as a multi-objective integer programming
problem whose objectives are to minimize both the monetary cost and the total
execution time of the application. In other words, in our case, it is defined
as the problem of scheduling tasks to VMs respecting the available storage
capacity and trying to minimize the makespan and the monetary costs.

Aiming at ensuring the application deadline $D$ no matter if and when spot VM
hibernations could happen, in our previous work [1], we defined $D_{spot}$ as
the worst-case estimated makespan, which guarantees that there will always
have enough spare time to migrate tasks of any hibernated spot VM to other VMs
and execute them. $D_{spot}$ is computed by considering the longest tasks that
might need to be migrated and executed to/in the system’s slowest virtual
machines.

Let the binary variable $X_{ijk}^{v}$ indicate whether a task $t_{i}\in B$
allocated to a $vcpu_{k}\in VC_{j}$ of a $vm_{j}\in M^{s}$ will start
executing ($X_{ijk}^{v}=1$), or not ($X_{ijk}^{v}=0$), at time period $v\in
T$. Let also $Z_{j}$ and $ZT$ be variables which respectively keep the last
period of execution of a $vm_{j}\in M^{s}$ and the total execution time of the
application (makespan).

The proposed objective function (Equation 1) is a weighted function that
minimizes the monetary cost and the makespan, where $\alpha$ and $1-\alpha$
are the respective weights given by the user for the objectives. Note that, in
this case, both the monetary cost and the makespan have to be first
normalized. The objective function is subject to the constraints given by
equations 2, 3, 4, 5, and 6.

$\begin{split}\min{(\alpha\sum_{vm_{j}\in
M^{s}}{Z_{j}c_{j}}+(1-\alpha)ZT)}\end{split}$ (1)

Subject to:

$\begin{split}&\sum_{t_{i}\in B}\sum_{vcpu_{k}\in
VC_{j}}{\sum_{q=p}^{v}{rm_{i}X_{ijk}^{q}}}\leq m_{j},\\\ &\forall vm_{j}\in
M^{s},\forall v\in T,\text{ and $p=\max(v-e_{ij},1)$}\end{split}$ (2)

$\begin{split}&\sum_{t_{i}\in B}\sum_{vcpu_{k}\in
VC_{j}}{\sum_{q=p}^{v}{X_{ijk}^{q}}}\leq|VC_{j}|,\\\ &\forall vm_{j}\in
M^{s},\forall v\in T,\text{ and $p=\max(v-e_{ij},1)$}\end{split}$ (3)

$\begin{split}&\sum_{vm_{j}\in M^{s}}\sum_{vcpu_{k}\in VC_{j}}{\sum_{v\in
T}{X_{ijk}^{v}}}=1,\forall i\in B\end{split}$ (4)

$\begin{split}&X_{ijk}^{v}(v+e_{ij})\leq Z_{j}\\\ &Z_{j}\leq D_{spot}\\\
&\forall t_{i}\in B,\forall vm_{j}\in M^{s},\forall vcpu_{k}\in VC_{j}\text{
and }\forall v\in T\end{split}$ (5)

$\begin{split}&X_{ijk}^{v}Z_{j}\leq ZT\\\ &\forall t_{i}\in B,\forall
vm_{j}\in M^{s},\forall vcpu_{k}\in VC_{j}\text{ and }\forall v\in
T\end{split}$ (6)

In Equations 2 and 3, we define the constraints in terms of memory and number
of virtual cores, respectively. Equation 4 determines that every task
$t_{i}\in B$ must be allocated and started only once, in a a single $vcpu_{k}$
of $vm_{j}\in M^{s}$ ($vcpu_{k}\in VC_{j}$). The constraint of Equation 5
ensures that $D_{spot}$ is respected while equation 6 defines the makespan
constraint.

In order to create the initial scheduling map, our previous Primary Scheduling
Module, HADS, proposed in [1], executes a simple greedy heuristic, which only
minimizes monetary cost while respecting the application deadline. In the
current work, we propose an Iterated Local Search (ILS) whose goal is to
minimize both the monetary cost and the execution time of that initial
scheduling map. ILS [2] is a metaheuristic that aims at improving a final
solution by sampling in a broader and distant neighborhood of candidate
solutions, and then applying a local search technique to refine solutions to
their local optima. It explores a sequence of solutions created by
perturbations of the current best solution to reach these distant
neighborhoods.

After finding a scheduling map with ILS, a second heuristic is applied to
include burstable instances into the solution. In case of spot VM
hibernations, these instances will be used, in burst mode, by the dynamic
scheduler, as an attempt to minimize the impact of these hibernations in the
monetary cost and/or the execution time. Therefore, the Primary Task
Scheduling algorithm (Algorithm 1) has two parts: i) the iterated local
search, and ii) the burstable instances allocation. Furthermore, in line 3, an
initial solution is generated by calling Algorithm 2, proposed, originally in
[1]. The latter is a greedy heuristic that schedules the set of tasks $B$ to a
set $M^{s}$ of spot VMs.

Initially, Algorithm 2 sorts the tasks of $B$ in descending order by their
memory size requirements (line 2). Calling the procedure check_schedule, it
then verifies if it is possible to schedule task $t_{i}$ in the selected
$vm_{j}$ of the current phase, i.e., the task is scheduled to the VM if the
memory requirements are satisfied and if $D_{spot}$ is not violated. Note that
scheduling tasks in an already allocated VM avoid VM deploying time. Thus, for
each task $t_{i}\in B$, the algorithm tries to schedule it to a core of a
virtual machine $vm_{j}$ from $A$, the set of already selected VMs (lines 7 to
12). If task $t_{i}$ can not be scheduled to a $vm_{j}$ of $A$, the algorithm
tries to select a new spot VM (lines 14 to 22) using a weighted round-robin
algorithm (WRR) [13]. In WRR, each spot VM has an associated weight, and the
algorithm selects the VMs in a round-robin way, according to such weights. As
shown in Equation 7, the weight of $vm_{j}$, $weight(j)$, is equal to the
quotient between $Gflops_{j}$ of $vm_{j}$, and $c_{j}$, the price of the VM
per time period. The $Gflops_{j}$ of $vm_{j}$ is estimated using the LINPACK
benchmark [14] and expresses the computing power of this VM. Our choice in
using WRR and spot VMs with different configurations is in agreement with
Amazon’s recommendations222https://aws.amazon.com/pt/ec2/spot/instance-
advisor/ that say that an application should use different types of spot VMs
to increase the availability of spot VM instances. According to Kumar et al.
[15], interruptions of spot VMs, which include hibernation, usually take place
in VMs of the same type. Therefore, a choice of heterogeneous spot VMs
minimizes the impact of possible VM hibernations. Finally, in line 24,
Algorithm 2 calls the function $create\\_solution$ that receives the set of
the selected VMs $A$ and returns a solution $S$ that defines a scheduling map.

$weight(vm_{j})=Gflops_{j}/c_{j},\textit{where $vm_{j}\in M$}$ (7)

Algorithm 1 Primary Task Scheduling

1:$B$, $M$, $M^{s}$, $M^{o}$, $M^{b}$, $max\\_ondemand$, $max\\_iterations$,
$max\\_failed$, $relaxed\\_rate$, $D_{spot}$ and  $D$

2:{/*PART 01 - Iterated Local Search*/}

3:$S\leftarrow initial\\_solution(B,M^{s},D_{spot})$ {/*Algorithm 2*/}

4:$S\leftarrow local\\_search(S,max\\_attempt,swap\\_rate)$ {/* Algorithm 3*/}

5:$S_{best}\leftarrow S$

6:$RD_{spot}\leftarrow D_{spot}$

7:$i\leftarrow 0$

8:$last\\_best\leftarrow i$

9:while $i<max\\_iteration$ do

10: {/* Perturbation */}

11: $vm_{j}\leftarrow random\\_choice(M^{s})$

12: $S.selected\\_vms\leftarrow S.selected\\_vms\cup vm_{j}$

13: $M^{s}\leftarrow M^{s}\backslash\\{vm_{j}\\}$

14: $failed\leftarrow i-last\\_best$

15: if $failed>max\\_failed$ then

16: $RD_{spot}\leftarrow RD_{spot}+(relax\\_rate\times RD_{spot})$

17: end if

18: $S\leftarrow local\\_search(S,max\\_attempt,swap\\_rate)$

19: if $fitness(S,D_{spot})<fitness(S_{best},D_{spot})$ then

20: $S_{best}\leftarrow S$

21: $last\\_best\leftarrow i$

22: end if

23: $i\leftarrow i+1$

24:end while

25:{/*PART 02: Burstable instance allocation*/}

26:$n\leftarrow\lceil burst\\_rate\times S.selected\\_vms\rceil$

27:$S_{final}\leftarrow
burst\\_allocation(S_{best},burst\\_rate,M^{b},D_{spot},D)$

28:$create\\_primary\\_map(S_{final})$

Algorithm 2 Initial Solution

1:$B$, $M^{s}$, $D_{spot}$

2:$sort\\_by\\_memory(B)$ {/*Sort Tasks by memory requirement $rm_{i}$*/}

3:$A\leftarrow\emptyset$ {/*Set of selected VMs*/}

4:for $\textbf{ all }t_{i}\in B$ do

5: {(/*Phase 1: Try to schedule the task in an already selected spot VM*/}

6: $sort\\_by\\_price(A)$ {/*Sort the selected VMs by price*/}

7: for all  $vm_{j}\in A$ do

8: if $check\\_schedule(t_{i},vm_{j},D_{spot})$ then

9: $schedule(t_{i},vm_{j})$

10: $break$ {/*Schedule next task*/}

11: end if

12: end for

13: {/*Phase 2: Try to schedule the task in a new spot VM*/}

14: if $\textbf{ not }scheduled$ then

15: $vm_{k}\leftarrow get\\_wrr\\_VM(M^{s})${/*Select a spot VM using the
weighted round-robin heuristic*/}

16: if $check\\_schedule(t_{i},vm_{k},D_{spot})$ then

17: $schedule(t_{i},vm_{k})$

18: $A\leftarrow A\cup\\{vm_{k}\\}$ {/*Update the set of selected VMs*/}

19: $M^{s}\leftarrow M^{s}\backslash\\{vm_{k}\\}$

20: $break$ {/*Schedule next task*/}

21: end if

22: end if

23:end for

24:$S\leftarrow create\\_solution(A)$

25:Return $S$ {*/Returns a scheduling solution $S$*/}

After obtaining an initial solution, the ILS algorithm tries to improve it by
applying local search and perturbation procedures (Algorithm 1, lines 4 \-
24). Thus, let $S$ be a solution that defines a scheduling map of all tasks
$t_{i}\in B$ to a subset of VMs of $M$. Let $fitness(S)$ be a weighted
function that assigns a value to the quality of $S$. Since this function is
equivalent to the objective function presented in Equation 1, we define in
Equation 8 the $fitness(S,D_{spot})$ function, where $cost$ is the total
monetary cost of $S$ and $mkp$ is the total execution time of the application.

$fitness(S,D_{spot})=\begin{cases}\infty,{\footnotesize\text{if violates
$D_{spot}$}}\\\
\alpha.cost+(1-\alpha).mkp,{\footnotesize\textit{otherwise}}\end{cases}$ (8)

Algorithm 1 executes a local search by calling, in line 4, the $local\\_seach$
procedure of Algorithm 3, which executes a series of attempts to improve the
current solution by swapping tasks between the selected VMs. Algorithm 3
receives as input the current solution $S$, the $max\\_attempt$ parameter that
determines the number of times the local search will be executed, the set $B$
and the $swap\\_rate\in]0,1]$ value that determines the number of tasks that
will be swapped at each iteration. The $swap\\_rate$ parameter is tuned before
the execution. All the parameters used in our tests, including the
$swap\\_rate$, $max\\_attempt$, $max\\_iteration$ and other parameters will be
presented in Section IV.

As can be observed in lines 5 and 9 of the Local Search algorithm (Algorithm
3), a solution $S$ is composed of two structures: (i) a vector, which controls
task allocation, where indexes correspond to tasks, and each element keeps the
identity of the VM that will execute the corresponding task, and (ii) a list
composed by selected VMs of $M$. Firstly, the algorithm computes the number of
tasks that will be swapped at each iteration (line 3) and randomly selects a
destination VM ($vm_{dest}$, line 5). After that, the algorithm starts the
tasks swapping procedure (lines 6 to 15), where $n$ tasks, also randomly
selected (line 8), are moved to the $vm_{dest}$. After each swap $movement$,
the $local\\_seach$ procedure checks if the quality of the new generated
solution has improved (line 10) and it updates the $S_{best}$ solution, if
necessary. In the end, the procedure returns the best-found solution (line
16).

Algorithm 3 Local Search

1:$S$, $max\\_attempt$, $swap\\_rate$ and  $D_{spot}$

2:$S_{best}\leftarrow S$

3:$n\leftarrow swap\\_rate\times|B|$

4:$attempt\leftarrow 0$

5:$vm_{dest}\leftarrow random\\_choice(S.selected\\_vms)$

6:while $attempt<max\\_attempt$ do

7: for $k\in\\{1,...,n\\}$ do

8: $t_{i}\leftarrow random\\_choice(B)$

9: $S.allocation\\_array[t_{i}]=vm_{dest}$

10: if $fitness(S,D_{spot})<fitness(S_{best},D_{spot})$ then

11: $S_{best}\leftarrow S$

12: end if

13: end for

14: $attempt\leftarrow attempt+1$

15:end while

16:return  $S_{best}$

After the first execution of the $local\\_search$ procedure (line 4),
Algorithm 1 has a loop that firstly performs a perturbation (lines 11-17) and
then a new local search (line 18). The perturbation is responsible for
diverting the metaheuristic from local optimal solutions. In the current work,
we use two simple perturbation strategies. The first one includes a not
selected spot $vm_{j}\in M^{s}$ into the current solution $S$ (lines 11-13).
The second one, called relaxing perturbation, increases the $D_{spot}$ limit
(lines 14-17). Note that the latter is executed only when the number of
iterations without finding a better solution (called $failed$ iterations) is
higher than the $max\\_failed$ parameter. In this case, the metaheuristic
increases the $D_{spot}$ limit in $relax\\_rate$ percent, where
$relax\\_rate\in]0,1]$ is also a parameter defined by the user.

Upon finishing the ILS (Part 1), Algorithm 1 executes the $burst\\_allocation$
procedure (Part 2, lines 25-27). A number of burstable VMs, which is a
percentage of the number of used spot VMs, $burst\\_rate$, are included in the
solution. Since the relaxed perturbation leads some tasks to violate the
$D_{spot}$ limit, the $burst\\_allocation$ procedure moves these tasks to the
burstable instances. Each of them can receive at most one task to be executed
in baseline mode. However, if there still exist tasks violating $D_{spot}$ and
no available burstable VM, the procedure allocates them to the cheapest
regular on-demand VMs. On the other hand, if a burstable VM remains idle, the
task with the latest finishing time in the scheduling map is moved to it.

Remark that our strategy of having a single task per burstable instance at a
time, executing in baseline mode, induces CPU credits accumulation.
Consequently, these burstable instances became the best candidates to receive
tasks in case of hibernations.

###  III-D Dynamic Scheduling Module

The Dynamic Scheduling Module performs some actions in response to events,
such as spot VM hibernation, resuming, and idleness, that may occur along with
the execution. Let BR, IR, HR, and TR of $M$ be the set of busy, idle,
hibernated, and terminated VMs respectively. Thus, Burst-HADS considers that a
$vm_{j}$ can be in one of the following states i) busy, if active and
executing tasks ($vm_{j}\in BR$); ii) idle, if active but not executing any
task ($vm_{j}\in IR$); iii) hibernated, if it has been hibernated by the cloud
provider ($vm_{j}\in HR$); and iv) terminated, if the VM has terminated or it
was not available at the beginning of the application execution ($vm_{j}\in
TR$).

One of the main goals of the Dynamic Scheduling Module is to decide when a VM
should terminate. On the one hand, as VMs are charged for each period of time
(see Section III-A), the user has an interest that a VM terminates as soon it
becomes idle, aiming for cost reduction and avoiding extra ones. On the other
hand, in some cases, it might be interesting to keep it because it can receive
and execute tasks without incurring deploying overhead. Hence, Burst-HADS has
a termination policy where the allocation time is logically divided into units
denoted Allocation Cycles (ACs). A $vm_{j}$ that reaches the end of its
current AC, denoted $AC\\_cur_{j}$, in idle state, is terminated.

The Dynamic Scheduling Module handles the following events related to a VM,
$vm_{j}$: i) $vm_{j}$ becomes idle; ii) $vm_{j}$, which is idle, reaches the
end of $AC\\_cur_{j}$; iii) $vm_{j}$ is a spot VM that hibernates; and iv)
$vm_{j}$, which has hibernated, resumes. The following actions are taken for
each of the events:

  * •

$vm_{j}$ becomes idle: When a $vm_{j}$ finishes the execution of all tasks
scheduled to it, its state is updated to idle and, if there exist scheduled
tasks that have not completely executed, a work-stealing procedure starts at
the beginning of the next $vm_{j}$’s $AC$, assigning some or all of these
tasks to $vm_{j}$, whose state is, thus, set to busy.

  * •

Non-burstable idle $vm_{j}$ reaches the end of $AC\\_cur_{j}$:

If at the end of $AC\\_cur_{j}$ a non-burstable $vm_{j}$ remains idle, it is
removed from the set IR of idle VMs and included into $TR$, the set of
terminated VMs.

  * •

Spot $vm_{j}$ hibernates: The $vm_{j}$’s state is updated to hibernated and if
it was $busy$, Burst-HADS starts the burst migration procedure (see Section
III-E).

  * •

Spot $vm_{j}$ resumes: When a hibernated spot $vm_{j}$ resumes, it is excluded
from $HR$, the set of hibernated VMs, and Burst-HADS starts a work-stealing
procedure that tries to move tasks from $busy$ VMs to $vm_{j}$ (see Section
III-F).

###  III-E Burst Migration Procedure

As previously explained, as soon as a spot $vm_{l}$ hibernates, Burst-HADS
executes the migration procedure, searching for a set of VMs to assign and
execute non-finished tasks, denoted affected tasks, that were previously
scheduled to $vm_{l}$. Algorithm 4 presents the migration procedure, which
always respects the deadline $D$ when selecting tasks to migrate. It receives
as input the set $Q_{l}\subset B$ of affected tasks, the sets of idle, busy,
and non-launched regular on-demand VMs ($IR$, $BR$ and $M^{o}$, respectively),
and the deadline $D$.

Algorithm 4 Burst Migration Procedure

1:$Q_{l}$, $IR$, $BR$, $M^{o}$,  and  $D$

2:$Q_{l}\leftarrow sort\\_tasks(Q_{l})$ {/* Prioritizes tasks with checkpoints
*/}

3:for each $t_{i}\in Q_{l}$ do

4: {/*Attempt 1 - Try to migrate task to a Burstable IDLE VM */}

5: for each burstable  $vm_{j}\in IR$ do

6: $rcc_{ij}\leftarrow\lceil e_{ij}/burst\\_period\rceil$

7: if $cc_{j}>rcc_{ij}\textbf{ and }check\\_migration(t_{i},vm_{j},D)$ then

8: $reserve\\_cpu\\_credits(rcc_{ij},vm_{j})$

9: $set\\_burst\\_mode(t_{i},vm_{j})$

10: $migrate(t_{i},vm_{j})$

11: $IR\leftarrow IR\backslash\\{vm_{j}\\}$

12: $BR\leftarrow BR\cup\\{vm_{j}\\}$

13: $break$ {/*Migrate next task*/}

14: end if

15: end for

16: if not $migrated$ then

17: {/*Attempt 2 - Try to migrate task to a NON-burstable Idle VM*/}

18: $sort\\_by\\_market(IR)$ {/* Prioritizes spot VMs */}

19: for each NON-burstable $vm_{j}\in IR$ do

20: if $check\\_migration(t_{i},vm_{j},D)$ then

21: $migrate(t_{i},vm_{j})$

22: $IR\leftarrow IR\backslash\\{vm_{j}\\}$

23: $BR\leftarrow BR\cup\\{vm_{j}\\}$

24: $break$ {/*Migrate next task*/}

25: end if

26: end for

27: end if

28: if not $migrated$ then

29: {/*Attempt 3 - Try to migrate task to a NON-burstable Busy VM*/}

30: $sort\\_by\\_market(BR)$ {/* Prioritizes spot VMs */}

31: for each NON-burstable $vm_{j}\in BR$ do

32: if $check\\_migration(t_{i},vm_{j},D)$ then

33: $migrate(t_{i},vm_{j})$

34: $break$ {/*Migrate next task*/}

35: end if

36: end for

37: end if

38: if not $migrated$ then

39: {/*Attempt 4 - Try to migrate task to a new NON-burstable on-demand VM*/}

40: $sort\\_by\\_price(M^{o})$

41: for each $vm_{j}\in M^{o}$ do

42: if $start_{ij}+e_{ij}+\alpha<D$ then

43: $start\\_vm(vm_{j})$

44: $migrate(t_{i},vm_{j})$

45: $M^{o}\leftarrow M^{o}\backslash\\{vm_{j}\\}$

46: $BR\leftarrow BR\cup\\{vm_{j}\\}$

47: $break$ {/*Migrate next task*/}

48: end if

49: end for

50: end if

51:end for

Initially, $Q_{l}$ is ordered, giving priority to those tasks that were
executing at the moment of the hibernation and had been previously
checkpointed (line 2). Burst-HADS applies the checkpoint/recovery mechanism
that we proposed and evaluated in our previous work [16] where checkpoints are
taken with the help of Checkpoint Restore In Userspace (CRIU) [17], a widely
used tool that records the state of individual applications. In order to avoid
the overhead of launching new VMs, the migration procedure gives priority to
the use of already launched VMs. For each task $t_{i}\in Q_{l}$ the algorithm
first tries to migrate the task to an idle burstable VM (lines 5 to 15).
Otherwise, it tries to schedule $t_{i}$ to one of the non-burstable idle VMs
of set $IR$ (lines 19 to 26). If not possible, it tries to schedule $t_{i}$ to
a non-burstable busy VM of set $BR$ (lines 31 to 36).

Tasks migrated to burstable VMs are executed in burst mode, i.e., using 100%
of the VM’s CPU processing power. Therefore, it is necessary to guarantee that
a selected burstable VM will have enough CPU credits to execute all tasks
assigned to it. Let $burst\\_period$ be the number of periods of $T$
corresponding to one credit consumption in burst mode. Since we consider that
a task $t_{i}$ is executed in only one core (see Section III-A), it is
possible to estimate (line 6) the number of CPU credits consumed by task
$t_{i}$, where $e_{ij}$ is the execution time of $t_{i}$ on $vm_{j}$ in burst
mode, and $rcc_{ij}$ is the estimated number of required CPU credits. Then,
the algorithm checks if $vm_{j}$ has enough CPU credits and call the
$check\\_migration$ function to guarantee that $vm_{j}$ has enough memory and
will execute $t_{i}$ before the deadline $D$ (line 7). If both conditions are
satisfied, the $rcc_{ij}$ CPU credits are reserved for $t_{i}$ (line 8), the
burst mode is set up (line 9), and $t_{i}$ is migrated to $vm_{j}$ (line 10).
In this case the burstable $vm_{j}$ is removed from set $IR$ and included in
set $BR$ (lines 11 and 12). Note that the cloud provider continuously updates
the number of credits, $cc_{j}$, of every burstable VM.

Moreover, when Algorithm 4 migrates a task $t_{i}$ to a non-burstable idle
$vm_{j}$, it also calls the function $check\\_migration$ to verify if the VM
has enough memory and will be able to finish the task before the deadline $D$
(lines 20 and 32). Furthermore, if $vm_{j}$ is a spot VM, the function
$check\\_migration$ should also verify if there will be enough spare time in
$vm_{j}$ between the end of the execution of $vm_{j}$ tasks (including task
$t_{i}$) and the deadline $D$ since, in this case, $vm_{j}$ is also subject to
hibernation. The spare time has to be greater than the execution time of the
longest task scheduled to $vm_{j}$, ensuring, therefore, that if a hibernation
occurs, there will be enough time to migrate and execute all affected tasks
before the deadline $D$.

Finally, if there does not exist any available already deployed VM able to
execute task $t_{i}$, the algorithm migrates the task to a new on-demand VM of
set $M^{o}$ (lines 41 to 49). In this case, it is necessary to verify that,
considering the start period of $t_{i}$ in $vm_{j}$ ($start_{ij}$), its
execution time ($e_{ij}$) plus the overhead $\alpha$ will not violate the
deadline (line 42). The new allocated on-demand VM is then removed from set
$M^{o}$ and included in set $BR$ (lines 45 and 46).

###  III-F Burst Work-Stealing

The work-stealing procedure, presented in Algorithm 5, aims at reducing the
allocation time of regular on-demand VMs as well as balancing the load of spot
VMs. It is triggered when a hibernated spot VM resumes or when a VM (spot or
on-demand) becomes idle. Basically, the procedure tries to move tasks from
non-burstable busy VMs to the idle VM.

For each non-burstable busy $vm_{j}\in BR$ the procedure selects the tasks
that can be stolen from it (line 4) and tries to migrate them to the idle
$vm_{k}$ (lines 5-15). Since regular on-demand VMs are more expensive than
spot ones, the procedure considers firstly the tasks from the former (line 2).

Similarly to the migration procedure, for each selected task of a $vm_{j}$,
the work-stealing procedure also verifies, by calling the function
$check\\_migration$, if the task migration would result in the deadline
violation (line 6). Since tasks migrated to burstable VMs by the work-stealing
procedure are executed in the baseline mode, after verifying if the idle
$vm_{k}$ is burstable (line 7), the algorithm sets up the execution to the
baseline mode (line 8). In this work, to set up a burstable VM to the baseline
mode means that the task cannot run using 100% of the CPU processing power,
but uses only the baseline performance defined by the
provider333https://docs.aws.amazon.com/AWSEC2/latest/WindowsGuide/burstable-
credits-baseline-concepts.html. To limit the CPU utilization, Burst-HADS uses
the cpulimit tool [18], an open-source program that limits the CPU usage of a
process in GNU/Linux. Moreover, if the idle $vm_{k}$ is burstable, only one
task is moved to it, to avoid a queue of tasks to be executed at the baseline
mode, which could increase the application total execution time. Thus, after
moving one task to the burstable $vm_{k}$ (line 10), the algorithm stops the
loop. Finally, if at least one task is migrated to $vm_{k}$, its state changes
to busy and, consequently, it is included into the set of busy VMs and removed
from the set of idle ones (lines 18 and 19).

Algorithm 5 Burst Work-Stealing Procedure

1:$BR$, $IR$, $vm_{k}$, $D$

2:$sort\\_by\\_market(BR)$ {/*Prioritizes non-burstable on-demand VMs*/}

3:for each NON-burstable $vm_{j}\in BR$ do

4: $S\leftarrow selectTasks(vm_{j})$ {/*Get tasks that can be stolen*/}

5: for each $t_{i}\in S$ do

6: if $check\\_migration(t_{i},vm_{k},D)$ then

7: if $vm_{k}$ is  burstable then

8: $set\\_baseline\\_mode(t_{i},vm_{k})$

9: $migrate(t_{i},vm_{k})$

10: stops the loop

11: else if $vm_{k}\textbf{ not }$ burstable then

12: $migrate(t_{i},vm_{k})$

13: end if

14: end if

15: end for

16:end for

17:if at least one task was stolen then

18: $BR\leftarrow BR\cup\\{vm_{k}\\}$

19: $IR\leftarrow IR\backslash\\{vm_{k}\\}$

20:end if

##  IV Experiments and Results

According to AWS, only spot VMs of types C3, C4, C5, M4, M5, R3, and R4 with
memory amount smaller than 100 GB are hibernation-prone. Therefore, in our
experiments, we used spot VMs C3 and C4 which are compute-optimized and have
high availability in the spot market
444https://aws.amazon.com/ec2/spot/instance-advisor/. Moreover, we also use
the T3.large instances that are the newest generation of the general proposed
burstable instances of EC2. Table II shows the computational characteristics
and the corresponding prices in on-demand and spot markets in September 2020.

Table II: VMs attributes

Type | #VCPUs | Memory | Price per Hour | Baseline
---|---|---|---|---
on-demand | spot | performance
C3.large | 2 | 3.75 GB | 0.105$ | 0.0299$ | -
C4.large | 2 | 3.75 GB | 0.100$ | 0.0366$ | -
C3.xlarge | 4 | 7.50 GB | 0.199$ | 0.0634$ | -
T3.large | 2 | 8 GB | 0.0832$ | - | 20%

In our experiments, we have considered two distinct workloads: i) synthetic
BoT applications composed by tasks generated with the application template
proposed in Alves et al. [3], and ii) the ED application available in the
GRIDNBP 3.1 suite of NAS benchmark [19]. The tasks of the synthetic
applications execute vector operations whose execution times depend on the
size of the vectors. Hence, several synthetic tasks are created, each one with
a memory footprint between 2.81 MB and 13.19 MB, resulting in execution times
which vary from 102 to 330 seconds. Then, we conceived three synthetic BoT
applications, J60, J80, and J100 by randomly selecting the tasks. Concerning
the ED application, a real embarrassingly distributed application, the job
ED200 is composed of 200 tasks solving the largest problem size (class B).

Table III shows the characteristics of the four jobs, including their
respective number of tasks and memory footprint. The same deadline $D=2700$
seconds (45 minutes) is considered for all evaluated jobs and experiments,
corresponding to the shortest deadline within which Burst-HADS can find a
feasible solution for all evaluated jobs, respecting the constraints defined
in Section III-A.

Table III: Characteristics of the Jobs

job | # tasks | memory footprint
---|---|---
min | avg | max
J60 | 60 | 2.85MB | 4.69MB | 12.20MB
J80 | 80 | 2.91MB | 4.71MB | 13.19MB
J100 | 100 | 2.81MB | 4.49MB | 10.86MB
ED200 | 200 | 153.74MB | 168.68MB | 177.77MB

For the execution of the ILS Primary Task Scheduling (Algorithms 1 and 3), the
following input parameters were empirically determined: $\alpha=0.5$,
$max\\_iteration=200$; $max\\_attempt=50$; $swap\\_rate=0.10$;
$max\\_failed=20$; $relaxed\\_rate=0.25$; $burst\\_rate=0.2$. Moreover, we
defined $AC=900$ seconds. As said in section III-E, Burst-HADS uses a
checkpoint approach proposed in [1]. In that approach, the user defines the
parameter $ovh$, the maximum percentage of time overhead that the checkpoint
mechanism is allowed to add in the original execution time of a task. From
this parameter, Burst-HADS defines the number of checkpoints of each task and
also the period between checkpoints. In this work, $ovh=10\%$ for all tests.

We have firstly evaluated Burst-HADS in a scenario without hibernation,
comparing it with (1) the schedule given by the proposed ILS using only on-
demand VMs and (2) the schedule given by HADS in a scenario without
hibernation. The aim of these experiments is to measure the impact in the
monetary cost and execution time of including burstable on-demand VMs into the
scheduling procedure. Table IV presents the average of three executions of the
synthetic jobs J60, J8, and J100, and the real application ED200, for each
case.

Table IV: Cost and Makespan of Burst-HADS and HADS, without hibernation; and ILS On-demand only.  JOB |  | Burst-HADS
---
Without Hibernation
| HADS
---
Without Hibernation
| ILS On-demand
---
cost | makespan | cost | makespan | cost | makespan
J60 | $0.112 | 1274 | $0.067 | 2290 | $0.271 | 1112
J80 | $0.151 | 1329 | $0.104 | 2295 | $0.312 | 1190
J100 | $0.176 | 1660 | $0.112 | 2332 | $0.371 | 1462
ED200 | $0.357 | 2275 | $0.267 | 2580 | $0.698 | 1887

In comparison with HADS, Table IV shows that Burst-HADS reduces the makespan
in 44.37%, 42.09%, 28.82%, and 11.82%, for jobs J60, J80, J100, and ED200,
respectively. However, the average monetary cost increases by 66.34%, 44.54%,
57.55%, and 33.71%, for the same comparison. The latter increases because
Burst-HADS already starts by using some burstable on-demand VMs Moreover, the
ILS based primary scheduling uses more VMs to reduce the execution time, while
in HADS, the initial scheduling aims at minimizing only the monetary cost.

On the other hand, compared to the ILS on-demand strategy, on average, Burst-
HADS reduces the monetary cost by more than 52.00%, with an average increase
of 15% in the makespan. The ILS on-demand strategy uses the scheduling plan
given by the ILS proposed in Algorithm 1, which does not include spot neither
burstable VMs, but only regular on-demand VMs. The longer makespan is due to
the execution of tasks in the baseline mode of burstable VMs, which does not
occur in the ILS on-demand strategy.

Since cloud users have no control over spot VM hibernations, we have emulated
different patterns of spot VM hibernations and resuming times by using Poisson
distribution [20] for each type of spot VM. We have applied distinct Poisson
functions for modeling the events in order to have distinct scenarios where
hibernating and resuming events have different probability mass functions
defined by the parameters $\lambda_{h}$ and $\lambda_{r}$, respectively. Let
the $\lambda$ parameter of Poisson distribution be the number of expected
events divided by a time interval. Since the application execution is
discretized by time interval and $D$ is the application deadline, if we
respectively define $k_{h}$ and $k_{r}$, as the expected number (rate) of
hibernating and resuming events during the application execution,
$\lambda_{h}$ and $\lambda_{r}$ parameters are given by $\lambda_{h}=k_{h}/D$
and $\lambda_{r}=k_{r}/D$. We should point out that, since we are considering
scenarios where multiple events can happen, the actual number of hibernation
(resp., resuming) events that occur in an experiment might be greater than
$k_{h}$ (resp., $k_{r}$). Table V presents five different scenarios by varying
$k_{h}$ and $k_{r}$.

Table V: Different execution scenarios generated by varying parameters
$\lambda_{h}$ and $\lambda_{r}$

ID | hibernating | resuming | $\lambda_{h}$ | $\lambda_{r}$
---|---|---|---|---
$sc_{1}$ | $k_{h}=1$ | $k_{r}=0$ | $1/2700$ | $0/2700$
$sc_{2}$ | $k_{h}=5$ | $k_{r}=0$ | $5/2700$ | $0/2700$
$sc_{3}$ | $k_{h}=1$ | $k_{r}=5$ | $1/2700$ | $5/2700$
$sc_{4}$ | $k_{h}=5$ | $k_{r}=5$ | $5/2700$ | $5/2700$
$sc_{5}$ | $k_{h}=3$ | $k_{r}=2.5$ | $3/2700$ | $2.5/2700$

Table VI presents the averages of three executions of jobs J60, J80, J100, and
ED200 using Burst-HADS and HADS in each of the five execution scenarios. For
each job and scenario, the table shows the average number of hibernations
followed by resume events. It also includes the number of non-burstable on-
demand VMs launched by the Dynamic Module of both Burst-HADS and HADS that
handle the hibernations as well as the average of monetary cost and makespan.
Finally, the two last columns represent the percentage difference between
Burst-HADS and HADS (diff) related to the monetary cost and the makespan.

Table VI: Comparison between Burst-HADS and HADS in terms of monetary cost and
makespan in scenarios $sc_{1}$ to $sc_{5}$

Job | scenario | # hibernations | # resume |  | # used regular on-demand VMs
---
Burst-HADS | HADS |  | Diff (%)
---
Burst-HADS | HADS | cost | makespan | cost | makespan | cost | makespan
J60 | $sc_{1}$ | 0.66 | 0.00 | 0.00 | 0.00 | $0.119 | 1274 | $0.091 | 2620 | -30.77% | 51.37%
$sc_{2}$ | 3.33 | 0.00 | 1.33 | 2.33 | $0.204 | 1277 | $0.257 | 2549 | 20.54% | 49.90%
$sc_{3}$ | 2.33 | 2.33 | 1.33 | 0.00 | $0.127 | 1752 | $0.101 | 2539 | -26.07% | 31.00%
$sc_{4}$ | 5.33 | 4.00 | 1.67 | 0.00 | $0.142 | 1857 | $0.119 | 2634 | -19.90% | 29.50%
$sc_{5}$ | 2.66 | 1.00 | 1.33 | 2.00 | $0.150 | 1445 | $0.169 | 2359 | 11.44% | 38.75%
J80 | $sc_{1}$ | 1.00 | 0.00 | 1.33 | 0.33 | $0.167 | 1419 | $0.150 | 2581 | -11.33% | 45.03%
$sc_{2}$ | 5.00 | 0.00 | 1.00 | 3.00 | $0.210 | 2267 | $0.298 | 2591 | 29.48% | 12.50%
$sc_{3}$ | 3.00 | 1.00 | 1.67 | 1.00 | $0.164 | 1367 | $0.147 | 2602 | -11.34% | 47.46%
$sc_{4}$ | 9.66 | 7.66 | 1.00 | 2.00 | $0.244 | 2488 | $0.212 | 2607 | -15.25% | 4.56%
$sc_{5}$ | 3.00 | 1.00 | 1.33 | 3.00 | $0.195 | 1589 | $0.246 | 2529 | 20.47% | 37.17%
J100 | $sc_{1}$ | 2.00 | 0.00 | 0.00 | 0.00 | $0.191 | 1798 | $0.157 | 2332 | -21.76% | 22.90%
’ | $sc_{2}$ | 7.00 | 0.00 | 1.33 | 3.00 | $0.212 | 1900 | $0.353 | 2518 | 39.94% | 24.54%
| $sc_{3}$ | 6.00 | 3.00 | 1.67 | 1.00 | $0.201 | 1925 | $0.166 | 2636 | -21.08% | 26.97%
| $sc_{4}$ | 11.00 | 9.00 | 1.00 | 0.00 | $0.286 | 2453 | $0.278 | 2591 | -2.88% | 5.33%
| $sc_{5}$ | 3.66 | 2.00 | 1.00 | 2.50 | $0.166 | 1547 | $0.189 | 2543 | 12.49% | 39.15%
ED200 | $sc_{1}$ | 3.00 | 0.00 | 1.00 | 0.33 | $0.388 | 2327 | $0.314 | 2680 | -23.57% | 13.17%
$sc_{2}$ | 8.00 | 0.00 | 2.00 | 5.00 | $0.482 | 2448 | $0.512 | 2676 | 5.86% | 8.52%
$sc_{3}$ | 6.66 | 4.00 | 2.33 | 1.00 | $0.427 | 2345 | $0.387 | 2672 | -10.34% | 12.24%
$sc_{4}$ | 9.00 | 6.00 | 2.00 | 1.00 | $0.411 | 2560 | $0.389 | 2690 | -5.66% | 4.83%
$sc_{5}$ | 4.33 | 2.33 | 1.67 | 3.00 | $0.367 | 2342 | $0.467 | 2674 | 21.41% | 12.42%

As can be observed in Table VI, Burst-HADS minimizes the makespan in all
execution cases, presenting an average reduction of 25.87%. As explained in
Section III-E, whenever a spot VM hibernates, Burst-HADS immediately migrates
the interrupted tasks to other VMs. Thus, the increment in the makespan is due
to the overhead of this procedure, which can include the launch of new VMs.
However, small jobs, i.e., jobs with fewer tasks, are less affected on those
scenarios than the biggest ones. For example, while for job J60, the average
makespan reduction, considering all scenarios, is 40.10%, for job ED200, that
reduction is only 10.24%. Such a behavior can be explained because, in our
experiments, we have fixed the same deadline for all jobs and, therefore,
small jobs have more spare time between its expected makespan defined by the
ILS and the deadline. Consequently, in this case, Burst-HADS benefits more
from the burst mode of the burstable VMs since it has more idle time to earn
CPU credits. Moreover, it also executes the work-stealing more frequently,
which also reduces the makespan.

On the other hand, independently of the scenario or job, HADS’s makespan get
closer to the deadline whenever a hibernation occurs. That happens because the
HADS framework postpones as much as possible the execution of the migration
procedure. Since HADS gives priority to the monetary cost save, its central
idea is to wait for a hibernated VMs resume and then avoid the launch of new
VMs.

In scenarios $sc_{2}$ and $sc_{5}$, Burst-HADS improved the monetary cost for
all jobs. The $sc_{2}$ is the worst execution case scenario, since it has the
highest rate of hibernation ($k_{h}=5$) and no resume rate ($k_{r}=0$), while
$sc_{5}$ is the average case scenario where the rate of hibernation is
$k_{h}=3.0$, and the rate of resume is $k_{h}=2.5$ (see Table V). In these
scenarios, Burst-HADS uses fewer regular on-demand VMs than HADS. Moreover, in
both cases, the number of hibernations is higher than the number of resumes.
Hence, compared to HADS, Burst-HADS is more efficient in minimizing the impact
of spot hibernations in those cases by migrating tasks to busy and idle VMs
and also to burstable VMs using the burst mode. It is worth pointing out that
the average increase of Burst-HADS makespan was 1.92%, considering all
executions.

Compared to the ILS On-demand, both Burst-HADS and HADS minimized the monetary
cost for all execution cases, presenting an average reduction of 41.80% and
39.65%, respectively. For job ED200, for example, the worst execution
scenario, $sc_{2}$, Burst-HADS reduced the monetary cost by 30.96%, while HADS
presented an average reduction of 26.66%.

##  V Conclusion and Future Work

This paper proposes the Burst Hibernation-Aware Dynamic Scheduler (Burst-
HADS), a dynamic scheduler that combines hibernation-prone spot VMs with
burstable ones for executing bag-of-task applications subject to a deadline.
The objective of the scheduler is to minimize both the makespan and the
monetary costs of the execution, respecting the application’s deadline even
when the spot VMs hibernate. Burst-HADS was evaluated in a real environment
using VMs of AWS EC2, considering scenarios with different hibernation and
resume rates.

The results show that compared to the ILS On-demand approach that uses only
regular on-demand VMs, Burst-HADS can reduce the monetary cost for all
execution scenarios at the expense of longer makespan due to the migration
overhead and the baseline mode of the burstable VMs. Furthermore, compared to
HADS, our previous proposed framework that uses only spot and on-demand VMs,
Burst-HADS can reduce the makespan by more than 25 %, with an average
increment of only 1.92% in the monetary cost. As future work, we intend to
include in the migration decision of Burst-HADS some predictions about the
future state of the spot market. For example, to consider which instance type
would improve the reliability of the execution. A second research direction
will be to conduct a study in order to determine which type of burstable VM
would offer the best tradeoff between price and performance in Burst-HADS.

## Acknowledgments

This research was supported by Programa Institucional de Internacionalização
(PrInt) from CAPES as part of the project REMATCH (process number
88887.310261/2018-00).

## References

  * [1] L. Teylo, L. Arantes, P. Sens, and L. M. Drummond, “A dynamic task scheduler tolerant to multiple hibernations in cloud environments,” _Cluster Computing_ , pp. 1–23, 2020.
  * [2] H. R. Lourenço, O. C. Martin, and T. Stützle, “Iterated local search,” in _Handbook of metaheuristics_. Springer, 2003, pp. 320–353.
  * [3] M. M. Alves and L. M. de Assumpção Drummond, “A multivariate and quantitative model for predicting cross-application interference in virtual environments,” _Journal of Systems and Software_ , vol. 128, pp. 150 – 163, 2017.
  * [4] P. Leitner and J. Scheuner, “Bursting with possibilities–an empirical study of credit-based bursting cloud instance types,” in _IEEE/ACM 8th International Conference on Utility and Cloud Computing (UCC)_ , 2015, pp. 227–236.
  * [5] A. Ali, R. Pinciroli, F. Yan, and E. Smirni, “Cedule: A scheduling framework for burstable performance in cloud computing,” in _IEEE International Conference on Autonomic Computing (ICAC)_ , 2018, pp. 141–150.
  * [6] Y. Jiang, M. Shahrad, D. Wentzlaff, D. H. Tsang, and C. Joe-Wong, “Burstable instances for clouds: Performance modeling, equilibrium analysis, and revenue maximization,” in _IEEE INFOCOM Conference on Computer Communications_ , 2019, pp. 1576–1584.
  * [7] R. K. Mehta and J. Chandy, “Leveraging checkpoint/restore to optimize utilization of cloud compute resources,” in _IEEE 40th Local Computer Networks Conference Workshops (LCN Workshops)_ , 2015, pp. 714–721.
  * [8] A. F. Baarzi, T. Zhu, and B. Urgaonkar, “Burscale: Using burstable instances for cost-effective autoscaling in the public cloud,” in _ACM Symposium on Cloud Computing_ , 2019, pp. 126–138.
  * [9] C. Wang, B. Urgaonkar, A. Gupta, G. Kesidis, and Q. Liang, “Exploiting spot and burstable instances for improving the cost-efficacy of in-memory caches on the public cloud,” in _Twelfth European Conference on Computer Systems_ , 2017, pp. 620–634.
  * [10] L. Teylo, L. Arantes, P. Sens, and L. M. d. A. Drummond, “A bag-of-tasks scheduler tolerant to temporal failures in clouds,” in _31st International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD)_ , 2019, pp. 144–151.
  * [11] J. Fabra, J. Ezpeleta, and P. Álvarez, “Reducing the price of resource provisioning using ec2 spot instances with prediction models,” _Future Generation Computer Systems_ , vol. 96, pp. 348–367, 2019.
  * [12] J. D. Ullman, “Np-complete scheduling problems,” _Journal of Computer and System sciences_ , vol. 10, no. 3, pp. 384–393, 1975.
  * [13] M. Katevenis, S. Sidiropoulos, and C. Courcoubetis, “Weighted round-robin cell multiplexing in a general-purpose atm switch chip,” _IEEE Journal on selected Areas in Communications_ , vol. 9, no. 8, pp. 1265–1279, 1991.
  * [14] J. J. Dongarra, P. Luszczek, and A. Petitet, “The linpack benchmark: past, present and future,” _Concurrency and Computation: practice and experience_ , vol. 15, no. 9, pp. 803–820, 2003.
  * [15] D. Kumar, G. Baranwal, Z. Raza, and D. P. Vidyarthi, “A survey on spot pricing in cloud computing,” _Journal of Network and Systems Management_ , vol. 26, no. 4, pp. 809–856, 2018.
  * [16] L. Teylo, R. C. Brum, L. Arantes, P. Sens, and L. M. d. A. Drummond, “Developing checkpointing and recovery procedures with the storage services of amazon web services,” in _49th International Conference on Parallel Processing-ICPP: Workshops_ , 2020, pp. 1–8.
  * [17] P. EMELYANOV, “Criu: Checkpoint/restore in userspace, july 2011,” _URL: https://criu. org_ , 2011.
  * [18] “cpu limit tool,” Available: http://cpulimit.sourceforge.net/.
  * [19] D. Bailey, T. Harris, W. Saphir, R. Van Der Wijngaart, A. Woo, and M. Yarrow, “The nas parallel benchmarks 2.0,” Technical Report NAS-95-020, NASA Ames Research Center, Tech. Rep., 1995.
  * [20] J. H. Ahrens and U. Dieter, “Computer methods for sampling from gamma, beta, poisson and bionomial distributions,” _Computing_ , vol. 12, no. 3, pp. 223–246, 1974.