Contiguity and Locality in Backfilling Scheduling

We consider the classical First Come First Served / backfilling algorithm which is commonly used in actual batch schedulers. As HPC platforms grow in size and complexity, an interesting question is how to enhance this algorithm in order to improve global performance by reducing the overall amount of communications. In this direction, we are interested in studying the impact of contiguity and locality allocation constraints on the behavior of batch scheduler. We provide a theoretical analysis of the cost of enforcing contiguity and locality properties. More specifically, we show that both properties do not impose strong limit on achievable make span performance while comparing feasible optimal solutions under different settings, we describe here the existing results on this topic and complete them with all combinations of constraints. We also propose a range of different allocation algorithms for backfilling by choosing between a strict or a soft enforcing of locality and contiguity. Our approach is validated through an extensive series of simulations based on batch scheduler traces. Experiments show that our algorithms do not increase the make span in average when comparing to actual practices. Interestingly, we observe that enforcing contiguity efficiently improves locality.