On the execution of parallel programs on multiprocessor systems—a queuing theory approach

Abstract

The new class of queuing models, called Synchronized Queuing Networks , is proposed for evaluating the performance of multiprogrammed and multitasked multiprocessor systems, where workloads consists of parallel programs of similar structure and where the scheduling discipline is first-come-first-serve. Pathwise evolution equations are established for these networks that capture the effects of competition for processors and the precedence constraints governing tasks executions. A general expression is deduced for the stability condition of such queuing networks under general statistical assumptions (basically the stationarity and the ergodicity of input sequences), which yields the maximum program throughput of the multiprocessor system, or equivalently, the maximum rate at which programs can be executed or submitted. The proof is based on the ergodic theory of queues. Basic integral equations are also derived for the stationary distribution of important performance criteria such as the workload of the queues and program response times. An iterative numerical schema that converges to this solution is proposed and various upper and lower bounds on moments are derived using stochastic ordering techniques.