{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T22:42:08Z","timestamp":1657233728500},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2022,3,22]],"date-time":"2022-03-22T00:00:00Z","timestamp":1647907200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,22]],"date-time":"2022-03-22T00:00:00Z","timestamp":1647907200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003945","name":"Link\u00f6ping University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003945","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Parallel Prog"],"published-print":{"date-parts":[[2022,8]]},"abstract":"Abstract<\/jats:title>SkePU is a pattern-based high-level programming model for transparent program execution on heterogeneous parallel computing systems. A key feature of SkePU is that, in general, the selection of the execution platform for a skeleton-based function call need not be determined statically. On single-node systems, SkePU can select among CPU, multithreaded CPU, single or multi-GPU execution. Many scientific applications use pseudo-random number generators (PRNGs) as part of the computation. In the interest of correctness and debugging, deterministic parallel execution is a desirable property, which however requires a deterministically parallelized pseudo-random number generator. We present the API and implementation of a deterministic, portable parallel PRNG extension to SkePU that is scalable by design and exhibits the same behavior regardless where and with how many resources it is executed. We evaluate it with four probabilistic applications and show that the PRNG enables scalability on both multi-core CPU and GPU resources, and hence supports the universal portability of SkePU code even in the presence of PRNG calls, while source code complexity is reduced.<\/jats:p>","DOI":"10.1007\/s10766-022-00726-5","type":"journal-article","created":{"date-parts":[[2022,3,22]],"date-time":"2022-03-22T11:03:33Z","timestamp":1647947013000},"page":"319-340","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Deterministic Portable Parallel Pseudo-Random Number Generator for Pattern-Based Programming of Heterogeneous Parallel Systems"],"prefix":"10.1007","volume":"50","author":[{"ORCID":"http:\/\/orcid.org\/0000-0001-6514-4601","authenticated-orcid":false,"given":"August","family":"Ernstsson","sequence":"first","affiliation":[]},{"given":"Nicolas","family":"Vandenbergen","sequence":"additional","affiliation":[]},{"given":"J\u00f6rg","family":"Keller","sequence":"additional","affiliation":[]},{"given":"Christoph","family":"Kessler","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,3,22]]},"reference":[{"key":"726_CR1","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/0021-9991(86)90032-X","volume":"64","author":"W Celmaster","year":"1986","unstructured":"Celmaster W., Kevin J.M.: Moriarty A method for vectorized random number generators. J. Comput. Phys. 64, 271\u2013275 (1986)","journal-title":"J. Comput. Phys."},{"issue":"7","key":"726_CR2","doi-asserted-by":"publisher","first-page":"3866","DOI":"10.1007\/s11227-019-02756-2","volume":"75","author":"T Ciglari\u010d","year":"2019","unstructured":"Ciglari\u010d T., \u0160trumbelj E., et al.: An OpenCL library for parallel random number generators. J. Supercomput. 75(7), 3866\u20133881 (2019)","journal-title":"J. Supercomput."},{"issue":"3","key":"726_CR3","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1016\/j.parco.2003.12.002","volume":"30","author":"M Cole","year":"2004","unstructured":"Cole M.: Bringing skeletons out of the closet: a pragmatic manifesto for skeletal parallel programming. Parallel comput. 30(3), 389\u2013406 (2004)","journal-title":"Parallel comput."},{"key":"726_CR4","volume-title":"Algorithmic Skeletons: Structured Management of Parallel Computation","author":"M Cole","year":"1989","unstructured":"Cole M.: Algorithmic Skeletons: Structured Management of Parallel Computation. Pitman and MIT Press, Cambridge, Mass (1989)"},{"key":"726_CR5","doi-asserted-by":"crossref","unstructured":"Danelutto M., Torquati M.: Structured parallel programming with \u201ccore\u201d FastFlow. In: Central European Functional Programming School, volume 8606 of LNCS, pages 29\u201375. Springer (2015)","DOI":"10.1007\/978-3-319-15940-9_2"},{"key":"726_CR6","doi-asserted-by":"crossref","unstructured":"Dastgeer U., Li L., Kessler C.: Adaptive implementation selection in the SkePU skeleton programming library. In: Advanced Parallel Processing Technologies, pages 170\u2013183. Springer (2013)","DOI":"10.1007\/978-3-642-45293-2_13"},{"issue":"24","key":"726_CR7","doi-asserted-by":"publisher","first-page":"4175","DOI":"10.1002\/cpe.4175","volume":"29","author":"D del Rio Astorga","year":"2017","unstructured":"del Rio Astorga D., Dolz M.F., Fern\u00e1ndez J, Garc\u00eda J.D.: A generic parallel pattern interface for stream and data processing. Concurrency Comput. Pract. Exp. 29(24), 4175 (2017)","journal-title":"Concurrency Comput. Pract. Exp."},{"key":"726_CR8","doi-asserted-by":"crossref","unstructured":"Enmyren J., Kessler C.: SkePU: A multi-backend skeleton programming library for multi-GPU systems. In: Proceedings of the fourth international workshop on High-level parallel programming and applications, pp. 5\u201314. ACM (2010)","DOI":"10.1145\/1863482.1863487"},{"key":"726_CR9","doi-asserted-by":"publisher","unstructured":"Ernstsson A., Ahlqvist J., Zouzoula S., Kessler C.: SkePU 3: Portable high-level programming of heterogeneous systems and HPC clusters. Int. J. Parallel Programm., May (2021) https:\/\/doi.org\/10.1007\/s10766-021-00704-3","DOI":"10.1007\/s10766-021-00704-3"},{"issue":"5","key":"726_CR10","doi-asserted-by":"publisher","first-page":"e5003","DOI":"10.1002\/cpe.5003","volume":"31","author":"A Ernstsson","year":"2019","unstructured":"Ernstsson A., Kessler C.: Extending smart containers for data locality-aware skeleton programming. Concurrency Comput. Pract. Exp. 31(5), e5003 (2019)","journal-title":"Concurrency Comput. Pract. Exp."},{"key":"726_CR11","unstructured":"Flajolet P., Odlyzko A.M.: Random mapping statistics. In: Jean-Jacques Quisquater and Joos Vandewalle, editors, Advances in Cryptology\u2014Proc. EUROCRYPT \u201989 Workshop on the Theory and Application of Cryptographic Techniques, Houthalen, Belgium, volume 434 of LNCS, pages 329\u2013354. Springer, (1989)"},{"key":"726_CR12","doi-asserted-by":"publisher","first-page":"308","DOI":"10.22237\/jmasm\/1430454120","volume":"14","author":"A Fog","year":"2015","unstructured":"Fog A.: Pseudo-random number generators for vector processors and multicore processors. J. Modern Appl. Stat. Meth. 14, 308\u2013334 (2015)","journal-title":"J. Modern Appl. Stat. Meth."},{"issue":"2","key":"726_CR13","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/S0167-8191(84)90072-3","volume":"1","author":"P Frederickson","year":"1984","unstructured":"Frederickson P., Hiromoto R., Jordan T.L., Smith B., Warnock T.: Pseudo-random trees in Monte Carlo. Parallel Comput. 1(2), 175\u2013180 (1984)","journal-title":"Parallel Comput."},{"issue":"4","key":"726_CR14","doi-asserted-by":"publisher","first-page":"1241","DOI":"10.1016\/j.cpc.2012.12.001","volume":"184","author":"S Gao","year":"2013","unstructured":"Gao S., Peterson G.D.: GASPRNG: GPU accelerated scalable parallel random number generator library. Computer Phys. Comm. 184(4), 1241\u20131249 (2013)","journal-title":"Computer Phys. Comm."},{"key":"726_CR15","unstructured":"Hanada M.: Markov chain Monte Carlo for dummies. arXiv:1808.08490 (2018)"},{"issue":"2","key":"726_CR16","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1145\/3282307","volume":"62","author":"JL Hennessy","year":"2019","unstructured":"Hennessy J.L., Patterson D.A.: A new golden age for computer architecture. Commun. ACM 62(2), 48\u201360 (2019)","journal-title":"Commun. ACM"},{"key":"726_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-77697-2","volume-title":"Random Numbers and Computers","author":"RT Kneusel","year":"2018","unstructured":"Kneusel R.T.: Random Numbers and Computers. Springer, Cham (CH) (2018)"},{"key":"726_CR18","volume-title":"The Art of Computer Programming. Seminumerical Algorithms","author":"DE Knuth","year":"1997","unstructured":"Knuth D.E.: The Art of Computer Programming. Seminumerical Algorithms, vol. 2, 3rd edn. Addison-Wesley Longman, Boston, MA (1997)","edition":"3"},{"key":"726_CR19","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.matcom.2016.05.005","volume":"135","author":"P L\u2019Ecuyer","year":"2017","unstructured":"L\u2019Ecuyer P., Munger D., Oreshkin B.N., Simard R.J.: Random numbers for parallel computers: requirements and methods, with emphasis on GPUs. Math. Comput. Simul. 135, 3\u201317 (2017)","journal-title":"Math. Comput. Simul."},{"key":"726_CR20","doi-asserted-by":"crossref","unstructured":"Leiserson C.E., Schardl T.B., Sukha J.: Deterministic parallel random-number generation for dynamic-multithreading platforms. In: Proc. 17th Symposium on Principles and Practice of Parallel Programming, page 193\u2013204. ACM, (2012)","DOI":"10.1145\/2370036.2145841"},{"key":"726_CR21","doi-asserted-by":"crossref","unstructured":"Marques R., Paulino H., Alexandre F., Medeiros P.D.: Algorithmic skeleton framework for the orchestration of GPU computations. In: Euro-Par 2013 Parallel Processing, volume LNCS 8097, pages 874\u2013885. Springer, (2013)","DOI":"10.1007\/978-3-642-40047-6_86"},{"issue":"3","key":"726_CR22","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1145\/358407.358427","volume":"26","author":"M Mascagni","year":"2000","unstructured":"Mascagni M., Srinivasan A.: Algorithm 806: SPRNG: a scalable library for pseudorandom number generation. ACM Trans. Math. Softw. 26(3), 436\u2013461 (2000)","journal-title":"ACM Trans. Math. Softw."},{"key":"726_CR23","doi-asserted-by":"crossref","unstructured":"Passerat-Palmbach J., Mazel C., Hill D.R.C.: Pseudo-random number generation on GP-GPU. In: Proc. IEEE\/ACM\/SCS Workshop on Principles of Advanced and Distributed Simulation, pages 146\u2013153, June (2011)","DOI":"10.1109\/PADS.2011.5936751"},{"key":"726_CR24","doi-asserted-by":"crossref","unstructured":"Perlin, K.: Improving noise. In: Proceedings of the 29th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH \u201902, pp. 681\u2013682, New York, NY, USA, Association for Computing Machinery (2002)","DOI":"10.1145\/566570.566636"},{"key":"726_CR25","first-page":"21","volume-title":"Algorithms and complexity","author":"MO Rabin","year":"1976","unstructured":"Rabin M.O.: Probabilistic algorithms. In: Traub, J.F. (ed.) Algorithms and complexity, pp. 21\u201339. Academic Press, Cambridge (1976)"},{"key":"726_CR26","doi-asserted-by":"crossref","unstructured":"Rieger C., Wrede F., Kuchen H.: Musket: a domain-specific language for high-level parallel programming with algorithmic skeletons. In: Proc. Symposium on Applied Computing (SAC\u201919), pp. 1534\u20131543. ACM (2019)","DOI":"10.1145\/3297280.3297434"},{"key":"726_CR27","doi-asserted-by":"crossref","unstructured":"Salmon J.K., Moraes M.A., Dror R.O., Shaw D.E.: Parallel random numbers: As easy as 1, 2, 3. In: Proc. Int. Conf. for High Performance Computing, Networking, Storage and Analysis, SC \u201911, pp. 16:1\u201316:12. ACM (2011)","DOI":"10.1145\/2063384.2063405"},{"key":"726_CR28","doi-asserted-by":"crossref","unstructured":"Steuwer M., Kegel P., Gorlatch S.: SkelCL\u2013a portable skeleton library for high-level GPU programming. In: 16th Int. Workshop on High-Level Parallel Programming Models and Supportive Environments (HIPS\u201911), pp. 1176\u20131182 (2011)","DOI":"10.1109\/IPDPS.2011.269"}],"container-title":["International Journal of Parallel Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-022-00726-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10766-022-00726-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-022-00726-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T22:09:21Z","timestamp":1657231761000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10766-022-00726-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,22]]},"references-count":28,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["726"],"URL":"https:\/\/doi.org\/10.1007\/s10766-022-00726-5","relation":{},"ISSN":["0885-7458","1573-7640"],"issn-type":[{"value":"0885-7458","type":"print"},{"value":"1573-7640","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,22]]},"assertion":[{"value":"18 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}
