Analysis of Processor Allocation in Multiprogrammed, Distributed-Memory Parallel Processing Systems

Abstract

A main objective of scheduling indenendent jobs composed of multiple sequential tasks in shared-memory and distributed-memory multiprocessor computer systems is the assignment of these tasks to processors in a manner that ensures efficient operation of the system. Achieving this objective requires the analysis of a fundamental tradeoff between maximizing parallel execution, suggesting that the tasks of a job be spread across all system processors, and minimizing synchronization and communication overheads, suggesting that the job’s tasks be executed on a single processor. We consider a class of scheduling policies that represent the essential aspects of this processor allocation tradeoff, and we model the system as a distributed fork-join queueing system. We derive an approximation for the expected job response time which includes the important effects of various parallel processing overheads (such as task synchronization and communication) induced by the processor allocation policy. The relative error of our approximation is typically less than 5%, though considerably smaller in most cases. Our results show that the best solution to the processor allocation problem is an adaptive scheduling policy that spreads the tasks of a job across all system processors when load is light, and continuously restricts the degree of parallel job execution with increasing system load. We further demonstrate how quickly the benefits of parallel processing are negated by its associated overheads across distributed multiprocessor environments, and we quantify the performance differences among the range of policies from all-processors allocation to single-processor allocation. © 1994 IEEE