Access Restriction

Author Bambos, Nicholas ♦ Walrand, Jean
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1991
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Database concurrency control ♦ Parallel processing ♦ Queueing networks ♦ Queueing theory ♦ Stability theory ♦ Subadditive ergodic theory
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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1991-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 38
Issue Number 2
Page Count 24
Starting Page 429
Ending Page 452

Open content in new tab

   Open content in new tab
Source: ACM Digital Library