Skip to Main content Skip to Navigation
Reports

Reservation Strategies for Stochastic Jobs (Extended Version)

Abstract : In this paper, we are interested in scheduling stochastic jobs on a reservation-based platform. Specifically, we consider jobs whose execution time follows a known probability distribution. The platform is reservation-based, meaning that the user has to request fixed-length time slots. The cost then depends on both (i) the request duration (pay for what you ask); and (ii) the actual execution time of the job (pay for what you use). A reservation strategy determines a sequence of increasing-length reservations, which are paid for until one of them allows the job to successfully complete. The goal is to minimize the total expected cost of the strategy. We provide some properties of the optimal solution, which we characterize up to the length of the first reservation. We then design several heuristics based on various approaches, including a brute-force search of the first reservation length while relying on the characterization of the optimal strategy, as well as the discretization of the target continuous probability distribution together with an optimal dynamic programming algorithm for the discrete distribution. We evaluate these heuristics using two different platform models and cost functions: The first one targets a cloud-oriented platform (e.g., Amazon AWS) using jobs that follow a large number of usual probability distributions (e.g., Uniform, Exponential, LogNormal, Weibull, Beta), and the second one is based on interpolating traces from a real neuroscience application executed on an HPC platform. An extensive set of simulation results show the effectiveness of the proposed reservation-based approaches for scheduling stochastic jobs.
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/hal-01903592
Contributor : Valentin Honoré <>
Submitted on : Thursday, January 31, 2019 - 4:56:39 PM
Last modification on : Wednesday, November 20, 2019 - 3:13:48 AM
Document(s) archivé(s) le : Wednesday, May 1, 2019 - 7:01:28 PM

File

research_report.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01903592, version 2

Citation

Guillaume Aupy, Ana Gainaru, Valentin Honoré, Padma Raghavan, Yves Robert, et al.. Reservation Strategies for Stochastic Jobs (Extended Version). [Research Report] RR-9211, Inria & Labri, Univ. Bordeaux; Department of EECS, Vanderbilt University, Nashville, TN, USA; Laboratoire LIP, ENS Lyon & University of Tennessee Knoxville, Lyon, France. 2018, pp.1-37. ⟨hal-01903592v2⟩

Share

Metrics

Record views

147

Files downloads

603