Scheduling heuristics for improved utilization in multi-resource parallel systems

Job scheduling schemes for multi-programmed, multi-resource systems is a mapping of available system resources to the jobs in the incoming job stream in such a way as to meet some performance objective. Recent studies have shown that the performance of many important scientific parallel applications is dependent upon the simultaneous availability of multiple critical resources. In this thesis, we define a generalized K-resource aware scheduling problem, where each job has K critical resource requirements and the system has K corresponding resource capabilities. We present a new heuristic for the generalized K-resource job scheduling problem, which we call resource balancing. The resource balancing heuristic uses information about the current utilization of the K system resources and ranks the candidate jobs waiting in the input queue according to how well they fit into the available system resources. This heuristic avoids the problem of premature resource depletion, which occurs when a single system resource becomes fully utilized while other resources remain partially idle.; We have applied the resource balancing heuristic to three related K-resource scheduling problems to show its versatility. The first of these is the K-resource bin-packing problem, where we use resource-balancing heuristics to guide item to bin matching. The second problem is the K-resource single server job scheduling problem, where we extend current backfill-based algorithms with an intelligent backfill job selection algorithm, based on balancing the server resources which are under-utilized in the current scheduling epoch. Finally, we extend the K-resource server model to an analogous K-resource load balancing problem, in which multiple K-resource servers are interconnected via a network. Here we apply the resource balancing heuristics to the load balancing policies so that the workload maintained at each server matches the resource configuration of that server. Our common goal for each case was to improve the utilization of the system resources. For each case, we constructed a model of the system, and simulated the performance of our algorithms against the classical algorithms on a synthetic workload. In all cases, our resource-balancing algorithms outperformed the corresponding classical algorithms, achieving significant improvements in total system resource utilization.