Characterization of Backfilling Strategies for Parallel Job Scheduling

Although there is wide agreement that backfilling produces significant benefits in scheduling of parallel jobs, there is no clear consensus on which backfilling strategy is preferable e.g., should conservative backfilling be used or the more aggressive EASY backfilling scheme; should a First-Come First-Served (FCFS) queue-priority policy be used, or some other such as Shortest job First (SF) or eXpansion Factor (XF); In this paper, we use trace-based simulation to address these questions and glean new insights into the characteristics of backfilling strategies for job scheduling. We show that by viewing performance in terms of slowdowns and turnaround times of jobs within various categories based on their width (processor requestsize), length (job duration) and accuracy of the user's estimate of run time, some consistent trends may be observed.