Certified lower and upper bounds on the pooled core capacity of an industrial compute farm under bounded job waiting times

Abstract

How many cores does a batch compute farm need if every job must start within a bound of its submission, and how much do waiting and job suspension save? We answer for a mod-el that pools the cores of each pool and knows the jobs in advance, on one month of ac-counting logs of four pools of Intel’s NetBatch farm, with 48,821,850 records. The non-preemptive problem is strongly NP-hard, so we bracket the optimum between energetic lower bounds, computed per interval length in time linear in the number of jobs and the horizon, and verified greedy list schedules found by binary search. In a pre-specified study, with three pools sealed until the plan was frozen, a bound of 1 h would lower the capacity needed without waiting by between 22.1% and 25.3% in pool A and between 17.9% and 21.8% in pool B, but only between 4.0% and 4.4% in pool D, so the hypothesis that it saves less than 10% was not supported; the second half of the month alone would have supported it in pool B. Suspension would save at most 0.4% more in pool D; in pools A and B the bounds could not decide whether it saves less than 2%, and by design they could never show that it saves more. On small instances solved exactly, the lower bound with the grid of the pools equalled the optimum in 27 of 31 cases, and the list schedule exceeded it by up to 28.9%. The frontiers price a waiting bound in pooled cores, a lower bound on what real machines would need, and the price differs strongly between pools and over time.