Contiguity and Locality in Backfilling Scheduling

International audienceWe consider the classical First Come First Served /backfilling algorithm which is commonly used in actual batchschedulers. As HPC platforms grow in size and complexity,an interesting question is how to enhance this algorithm inorder to improve global performance by reducing the overallamount of communications. In this direction, we are interestedin studying the impact of contiguity and locality allocationconstraints on the behavior of batch scheduler. We providea theoretical analysis of the cost of enforcing contiguity andlocality properties. More specifically, we show that both propertiesdo not impose strong limit on achievable makespanperformance while comparing feasible optimal solutions underdifferent settings; we describe here the existing results on thistopic and complete them with all combinations of constraints.We also propose a range of different allocation algorithms forbackfilling by choosing between a strict or a soft enforcingof locality and contiguity. Our approach is validated throughan extensive series of simulations based on batch schedulertraces. Experiments show that our algorithms do not increasethe makespan in average when comparing to actual practices.Interestingly, we observe that enforcing contiguity efficientlyimproves locality