Reservation and Checkpointing Strategies for Stochastic Jobs (Extended Version)

Dans ce rapport, nous nous interessons a l’ordonnancement de tâches stochastiques executees sur une plateforme a reservations, ou l’utilisateur realise des requetes successives de temps de calcul. Le temps d’execution des tâches considerees n’est pas connu a l’avance. Ce temps est represente par une loi de probabilite, decrite sous la forme d’une densite de probabilite. Nous nous interessons a ordonnancer une instance d’une telle tâche, c’est a dire que nous ne connaissons pas son temps d’execution qui reste constant tout au long de l’ordonnancement. Dans ce cas, le cout de l’ordonnancement depend a la fois de la duree des requetes et du temps d’execution de la tâche consideree. Nous supposons de plus que la tâche peut etre interrompue a tout instant (tâche divisible) pour un point de sauvegarde. Nous avons donc la possibilite de prendre un point de sauvegarde a la fin de certaines reservations bien choisies. L’avantage est de pouvoir repartir de l’etat sauvegarde a la prochaine reservation au lieu de repartir du debut, si la tâche ne termine pas pendant la reservation courante. Le prix a payer est le temps de sauvegarde, et de redemarrage. L’objectif de ce travail est de determiner une strategie de reservation optimale qui minimise le cout total de l’ordonnancement. Une strategie de reservations est une sequence de requetes croissantes, qui sont payees les unes a la suite des autres en ordre croissant jusqu’a completion de la tâche. Pour chaque reservation, nous indiquons si un point de sauvegarde doit etre pris ou non. Nous decrivons une telle solution optimale pour des distributions de probabilite discretes, et nous donnons un schema d’approximation polynomial pour les distributions continues a sup- port compact. Nous comparons experimentalement ces strategies aux strategies usuelles qui incrementent la longueur de chaque reservation par une valeur constante, et qui decident de sauvegarder soit toutes les reservations, soit aucune. Nous utilisons un grand nombre de lois de probabilite usuelles (i.e. Uniforme, Exponentielle, Log-Normale, Weibull, Beta etc), ainsi qu’une distribution basee sur l’interpolation de traces d’applications de neurosciences executees sur une plateforme HPC.