Maximal throughput for stability of a class of parallel processing systems

Author

Bambos, Nicholas ; Walrand, Jean

Author_Institution

Dept. of Electr. Eng., California Univ., Los Angeles, CA, USA

fYear

1990

fDate

5-7 Dec 1990

Firstpage

161

Abstract

Considered are a parallel processing system consisting of a finite number of identical processors that can work concurrently, and a random stream of arriving jobs, each requiring for its execution a random number of processors to be engaged concurrently for some random processing time. Arriving jobs are placed in an infinite capacity buffer and are allocated to the processors to be executed nonpreemptively. The arrival times, the number of concurrently required processors, and the processing times of the jobs form a stationary and ergodic sequence. The queueing theoretic stability aspects of this system raised because of the infinite capacity buffer are discussed. It is concluded that if the arrival date λ* of jobs to the system is greater than some threshold value λ*, the system is unstable under any possible processing scheme (allocation policy of jobs to processors) used to operate it. However, for any arrival rate λ less than λ*, a processing scheme is constructed which keeps the system stable

Keywords

optimisation; parallel processing; queueing theory; scheduling; stability; arrival times; capacity buffer; job allocation; job scheduling; maximal throughput; parallel processing systems; processing times; queueing theory; stability; Automatic control; Buffer storage; Concurrent computing; Parallel processing; Processor scheduling; Queueing analysis; Resource management; Stability; Throughput; Time factors;

fLanguage

English

Publisher

ieee

Conference_Titel

Decision and Control, 1990., Proceedings of the 29th IEEE Conference on

Conference_Location

Honolulu, HI

Type

conf

DOI

10.1109/CDC.1990.203568

Filename

203568