{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T10:19:26Z","timestamp":1770977966808,"version":"3.50.1"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030993351","type":"print"},{"value":"9783030993368","type":"electronic"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T00:00:00Z","timestamp":1648512000000},"content-version":"vor","delay-in-days":87,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Probabilistic programming languages (PPLs) allow users to encode arbitrary inference problems, and PPL implementations provide general-purpose automatic inference for these problems. However, constructing inference implementations that are efficient enough is challenging for many real-world problems. Often, this is due to PPLs not fully exploiting available parallelization and optimization opportunities. For example, handling probabilistic <jats:italic>checkpoints<\/jats:italic> in PPLs through continuation-passing style transformations or non-preemptive multitasking\u2014as is done in many popular PPLs\u2014often disallows compilation to low-level languages required for high-performance platforms such as GPUs. To solve the checkpoint problem, we introduce the concept of <jats:italic>PPL control-flow graphs<\/jats:italic> (PCFGs)\u2014a simple and efficient approach to checkpoints in low-level languages. We use this approach to implement <jats:italic>RootPPL<\/jats:italic>: a low-level PPL built on CUDA and C++ with OpenMP, providing highly efficient and massively parallel SMC inference. We also introduce a general method of <jats:italic>compiling<\/jats:italic> universal high-level PPLs to PCFGs and illustrate its application when compiling <jats:italic>Miking CorePPL<\/jats:italic>\u2014a high-level universal PPL\u2014to RootPPL. The approach is the first to compile a universal PPL to GPUs with SMC inference. We evaluate RootPPL and the CorePPL compiler through a set of real-world experiments in the domains of phylogenetics and epidemiology, demonstrating up to 6<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\times $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                <mml:mo>\u00d7<\/mml:mo>\n              <\/mml:math><\/jats:alternatives><\/jats:inline-formula> speedups over state-of-the-art PPLs implementing SMC inference.<\/jats:p>","DOI":"10.1007\/978-3-030-99336-8_2","type":"book-chapter","created":{"date-parts":[[2022,3,28]],"date-time":"2022-03-28T20:02:48Z","timestamp":1648497768000},"page":"29-56","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Compiling Universal Probabilistic Programming Languages with Efficient Parallel Sequential Monte Carlo Inference"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3127-5640","authenticated-orcid":false,"given":"Daniel","family":"Lund\u00e9n","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6342-268X","authenticated-orcid":false,"given":"Joey","family":"\u00d6hman","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3806-4950","authenticated-orcid":false,"given":"Jan","family":"Kudlicka","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3340-5963","authenticated-orcid":false,"given":"Viktor","family":"Senderov","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3929-251X","authenticated-orcid":false,"given":"Fredrik","family":"Ronquist","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8457-4105","authenticated-orcid":false,"given":"David","family":"Broman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,3,29]]},"reference":[{"key":"2_CR1","unstructured":"CUDA Toolkit $$|$$ NVIDIA Developer. https:\/\/developer.nvidia.com\/cuda-toolkit (2021), accessed: 2021-09-20"},{"key":"2_CR2","unstructured":"GCC, the GNU Compiler Collection - GNU Project. https:\/\/gcc.gnu.org\/ (2021), accessed: 2021-09-20"},{"key":"2_CR3","unstructured":"Home - OpenMP. https:\/\/www.openmp.org\/ (2021), accessed: 2021-09-20"},{"key":"2_CR4","unstructured":"Miking DPPL. https:\/\/github.com\/miking-lang\/miking-dppl (2021), accessed: 2021-12-01"},{"key":"2_CR5","unstructured":"PyTorch. https:\/\/pytorch.org\/ (2021), accessed: 2021-10-11"},{"key":"2_CR6","unstructured":"The LLVM Compiler Infrastructure Project. https:\/\/llvm.org\/ (2021), accessed: 2021-09-20"},{"key":"2_CR7","unstructured":"Thrust - Parallel Algorithms Library. https:\/\/thrust.github.io\/ (2021), accessed: 2021-09-24"},{"key":"2_CR8","unstructured":"Aho, A.V., Lam, M.S., Sethi, R., Ullman, J.D.: Compilers: principles, techniques and tools. Addison-Wesley (2006)"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"Appel, A.W.: Compiling with Continuations. Cambridge University Press (1991)","DOI":"10.1017\/CBO9780511609619"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Bingham, E., Chen, J.P., Jankowiak, M., Obermeyer, F., Pradhan, N., Karaletsos, T., Singh, R., Szerlip, P., Horsfall, P., Goodman, N.D.: Pyro: Deep universal probabilistic programming. Journal of Machine Learning Research 20(28), \u00a01\u20136 (2019)","DOI":"10.1145\/3315508.3329974"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Broman, D.: A vision of miking: Interactive programmatic modeling, sound language composition, and self-learning compilation. In: Proceedings of the 12th ACM SIGPLAN International Conference on Software Language Engineering. p. 55\u201360. SLE 2019, ACM, New York, NY, USA (2019)","DOI":"10.1145\/3357766.3359531"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"Carpenter, B., Gelman, A., Hoffman, M., Lee, D., Goodrich, B., Betancourt, M., Brubaker, M., Guo, J., Li, P., Riddell, A.: Stan: A probabilistic programming language. Journal of Statistical Software, Articles 76(1), 1\u201332 (2017)","DOI":"10.18637\/jss.v076.i01"},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"Cusumano-Towner, M.F., Saad, F.A., Lew, A.K., Mansinghka, V.K.: Gen: A general-purpose probabilistic programming system with programmable inference. In: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation. pp. 221\u2013236. PLDI 2019, ACM, New York, NY, USA (2019)","DOI":"10.1145\/3314221.3314642"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"Doucet, A., de\u00a0Freitas, N., Gordon, N.: Sequential Monte Carlo Methods in Practice. Information Science and Statistics, Springer New York (2001)","DOI":"10.1007\/978-1-4757-3437-9"},{"key":"2_CR15","doi-asserted-by":"crossref","unstructured":"Flanagan, C., Sabry, A., Duba, B.F., Felleisen, M.: The essence of compiling with continuations. In: Proceedings of the ACM SIGPLAN 1993 Conference on Programming Language Design and Implementation. p. 237\u2013247. PLDI 1993, ACM, New York, NY, USA (1993)","DOI":"10.1145\/155090.155113"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Funk, S., Kucharski, A.J., Camacho, A., Eggo, R.M., Yakob, L., Murray, L.M., Edmunds, W.J.: Comparative analysis of dengue and zika outbreaks reveals differences by setting and virus. PLOS Neglected Tropical Diseases 10(12), 1\u201316 (12 2016)","DOI":"10.1371\/journal.pntd.0005173"},{"key":"2_CR17","unstructured":"Ge, H., Xu, K., Ghahramani, Z.: Turing: a language for flexible probabilistic inference. In: International Conference on Artificial Intelligence and Statistics, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain. pp. 1682\u20131690 (2018)"},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"Gilks, W., Richardson, S., Spiegelhalter, D.: Markov Chain Monte Carlo in Practice. Chapman & Hall\/CRC Interdisciplinary Statistics, Taylor & Francis (1995)","DOI":"10.1201\/b14835"},{"key":"2_CR19","unstructured":"Goodman, N.D., Mansinghka, V.K., Roy, D., Bonawitz, K., Tenenbaum, J.B.: Church: A language for generative models. In: Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence. pp. 220\u2013229. AUAI Press (2008)"},{"key":"2_CR20","unstructured":"Goodman, N.D., Stuhlm\u00fcller, A.: The design and implementation of probabilistic programming languages. http:\/\/dippl.org (2014), accessed: 2020-07-09"},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"Gordon, A.D., Henzinger, T.A., Nori, A.V., Rajamani, S.K.: Probabilistic programming. In: Future of Software Engineering Proceedings. p. 167\u2013181. FOSE 2014, ACM, New York, NY, USA (2014)","DOI":"10.1145\/2593882.2593900"},{"key":"2_CR22","doi-asserted-by":"crossref","unstructured":"Huang, D., Tristan, J.B., Morrisett, G.: Compiling markov chain monte carlo algorithms for probabilistic modeling. In: Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation. p. 111\u2013125. PLDI 2017, ACM, New York, NY, USA (2017)","DOI":"10.1145\/3062341.3062375"},{"key":"2_CR23","doi-asserted-by":"crossref","unstructured":"Jetz, W., Thomas, G.H., Joy, J.B., Hartmann, K., Mooers, A.O.: The global diversity of birds in space and time. Nature 491(7424), 444\u2013448 (Nov 2012)","DOI":"10.1038\/nature11631"},{"key":"2_CR24","doi-asserted-by":"crossref","unstructured":"Lund\u00e9n, D., Borgstr\u00f6m, J., Broman, D.: Correctness of sequential Monte Carlo inference for probabilistic programming languages. In: Programming Languages and Systems. pp. 404\u2013431. Springer International Publishing, Cham (2021)","DOI":"10.1007\/978-3-030-72019-3_15"},{"key":"2_CR25","unstructured":"Lund\u00e9n, D., Broman, D., Ronquist, F., Murray, L.M.: Automatic alignment of sequential Monte Carlo inference in higher-order probabilistic programs. arXiv e-prints p. arXiv:1812.07439 (2018)"},{"key":"2_CR26","doi-asserted-by":"publisher","unstructured":"Lund\u00e9n, D., \u00d6hman, J., Kudlicka, J., Senderov, V., Ronquist, F., Broman, D.: Artifact: Compiling Universal Probabilistic Programming Languages with Efficient Parallel Sequential Monte Carlo Inference (Jan 2022). https:\/\/doi.org\/10.5281\/zenodo.5914164","DOI":"10.5281\/zenodo.5914164"},{"key":"2_CR27","doi-asserted-by":"crossref","unstructured":"Lund\u00e9n, D., \u00d6hman, J., Kudlicka, J., Senderov, V., Ronquist, F., Broman, D.: Compiling universal probabilistic programming languages with efficient parallel sequential monte carlo inference. arXiv e-prints p. arXiv:2112.00364 (2022)","DOI":"10.1007\/978-3-030-99336-8_2"},{"key":"2_CR28","unstructured":"Murray, L., Lund\u00e9n, D., Kudlicka, J., Broman, D., Sch\u00f6n, T.: Delayed sampling and automatic Rao-Blackwellization of probabilistic programs. In: Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics. vol.\u00a084, pp. 1037\u20131046. PMLR (2018)"},{"key":"2_CR29","unstructured":"Murray, L.M.: Bayesian state-space modelling on high-performance hardware using LibBi. arXiv e-prints p. arXiv:1306.3277 (2013)"},{"key":"2_CR30","unstructured":"Murray, L.M.: Lazy object copy as a platform for population-based probabilistic programming. arXiv e-prints p. arXiv:2001.05293 (2020)"},{"key":"2_CR31","doi-asserted-by":"crossref","unstructured":"Murray, L.M., Lee, A., Jacob, P.E.: Parallel resampling in the particle filter. Journal of Computational and Graphical Statistics 25(3), 789\u2013805 (2016)","DOI":"10.1080\/10618600.2015.1062015"},{"key":"2_CR32","doi-asserted-by":"crossref","unstructured":"Murray, L.M., Sch\u00f6n, T.B.: Automated learning with a probabilistic programming language: Birch. Annual Reviews in Control 46, 29\u201343 (2018)","DOI":"10.1016\/j.arcontrol.2018.10.013"},{"key":"2_CR33","doi-asserted-by":"crossref","unstructured":"Naesseth, C., Lindsten, F., Sch\u00f6n, T.: Elements of Sequential Monte Carlo. Foundations and Trends in Machine Learning Series, Now Publishers (2019)","DOI":"10.1561\/9781680836332"},{"key":"2_CR34","doi-asserted-by":"crossref","unstructured":"Narayanan, P., Carette, J., Romano, W., Shan, C., Zinkov, R.: Probabilistic inference by program transformation in Hakaru (system description). In: International Symposium on Functional and Logic Programming - 13th International Symposium, FLOPS 2016, Kochi, Japan, March 4-6, 2016, Proceedings. pp. 62\u201379. Springer (2016)","DOI":"10.1007\/978-3-319-29604-3_5"},{"key":"2_CR35","doi-asserted-by":"crossref","unstructured":"Nielson, F., Nielson, H.R., Hankin, C.: Principles of Program Analysis. Springer-Verlag (1999)","DOI":"10.1007\/978-3-662-03811-6"},{"key":"2_CR36","doi-asserted-by":"crossref","unstructured":"Ronquist, F., Kudlicka, J., Senderov, V., Borgstr\u00f6m, J., Lartillot, N., Lund\u00e9n, D., Murray, L., Sch\u00f6n, T.B., Broman, D.: Universal probabilistic programming offers a powerful approach to statistical phylogenetics. Communications Biology 4(1), \u00a0244 (Feb 2021)","DOI":"10.1038\/s42003-021-01753-7"},{"key":"2_CR37","doi-asserted-by":"crossref","unstructured":"Tolpin, D., van\u00a0de Meent, J.W., Yang, H., Wood, F.: Design and implementation of probabilistic programming language Anglican. In: Proceedings of the 28th Symposium on the Implementation and Application of Functional Programming Languages. IFL 2016, ACM, New York, NY, USA (2016)","DOI":"10.1145\/3064899.3064910"},{"key":"2_CR38","unstructured":"Tran, D., Kucukelbir, A., Dieng, A.B., Rudolph, M., Liang, D., Blei, D.M.: Edward: A library for probabilistic modeling, inference, and criticism. arXiv e-prints p. arXiv:1610.09787 (2016)"},{"key":"2_CR39","doi-asserted-by":"crossref","unstructured":"Wainwright, M.J., Jordan, M.I.: Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning 1(1\u20132), 1\u2013305 (2008)","DOI":"10.1561\/2200000001"},{"key":"2_CR40","unstructured":"Wood, F., Meent, J.W., Mansinghka, V.: A new approach to probabilistic programming inference. In: Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics. vol.\u00a033, pp. 1024\u20131032. PMLR (2014)"}],"container-title":["Lecture Notes in Computer Science","Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-99336-8_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,15]],"date-time":"2024-11-15T05:06:21Z","timestamp":1731647181000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-99336-8_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783030993351","9783030993368"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-99336-8_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"29 March 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ESOP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"European Symposium on Programming","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Munich","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 April 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 April 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"esop2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2022\/esop","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"HotCRP","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"64","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"21","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.5","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}