Nicholas Bambos
Abstract
The general problem of parallel (concurrent) processing is investigated from a queuing theoretic point of view.
As a basic simple model, consider infinitely many processors that can work simultaneously, and a stream of arriving jobs, each carrying a processing time requirement. Upon arrival, a job is allocated to a processor and starts being executed, unless it is blocked by another one already in the system. Indeed, any job can be randomly blocked by any preceding one, in the sense that it cannot start being processed before the one that blocks it leaves. After execution, the job leaves the system. The arrival times, the processing times and the blocking structures of the jobs form a stationary and ergodic sequence.
The random precedence constraints capture the essential operational characteristic of parallel processing and allow a unified treatment of concurrent processing systems from such diverse areas as parallel computation, database concurrency control, queuing networks, flexible manufacturing systems. The above basic model includes the G/G/1 and G/G/∞ queuing systems as special extreme cases.
Although there is an infinite number of processors, the precedence constraints induce a queuing phenomenon, which, depending on the loading conditions, can lead to stability or instability of the system.
In this paper, the condition for stability of the system is first precisely specified. The asymptotic behavior, at large times, of the quantities associated with the performance of the system is then studied, and the degree of parallelism, expressed as the asymptotic average number of processors that work concurrently, is computed. Finally, various design and simulation aspects concerning parallel processing systems are considered, and the case of finite number of processors is discussed.
The results proved for the basic model are then extended to cover more complex and realistic parallel processing systems, where each job has a random internal structure of subtasks to be executed according to some internal precedence constriants.
- 1 BACCELLI, F., AND BREMAUD, P. Paim probabilities and stationary queues. In Lecture Notes in Statisncs. vol 41. Sprmger-Verlag, New York, 1987.Google Scholar
- 2 BACCELLI, F., AND LIU, Z On the stability condmon of a precedence-based queuelng discipline Res. Rep No 880. INRIA Sophia Antipolls, France, July 1988.Google Scholar
- 3 FRANKEN, P , KOFNIG, D., ARNDT, U., AND SCHMIDT, V Verlag, Berhn, Germany, 1982. Queues and point processes AkademleGoogle Scholar
- 4 KINGMAN, J. F. C. The ergodic theory of subadditlve stochasnc processes. J. Roy. Statist. Soc., Ser. B 30 (1968), 499-510.Google Scholar
- 5 KINGMAN, J. F. C. Subaddmve ergo&c theory. Annals Prob. 1, 6 (1973), 883-909Google Scholar
- 6 KINGMAN, J. F. C Subaddiuve processes Ecole d'Ete de Probabitite de Salnt-Flour, V-1975. In P. L. Hennequln, Ed. Lecture Notes in Mathemattcs, vol. 539. Sprmger-Verlag, New YorkGoogle Scholar
- 7 LOYNES, R. M. The stab~llty of a queue with non-independent rater-arrival and service times Proc. Cambridge Philosophzcal Soc., 58 (1962), 497-520.Google Scholar
- 8 MATTHES, K, KERSTAN, J., 4ND MECKE, J.Infinitely Divzszble Point Processes. Akademle Verlag, Berlin, 1978.Google Scholar
- 9 PAPADIMITRIOU, C. The Theoo' of Database Concurrency Control. Computer Science Press, New York, 1986. Google Scholar
- 10 TSITSIKLIS, J., PAPADIMITRIOU, C., ~ND HUMBLET, P. The performance of a precedence-based queuing &scipline J. A CM 33, 3 (July 1986), 593-602. Google Scholar
- 11 WALRAND, J.An Introduction to Queuing Networks. Prentace Hail, New York, 1988Google Scholar
- 12 WALTERS, P. An lntroductlon to Ergodic Theory. Sprlnger-Verlag, New York, 1982.Google Scholar
Index Terms
- On stability and performance of parallel processing systems
Recommendations
On Parallel Processing Systems: Amdahl's Law Generalized and Some Results on Optimal Design
The authors model a job in a parallel processing system as a sequence of stages, each of which requires a certain integral number of processors for a certain interval of time. They derive the speedup of the system for two cases: systems with no arrivals,...
Some Equivalence Results for Load-Independent Exponential Queueing Networks
In this paper we derive a number of results concerning the behavior of closed load-independent exponential queueing networks. It is shown that if the service rate of any station is increased (decreased), then the throughput of the network itself also ...
Performance Analysis of Parallel Processing Systems
A bulk arrival M^x/M/c queueing system is used to model a centralized parallel processing system with job splitting. In such a system, jobs wait in a central queue, which is accessible by all the processors, and are split into independent tasks that can ...
Reviews
David Karl Probst
Following Tsitsiklis and Papadimitriou [1], the authors use queueing theory to investigate the stability and performance of parallel processing systems, assuming that precedence constraints among job executions are their most essential characteristic. A basic model of systems with an infinite number of processors is developed, in which the input process N also defines a set of random precedences on jobs. The basic model, in contrast to earlier work, assumes only stationaryness and ergodicity of the input. The parallel traffic intensity &ggr;, defined by the authors as a particular functional of the input N , allows them to specify the stability condition of the system. In theorem 1, the stability condition is shown to be &ggr; < 1. A disconcerting misprint occurs here; the instability condition should read &ggr; > 1. The asymptotic behavior of a number of performance measures is studied, including completion time, workload, processor number (that is, the number of active processors), and waiting time. In stable parallel processing systems, define the degree of parallelism &pgr; as the expected number of active processors in the stationary state. Theorem 4 shows this to be equal to the (ordinary) traffic intensity &rgr;. In Section 5, the need for a good statistical estimator of the parallel traffic intensity &ggr; is pointed out. Also, since only a finite number of processors of stable systems are active in the stationary state, this provides a bridge to more realistic models with a finite number of processors. The methods of this paper, which investigate how queueing phenomena arising from precedence constraints limit the full use of all the processors, may shed light on choosing the number of processors required for good performance. Section 6 studies more complex models, including one motivated by two-phase locking. In Section 8 (the conclusion), the authors argue that the “essentially qualitative nature” of their methods allows them to be applied to a broad range of queueing and processing systems.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments