language: en

Approximate Analysis of Parallel Processor Allocation Policies *

Rajesh K. Mansharamani and Mary K. Vernon
(mansha@cs.wisc.edu) (vernon@cs.wisc.edu)
Computer Sciences Department University of Wisconsin
1210 West Dayton Street Madison, WI 53706.
November 29, 1993

Abstract The complexity of parallel applications and parallel processor scheduling policies makes both exact analysis and simulation difficult, if not intractable, for large systems. In this paper we propose a new approach to performance modeling of multiprogrammed processor scheduling policies, that of interpolation approximations. We first define a workload model that contains parameters for the essential properties of parallel applications with respect to scheduling discipline performance, yet lends itself to mathematical analysis. Key features of the workload model include general distribution of total job processing time, general distribution of available job parallelism, and a simple characterization of parallelism overheads. We then show that one can find specific values of the system parameters for which the parallel system under a given scheduling policy reduces to a queueing system with a known (closed-form) solution. Finally, interpolation between the points with known solutions is used to arrive at mean response time estimates that hold over the entire system parameter space. The interpolation approximations readily yield insight into policy behavior and are easy to evaluate for systems with hundreds of processors. We illustrate the approach by developing and validating models of three scheduling policies, under the assumptions of linear job execution rates and independence between job parallelism and processing time. We discuss several insights and results obtained from the analysis of the three policies under the assumed workloads. One result clarifies and generalizes observations in two previous simulation studies of how policy performance varies with the coefficient of variation in job processing requirement. Another result of the interpolation models yields new insight into how policy performance varies with job parallelism. We also comment on the generalizations of these insights for workloads with less restrictive assumptions.

[This research was partially supported by the National Science Foundation under grants CCR-9024144 and CDA-9024618.]