S De Liberato

D Gerace

I Carusotto

C Ciuti

Extracavity quantum vacuum radiation from a single qubit

Keywords: numbers: 03, 70, +k; 42, 50, Pq, 85, 35, Gv

We present a theory of the quantum vacuum radiation that is generated by a fast modulation of the vacuum Rabi frequency of a single two-level system strongly coupled to a single cavity mode. The dissipative dynamics of the Jaynes-Cummings model in the presence of anti-rotating wave terms is described by a generalized master equation including non-Markovian terms. Peculiar spectral properties and significant extracavity quantum vacuum radiation output are predicted for state-ofthe-art circuit cavity quantum electrodynamics systems with superconducting qubits.

Cavity quantum electrodynamics (CQED) is a very exciting and active research field of fundamental quantum physics, characterized by an unprecedented control of light-matter interaction down to the single quantum level [1]. A number of different systems and a wide range of electromagnetic frequencies are presently being explored in this context, including Rydberg atoms in superconductor microwave cavities [1], alkali atoms in high-finesse optical cavities [2,3], single quantum dots in semiconductor optical nanocavities [4,5], superconductor Cooper pair quantum boxes in microwave strip-line resonators [6,7,8,9].

Most of the research in CQED has so far concerned systems whose properties are slowly varying in time with respect to the inverse resonance frequency of the cavity mode. Only very recently, experiments with semiconductor microcavities [10] have demonstrated the possibility of modulating the vacuum Rabi coupling on a time scale comparable to a single oscillation cycle of the field. For this novel regime, theoretical studies have anticipated the possibility of observing a sizeable emission of quantum vacuum radiation [11] via a process that is closely reminiscent of the still elusive dynamical Casimir effect [12]: the modulation of the Rabi coupling provides a modulation of the effective optical length of the cavity, and it is analogous to a rapid displacement of the cavity mirrors.

A recent paper [13] has applied this general scheme to a Jaynes-Cummings (JC) model in the presence of a fast modulation of the artificial atom resonance frequency. However, as the theoretical model did not include dissipation, the predictions were limited to short times and were not able to realistically describe the system steady state. In particular, no quantitative estimation of the extracavity radiation intensity was provided.

In the present Letter, we introduce a full quantum theory to describe the non-adiabatic response of a JC model including both the anti-rotating wave terms of the lightmatter interaction and a realistic dissipative coupling to the environment. While the former terms are responsi-ble for the generation of photons out of the non-trivial ground state [11,14], radiative coupling to the external world is essential to detect the generated photons as emitted radiation. Our attention will be focussed on the most significant case of harmonic temporal modulation of the vacuum Rabi coupling of superconducting qubits in circuit CQED systems: for fast, yet realistic [15,[START_REF]A modulation of the microwave cavity frequency on a time scale fast as compared to γ, still slow as compared to ω0 has[END_REF] modulations of the vacuum Rabi coupling, the photon emission turns out to be significant even in the presence of a strong dissipation. Furthermore, in contrast to other systems that have been proposed in view of observing the dynamical Casimir effect [17,18,19,20], the intrinsic quantum nonlinear properties of the two-level system should allow experimentalists to isolate the vacuum radiation from the parametric amplification of pre-existing thermal photons.

In addition to its importance concerning the observation of the dynamical Casimir effect, the theory developed here appears of great interest also from the general point of view of the quantum theory of open systems [START_REF] Breuer | The theory of open quantum systems[END_REF]. As a consequence of the anti-rotating wave terms in the Hamiltonian, the ground state of the system contains a finite number of photons. In order for the theory not to predict unphysical radiation from these bound, virtual photons [START_REF] Ciuti | [END_REF], the theoretical model has to explicitly take into account the colored nature of the dissipation bath. This suggests circuit CQED systems as unique candidates for the study of non-Markovian effects in the dissipative dynamics of open quantum systems.

A sketch of the system under consideration is shown in the left panel of Fig. 1. The theoretical description of its dynamics is based on the Jaynes-Cummings Hamiltonian:

Ĥ(t) = ω 0 â † â + ω ge ĉ † ĉ + g(t)(â + â † )(ĉ + ĉ † ) . (1)
whose ladder of eigenstates is schematically drawn in the right panel. Here, â † is the bosonic creation operator of a cavity photon and ĉ † is the raising operator describing the excitation of the two-level system (qubit), ĉ † |g = |e , where |g and |e are its ground and excited states, re- A single two-level system (qubit) is strongly coupled to a single cavity mode. A possible realization of such a device consists of a Cooper pair quantum box embedded in a microwave resonator. Right panel: schematic representation of the JC ladder of eigenstates of the isolated system in the absence of modulation, dissipation and anti-rotating wave terms. In this limit, the eigenstates |n, ± = (|n, g

± |n -1, e )/ √ 2 have energies En,± = nω0 ± √ ng0.
spectively; ω 0 is the bare frequency of the cavity mode and ω ge is the qubit transition frequency. The term proportional to g(t) describes the vacuum Rabi coupling between the two-level system and the cavity mode and fully includes those anti-resonant, non-rotating wave processes that are generally neglected in the so-called rotating-wave approximation (RWA).

While the RWA has provided an accurate description of most physical CQED systems [1,2,3,4,5,6,7,8,9], it becomes inaccurate as soon as one enters the so-called ultrastrong coupling regime, i.e. when the Rabi coupling, g, is comparable to the resonance frequencies, ω 0 and ω ge . This regime has been recently achieved in a solid state device consisting of a dense two-dimensional electron gas with an intersubband transition coupled to a microcavity photon mode [23]. Values of the g/ω ge ratio of the order of 0.01 (approaching the so-called fine structure constant limit) have been recently observed also in circuit CQED systems, and even larger values have been predicted for more recent unconventional coupling configurations [24]. Fully taking into account the anti-RWA terms is even more crucial in the experimentally novel [10,15] regime where the Rabi frequency g(t) is modulated in time at frequencies comparable or higher than the qubit transition frequency. In fact, in this regime of non-adiabatic modulation the anti-RWA terms may lead to the emission of quantum vacuum radiation, a phenomenon that would be completely overlooked if these terms were neglected. As we show in this Letter, a significant amount of quantum vacuum radiation with peculiar spectral features can be already expected for moderate values of g/ω ge , i. e. compatible with already existing circuit CQED samples.

In order to fully describe the quantum dynamics of the system, the JC model has to be coupled to its environment. A simple description involves two thermal baths, corresponding to the radiative and non-radiative dissipation channels. The non-Markovian nature of the baths is taken into account by means of a so-called second order time-convolutionless projection operator method [START_REF] Breuer | The theory of open quantum systems[END_REF], which gives a master equation of the general form

dρ dt = 1 i [ Ĥ, ρ]+ j=cav,ge Ûj ρ Ŝj + Ŝj ρ Û † j -Ŝj Ûj ρ -ρ Û † j Ŝj , (2)
where Ŝcav = (â + â † )/ , Ŝge = (ĉ + ĉ † )/ , and Ûj are given by integral operators as

Ûj = ∞ 0 v j (τ )e -i Ĥτ Ŝj e i Ĥτ dτ, (3)
v j (τ ) = ∞ -∞ γ j (ω) 2π [n j (ω)e iωτ + (n j (ω) + 1)e -iωτ ]dω. ( 4
)
The energy-dependent loss rates, γ j (ω), for the cavity (i.e. j = cav) and for the qubit transition (j = ge) are related to the density of states at energy ω in the baths, and thus they must be set to zero for ω < 0.

In the numerical simulations, we used the simple form γ j (ω) = γ j Θ(ω) for the non-white loss rates, where Θ(ω) is the Heaviside step function. In the following, the background number of thermal excitations at energy ω in the corresponding bath will be set as n j (ω) = 0. The usually employed master equation (see, e.g., Ref. [25]) can be obtained from Eq. ( 2) by assuming the baths to be perfectly white, i.e. γ j (ω) = γ j . By doing so, one implicitly introduces unphysical negative-energy radiative photon modes, incorrectly leading to the unphysical emission of light out of the vacuum state even in absence of any modulation [25].

In the present Letter, we shall focus on the steady state of the system under a harmonic modulation of the form

g(t) = g 0 + ∆g sin(ω mod t) , (5)
where ∆g and ω mod are the modulation amplitude and frequency, respectively. Direct application to the present JC model of the input-output formalism, e.g. discussed in Ref. [START_REF] Ciuti | [END_REF], leads to the following expression for the spectral density of extracavity photons emitted per unit time

S(ω) = γ cav (ω) 2π G(ω) (6)
in terms of the intra-cavity field spectrum, G(ω). As a consequence of the (harmonic) modulation g(t), the spectrum G(ω) involves a temporal average over the modulation period T mod = 2π/ω mod ,

G(ω) = 1 T mod T mod 0 dt ∞ -∞ dτ e -iωτ T r{â † (t + τ )â(t)ρ} . (7)
The cavity field operators â(t) are defined here in the Heisenberg picture.

The total number of extracavity photons emitted per unit time is given by 1.9 the spectral integral R em = ∞ -∞ dωS(ω). This formula is to be contrasted with the one giving the time-average of the intracavity photon number, N in = T -1 mod T mod 0 dt T r{â † (t)â(t)ρ}. The master equation ( 2) is numerically solved by representing â and ĉ on a basis of Fock number states. The operators Ŝ and Û are also numerically built and all the time evolutions are performed by a Runge-Kutta algorithm. Examples of numerical results are shown in Figs. 2 and3 for the resonant case (ω 0 = ω ge ), but we have checked that the qualitative features do not change when we introduce a finite detuning. Realistic parameters for circuit CQED systems are considered, as indicated in the caption.

In Fig. 2 we show the steady-state rate of emitted photons as a function of the modulation frequency, ω mod , for the case of a weak modulation amplitude, ∆g/γ ≪ 1. In this regime, the spectra are dominated by two resonant peaks close to

ω mod ≃ ω 2,± = 2ω 0 ± √ 2 g 0 [26]
. Thanks to the relatively small value of g 0 /ω 0 = 0.02 considered here, the position of the two peaks can be interpreted within the standard RWA in terms of transitions from the vacuum state to the doubly-excited states of the JC ladder in the isolated system, |2, ± ; the anti-RWA terms in the Hamiltonian that are responsible and essential for the quantum vacuum radiation instead provide only a minor correction to the spectral position of the peaks.

As typical of the dynamical Casimir effect, the periodic

ω 2,- ω mod = ω 2,+ ω mod = ω 2,- ω 0 ω 0 ω 2,+ ω 1,+ ω 1,- 0 ω 2,- ω 0 ω 0 ω 2,+ ω 1,+ ω 1,- 0 (x 10 ) -3 (x 10 ) -3
FIG. 3: Spectrally resolved emission per unit time for given values of the modulation frequency: ω mod = ω2,-(top panel), ω mod = ω2,+ (bottom panel). The modulation amplitude is ∆g/γ = 0.1. The insets illustrate the optical transitions responsible for the different emission lines that are visible in the main panels. For the sake of clarity, the level spacings in the insets are not in scale. modulation of the system parameters is only able to create pairs of excitations out of the vacuum state. However, in contrast to the usual case of (almost) non-interacting photons or bosonic polaritons [17,18,19], the nonlinear saturation of the two-level system is crucial here to determine the position of the peaks. This remarkable fact provides a unique spectral signature to separate the vacuum radiation from spurious processes such as the parametric amplification of thermal radiation. In fact, due to the anharmonicity of the Jaynes-Cummings spectrum, the resonant modulation frequency for the process having the ground state (vacuum) as initial state is different from other processes having a (thermal) excited state as initial state.

The conceptual difference between the emission rate R em and in-cavity photon number N in is illustrated in Fig. 2: standard Markovian theories would in fact predict the emission rate to be rigorously proportional to the intra-cavity photon number. Even though a reasonable agreement is observed around the peaks, this approximation leads to the unphysical prediction of a finite emission even in the absence of a modulation ∆g = 0 or for a modulation very far from resonance. Inclusion of the non-Markovian nature of the baths is able to eliminate this pathology by correctly distinguishing the virtual, bound photons that exist even in the ground state from the actual radiation [11,[START_REF] Ciuti | [END_REF].

The emission spectra S(ω) at a fixed and resonant value of the modulation frequencies ω mod = ω 2,± are shown in the two panels of Fig. 3. Thanks to the relatively weak value ∆g/g 0 = 0.01 (∆g/γ = 0.1) of the modulation amplitude considered here, the position of the main emission lines can be again understood in terms of transitions between eigenstates of the JC ladder. As shown in the insets, two spectral lines (red and blue, full lines in the schemes) correspond to radiative decay (emission) of the |2, ± states into the lower |1, ± states of the JC ladder, while the other two emission peaks (black and green, dashed lines) correspond to the radiative decay of the |1, ± states into the ground state. This interpretation is confirmed by the observation that the position of the former (latter) lines depends (does not depend) on the specific value of the modulation frequency ω mod chosen. The significant difference of spectral weight between the lines is due to interference effects in the radiative matrix element between JC eigenstates, 1, ±|â|2, ± . Stronger modulations (not shown) lead to distortion of the spectra as a result of significant spectral shifts and mixing of the dressed states.

The behavior of the exact numerical results can be understood in terms of a simplified two-state model. When the modulation frequency is close to resonance with one of the ω mod = ω 2,± peaks, the dynamics of the system is mostly limited to the |0 and |2, ± states, all other states in the JC ladder being far off-resonant [3]. The modulation in Eq. ( 5) is responsible for an effective coupling between such two states, quantified by Ω R ≃ ∆g/ √ 2 [19]. As a result, the probability of being in the excited state has the usual saturable Lorentzian shape

P |2,± ≃ (∆g) 2 /2 Γ 2 + (∆g) 2 + 4δ 2 2,± . (8)
Here, Γ = [γ ge + 3 γ cav ]/2 is the total (radiative + nonradiative)decay rate of the excited |2, ± state (in the case ω cav = ω ge ), and δ 2,± = ω modω 2,± is the detuning of the modulation frequency. By considering all the possible emission cascades (see insets of Fig. 3), the radiative emission rate in the neighborhood of a peak is then approximately given by

R em ≃ P |2,± γ cav 3γ cav + 2γ ge γ cav + γ ge . (9)
This analytical expression is in excellent agreement with the exact numerical results for ω mod ≃ ω 2,± . It is interesting to note that for typical parameters taken from state-of-the art circuit CQED devices, such as a resonance frequency ν 0 = ω 0 /2π ∼ 7 GHz [9] and (overestimated) decay rates γ/2π = 14 MHz, a resonant, yet quite small modulation amplitude ∆g/γ = 0.1 can already lead to a sizeable emission intensity, R em ≃ 4 × 10 4 photons/second. As clearly shown by the analytical expression in Eq. ( 9), a further enhancement of the emission rate can be obtained for much smaller decay rates, such as γ/2π 1 MHz recently measured in the latest experiments [7,8,9].

In conclusion, we have presented and solved a complete theory of the quantum vacuum emission that is generated from a single mode cavity with an embedded two-level system when the vacuum Rabi frequency of the light-matter interaction is modulated at frequencies comparable to the cavity (emitter) resonance frequency. Our theory fully takes into account the anti-RWA terms of the light matter-interaction, as well as the radiative and nonradiative dissipation channels. This has required extending the standard master equation treatment to include non-Markovian effects due to the necessarily colored nature of any realistic dissipation bath. The sizable value of the emission intensity that results from our numerical predictions suggests the promise of superconductor Cooper quantum boxes in microwave resonators for studies of quantum vacuum radiation phenomena.

The authors wish to thank M. Devoret, A.V. Dodonov, S. Girvin, and R. Schoelkopf for discussions.

FIG. 1 :

 1 FIG.1: Left panel: sketch of the system under consideration. A single two-level system (qubit) is strongly coupled to a single cavity mode. A possible realization of such a device consists of a Cooper pair quantum box embedded in a microwave resonator. Right panel: schematic representation of the JC ladder of eigenstates of the isolated system in the absence of modulation, dissipation and anti-rotating wave terms. In this limit, the eigenstates |n, ± = (|n, g ± |n -1, e )/ √ 2 have energies En,± = nω0 ± √ ng0.

FIG. 2 :

 2 FIG.2: Extracavity photon emission rate Rem(units of ω0) as a function of the modulation frequency, ω mod , for a modulation amplitude of the vacuum Rabi frequency ∆g/γ = 0.1. Parameters: ω0 = ωge; γ = γcav = γge = 0.002ω0; g0 = 0.02ω0. For comparison, the dashed line shows the extracavity emission rate γcavNin (where Nin is the steady-state intracavity photon number) that would be predicted by the Markovian approximation: note the unphysical prediction of a finite value of the emission even far from resonance.


Luan Teylo

Luciana Arantes

Pierre Sens

L Úcia

Maria De A Drummond

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

Keywords: Cloud Computing, BoT Scheduling, Burstable VMs, Spot VM Hibernation !

Cloud providers offer several types of Virtual Machines (VMs) in diverse markets, with different guarantees in terms of availability and reliability. Among them, the most popular market models are the on-demand and the spot. On-demand VMs are allocated for a fixed cost per time, and their availability is ensured during the whole execution. On the other hand, in the spot market, VMs are offered with a huge discount, but their availability fluctuates according to cloud's current demand that can terminate or hibernate a spot VM at any time. Furthermore, to cope with workload variations, cloud providers have also introduced the concept of burstable VMs, which can burst up their CPU performance during a limited period of time. In this work, we present the Burst Hibernation-Aware Dynamic Scheduler (Burst-HADS), a framework that executes Bag-of-Tasks applications with deadline constraints by exploiting both spot and on-demand burstable VMs, aiming at minimizing both the monetary cost and the execution time. Performance results on Amazon EC2 show that Burst-HADS reduces the monetary cost and meets the application deadline even in spot hibernation scenarios, when compared to other approaches from the related literature which uses only spot and non-burstable on-demand instances.

INTRODUCTION

In the past few years, cloud computing has emerged as an attractive solution to execute different applications. It brings several advantages compared with dedicated infrastructure, as, for example, a significant reduction in operational costs. However, in cloud environments, besides the usual goal of minimizing the application's execution time, it is also essential to reduce the monetary cost because even though in the cloud, computational resources are virtually infinite, the user's budget is not.

Cloud platforms enable users to dynamically acquire computational resources wrapped as Virtual Machines (VMs), that can be selected by the users according to their application requirements (CPU, memory, I/O, etc.) in a payas-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 called markets): i) reserved market, where the user pays an upfront price, guaranteeing long-term availability; ii) ondemand 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, but such resources can be requested at any time.

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,

• Luan Teylo and L úcia Maria de A. Drummond are with the Institute of Computing, Federal Fluminense University, Brazil.

• Luciana Arantes and Pierre Sens are with Sorbonne Université, CNRS, Inria, France.

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" 1 . Instances types are grouped into families based on their respective use cases.

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, with which the user agreed to be charged.

Besides the markets, some leading cloud providers (e.g. Microsoft Azure, Amazon EC2), introduced in the last years the concept of a 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 credits. They can then accumulate CPU credits per hour, whose amount also 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 the latter needs to burst above the baseline performance level, it spends the accrued credits. The higher the number of credits that a burstable instance has accumulated, 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 neither hibernation. 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 defining bursting periods. In Amazon EC2, burstable VMs are of type T3, T3a, or T2 [START_REF] Services | Burstable performance instances[END_REF].

In the current work, we consider Bag-of-Tasks (BoT) applications, which are commonly used in solving various science and engineering problems, such as parameter sweep, chromosome mapping, Monte Carlo simulation and computer imaging applications [START_REF] Thai | A survey and taxonomy of resource optimisation for executing bag-of-task applications on public clouds[END_REF]. As the interconnection network is not the bottleneck for the good performance of this type of applications, it is possible to speed up them by distributing their tasks on a large number of VMs in the cloud. In this context, an important issue is the definition of an efficient initial scheduling for the tasks which minimizes both the execution time and the financial cost, typically conflicting objectives. To this end, we propose to mathematically formulate it as a multi-objective integer programming problem and/or solve it by applying metaheuristics efficiently. Furthermore, for many of such applications, cost optimization algorithms should respect a given deadline, otherwise, a temporal failure takes place. Considering that the application executes on spot VMs that can be revoked/hibernated, we should provide a second scheduler, denoted dynamic scheduler, which would be responsible for provisioning new VMs and migrating tasks between different VMs, if necessary.

Therefore, this article presents a framework for scheduling Bag-of-Tasks (BoT) applications with deadline constraints, exploring hibernate-prone spot instances and ondemand burstable instances aiming at minimizing both the monetary cost and the execution time of applications. The proposed framework, denoted Burst Hibernation-Aware Dynamic Scheduler (Burst-HADS), is an eventdriven 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 in case of hibernation.

In a previous work [START_REF] Teylo | A dynamic task scheduler tolerant to multiple hibernations in cloud environments[END_REF], we have explored the use of hibernation-prone spot instances to minimize the monetary cost of BoT applications execution, respecting their deadline constraints. To meet such a deadline, even in the presence of multiple hibernations, new on-demand VMs, not allocated in the initial mapping, could 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 may considerably increase when compared to a solution that uses only on-demand instances. Hence to tackle such a problem, in this article, we investigate how burstable instances can be used to reduce the impact on the execution time of the application and the corresponding monetary costs. We also propose a formulation of the task scheduling problem as a multi-objective integer programming problem (execution time and financial cost objectives), and a heuristic based on the Iterated Local Search (ILS) [START_REF] Lourenc ¸o | Iterated local search[END_REF] method for generating the initial scheduling map.

Applying different scenarios, we have studied and evaluated our proposed framework. The results show that the burstable instance based approach can optimize the monetary cost without degrading the application execution time, even in the presence of several hibernations. The evaluation of Burst-HADS targeted different issues. Firstly, we focused on the new proposed Iterated Local Search (ILS) based primary scheduler. The ILS approach was compared to optimal solutions given by the exact model of the problem and also with three widely used scheduling heuristics: MinMin, MaxMin and Greedy [START_REF] Gutierrez-Garcia | A family of heuristics for agent-based elastic cloud bag-of-tasks concurrent scheduling[END_REF]. Next, we conducted a series of experiments with a real scenario using the Amazon EC2 cloud [START_REF] Services | Amazon ec2 instance types[END_REF], where Burst-HADS was compared to three other approaches: (i) a baseline case where only on-demand VMs are used, (ii) HADS, proposed in our previous work [START_REF] Teylo | A dynamic task scheduler tolerant to multiple hibernations in cloud environments[END_REF], and (iii) an approach based on AutoBoT [START_REF] Varshney | Autobot: Resilient and costeffective scheduling of a bag of tasks on spot vms[END_REF], a BoT scheduler that also exploits spot VMs to minimize the monetary cost while meeting the deadline defined by the user. To the best of our knowledge, AutoBoT is the closest to our work in the literature. However, since it considers the old EC2 price model, which was based on price history and spot market bid, and its original code is not available, we have implemented a version of AutoBot, denoted AutoBot-like, adapting some procedures of it to the current EC2 price model, defined by the supply and demand of spare resources. Performance results with experiments using both real and synthetic BoT applications in different scenarios subject to several spot VM hibernations and resuming events confirm the effectiveness of Burst-HADS in terms of monetary costs and execution times when compared to the other approaches.

The remainder of this paper is organized as follows. Section 2 discusses some related work, including the description of AutoBot and HADS, used in our analysis. Section 3 presents the mathematical formulation and the primary and dynamic modules of the Burst-HADS framework. The evaluation results of both the ILS based primary scheduling module and the dynamic module are presented in Section 4. Finally, Section 5 concludes the paper and introduces some future directions.

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 performance gain obtained by using burstable VMs. In [START_REF] Leitner | Bursting with possibilities-an empirical study of credit-based bursting cloud instance types[END_REF], Leitner and Scheuner presented a first empirical and analytical study about the second generation of AWS burstable instances (T2 family). They considered the T2.micro, T2.small, and T2.medium instances. Their work aimed at answering if, in terms of monetary cost and performance, these instance types are more effective than other ones. The results show that compared to generalpurpose 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%. To figure out the CPU usage limits on-the-fly, considering the dynamic variation of workloads, Ali et al. proposed in [START_REF] Ali | Cedule: A scheduling framework for burstable performance in cloud computing[END_REF] an autonomic framework that combines light-weight profiling and an analytical model. The objective was 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 Leitner and Scheuner's work [START_REF] Leitner | Bursting with possibilities-an empirical study of credit-based bursting cloud instance types[END_REF], their results also confirmed the benefits of active CPU usage control when burstable instances are exploited.

Jiang et al. [START_REF] Jiang | Burstable instances for clouds: Performance modeling, equilibrium analysis, and revenue maximization[END_REF] analytically modeled the performance of burstable VMs, considering their configurations, such as CPU, memory, and CPU credits parameters. They also showed that providers could 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 interesting since it states that providers can offer burstable instances for low prices without losing revenue while meeting QoS parameters.

Other works take advantage of burstable instance features in scheduling and scaling problems. In [START_REF] Baarzi | Burscale: Using burstable instances for cost-effective autoscaling in the public cloud[END_REF], for example, Baarzi et al. proposed an autoscale tool denoted BurScale, which uses burstable instances, together with ondemand ones, in order to handle transient queuing which arises due to traffic variation. They also presented how burstable instances can mask VM startup/warmup costs when autoscaling, which handles flash crowds, takes place. Using two distinct workloads, a stateless web server cluster and a stateful Memcached caching cluster, the authors showed that a careful combination of burstable and regular instances ensures similar performance for applications as traditional autoscaling systems while reducing up to 50% of the monetary cost. In [START_REF] Wang | Exploiting spot and burstable instances for improving the costefficacy of in-memory caches on the public cloud[END_REF], Wang et al. combined on-demand, spot, and burstable instances proposing an in-memory distributed storage approach. Burstable instances were 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 using burstable instances presents latency 25% lower than the latency of backup based on regular instances, inducing, therefore, a significant monetary cost saving.

Spot and on-demand instances have received a lot of attention in applications scheduling [START_REF] Varshney | Autobot: Resilient and costeffective scheduling of a bag of tasks on spot vms[END_REF], [START_REF] Subramanya | Spoton: a batch computing service for the spot market[END_REF], [START_REF] Menache | On-demand, spot, or both: Dynamic resource allocation for executing batch jobs in the cloud[END_REF], [START_REF] Sharma | Spotcheck: designing a derivative iaas cloud on the spot market[END_REF], [START_REF] Teylo | A bag-of-tasks scheduler tolerant to temporal failures in clouds[END_REF], [START_REF] Pham | Evolutionary multi-objective workflow scheduling for volatile resources in the cloud[END_REF]. Most of those works cope with termination/revocation of spot VMs and do not consider the hibernation feature. Moreover, the majority of them exploit the historical of spot VM price variation to predict spot VMs' revocations. However, since EC2 adopted a new price model (announced in December 2017), prices of VMs in the spot market are quite stable and defined exclusively by the supply and demand of spare capacity and no more by bid prices 2 . Therefore, it is no longer possible to predict the revocation/termination of spot VMs based only on the history of price variations as those works do.

To the best of our knowledge, the hibernation mechanism of the spot VMs is only discussed in our previous works [START_REF] Teylo | A dynamic task scheduler tolerant to multiple hibernations in cloud environments[END_REF], [START_REF] Teylo | A bag-of-tasks scheduler tolerant to temporal failures in clouds[END_REF] and in Fabra et al. [START_REF] Fabra | Reducing the price of resource provisioning using ec2 spot instances with prediction models[END_REF]. We proposed, in [START_REF] Teylo | A bag-of-tasks scheduler tolerant to temporal failures in clouds[END_REF], a static heuristic that creates predefined backup maps before the execution of the job tasks themselves. It was the first attempt to cope with spot VMs hibernation, and results from simulations showed that the hibernation problem is better handled with a dynamic approach. In [START_REF] Teylo | A dynamic task scheduler tolerant to multiple hibernations in cloud environments[END_REF], 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. In [START_REF] Fabra | Reducing the price of resource provisioning using ec2 spot instances with prediction models[END_REF], the authors consider a scenario where hibernation-prone spot VMs can be used and then they show that deadline constraints add complexity to the problem of resource provisioning. However, no performance experiment results are presented neither discussed. Moreover, the work does not focus on the task scheduling problem, but on resource provisioning.

Recently, in [START_REF] Varshney | Autobot: Resilient and costeffective scheduling of a bag of tasks on spot vms[END_REF], Varshney and Simmhan proposed the AutoBoT Scheduler. According to the authors, AutoBoT uses several heuristics to choose a set of spot and ondemand VMs to execute BoT applications subject to a deadline defined by the user. The objective is to reduce the monetary cost of the execution, and the scheduler combines checkpoints and migration procedures to meet the deadline, even with spot revocations. Like Burst-HADS, AutoBoT also has two execution phases: i) the initial mapping, where an initial execution map is built, and ii) the execution phase, where the tasks are executed. Similarly to the Dynamic Scheduling of Burst-HADS, the execution phase of AutoBoT also reacts to the spot revocations by changing the initial execution map, adding on-demand VMs, and migrating the affected tasks. However, there are some crucial differences between AutoBoT and Burst-HADS. Firstly, although it is a recent work, AutoBoT takes some scheduling decisions based on the old spot price model. Moreover, differently from Burst-HADS, AutoBoT does not explore the hibernation feature of spot VMs neither the burst capacity of burstable VMs to reduce the monetary cost and minimize the execution time. Another important point to highlight is that AutoBoT was not evaluated in a real cloud. Instead, the authors presented a comprehensive study in a simulated environment.

SCHEDULING WITH HIBERNATION-PRONE SPOT AND BURSTABLE ON-DEMAND INSTANCES

The Burst Hibernation-Aware Dynamic Scheduler (Burst-HADS) has two main scheduling modules: i) the Primary Scheduling Module, that defines an initial scheduling map (Section 3.2); and ii) a Dynamic Scheduling Module responsible for migrating tasks or executing task rollback recovering in idle VMs (Section 3.3). In this section, we present 2. https://aws.amazon.com/pt/blogs/compute/new-amazon-ec2spot-pricing/ the algorithms and procedures proposed for each one of these modules. In Section 3.1, we formulate the primary scheduling map as a multi-objective integer programming problem.

Mathematical Formulation

The problem of scheduling tasks in distributed computing resources is an NP-complete one [START_REF] Ullman | Np-complete scheduling problems[END_REF], even in simple scenarios. Furthermore, some features of clouds render it more difficult. We thus model the primary task 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 creating an initial scheduling strategy, respecting the limit of available virtual cores (vCPUs) and memory capacity of the used VMs while minimizing the makespan and the monetary costs of the execution. Then, a number of burstable VMs, defined in function of the number of selected spot VMs, are included as an additional resource at the last step of the Primary Scheduling Module (see Section 3.2). Therefore, in the mathematical model we consider only spot VMs.

Let M s be the set of spot VMs that can be used to execute the BoT application and let D be the application deadline, defined by the user. We then consider a set T = {1, . . . , D} of discrete valid time periods. Each vm j ∈ M s has a memory capacity of m j gigabytes and nvc j vCPUs. When a new vm j is launched, the user is charged c j for each period of time. When the VM terminates or hibernates, 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 ∈ B requires a known amount of memory rm i , and it is executed in only one vCPU of vm j . A multi-core vm j (nvc 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 ∈ M s is known beforehand.

Aiming at ensuring the application deadline D no matter if and when spot VM hibernations happen, in our previous work [START_REF] Teylo | A dynamic task scheduler tolerant to multiple hibernations in cloud environments[END_REF], we define 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 to execute them before the deadline D. D spot is computed by considering the deadline D and the longest tasks that might need to be migrated and executed to/in the slowest VMs. Let the binary variable X v ij indicate whether a task t i ∈ B allocated to a vm j ∈ M s will start executing (X v ij = 1), or not (X v ij = 0), at time period v ∈ T . Let also Z j and ZT be continuous variables which respectively keep the last period of execution of a vm j ∈ M s and the total execution time of the application (makespan).

All variables and parameters defined in this section are summarized in Table 1. The proposed objective function (Equation 1) is a weighted function that minimizes the monetary cost and the makespan, where α is the weight given by the user for the objectives.

min (α × ( vmj ∈M s Z j × c j ) + (1 -α) × ZT ) (1)
Note that, in this case, both the monetary cost and the makespan have to be first normalized. The normalization procedure updates the target values to share the same minimum and maximum values, 0 and 1, respectively. Thus, the solution's total monetary cost was divided by the product of the monetary cost of hiring the most expensive spot vm j ∈ M s , during D spot periods, times the maximum number of VMs that can be deployed. Similarly, the makespan is divided by D spot . When the heuristic finds a solution with makespan longer than the D spot limit, it does not accomplish the normalization, and that solution is discarded by ILS. The objective function is subject to the following constraints.

Constraint 2 guarantees that every task t i ∈ B must be executed, starting at a time v ∈ T in a vm j ∈ M s . Constraint 3 ensures that tasks' memory demand does not outpace the memory capacity of the VM, while constraint 4 guarantees that the number of parallel tasks allocated to a vm j ∈ M s does not exceed the number of virtual cores of the VM.

vmj ∈M s v∈T X v ij = 1, ∀i ∈ B (2) ti∈B v q=p rm i × X q ij ≤ m j , ∀vm j ∈ M s , ∀v ∈ T, and p = max(v -e ij , 1) (3)
ti∈B v q=p X q ij ≤ nvc j , ∀vm j ∈ M s , ∀v ∈ T, and p = max(v -e ij , 1) (4)
Inequalities 5 and 6 relate the last period of execution of each vm j ∈ M s with the application total execution time (makespan). Finally, constraint 7 ensures that the application makespan does not exceed the D spot value.

X v ij × (v + e ij ) ≤ Z j ∀t i ∈ B, ∀vm j ∈ M s and ∀v ∈ T (5) X v ij × Z j ≤ ZT ∀t i ∈ B, ∀vm j ∈ M s and ∀v ∈ T (6) Z j ≤ D spot , ∀vm j ∈ M s (7)
As shown in Section 4, the execution time to solve the exact model is prohibitive even to small BoT applications. Hence, in order to find good solutions to the scheduling problem in an acceptable time, we adopt the heuristic approach presented in Section 3.2.

Primary Scheduling Module

In order to create the initial scheduling map according to the Mathematical Formulation presented in Section 3.1, we propose an Iterated Local Search (ILS) able to solve the problem in an acceptable time. The ILS [START_REF] Lourenc ¸o | Iterated local search[END_REF] is a metaheuristic that aims at improving a final solution by sampling in a broad 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.

Let M b be the set of burstable on-demand VMs. After finding a scheduling map with the ILS, a second heuristic is applied to include burstable instances from M b into the solution. In case of spot VM hibernations, the respective 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, that solves the scheduling problem defined in Section 3.1 and ii) the burstable instances allocation, that includes burstable instances to the final solution. Table 2 summarizes the variables and parameters used in the Primary Task Scheduling Algorithms 1, 2 and 3.

Initially, in line 2 of Algorithm 1, an initial solution is generated by calling Algorithm 2, originally proposed in [START_REF] Teylo | A dynamic task scheduler tolerant to multiple hibernations in cloud environments[END_REF]. The latter is a greedy heuristic that schedules the set of tasks B to a set M s of spot VMs. First, in line 2 of Algorithm 2, all tasks of B are sorted in descending order by their memory size requirements. Then, by calling the procedure check schedule, it 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 avoids VM deploying time. Thus, for each task t i ∈ B, the algorithm tries to schedule it to a vm j from A, the set of already selected VMs (lines 7 to 12). If task t i cannot be scheduled to a vm j of A, the algorithm tries to select a new spot VM (lines 14 to Set of selected VMs 23) using a weighted round-robin algorithm (WRR) [START_REF] Katevenis | Weighted round-robin cell multiplexing in a general-purpose atm switch chip[END_REF].

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 8, the weight of vm j , weight(vm j ), is equal to the quotient between Gf lops j of vm j , and c j , the price of the VM per time period. In this work, the Gf lops j of a vm j is used to quantify the computing power of vm j . It is previously estimated using the LINPACK benchmark [START_REF] Dongarra | The linpack benchmark: past, present and future[END_REF] and allows us to compare the VMs' performance. Our choice in using WRR and spot VMs with different configurations is in agreement with Amazon's recommendations 3 that say that an application should use different types of spot VMs to increase the availability of spot VM instances. 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 25, 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 ) = Gf lops j /c j , where vm j ∈ M

After obtaining an initial solution, the ILS algorithm tries to improve it by applying local search and perturbation procedures (Algorithm 1, lines 3 to 20). Thus, let S be a solution that defines a scheduling map of all tasks t i ∈ B to a subset of VMs of M s . Let f itness(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 9 the f itness(S, D spot ) function, where cost is the total monetary cost of S and mkp is the total execution time of the application.

f itness(S, D spot ) = ∞, if violates Dspot α.cost + (1 -α).mkp, otherwise (9)
Algorithm 1 executes a local search by calling, in line 3, the local search procedure (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 of tasks B, the swap rate and the D spot value. The swap rate ∈ ]0, 1] parameter is tuned before the execution and determines the number of tasks that will be swapped at each iteration. All the parameters used in our experiments, including the swap rate, max attempt, max iteration and other parameters will be presented in Section 4.

As can be observed in lines 4 and 8 of 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. Firstly, the algorithm computes the number of tasks that will be swapped at each iteration (line 2) and randomly selects a destination VM (vm dest , line 4). After that, the algorithm starts the tasks swapping procedure (lines 5 to 14), where n tasks, also randomly selected (line 7), are moved to the vm dest . After each swap movement, the local search procedure checks if the quality of the new generated solution has improved (line 9) and it updates the S best solution, if necessary. In the end, the procedure returns the best solution (line 15).

Algorithm 2 Initial Solution

Input: B, M s , Dspot sort by price(A) {Sort VMs v j ∈ A according to c j } 7:

for all vm j ∈ A do 8:

if check schedule(t i , vm j , Dspot) then 9:

schedule(t i , vm j ) 10:

break After the first execution of the local search procedure (Algorithm 1, line 3), Algorithm 1 has a loop that firstly performs a perturbation (lines 8 to 13) and then a new local search (line 14). The perturbation is responsible for diverting the metaheuristic from local optimal solutions. In the current work, we use two perturbation strategies. The first one includes a not selected spot vm j ∈ M s into the current solution S (lines 8 to 10). The second one, called relaxing perturbation, increases the D spot bound value (lines 11 to 13). Note that the latter is executed only when the number of iterations without finding a better solution is higher than the max f ailed parameter (line 11). In this case, the metaheuristic increases the D spot limit in relaxed rate percent, where relaxed rate ∈]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 22 to 24). In this procedure, n burstable VMs are included in the final solution, where n is a percentage, given by the parameter burst rate, of the selected spot VMs of the best solution found by the ILS. For example, if 20 spot VMs were selected by the ILS, with burst rate = 0.1, only 2 burstable VMs will be included.

Since the relaxed perturbation leads some tasks to violate the D spot limit, the burst allocation procedure also moves these tasks to the burstable instances. Each burstable VM 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 become the best candidates to receive tasks in case of spot VM hibernations.

Dynamic Scheduling Module

The Dynamic Scheduling Module is responsible for performing 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 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 ∈ BR); ii) idle, if active but not executing any task (vm j ∈ IR); iii) hibernated, if it has been hibernated by the cloud provider (vm j ∈ HR); and iv) terminated, if the VM has terminated or it was not available at the beginning of the application execution (vm j ∈ T R).

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 3.1), the user has an interest that a VM terminates as soon it becomes idle, reducing cost 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. To tackle such a trade-off, 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 events and respective actions handled by the Dynamic Scheduling Module are the following:

• 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 assigning some or all of these tasks to vm j , whose state is, thus, set to busy (see Section 3.5).

• 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 terminated and removed from the set IR of idle VMs and included into T R, 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 3.4).

• 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 3.5).

Table 3 summarizes the variables and parameters used on Algorithms of the Dynamic Schedule Module (Algorithms 4 and 5). Set of tasks that can be stolen from vm j

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, that were previously scheduled to vm l . These tasks are denoted affected tasks. 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 ⊂ 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. Note that, in the case of a burstable vm j ∈ 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) and each vm j ∈ M b have a current CPU credit amount cc j that is constantly updated by the cloud provider (in the case of vm j ∈ M b , i.e., non-burstable VMs, cc j = ∞).

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 1). Burst-HADS applies the checkpoint/recovery mechanism that we proposed and evaluated in our previous work [START_REF] Teylo | Developing checkpointing and recovery procedures with the storage services of amazon web services[END_REF] where checkpoints are taken with the help of Checkpoint Restore In Userspace (CRIU) [START_REF] Emelyanov | Criu: Checkpoint/restore in userspace, july 2011[END_REF], 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 ∈ Q l , the algorithm first tries to migrate the task to an idle burstable VM (lines 4 to 13). Otherwise, it tries to schedule t i to one of the non-burstable idle or busy VM of end for 41: end if 42: end for set K = IR ∪ BR (lines 18 to 27). Note that, the set K is created by sorting the idle and busy VMs according to its market, putting the spot VMs in the front of the ordered set K (Algorithm 4 line 17).

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 ensure 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 3.1), it is possible to estimate (line 5) 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 6). If both conditions are satisfied, t i is migrated to vm j in burst mode (line 8). In this case the burstable vm j is removed from set IR and included in set BR (lines 9 and 10). Note that the cloud provider continuously updates the number of credits, cc j , of every burstable VM.

Similarly, when Algorithm 4 migrates a task t i to a non-burstable idle or busy 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, respecting the deadline D (line 19). However, 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, a busy or idle spot 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 32 to 40). In this case, it is necessary to verify that, considering the start period of t i in vm j (start ij ), plus its execution time (e ij ) will not violate the deadline (line 33). The new allocated on-demand VM is then removed from set M o and included in set BR (lines 36 and 37).

Work-Stealing

The work-stealing procedure, presented in Algorithm 5, aims at reducing the allocation time duration of regular ondemand 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 ∈ BR the procedure selects the tasks that can be stolen from it (line 3) and tries to migrate them to the idle vm k (lines 4 to 14). Since regular on-demand VMs are more expensive than spot ones, the procedure considers firstly the tasks from the former (line 1).

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 deadline violation (line 5). 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 6), the algorithm sets up the execution to the baseline mode (line 7). 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 provider. In order to limit the use of the CPU, Burst-HADS exploits the cpulimit tool 4 , 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 in the baseline mode, which could increase the application total execution time. Since stolen tasks are executed in baseline mode on burstable VMs non consumed CPU credits consuming keep available if a spot VM hibernates. Thus, after moving one task to the burstable vm k , the algorithm stops the loop (line 9). Finally, if at least one task is migrated to vm k , its state changes to busy and,

EXPERIMENTS AND RESULTS

In this section, we first evaluate the ILS, part one of Algorithm 1, in terms of quality of solution and execution time, by comparing it with the solutions given by the mathematical formulation presented in Section 3.2 (solved with Gurobi 9.1) and with three commonly used BoT scheduling heuristics [START_REF] Fujimoto | A comparison among grid scheduling algorithms for independent coarse-grained tasks[END_REF], [START_REF] Li | Job scheduling and processor allocation for grid computing on metacomputers[END_REF], [START_REF] Maheswaran | Dynamic mapping of a class of independent tasks onto heterogeneous computing systems[END_REF]: MinMin, MaxMin and Greedy (Section 4.1). We also present a evaluation in AWS EC2 (Section 4.2), where the jobs were executed in a real cloud environment. In the experiments, we have considered two distinct workloads: i) synthetic BoT applications composed by tasks generated with the application template proposed in Alves et al. [START_REF] Alves | A multivariate and quantitative model for predicting cross-application interference in virtual environments[END_REF], and ii) the ED application available in the GRIDNBP 3.1 suite of NAS benchmark [START_REF] Bailey | The nas parallel benchmarks 2.0[END_REF]. The tasks of the synthetic applications execute vector operations whose execution times depend on the size of the vectors.

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. Moreover, we also use the T3.large instances that are the newest generation of the general proposed burstable instances of EC2. Table 4 shows the computational characteristics and the corresponding prices in on-demand and spot markets in November 2020. For the execution of Algorithms 1 and 3, the following input parameters were used: α = 0.5, max iteration = 200; max attempt = 50; swap rate = 0.10; max f ailed = 20; relaxed rate = 0.25; burst rate = 0.2. Moreover, we defined AC = 900 seconds. Except for α = 0.5, which was used to give the same weights to both objectives, the parameters' values were defined by executing a set of empirical tests. As mentioned in Section 3.4, Burst-HADS uses a checkpoint approach proposed in [START_REF] Teylo | A dynamic task scheduler tolerant to multiple hibernations in cloud environments[END_REF] where the user defines the parameter ovh as the maximum percentage of time overhead that the checkpoint mechanism is allowed to add to the original execution time of a task. From this parameter, Burst-HADS defines the time interval between checkpoints. In this work, ovh = 10% for all experiments.

Evaluation of the ILS Primary Task Scheduling

To evaluate the quality of the solution given by the ILS executed in the first part of the primary scheduling heuristic (Algorithm 1), we compared it with the optimal solution given by the exact model and also with the solutions given by three widely used benchmark scheduling heuristics [START_REF] Gutierrez-Garcia | A family of heuristics for agent-based elastic cloud bag-of-tasks concurrent scheduling[END_REF]: (i) MinMin, where the scheduling gives priority to VMs with the minimum earliest completion time; (ii) MaxMin, where the scheduling gives priority to VMs with the maximum earliest completion time; and (iii) Greedy, where the shortest execution time task is scheduled to the cheapest available VM.

For the comparison with the exact model, we create six small synthetic jobs (from 5 to 30 tasks), composed of tasks with execution times varying from 5 to 15 seconds. We have chosen this set with up to 30 tasks because the exact model took more than ten hours to solve the problem for jobs with more than 30 tasks. In these experiments, the deadline was fixed in 15 minutes (D = 900) for all jobs, and we used as input the spot VMs presented in Table 4, except for the burstable VM, since we are evaluating just the ILS heuristic. The experiments were executed on a computer with a processor Intel Core i7-3770 CPU 3.40 GHz with 12GB of memory and Ubuntu 18.04 was used. The mathematical formulation was solved by using the Gurobi Solver 9.0 5 .

Table 5 summarizes the results with both the exact approach and the ILS-based heuristic. The first column identifies the number of tasks. The three columns that follow correspond to the results achieved by ILS: makespan, monetary cost, and the execution time to obtain the solution. The next three columns present the same results for the exact approach. The values shown for the ILS are averages of three executions. The ILS standard deviations were zero for all jobs. As we can observe in Table 5, ILS obtains the same solutions of the exact approach for these small jobs, taking significantly less time than the mathematical formulation.

5. http://www.gurobi.com On average, the ILS takes 0.048s against 2101.43s of the exact approach. Although these results are very encouraging, the experiments were limited to jobs with few tasks (up to 30 tasks) due to the huge required time to obtain the exact solution for jobs with more tasks.

For the evaluation with the other heuristics, six synthetic jobs were created with sizes varying from 50 to 300 tasks. The tasks execution times varied from 15 to 35 seconds, and the same deadline of 15 minutes (D = 900) was applied. Table 6 presents the makespan and monetary cost obtained by the ILS, MinMin, MaxMin, and Greedy heuristics. As shown in Table 6, the ILS heuristic outperforms MinMin in terms of monetary cost but increases the makespan. On average, the ILS makespan is increased of 18.11%, while the average monetary cost is reduced by more than 38.00%. Compared to both MaxMin and Greedy, the ILS presents an average reduction in the makespan by more than 80%, with an average increment in the monetary cost by only 6.78% when compared to MaxMin, and 13.14% when compared to the Greedy heuristic. Contrarily to the MinMin heuristic, both MaxMin and Greedy heuristics reduce the solution's monetary cost since they give priority to the cheapest VMs, which increases the makespan.

It is worth noticing that both objectives were evenly considered in the ILS solutions and that the average loss in one of the objectives was always smaller than the gain in the other. Those results confirm the effectiveness of the proposed ILS to the BoT primary scheduling problem.

Evaluation of Burst-HADS on AWS EC2

For the experiments, several synthetic tasks were 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 comprises 200 tasks solving the largest problem size (class B), taking 211 seconds per task on average.

Table 7 shows the four jobs' features, including their respective number of tasks, memory footprint and tasks runtime. In our experiments, we considered the shortest deadline in which Burst-HADS can find a feasible solution for all evaluated jobs, D = 2700 seconds (45 minutes), respecting the constraints. For some jobs, it was a tight deadline, while for other ones it was not. This approach allowed us to observe the behavior of the framework in those different scenarios. 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;

(2) the schedule given by HADS, and (3) the schedule given by AutoBoT-like. The aim of these experiments is to measure the impact of including burstable on-demand VMs into the scheduling procedure in both the monetary cost and execution time. Table 8 presents the average of three executions of the synthetic jobs J60, J80, and J100, and the real application ED200, for each case.

AutoBoT-like is inspired by the work presented in [START_REF] Varshney | Autobot: Resilient and costeffective scheduling of a bag of tasks on spot vms[END_REF] (see Section 2). AutoBoT-like uses the same heuristics, procedures and parameters defined in [START_REF] Varshney | Autobot: Resilient and costeffective scheduling of a bag of tasks on spot vms[END_REF], but the price history and the spot market bid are not considered in that adapted version. In our implementation, we use the current price model of AWS, which is more stable.

Initially, AutoBoT-like, as in the original version, considers a critical time point beyond which it is not possible to complete the remaining tasks without violating the deadline constraint, in case of a spot VM revocation. Thus, when a task, running on a spot VM, reaches this point, it is immediately migrated to an on-demand VM. The number of launched on-demand VMs in this case is defined in accordance with a sweep heuristic, based on the following parameters: the number of available on-demand VMs, the deadline and the total number of tasks of the application.

In the second step, along with the execution of the application, AutoBot-like, as in the original version, takes checkpoints and migrate tasks to on-demand VMs. Although the authors propose three different strategies for checkpointing, we adopted the optimistic one, where checkpoints are recorded just before the critical time point, because the other ones depended on the price history and they did not present significant advantages.

In comparison with HADS, Table 8 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. It happens 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.

As can also observe in in the same table, in the executions without spot revocations, Burst-HADS presents an average reduction of 20.92% in the monetary cost and 31.11% in the makespan, when compared to AutoBoT-like. Such a result is expected since AutoBoT-like launches additional on-demand instances even without spot revocations when the BoT execution gets the critical time point.

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 includes neither spot nor 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 the events of spot hibernations and resume by using a Poisson distribution function. We have applied the Poisson function to modeling several scenarios where hibernating and resuming events have different probability mass functions defined by the parameters λ h and λ r , respectively. Let the λ 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, λ h and λ r parameters are given by λ h = k h /D and λ r = k r /D. Table 9 presents five different scenarios by varying k h and k r . Note that, since AutoBoT-like does not explore the hibernation feature of the spot VMs, instead of emulating the hibernation, the spot instances are terminated according to the Poisson function with probability mass functions also defined by the parameters λ h .

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 10 presents the averages of three executions of jobs J60, J80, J100, and ED200 using Burst-HADS, HADS and AutoBoT-like in each of the five execution scenarios. For each job and scenario, the table shows the average number of hibernations/revocations followed by resume events. It also includes the number of non-burstable ondemand VMs launched during the frameworks' execution and the average of monetary cost and makespan. Finally, the last four columns present the percentage differences related to the monetary cost and the makespan between Burst-HADS and HADS (Diff HADS), and between Burst-HADS and AutoBoT-like (Diff AutoBoT-like).

As shown in Table 10, in comparison to HADS, Burst-HADS minimizes the makespan in all execution scenarios, presenting an average reduction of 25.87%. As explained in Section 3.4, whenever a spot VM hibernates, Burst-HADS immediately migrates the interrupted tasks to other VMs. Thus, the increase in the makespan is due to the overhead of this procedure, which might include the launch of new VMs. However, in these scenarios, the overhead has a lower impact in small jobs, i.e., jobs with fewer tasks, than in the ones with a higher number of tasks. 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 gets 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 saving, its central idea is to wait as much as possible for the resume of hibernated VMs in order to avoid the launch of new VMs.

Still compared to HADS, Burst-HADS improves the monetary cost for all jobs in scenarios sc 2 and sc 5 . The sc 2 is the worst case scenario, since it has the highest rate of hibernation (k h = 5) and no resume (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 9). 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, in those cases, by migrating tasks to busy and idle VMs and burstable VMs, exploring the burst mode, Burst-HADS is more effective in minimizing the impact of spot hibernations than HADS. It is also worth pointing out that, considering all executions, the average increase of Burst-HADS monetary cost is 1.92% compared to HADS.

Compared to AutoBoT-like, Burst-HADS can reduce the monetary cost for all jobs in almost all scenarios, presenting an average reduction of 11.65%. In our evaluation, AutoBoTlike reduced the monetary cost only in scenario sc 2 and for the jobs J60 and ED200. As explained before, this scenario has the highest rate of hibernation (k h = 5), but there are no resume events (k r = 0). Therefore, in this case, HADS and Burst-HADS cannot explore the resumed spot VMs to minimize the monetary cost. Although Burst-HADS is more effective than HADS to minimize that impact by using burstable VMs, for these two jobs, AutoBoT-like migrated the majority of tasks just before the VMs interruptions and selected a cheap set of on-demand VMs able to execute the remaining tasks. However, we should point out that the AutoBot-like approach is unsuitable for the other scenarios since it does not take advantage of the hibernation feature. In terms of makespan, Burst-HADS presented a better result in almost all cases when compared to AutoBoT-like, with an average reduction of 21.08%. The only exception for the makespan was scenario sc 4 for job J80, where there were many hibernations and resumes, which increased the overhead of Burst-HADS due to migrations and task workstealing. But even in this case, the makespan difference was only 1.14%. Finally, compared to the ILS On-demand, both Burst-HADS and HADS minimize the monetary cost for all execution cases, presenting an average reduction of 41.80% and 39.65%, respectively. For job ED200, for example, in the worst execution scenario, sc 2 , Burst-HADS reduces the monetary cost by 30.96%, while HADS presents an average reduction of 26.66%.

Since cloud environments can face random fluctuation in terms of performance, we also carried out some experiments considering an increase of 20% in the execution time of the tasks of job J60. We observed in Table 11 that both frameworks, AutoBoT-like and Burst-HADS, were able to meet the deadlines for all scenarios. However, just Burst-HADS kept the monetary cost below the on-demand only solution ($0.271). However, for tight deadlines and depending on the range of the fluctuations, the frameworks might not meet the deadlines.

CONCLUSION AND FUTURE WORK

This paper proposes the Burst Hibernation-Aware Dynamic Scheduler (Burst-HADS) framework which uses regular ondemand VMs, hibernation-prone spot VMs, and burstable VMs for executing deadline constrained bag-of-task applications. The framework creates a primary scheduling plan using an ILS based heuristic and then executes a Dynamic Scheduling Module that monitors the execution, applying both task migration and work-stealing techniques whenever necessary. The objective of Burst-HADS is to minimize both the makespan and the monetary cost of the execution, respecting applications deadline even when spot VMs in use hibernate.

Results show that, when compared to the exact approach, ILS also reaches the optimal solutions but faster (less than one second on average) than the former. Furthermore, when compared to baseline heuristics, ILS presents more balanced solutions considering both objectives. It reduces the average monetary cost by more than 38% with an increment of the makespan of 18% when compared to MinMin. Finally, ILS reduces the makespan by more than 80%, with a small increment of the monetary cost; 6.78% and 13.14% when respectively compared to MaxMin and to the Greedy approaches. In all cases the percentage loss in one objective was smaller than the corresponding gain in the other one.

Burst-HADS was evaluated in a real environment using VMs of AWS EC2, considering scenarios with different hibernation and resuming rates. When compared to the ILS On-demand approach that uses only regular ondemand VMs, Burst-HADS reduces the monetary cost for all execution scenarios at the expense of slightly longer makespans due to the migration overhead. Moreover, compared to HADS, our previous proposed framework that uses only spot and on-demand VMs, Burst-HADS reduces the makespan by more than 25%, with an average increase of only 1.92% in the monetary cost. Burst-HADS was also compared to AutoBoT-like, an approach inspired by Vashney and Simmhan's work. AutoBoT-like also combines spot and on-demand VMs but does not explore the hibernation feature. Our results show that, in this case, Burst-HADS reduces the average monetary cost and the makespan by 11.65% and 21.08%, respectively.

As future work, we would like to include in the migration decision of Burst-HADS some prediction of the future state of the spot market, considering, for example, the historic of VMs hibernation. A second research direction would focus on the selection of burstable VMs, with a deeper analysis of the most suitable one, based on the tradeoff between price and performance, in different execution scenarios. Finally, we intend to propose a more realistic scheduler which does not require precise knowledge of the execution time of the application as input, and that may launch or eliminate VMs in accordance with the real application behavior.

ACKNOWLEDGMENT

This research is supported by project CNPq/AWS 440014/2020-4, Brazil and by the Programa Institucional de Internacionalização (PrInt) from CAPES as part of the project REMATCH (process number 88887.310261/2018-00).

1 : 2 : 5 :

 125 sort by memory(B) {Sort Tasks ti ∈ B according to rmi} 3: A ← ∅ {Set of selected VMs} 4: for all ti ∈ B do {P1: Try to schedule the task in an already selected spot VM} 6:

TABLE 1 :

 1 Notation and Variables used in the Mathematical Formulation. Dspot 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 vm j Virtual machine m j Memory capacity of vm j in gigabytes c j Cost per period of time of vm j nvc j Number of vCPUs 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 X v ij Binary variable which indicates whether task t i ∈ B begins its execution in a vm j ∈ M s at time period v ∈ T or not Z j Continuous variable which keep the last period of execution of a vm j ZT Continuous variable which indicates the total time to execute the BoT application (makespan)

	Name	Description
	B M s	Set of tasks Set of spots VMs

T Discretized time set D Deadline defined by the user

TABLE 2 :

 2 Variables and parameters used in Algorithms 1, 2 and 3

	Name	Description
	B M s	Set of tasks Set of spot VMs
	M b	Set of on-demand burstable VMs
	D	Application deadline
	Dspot	Estimated time limit which ensures that there
		will be enough spare time to migrate tasks
	t i	Task t i ∈ B
	vm j	Virtual machines
	max iteration	Number of iterations of the ILS
	max f ailed	Tolerated number of iterations without improv-
		ing the solution
	max attempt	Maximum number of attempts to find a better
		solution
	attempt	Current attempt to find a better solution
	RDspot	Relaxed Dspot value
	relaxed rate	Percentage of increment of the RDspot value
	it	Current iteration of the ILS
	it best	Last iteration where a best solution was found
	swap rate	Percentage of tasks to be swapped
	S	A scheduling solution
	n	Number of burstable VMs added to the final
		solution
	S f inal	The final scheduling solution
	burst rate	Percentage of burstable VMs included into the
		final solution
	A

  Primary Task Scheduling Input: B, M , M s , M b , max iteration, max attempt, max f ailed, relaxed rate, Dspot and D 1: {/*PART 01 -Iterated Local Search*/} 2: S ← initial solution(B, M s , Dspot) {Algorithm 2} 3: S ← local search(S, max attempt, B, swap rate, Dspot) {Algorithm 3} 4: S best ← S 5: RDspot ← Dspot 6: it, it best ← 0 7: while it < max iteration do {/*PART 02: Burstable instance allocation*/} 23: n ← burst rate × S best .selected vms 24: S f inal ← burst allocation(S best , burst rate, M b , Dspot, D) 25: create primary map(S f inal )

	8:	vmj ← random choice(M s )
	9: 10:	S.selected vms ← S.selected vms ∪ vmj M s ← M s \{vmj}
	11:	if (it -it best ) > max f ailed then
	12:	RDspot ← RDspot + (relaxed rate × RDspot)
	13:	end if
	14:	S ← local search(S, max attempt, B, swap rate, RDspot)
	15:	if f itness(S, RDspot) < f itness(S best , RDspot) then
	16:	S best ← S
	17:	it best ← it
	18:	end if
	19:	it ← it + 1
	20: end while
	21:
	22:

3. https://aws.amazon.com/pt/ec2/spot/instance-advisor/ Algorithm 1

TABLE 3 :

 3 Variables and parameters used on Algorithms 4 and 5 BR Ordered set of idle and busy VMs start ij The time period a task t i will start executing when allocated to a vm j e ij Time required to execute task t i in a vm j ω Time overhead to deploy a new VM vm j and vm k Virtual machines ST j

	Name	Description
	Q l	Set of unfinished tasks of a hibernated spot vm l
	IR	Set of idle VMs
	BR M o	Set of busy VMs Set of on-demand VMs
	D	Application deadline
	cc j	Current amount of CPU credit
	rcc ij	Estimated number of required CPU credits
	burst period	Number of periods of T corresponding to the use
		of one CPU credit
	K = IR ∪

Algorithm 4

 4 Burst Migration Procedure Input: Q l , IR, BR, M o , and D 1: Q l ← sort tasks(Q l ) {/* Prioritizes tasks with checkpoints */} 2: for each t i ∈ Q l do 3: {Attempt 1 -Try to migrate task to a Burstable IDLE VM} 4: for each burstable vm j ∈ IR do 5: rcc ij ← e ij /burst period 6: if cc j > rcc ij and check migration(t i , vm j , D) then 7: {Migrate t i to burstable vm j on burst mode} 8:

		migrate(t i , vm j )
	9:	IR ← IR\{vm j }
	10:	BR ← BR ∪ {vm j }
	11:	break {/*Migrate next task*/}
	12:	end if
	13: end for
	14: {Attempt 2 -Try to migrate task to a NON-burstable Idle or Busy
		VM}
	15: if not migrated then
	16:	{/* Prioritizes idle spot VMs */}
	17:	K ← sort by market(IR ∪ BR)
	18:	for each NON-burstable vm j ∈ K do
	19:	if check migration(t i , vm j , D) then
	20:	migrate(t i , vm j )
	21:	if vm j ∈ IR then
	22:	IR ← IR\{vm j }
	23:	BR ← BR ∪ {vm j }
	24:	end if
	25:	break {/*Migrate next task*/}
	26:	end if
	27:	end for
	28: end if
	29: {Attempt 3 -Migrate task to a new NON-burstable on-demand
		VM}
	30: if not migrated then sort by price(M o ) 31: 32: for each vm j ∈ M o do
	33:	if start ij + e ij + ω < D then
	34:	start vm(vm j )
	35: 36:	migrate(t i , vm j ) M o ← M o \{vm j }
	37:	BR ← BR ∪ {vm j }
	38:	break {/*Migrate next task*/}
	39:	end if
	40:

at least one task was stolen then

  , it is included into the set of busy VMs and removed from the idle set (lines 17 and 18). BR, IR, vm k , D 1: sort by market(BR) {/*Prioritizes non-burstable on-demand VMs*/} 2: for each NON-burstable vm j ∈ BR do 3: ST j ← selectT asks(vm j ) {Select the tasks that can be stolen/} 4: for each t i ∈ ST j do 17: BR ← BR ∪ {vm k } 18: IR ← IR\{vm k } 19: end if

	Algorithm 5 Burst Work-Stealing Procedure
	5:	if check migration(t i , vm k , D) then
	6:	if vm k is burstable then
	7:	set baseline mode(t i , vm k )
	8:	migrate(t i , vm k )
	9:	stops the loop
	10:	else if vm k not burstable then
	11:	migrate(t i , vm k )
	12:	end if
	13:	end if
	14: end for
	15: end for
	16: if

4. http://cpulimit.sourceforge.net/ consequentlyInput:

TABLE 4 :

 4 VMs attributes

	Type	#VCPUs Memory	Price per Hour (USD) on-demand spot	Baseline 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%

TABLE 5 :

 5 Results of the ILS-based Primary Scheduling Heuristic and the Exact Approach

	# Tasks	Makespan	ILS Cost	Time	Exact Approach Makespan Cost	Time
	5	21	$0.0005 0.0071	21	$0.0005	49.04
	10	34	$0.0011 0.0306	34	$0.0011	70.10
	15	34	$0.0020 0.0297	34	$0.0020	106.03
	20	34	$0.0021 0.0558	34	$0.0021	233.10
	25	34	$0.0027 0.0736	34	$0.0027	751.72
	30	34	$0.0035 0.0922	34	$0.0035 9346.21

TABLE 6 :

 6 Results of the ILS-based Primary Scheduler, Min-Min, MaxMin and Greedy Heuristics.

	# Tasks	mkp	ILS	cost	MinMin mkp cost	MaxMin mkp cost	Greedy mkp cost
	50	57	$0.0060	47	$0.0073	610	$0.0055	597	$0.0051
	100	86	$0.0112	71	$0.0220	897	$0.0107	843	$0.0101
	150	109	$0.0169	99	$0.0338	885	$0.0157	823	$0.0148
	200	138	$0.0235	123	$0.0376	898	$0.0220	819	$0.0205
	250	163	$0.0282	133	$0.0461	888	$0.0261	793	$0.0246
	300	204	$0.0340	168	$0.0551	899	$0.0323	775	$0.0317

TABLE 7 :

 7 Characteristics of the Jobs

	job	# tasks	min	memory footprint avg	max	task runtime(s) min avg max
	J60	60	2.85MB	4.69MB	12.20MB	102	198	323
	J80	80	2.91MB	4.71MB	13.19MB	103	199	322
	J100	100	2.81MB	4.49MB	10.86MB	107	190	330
	ED200	200	153.74MB 168.68MB 177.77MB	161	211	354

TABLE 8 :

 8 Cost and Makespan of Burst-HADS, HADS (without hibernation), AutoBoT-like (without spot interruptions) and ILS On-demand only.

	JOB	Burst-HADS w/o Hibernation	HADS w/o Hibernation	AutoBoT-like w/o Interruptions	ILS On-demand
		cost	makespan	cost	makespan	cost	makespan	cost	makespan
	J60	$0.112	1274	$0.067	2290	$0.166	2221	$0.271	1112
	J80	$0.151	1329	$0.104	2295	$0.199	2266	$0.312	1190
	J100	$0.176	1660	$0.112	2332	$0.218	2342	$0.371	1462
	ED200 $0.357	2275	$0.267	2580	$0.387	2566	$0.698	1887

TABLE 9 :

 9 Different execution scenarios generated by varying parameters λ h and λ r

	ID	hibernating	resuming	λ h	λ r
	sc 1

TABLE 10 :

 10 Comparison between Burst-HADS, HADS and AutoBoT-like in terms of monetary cost and makespan in scenarios sc 1 to sc 5

	Job	scenario	# hibernations	# resumes	# used regular on-demand VMs Burst-HADS HADS AutoBoT-like	Burst-HADS cost makespan	cost	HADS makespan	AutoBoT-like cost makespan	Diff HADS (%) cost makespan	Diff AutoBoT-like (%) cost makespan
		sc1	0.66	0.00	0.00	0.00	1	$0.119	1274	$0.091	2620	$0.166	2221	-30.77%	51.37%	28.31%	42.64%
		sc2	3.33	0.00	1.33	2.33	1	$0.204	1277	$0.257	2549	$0.173	2228	20.54%	49.90%	-17.92%	42.68%
	J60	sc3	2.33	2.33	1.33	0.00	1	$0.127	1752	$0.101	2539	$0.178	2237	-26.07%	31.00%	28.46%	21.68%
		sc4	5.33	4.00	1.67	0.00	1	$0.142	1857	$0.119	2634	$0.180	2252	-19.90%	29.50%	21.07%	17.54%
		sc5	2.66	1.00	1.33	2.00	1	$0.150	1445	$0.169	2359	$0.170	2236	11.44%	38.75%	11.96%	35.38%
		sc1	1.00	0.00	1.33	0.33	2	$0.167	1419	$0.150	2581	$0.206	2273	-11.33%	45.03%	18.93%	37.57%
		sc2	5.00	0.00	1.00	3.00	2	$0.210	2267	$0.298	2591	$0.211	2278	29.48%	12.50%	0.47%	0.48%
	J80	sc3	3.00	1.00	1.67	1.00	2	$0.164	1367	$0.147	2602	$0.214	2276	-11.34%	47.46%	23.52%	39.94%
		sc4	9.66	7.66	1.00	2.00	3	$0.244	2488	$0.212	2607	$0.301	2460	-15.25%	4.56%	18.83%	-1.14%
		sc5	3.00	1.00	1.33	3.00	2	$0.195	1589	$0.246	2529	$0.228	2266	20.47%	37.17%	14.25%	29.88%
		sc1	2.00	0.00	0.00	0.00	2	$0.191	1798	$0.157	2332	$0.226	2350	-21.76%	22.90%	15.49%	23.49%
		sc2	7.00	0.00	1.33	3.00	2	$0.212	1900	$0.353	2518	$0.222	2342	39.94%	24.54%	4.50%	18.87%
	J100	sc3	6.00	3.00	1.67	1.00	2	$0.201	1925	$0.166	2636	$0.224	2360	-21.08%	26.97%	10.27%	18.43%
		sc4	11.00	9.00	1.00	0.00	3	$0.286	2453	$0.278	2591	$0.312	2677	-2.88%	5.33%	8.33%	8.37%
		sc5	3.66	2.00	1.00	2.50	2	$0.166	1547	$0.189	2543	$0.227	2366	12.49%	39.15%	26.98%	34.62%
		sc1	3.00	0.00	1.00	0.33	3	$0.388	2327	$0.314	2680	$0.414	2630	-23.57%	13.17%	6.28%	11.52%
		sc2	8.00	0.00	2.00	5.00	3	$0.482	2448	$0.512	2676	$0.430	2661	5.86%	8.52%	-12.09%	8.00%
	ED200	sc3	6.66	4.00	2.33	1.00	3	$0.427	2345	$0.387	2672	$0.457	2675	-10.34%	12.24%	6.56%	12.34%
		sc4	9.00	6.00	2.00	1.00	3	$0.411	2560	$0.389	2690	$0.447	2667	-5.66%	4.83%	8.05%	4.01%
		sc5	4.33	2.33	1.67	3.00	3	$0.367	2342	$0.467	2674	$0.411	2765	21.41%	12.42%	10.71%	15.30%

TABLE 11 :

 11 Comparison of Burst-HADS and AutoBoT-like with an unexpected increment of 20% in the execution time of the tasks of J60

		With Time Fluctuation (20%)		Without Fluctuation
	Burst-HADS	AutoBoT-like	Burst-HADS	AutoBoT-like
	cost	makespan	cost	makespan	cost	makespan	cost	makespan
	$0.199	1429	$0.269	2408	$0.112	1274	$0.166	2221
	$0.231	1493	$0.274	2424	$0.119	1274	$0.166	2221
	$0.254	2595	$0.295	2453	$0.204	1277	$0.173	2228
	$0.227	1834	$0.282	2457	$0.127	1752	$0.178	2237
	$0.225	1833	$0.276	2439	$0.142	1857	$0.180	2252
	$0.195	1648	$0.279	2483	$0.150	1445	$0.170	2236