A Stochastic Model of Multiprocessing.

Abstract

A model of the behavior of multiprocessor systems consisting of processors, an interconnection network, and resource modules--typically memory devices--is developed. The model allows processor activity to be represented using stochastic finite state machines. These stochastic finite state machines may reflect program activity directly, or alternatively may reflect other levels of processor activity. The model is based on approximating processor behavior using semi-Markov processes, one for each processor. Using the semi-Markov descriptions, expressions are obtained for a set of performance measures that may be used to evaluate system performance at the level of system operation chosen for processor representation. The set of performance measures includes timing measures such as mean rates of computation, mean program execution times, and system component utilizations. The model is appropriate for more general systems where requestors, whose behavior may be modeled as semi-Markov processes, contend for system resources. In evaluating semi-Markov process quantities, queueing approximations are developed for waiting times in resource queues present within the multiprocessor system. The queueing approximations also have applications in small finite-customer queueing network analysis. The model provides a framework and a set of analysis techniques that may be used in the development of models for specific applications. The model described unifies and extends previous models of multiprocessor resource contention by allowing more sophisticated descriptions of processor activity to be used.