A framework for parallel job scheduling
Raghu Subramanian · 1996
The problem considered in this thesis is how to run a workload of multiple parallel jobs on a single parallel machine. Jobs are assumed to be data-parallel with large degrees of parallelism, and the machine is assumed to have an MIMD architecture. We identify a spectrum of scheduling policies between the two extremes of time-slicing, in which jobs take turns to use the whole machine, and space-slicing, in which jobs get disjoint subsets of processors for their own dedicated use. Each of these scheduling policies is evaluated using a metric suited for interactive execution: the minimum machine power being devoted to any job, averaged over time. The following result is demonstrated. If there is no advance knowledge of job characteristics (such as running time, I/O frequency and communication locality) the best scheduling policy is gang-scheduling with instruction-balance. This conclusion validates some of the current practices in commercial systems. The proof uses the notions of clairvoyant adversaries and competitive ratios, drawn from the field of on-line algorithms. The work is then extended to irregular jobs, i.e., jobs in which the degree of parallelism varies during execution. It is shown that even though the scheduler may grant an irregular job substantial machine power, the job may not be able to harness that power efficiently unless it receives special run-time support in the form of load-balancing. A unified analysis is then presented to compare and evaluate various load-balancing schemes. We conclude with some preliminary ideas on the interaction between scheduling and other functions of the operating systems, such as dynamic memory allocation, virtual memory and I/O.