Backfilling Using Runtime Predictions Rather Than User Estimates
Dan Tsafrir, Yoav Etsion, Dror G. Feitelson · 2005
The most commonly used scheduling algorithm for parallel supercomputers is FCFS with backfilling, as originally introduced in the EASY scheduler. Backfilling means that short jobs are allowed to run ahead of their time provided they do not delay previously queued jobs (or at least the first queued job). To make such determinations possible, users are required to provide estimates of how long jobs will run, and jobs that violate these estimates are killed. Empirical studies have repeatedly shown that user estimates are inaccurate, and that history-based system generated predictions may be significantly better. Remarkably, predictions were never incorporated into production schedulers. One reason explaining this anomaly is studies claiming inaccuracy is actually good for performance. More important is the fact no study overcame the difficulty of what to do when job runtimes exceed system generated predictions: with backfilling such jobs are killed, but users will not tolerate jobs being killed just because system predictions were too short. We solve this problem by divorcing kill-time from the runtime prediction. To make this work, predictions need to be corrected adaptively if proved wrong. The end result is a surprisingly simple scheduler we call EASY++, which requires minimal deviations from current practices (e.g. using FCFS as the basis), and behaves exactly like EASY as far as users are concerned. Nevertheless it achieves significant improvements in performance, predictability, and accuracy, and we argue it can (and in our opinion should) replace the default currently in use on production systems. In addition, our techniques can be used to enhance any backfilling algorithm previously suggested.