{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:40:47Z","timestamp":1787388047260,"version":"build-2736575974"},"reference-count":16,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1987,10]]},"abstract":"<jats:p>We describe a nonuniform deterministic simulation of PRAMs on module parallel computers (MPCs) and on processor networks of bounded degree. The simulating machines have the same number n of processors as the simulated PRAM, and if the size of the PRAM\u2019s shared memory is polynomial in n, each PRAM step is simulated by $O(\\log n)$ MPC steps or by $O((\\log n)^2 )$ steps of the bounded-degree network.This improves upon a previous result by Upfal and Wigderson. We also prove an $\\Omega ({{(\\log n)^2 } \/ {\\log \\log n}})$ lower bound on the number of steps needed to simulate one PRAM step on a bounded-degree network under the assumption that the communication in the network is point to point. As an important part of the simulation of PRAMs on MPCs, we use a new technique for dynamically averaging out a given work load among a set of processors operating in parallel.<\/jats:p>","DOI":"10.1137\/0216053","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:28:18Z","timestamp":1109226498000},"page":"808-835","source":"Crossref","is-referenced-by-count":51,"title":["Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones"],"prefix":"10.1137","volume":"16","author":[{"given":"Helmut","family":"Alt","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Torben","family":"Hagerup","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kurt","family":"Mehlhorn","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Franco P.","family":"Preparata","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.37"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Koml\u00f3s, E. Szemer\u00e9di,  An  $O(n \\log n)$ sorting network,  Proc. 15th Annual ACM Symposium on Theory of Computing,  1983,  1\u20139","DOI":"10.1145\/800061.808726"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"K. E. Batcher,  Sorting networks and their applications,  Proc. AFIPS Spring Joint Computer Conference, Vol. 32,  1968,  307\u2013314","DOI":"10.1145\/1468075.1468121"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"A. Borodin, J. E. Hopcroft,  Routing, merging, and sorting on parallel models of computation,  Proc. 14th Annual ACM Symposium on Theory of Computing,  1982,  338\u2013344","DOI":"10.1145\/800070.802209"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804339"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.16"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/356683.356686"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"A. R. Karlin, E. Upfal,  Parallel hashing\u2013an efficient implementation of shared memory,  Proc. 18th Annual ACM Symposium on Theory of Computing,  1986,  160\u2013168","DOI":"10.1145\/12130.12146"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"T. Leighton,  Tight bounds on the complexity of parallel sorting,  Proc. 16th Annual ACM Symposium on Theory of Computing,  1984,  71\u201380","DOI":"10.1145\/800057.808667"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264615"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1090\/coll\/038"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1145\/358645.358660"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0012790"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"E. Upfal,  A probabilistic relation between desirable and feasible models of parallel computation,  Proc. 16th Annual ACM Symposium on Theory of Computing,  1984,  258\u2013265","DOI":"10.1145\/800057.808689"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"E. Upfal, A. Wigderson,  How to share memory in a distributed system,  Proc. 25th Annual IEEE Symposium on Foundations of Computer Science,  1984,  171\u2013180","DOI":"10.1109\/SFCS.1984.715913"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80003-5"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0216053","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:43:49Z","timestamp":1787337829000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0216053"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,10]]},"references-count":16,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1987,10]]}},"alternative-id":["10.1137\/0216053"],"URL":"https:\/\/doi.org\/10.1137\/0216053","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987,10]]}}}