Scheduling Batch and Heterogeneous Jobs with Runtime Elasticity in a Parallel Processing Environment

, and
IEEE International Parallel and Distributed Processing Symposium Workshops, the 21st International Heterogeneity in Computing Workshop (HCW)
Shanghai, China,
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 DelayedLOS & 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.
Bibtex. 
@inproceedings{kumar-IPDPS-HCW-workshop-2012,
author = {Dinesh and Kumar and Hani and Jamjoom and Zon-yin and Shae},
title = {{Scheduling Batch and Heterogeneous Jobs with Runtime Elasticity in a Parallel Processing Environment}},
booktitle = {IEEE International Parallel and Distributed Processing Symposium Workshops, the 21st International Heterogeneity in Computing Workshop (HCW)},
address = {Shanghai, China},
month = {May},
year = {2012}
}