Campaign Scheduling

Résumé : We study the problem of scheduling in parallel systems with many users. We analyze scenarios with many submissions issued over time by several users. These submissions contain one or more jobs; the set of submissions are organized in successive campaigns. Jobs belonging to a single campaign are sequential and independent, but any job from a campaign cannot start until all the jobs from the previous campaign are completed. Each user's goal is to minimize the sum of flow times of his campaigns. We define a theoretical model for Campaign scheduling and show that, in the general case, it is NP-hard. For the single-user case, we show that an ρ-approximation scheduling algorithm for the (classic) parallel job scheduling problem is also an ρ-approximation for the Campaign scheduling problem. For the general case with k users, we establish a fairness criterion inspired by time sharing. We propose FAIRCAMP, a scheduling algorithm which uses campaign deadlines to achieve fairness among users between consecutive campaigns. We prove that FAIRCAMP increases the flow time of each user by a factor of at most kρ compared with a machine dedicated to the user. We also prove that FAIRCAMP is a ρ-approximation algorithm for the maximum stretch. By simulation, we compare FAIRCAMP to the First-Come-First-Served (FCFS). We show that, compared with FCFS, FAIRCAMP reduces the maximum stretch by up to 3.4 times. The difference is significant in systems used by many (k > 5) users. Our results show that, rather than just individual, independent jobs, campaigns of jobs can be handled by the scheduler efficiently and fairly.
Type de document :
Communication dans un congrès
HiPC 2012 - 19th international Conference on High Performance Computing, Dec 2012, Pune, India. IEEE, High Performance Computing (HiPC), 2012 19th International Conference on, pp.1-10, 2012, 〈10.1109/HiPC.2012.6507489〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00796259
Contributeur : Grégory Mounié <>
Soumis le : samedi 2 mars 2013 - 14:13:49
Dernière modification le : mercredi 11 avril 2018 - 01:56:44

Identifiants

Citation

Vinicius Pinheiro, Krzysztof Razdca, Denis Trystram. Campaign Scheduling. HiPC 2012 - 19th international Conference on High Performance Computing, Dec 2012, Pune, India. IEEE, High Performance Computing (HiPC), 2012 19th International Conference on, pp.1-10, 2012, 〈10.1109/HiPC.2012.6507489〉. 〈hal-00796259〉

Partager

Métriques

Consultations de la notice

161