Qualitative Behavior of the EQS Parallel Processor Allocation Policy
Rajesh K. Mansharamani, Mary K. Vernon · 1993
This paper addresses these issues for an idealization of the Spatial EQuiallocation policy (EQS) and a workload model that characterizes the essential features of parallel applications with respect to scheduling discipline performance. Important features of the workload model include general distribution for available job parallelism, controlled correlation between available parallelism and total job processing requirement, general distribution of processing requirement per class of jobs in the correlation model, and general nondecreasing deterministic job execution rates (i.e., speedups) that represent synchronization and communication overheads as well as load imbalance for parallel programs. The performance of EQS is analyzed using sample path analysis to derive bounds and using highly efficient and extensively validated interpolation approximations to derive estimates for mean response time (REQS ). The bounds show that under exponential job processing requirements (demands) and any concave nondecreasing job execution rate function for all jobs REQS is minimum when all jobs are fully parallel and is maximum when all jobs are fully sequential. The upper bound is also shown to hold under very general workload conditions. The approximation is used to obtain the demand and parallelism parameters that are key determinants of EQS performance and to study the behavior of REQS as a function of changes in the workload. Mean response time is shown to decrease with stochastic increase in available parallelism, decrease in variability of parallelism, and increase in correlation. Under certain potentially realistic assumptions, the mean response time is also shown to be fairly insensitive to parallel program overheads.