Deviation Backfilling: A Robust Backfilling Scheme for Improving the Efficiency of Job Scheduling on High Performance Computing Systems
Authors:
- 22 November 2023
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 32-37
Abstract
The Big Data era has led to the rapid development of modern sciences. Making effective use of extremely large amounts of collected data is putting extremely urgent demands on High Performance Computing (HPC) systems, especially the resource allocation process, which is commonly managed by the job scheduler. Despite the potential for improved scheduling outcomes offered by modern algorithms, these systems still continue to favor the FCFS and EASY backfilling approach due to its straightforward implementation and fair resource allocation. In this paper, we propose a novel and robust backfilling scheme called Deviation Backfilling to enhance the efficiency of job scheduling on HPC systems while maintaining user fairness. Combined with the job runtime prediction method using kNN, the Deviation Backfilling uses the deviation between user estimates and system prediction as the delay threshold for the first job at the backfilling queue. Our experimental results show that Deviation Backfilling outperforms existing scheduling strategies regarding performance metrics on real-world datasets. This performance improvement also signifies the capability to motivate users to offer more accurate estimates for assisting the HPC scheduling procedures.Keywords
This publication has 15 references indexed in Scilit:
- A Working time Deadline-based Backfilling Scheduling solution2020
- Machine Learning Predictions for Underestimation of Job Runtime on HPC System2018
- Batsim: A Realistic Language-Independent Resources and Jobs Management Systems Simulator2017
- Fattened backfilling: An improved strategy for job scheduling in parallel systemsJournal of Parallel and Distributed Computing, 2016
- Experience with using the Parallel Workloads ArchiveJournal of Parallel and Distributed Computing, 2014
- The Impact of More Accurate Requested Runtimes on Production Job Scheduling Performance2002
- Metrics for Parallel Job Scheduling and Their Convergence2001
- Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backfillingIEEE Transactions on Parallel and Distributed Systems, 2001
- The EASY — LoadLeveler API project1996
- NP-complete scheduling problemsJournal of Computer and System Sciences, 1975