Improving Parallel Job Scheduling by Combining Gang Scheduling and Backfilling Techniques

Effective scheduling strategies to improve response times, throughput, and utilization are an important consideration in large supercomputing environments. Such machines have traditionally used space-sharing strategies to accommodate multiple jobs at the same time. This approach, however, can result in low system utilization and large job wait times. There have been two recent approaches to address this problem: (a) augmenting space sharing with backfilling, which performs out of order job scheduling; and (b) augmenting space sharing with time sharing, using a technique called coscheduling or gang scheduling. Logically, it appears that one could combine these two approaches into a strategy that uses backfilling with gang scheduling. However, this has not been considered as a viable option until now, because of the difficulty in estimating job execution time, as required for backfilling. With three important experimental results -- impact of priority queue order on backfilling, impact of overestimation of job execution times, and comparison of scheduling techniques -- this paper presents an integrated strategy that combines backfilling with gang scheduling. Using extensive simulations based on detailed models of realistic workloads, the benefits of combining backfilling and gang scheduling are clearly demonstrated over a spectrum of performance criteria.