Scheduling batch and heterogeneous jobs with runtime elasticity in a parallel processing environment

Abstract

Today's schedulers for a parallel processing environment are generally optimized for submit-time elasticity of batch jobs only, where resource needs are specified only at submission time. They are not designed for runtime elasticity of heterogeneous workloads comprising both batch and interactive jobs. By runtime elasticity it is meant that resource requirements for a job can change during its execution. This paper examines today's workload models and schedulers from this novel perspective. We show the need for an extended workload model with runtime elasticity. We then propose Delayed-LOS and Hybrid-LOS, two novel scheduling algorithms that improve and build on an existing Dynamic Programming based scheduler (LOS) designed only for batch jobs. While Delayed-LOS improves significantly over LOS, Hybrid-LOS is specifically designed for heterogeneous parallel workloads. We further propose elastic versions of these algorithms that incorporate runtime elasticity as well. Extensive simulations with GridSim framework demonstrate that Delayed-LOS & Hybrid-LOS improve average utilization by up to 4.1% & 4.55%, thereby reducing mean job-waiting time and slowdown by up to 31.88% & 25.31% and 30.3% & 24.29%, respectively. © 2012 IEEE.