When trying to minimize the mean response time of parallel programs in a multiprogrammed environment, a fundamental tension exists between allocating a sufficiently large number of processors to a job (in order to minimize its execution time) and allocating a sufficiently small number of processors (in order to maximize the efficiency with which the processors are used). This tension exists because if one job is not efficiently utilizing the processors it has been allocated, another job might be able to make better use of them. The problem of minimizing mean response time is further complicated by other factors: the amount of work to be executed by each job (its service demand) and the arrival of new jobs.
Understanding that the optimal uniprocessor scheduling policy executes the job with the Shortest Remaining Processor Time (SRPT) first has led to significant improvements in many uniprocessor scheduler implementations, even though the execution time of jobs is not known a priori . For example, one of the objectives of multi-level feedback queue schedulers [6, 2, 15], popular in many UNIX systems, is to try to approximate the SRPT algorithm by decreasing the amount of CPU time (the number of quantums) allocated to long running jobs. This approach helps to complete shorter jobs first and reduces mean response time when compared with a Round Robin algorithm [16]. Policies that attempt to approximate a SRPT approach have been proposed and studied in multiprocessor scheduling contexts [20, 32, 3]. However, we believe that such strategies must also consider the efficiency with which parallel programs execute.
Previous work has suggested approaches for obtaining estimates of a job's efficiency during runtime [3]. Recently, Nguyen, Vaswani, and Zahorjan [25, 24] have experimentally demonstrated that such estimates can in fact be determined by monitoring the job's execution during run time. They also find that the performance of scheduling policies that use these estimates achieve performance surprisingly close to that possible when perfect a priori information is used.
We seek foundational insights into the properties of effective scheduling algorithms for multiprogrammed multiprocessors by examining policies that assume a priori knowledge of job characteristics (work and efficiency) to improve processor allocation decisions. We believe that these insights and resulting algorithms, when combined with the recently demonstrated techniques for obtaining job characteristics at runtime, can form the basis of future multiprocessor scheduler implementations.
In this paper we use simulations to evaluate a number of different processor allocation policies that are designed to reduce mean response time when compared with an equipartition policy. In Section 2 we discuss related work. This is followed by descriptions of the job, workload and system models, in Section 3. In Section 4 we describe a generalization of a family of processor allocation policies. We then use this generalization to explore a spectrum of policies that make processor allocation decisions based on the work a job executes (in Section 5), the efficiency with which jobs execute (in Section 6) and the knee of the execution time - efficiency profile (in Section 7). The results of these experiments show that while each approach is capable of reducing mean response time, the reductions are either relatively small or limited to a relatively small subset of possible workloads. In Section 8 we use the insights gained from these experiments to propose and evaluate a new strategy that incorporates characteristics of both a job's work and its efficiency. Our evaluation of this technique shows that it can be used to obtain significantly lower mean response times than equipartition under a variety of workloads. We present our conclusions in Section 9.