Skip to Main content Skip to Navigation
Conference papers

Scheduling independent stochastic tasks on heterogeneous cloud platforms

Abstract : This work introduces scheduling strategies to maximize the expected number of independent tasks that can be executed on a cloud platform within a given budget and under a deadline constraint. The cloud platform is composed of several types of virtual machines (VMs), where each type has a unit execution cost that depends upon its characteristics. The amount of budget spent during the execution of a task on a given VM is the product of its execution length by the unit execution cost of that VM. The execution lengths of tasks follow a variety of standard probability distributions (exponential, uniform, halfnormal, etc.), which is known beforehand and whose mean and standard deviation both depend upon the VM type. Finally, there is a global available budget and a deadline constraint, and the goal is to successfully execute as many tasks as possible before the deadline is reached or the budget is exhausted (whichever comes first). On each VM, the scheduler can decide at any instant to interrupt the execution of a (long) running task and to launch a new one, but the budget already spent for the interrupted task is lost. The main questions are which VMs to enroll, and whether and when to interrupt tasks that have been executing for some time. We assess the complexity of the problem by showing its NPcompleteness and providing a 2-approximation for the asymptotic case where budget and deadline both tend to infinity. Then we introduce several heuristics and compare their performance by running an extensive set of simulations.
Complete list of metadatas

Cited literature [41 references]  Display  Hide  Download

https://hal.inria.fr/hal-02271675
Contributor : Equipe Roma <>
Submitted on : Tuesday, August 27, 2019 - 10:28:06 AM
Last modification on : Wednesday, September 16, 2020 - 10:42:52 AM
Long-term archiving on: : Friday, January 10, 2020 - 8:25:17 AM

File

cluster2019-hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02271675, version 1

Citation

Yiqin Gao, Louis-Claude Canon, Yves Robert, Frédéric Vivien. Scheduling independent stochastic tasks on heterogeneous cloud platforms. IEEE Cluster 2019 - International Conference on Cluster Computing, Sep 2019, Albuquerque, United States. pp.1-11. ⟨hal-02271675⟩

Share

Metrics

Record views

70

Files downloads

483