{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T05:16:06Z","timestamp":1672290966190},"reference-count":12,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1991,4]]},"abstract":"The general problem of parallel (concurrent) processing is investigated from a queuing theoretic point of view.<\/jats:p>\n 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.<\/jats:p>\n 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\/\u221e queuing systems as special extreme cases.<\/jats:p>\n 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.<\/jats:p>\n 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.<\/jats:p>\n 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.<\/jats:p>","DOI":"10.1145\/103516.103520","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:25:57Z","timestamp":1027769157000},"page":"429-452","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["On stability and performance of parallel processing systems"],"prefix":"10.1145","volume":"38","author":[{"given":"Nicholas","family":"Bambos","sequence":"first","affiliation":[{"name":"Univ. of California at Los Angeles, Los Angeles"}]},{"given":"Jean","family":"Walrand","sequence":"additional","affiliation":[{"name":"Univ. of California at Berkeley, Berkeley"}]}],"member":"320","published-online":{"date-parts":[[1991,4]]},"reference":[{"key":"e_1_2_1_1_2","series-title":"Lecture Notes in Statisncs. vol 41","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-7561-0","volume-title":"Paim probabilities and stationary queues","author":"BACCELLI F.","year":"1987","unstructured":"BACCELLI , F. , AND BREMAUD , P. Paim probabilities and stationary queues . In Lecture Notes in Statisncs. vol 41 . Sprmger-Verlag , New York , 1987 . BACCELLI, F., AND BREMAUD, P. Paim probabilities and stationary queues. In Lecture Notes in Statisncs. vol 41. Sprmger-Verlag, New York, 1987."},{"key":"e_1_2_1_2_2","volume-title":"INRIA Sophia Antipolls","author":"BACCELLI F.","year":"1988","unstructured":"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 . 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."},{"key":"e_1_2_1_3_2","unstructured":"FRANKEN P KOFNIG D. ARNDT U. AND SCHMIDT V Verlag Berhn Germany 1982. Queues and point processes Akademle FRANKEN P KOFNIG D. ARNDT U. AND SCHMIDT V Verlag Berhn Germany 1982. Queues and point processes Akademle"},{"key":"e_1_2_1_4_2","first-page":"499","article-title":"The ergodic theory of subadditlve stochasnc processes","volume":"30","author":"KINGMAN J. F.","year":"1968","unstructured":"KINGMAN , J. F. C . The ergodic theory of subadditlve stochasnc processes . J. Roy. Statist. Soc., Ser. B 30 ( 1968 ), 499 - 510 . KINGMAN, J. F. C. The ergodic theory of subadditlve stochasnc processes. J. Roy. Statist. Soc., Ser. B 30 (1968), 499-510.","journal-title":"J. Roy. Statist. Soc., Ser. B"},{"key":"e_1_2_1_5_2","volume-title":"Subaddmve ergo&c theory. Annals Prob. 1, 6","author":"KINGMAN J. F.","year":"1973","unstructured":"KINGMAN , J. F. C. Subaddmve ergo&c theory. Annals Prob. 1, 6 ( 1973 ), 883-909 KINGMAN, J. F. C. Subaddmve ergo&c theory. Annals Prob. 1, 6 (1973), 883-909"},{"key":"e_1_2_1_6_2","volume-title":"V-1975","author":"KINGMAN J. F.","unstructured":"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 York 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 York"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1017\/S0305004100036781","article-title":"The stab~llty of a queue with non-independent rater-arrival and service times Proc","volume":"58","author":"LOYNES R. M","year":"1962","unstructured":"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 . 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.","journal-title":"Cambridge Philosophzcal Soc."},{"key":"e_1_2_1_8_2","author":"MATTHES K","year":"1978","unstructured":"MATTHES , K , KERSTAN , J., 4ND MECKE, J.Infinitely Divzszble Point Processes. Akademle Verlag, Berlin , 1978 . MATTHES, K, KERSTAN, J., 4ND MECKE, J.Infinitely Divzszble Point Processes. Akademle Verlag, Berlin, 1978.","journal-title":"J., 4ND MECKE, J.Infinitely Divzszble Point Processes. Akademle Verlag, Berlin"},{"key":"e_1_2_1_9_2","volume-title":"The Theoo' of Database Concurrency Control","author":"PAPADIMITRIOU C.","year":"1986","unstructured":"PAPADIMITRIOU , C. The Theoo' of Database Concurrency Control . Computer Science Press , New York , 1986 . PAPADIMITRIOU, C. The Theoo' of Database Concurrency Control. Computer Science Press, New York, 1986."},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5936"},{"key":"e_1_2_1_11_2","volume-title":"Prentace Hail","author":"WALRAND J.","year":"1988","unstructured":"WALRAND , J. An Introduction to Queuing Networks . Prentace Hail , New York , 1988 WALRAND, J.An Introduction to Queuing Networks. Prentace Hail, New York, 1988"},{"key":"e_1_2_1_12_2","doi-asserted-by":"crossref","volume-title":"An lntroductlon to Ergodic Theory","author":"WALTERS P.","year":"1982","unstructured":"WALTERS , P. An lntroductlon to Ergodic Theory . Sprlnger-Verlag , New York , 1982 . WALTERS, P. An lntroductlon to Ergodic Theory. Sprlnger-Verlag, New York, 1982.","DOI":"10.1007\/978-1-4612-5775-2"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/103516.103520","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T16:28:31Z","timestamp":1672244911000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/103516.103520"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,4]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1991,4]]}},"alternative-id":["10.1145\/103516.103520"],"URL":"http:\/\/dx.doi.org\/10.1145\/103516.103520","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1991,4]]},"assertion":[{"value":"1991-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}