New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

Fine-grain Dynamic Resource Allocation vs. Batch Scheduling

SpeakerFrederic Vivien

Co-authorHenri Casanova and Mark Stillwell

We propose a novel job scheduling approach that shares cluster resources in a precise and controlled manner using virtual machine technology. We formalize the job scheduling problem, assess its complexity, and derive absolute performance bounds. We develop algorithms for the online, non-clairvoyant version of the problem. We evaluate these algorithms in simulation with both synthetic and real-world workloads. We find that our approach improves over batch scheduling by orders of magnitude in term of job stretch, while leading to comparable or better resource utilization. Our results demonstrate that virtualization technology coupled with lightweight scheduling strategies can afford dramatic improvements for executing HPC workload