Reservation Strategies for Stochastic Jobs (Extended Version) - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2018

Reservation Strategies for Stochastic Jobs (Extended Version)

Stratégies de réservation pour l’ordonnancement de tâches stochastiques

(1) , (2) , (3, 1) , (2) , (4) , (2)
1
2
3
4

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.
Dans ce papier, nous nous intéressons à l'ordonnancement de tâches stochastiques exécutées sur une plateforme à réservations, où l'utilisateur réalise des requêtes successives de temps de calcul. Le temps d'exécution des tâches considérées n'est pas connu à l'avance. Ce temps est représenté par une loi de probabilité, décrite sous la forme d'une densité de probabilité. Nous nous intéressons à ordonnancer une instance d'une telle tâche, c'est à dire que nous ne connaissons pas son temps d'éxécution qui reste constant tout au long de l'ordonnancement. Dans ce cas, le coût de l'ordonnancement dépend à la fois de la durée des requêtes et du temps d'exécution de la tâche considérée. L'objectif de ce travail est de déterminer une stratégie de réservation optimale qui minimise le coût total de l'ordonnancement. Une stratégie de réservations est une séquence de requêtes croissantes, qui sont payées les unes à la suite des autres en ordre croissant jusqu'à complétion de la tâche. Pour ce faire, nous fournissons quelques propriétés de cette stratégie optimale, notamment l'importance de la taille de la première réservation. Nous proposons aussi différentes heuristiques basées sur de nombreuses approches, dont une heuristique calculant par brute-force la taille de la première réservation au regard de la caractérisation de la solution optimale. Nous fournissons également une heuristique basée sur une procédure de discrétisation de la densité de probabilité considérée couplée à un algorithme optimal de programmation dynamique pour la loi de probabilité discrète. Nous procédons à l'évaluation de la performance de nos heuristiques en utilisant deux modèles de plateforme différents, la première est une plateform orientée cloud-computing (i.e., Amazon AWS) avec des tâches suivant un grand nombre de lois de probabilité usuelles (i.e. Uniforme, Exponentielle, Log-Normale, Weibull, Beta etc), et une deuxième basée sur l'interpolation de traces d'applications de neurosciences exécutées sur une plateforme HPC. Des résults complets de simulation valident les stratégies de réservation proposées pour l'ordonnancement de tâches stochastiques.
Fichier principal
Vignette du fichier
research_report.pdf (1.55 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01903592 , version 1 (24-10-2018)
hal-01903592 , version 2 (31-01-2019)

Identifiers

  • HAL Id : hal-01903592 , version 2

Cite

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⟩
145 View
208 Download

Share

Gmail Facebook Twitter LinkedIn More