Resource Scheduling for Parallel Database and Scientific Applications

Abstract

We initiate a study of resource scheduling problems in parallel database and scientific applications. Based on this study we formulate a problem. In our formulation, jobs specify their running times and amounts of a fixed number of other resources (like memory, IO) they need. The resourcetime trade-off may be fundamentally different for different resource types. The processor resource is malleable, meaning we can trade processors for time gracefully. Other resources may not be malleable. One way to model them is to assume no malleability: the entire requirement of those resources has to be reserved for a job to begin execution, and no smaller quantity is acceptable. The jobs also have precedences amongst them; in our applications, the precedence structure may be restricted to being a collection of trees or series-parallel graphs.
Not much is known about considering precedence and non-malleable resource constraints together. For many other problems, it has been possible to find schedules whose length match to a constant factor the sum of two obvious lower bounds: the total resource-time product of jobs, denoted V, and the critical path in the precedence graph, denoted II. We show that there are instances when the optimal makespan is OMEGA(V + II log T) in our model. Here T is the ratio between longest and shortest job execution times, where typically T << n, the number of jobs.
We then give a polynomial time makespan algorithm that produces a schedule of length O(V + II log T), which is therefore an O(logT) approximation. This contrasts with most existing solutions for this problem, which are greedy, list-based strategies. These fail under heavy load and that is provably unavoidable since theoretical results have established various adversaries for them that force OMEGA(T) or OMEGA(n) approximations. The makespan algorithm can be extended to minimize the weighted average completion time over all the jobs to the same approximation factor of O(log T).