Using knowledge of job characteristics in multiprogrammed multiprocessor scheduling
Kenneth C. Sevcik, Eric W. Parsons · 1997
Multiprocessors are being used increasingly to support workloads in which some or all of the jobs are parallel. For these systems, new scheduling algorithms are required to allocate resources in such a way as to offer good response times while being capable of sustaining high system loads. Until recently, research in this area has focussed on processors as the critical resource, but for many parallel workloads, memory will likely also become a concern. In this thesis, we investigate the design of parallel-job scheduling disciplines, considering simultaneously processors and memory as critical resources. First, we demonstrate that preemption is a necessary feature of parallel-job schedulers in order to obtain good response times given the types of workloads found in practice. Next, we develop analytic bounds on the achievable system throughput with respect to both processing and memory for the case where no knowledge exists about the speedup characteristics of individual jobs. Through the derivation of these bounds, we show that an equi-allocation scheduling discipline, one which allocates processors evenly among jobs selected to run, is the best approach. The key factor to obtaining good performance for such disciplines is to make effective use of memory. If the scheduler possesses speedup knowledge of jobs, however, then the equi-allocation strategy is no longer recommended for workloads in which there exists a correlation between the memory requirements of jobs and their speedup characteristics. In this case, it is theoretically possible to achieve an arbitrary increase in the sustainable throughput over equi-allocation by using this speedup information in allocating processors. Finally, we present the implementation of a family of scheduling disciplines, based on Platform Computing's Load Sharing Facility. Each of these disciplines makes different assumptions about the characteristics of the system, such as the type of preemption that is available or the flexibility that the system possesses in allocating processors. Through this work, we demonstrate, in a practical setting, that sophisticated parallel-jobs scheduling disciplines can be successfully implemented and can deliver improved performance relative to disciplines typically being used today.