Job Scheduling for HPC Clusters: Constraint Programming vs. Backfilling Approaches
Alexander V. Goponenko, Kenneth Lamar, Benjamin A. Allan, James M. Brandt, Damian Dechev · 2024
Scheduling problems are naturally formulated in terms of Constraint Programming (CP), yet the application of CP-based approaches for job scheduling on High-Performance Computing (HPC) clusters remains underexplored. This study aims to bridge this gap by analyzing the scheduling of diverse real workload traces using IBM ILOG CP Optimizer. The analysis considers not just the basic metrics Average Bounded Slowdown and Average Response Time, but also Area-Weighted Average Response Time and Level-2 Priority-Weighted Specific Time, which measure packing efficiency and fairness. For each workload trace and metric combination, schedules produced through optimizing the metric with CP Optimizer are compared against schedules generated by the variants of the list scheduling with backfilling that are most suitable for the metric. The CP-based scheduling improves scheduling quality in most of the examined cases. The analysis of the metrics that represent different scheduling goals uncovers several non-trivial insights. Presently, CP Optimizer still encounters scalability issues with large wait queues and non-linear objective functions. Nonetheless, it often demonstrates improvements in packing efficiency, which make CP techniques attractive, particularly in scenarios where high-maintenance clusters run a moderate number of large, rigid, well-characterized jobs.