Revised version published as "Backfilling with guarantees made as jobs arrive."
Written with A.M. Lindsay, M. Galloway-Carson, C.R. Johnson, and
V.J. Leung.
Concurrency and Computation: Practice and
Experience, special issue devoted to papers from the 17th
International European Conference on Parallel and Distributed
Computing (EuroPar),
volume 25, issue 4, pages 513-523, 2013.
©2012 John Wiley & Sons, Ltd.
Abstract:
In this paper, we present scheduling algorithms that simultaneously support guaranteed starting times and favor jobs with system-desired traits. To achieve the first of these goals, our algorithms keep a profile with potential starting times for every unfinished job and never move these starting times later, just as in Conservative Backfilling. To achieve the second, they exploit previously unrecognized flexibility in the handling of holes opened in this profile when jobs finish early. We find that, with one choice of job selection function, our algorithms can consistently yield a lower average waiting time than Conservative Backfilling while still providing a guaranteed start time to each job as it arrives. In fact, in most cases, the algorithms give a lower average waiting time than the more aggressive EASY backfilling algorithm, which does not provide guaranteed start times. Alternately, with a different choice of job selection function, our algorithms can focus the benefit on the widest submitted jobs, the reason for the existence of parallel systems. In this case, these jobs experience significantly lower waiting time than Conservative Backfilling with minimal impact on other jobs.