|
Abstract : |
ABSTRACT. The first result of this paper is a lower bound on mean response time, under very general workload assumptions, per class of multiprogrammed parallel processor allocation policies. Each class of parallel allocation policies is defined by the information structure of the policies. Each bound is derived from the mean response time of the optimal uniprocessor scheduling policy that uses (at least) the same workload information as the class of parallel processor allocation policies. The derivation of the bound also suggests how tighter bounds can be obtained for individual parallel processor allocation policies in some cases. The workload assumptions include general distributions of total job processing requirment, desired job parallelism, and inter-arrival times, general job execution rate functions (i.e., general speedup curves), and arbitrary dependencies among these workload variables. The second result is that for linear execution rates (i.e., perfect speedups) and for i.i.d. exponential job demands that are independent of all other variables, the Preemptive Smallest Desired Parallelism First policy is optimal among policies that use no explicit information about job demand. Likewise, among all processor conserving policies the Preemptive Largest Desired Parallelism First policy is pessimal. For the same assumptions it is also shown that the performance of a processor conserving policy is best when every job can make use of all processors and is worst when all jobs are fully sequential, leading to computable per-policy bounds on mean response time. Quantitative results are given that illustrate the use and tightness of the various bounds. The second and third result are also shown to be sensitive to, |
