Backlling Using Runtime Predictions Rather Than User Estimates

The most commonly used scheduling algorithm for parallel super-computers is FCFS with backlling, as originally introduced in the EASY scheduler. Backlling means that short jobs are allowed to run ahead of their time provided they do not delay previously queued jobs (or at least the rst queued job). To make such de-terminations 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 signicantly better. Remarkably, predictions were never in-corporated into production schedulers. One reason explaining this anomaly is studies claiming inaccuracy is actually good for per-formance. More important is the fact no study overcame the dif-culty of what to do when job runtimes exceed system generated predictions: with backlling 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 cor-rected adaptively if proved wrong. The end result is a surprisingly simple scheduler we call EASY++, which requires minimal devi-ations from current practices (e.g. using FCFS as the basis), and behaves exactly like EASY as far as users are concerned. Never-theless it achieves signicant improvements in performance, pre-dictability, 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 backlling algorithm previously suggested. 1