{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T11:20:43Z","timestamp":1770290443054,"version":"3.49.0"},"reference-count":69,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T00:00:00Z","timestamp":1609718400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nd\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"crossref","award":["ONR-N00014-17-1-269"],"award-info":[{"award-number":["ONR-N00014-17-1-269"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2021,1,4]]},"abstract":"<jats:p>A Reduction \u2013 an accumulation over a set of values, using an associative and commutative operator \u2013 is a common computation in many numerical computations, including scientific computations, machine learning, computer vision, and financial analytics. Contemporary polyhedral-based compilation techniques make it possible to optimize reductions, such as prefix sums, in which each component of the reduction\u2019s output potentially shares computation with another component in the reduction. Therefore an optimizing compiler can identify the computation shared between multiple components and generate code that computes the shared computation only once.<\/jats:p>\n          <jats:p>These techniques, however, do not support reductions that \u2013 when phrased in the language of the polyhedral model \u2013 span multiple dependent statements. In such cases, existing approaches can generate incorrect code that violates the data dependences of the original, unoptimized program.<\/jats:p>\n          <jats:p>In this work, we identify and formalize the optimization of dependent reductions as an integer bilinear program. We present a heuristic optimization algorithm that uses an affine sequential schedule of the program to determine how to simplfy reductions yet still preserve the program\u2019s dependences.<\/jats:p>\n          <jats:p>\n            We demonstrate that the algorithm provides optimal complexity for a set of benchmark programs from the literature on probabilistic inference algorithms, whose performance critically relies on simplifying these reductions. The complexities for 10 of the 11 programs improve siginifcantly by factors at least of the sizes of the input data, which are in the range of 10\n            <jats:sup>4<\/jats:sup>\n            to 10\n            <jats:sup>6<\/jats:sup>\n            for typical real application inputs. We also confirm the significance of the improvement by showing speedups in wall-clock time that range from 1.1x to over 10\n            <jats:sup>6<\/jats:sup>\n            x.\n          <\/jats:p>","DOI":"10.1145\/3434301","type":"journal-article","created":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T17:34:24Z","timestamp":1609781664000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Simplifying dependent reductions in the polyhedral model"],"prefix":"10.1145","volume":"5","author":[{"given":"Cambridge","family":"Yang","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Atkinson","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Carbin","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,1,4]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15769-1_8"},{"key":"e_1_2_2_2_1","unstructured":"Eric Atkinson Cambridge Yang and Michael Carbin. 2018. Verifying Handcoded Probabilistic Inference Procedures. In arXiv e-prints.  Eric Atkinson Cambridge Yang and Michael Carbin. 2018. Verifying Handcoded Probabilistic Inference Procedures. In arXiv e-prints."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2010.118"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11970-5_16"},{"key":"e_1_2_2_5_1","article-title":"Pyro: Deep Universal Probabilistic Programming","volume":"20","author":"Bingham Eli","year":"2019","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_2_6_1","volume-title":"Pattern Recognition and Machine Learning ( Information Science and Statistics)","author":"Bishop Christopher M."},{"key":"e_1_2_2_7_1","article-title":"Latent Dirichlet Allocation","author":"Blei David M.","year":"2003","journal-title":"Journal of Machine Learning Research 3"},{"key":"e_1_2_2_8_1","volume-title":"Conference on Programming Language Design and Implementation.","author":"Bondhugula Uday"},{"key":"e_1_2_2_9_1","volume-title":"Fuzzy Array Dataflow Analysis. In Symposium on Principles and Practice of Parallel Programming.","author":"Collard Jean-Fran\u00e7ois","year":"1995"},{"key":"e_1_2_2_10_1","volume-title":"Modelling Survival Data in Medical Research","author":"Collett D"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1972.tb00899.x"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314642"},{"key":"e_1_2_2_13_1","volume-title":"Compiling Markov Chain Monte Carlo Algorithms for Probabilistic Modeling. In Conference on Programming Language Design and Implementation.","author":"Daniel Huang Greg Morisett","year":"2017"},{"key":"e_1_2_2_14_1","volume-title":"International Workshop on Polyhedral Compilation Techniques.","author":"Doerfert Johannes","year":"2015"},{"key":"e_1_2_2_15_1","doi-asserted-by":"crossref","unstructured":"E. Ehrhardt. 1967. Sur un probl\u00e8me de G\u00e9om\u00e9trie Diophantienne Lin\u00e9aire. II. Journal f\u00fcr die Reine und Angewandte Mathematik 1967 ( 1967 ) 25-49. Issue 227.  E. Ehrhardt. 1967. Sur un probl\u00e8me de G\u00e9om\u00e9trie Diophantienne Lin\u00e9aire. II. Journal f\u00fcr die Reine und Angewandte Mathematik 1967 ( 1967 ) 25-49. Issue 227.","DOI":"10.1515\/crll.1967.227.25"},{"key":"e_1_2_2_16_1","volume-title":"Array Expansion. In International Conference on Supercomputing.","author":"Feautrier P.","year":"1988"},{"key":"e_1_2_2_17_1","first-page":"5","article-title":"Some eficient solutions to the afine scheduling problem. I. One-dimensional time","volume":"21","author":"Feautrier Paul","year":"1992","journal-title":"International Journal of Parallel Programming"},{"key":"e_1_2_2_18_1","first-page":"6","article-title":"Some eficient solutions to the afine scheduling problem. Part II. Multidimensional time","volume":"21","author":"Feautrier Paul","year":"1992","journal-title":"International Journal of Parallel Programming"},{"key":"e_1_2_2_19_1","volume-title":"Weighing and Integrating Evidence for Stochastic Simulation on Bayesian Networks. In Conference on Uncertainty in Artificial Intelligence.","author":"Robert"},{"key":"e_1_2_2_20_1","volume-title":"Simplifying Reductions. In Symposium on Principles of Programming Languages.","author":"Rajopadhye Gautam"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.3102\/1076998615606113"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1984.4767596"},{"key":"e_1_2_2_23_1","volume-title":"Discovery and Exploitation of General Reductions: A Constraint Based Approach. In International Symposium on Code Generation and Optimization.","author":"Ginsbach Philip"},{"key":"e_1_2_2_24_1","volume-title":"Conference on Uncertainty in Artificial Intelligence.","author":"Goodman Noah D."},{"key":"e_1_2_2_25_1","unstructured":"Noah D Goodman and Andreas Stuhlm\u00fcller. 2014. The Design and Implementation of Probabilistic Programming Languages. http:\/\/dippl.org. Accessed: 2020-10-30.  Noah D Goodman and Andreas Stuhlm\u00fcller. 2014. The Design and Implementation of Probabilistic Programming Languages. http:\/\/dippl.org. Accessed: 2020-10-30."},{"key":"e_1_2_2_26_1","volume-title":"Optimizing and Auto-tuning Belief Propagation on the GPU. In Workshop on Languages and Compilers for Parallel Computing.","author":"Grauer-Gray Scott","year":"2011"},{"key":"e_1_2_2_27_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1073\/pnas.0307752101","article-title":"Finding Scientific Topics","volume":"101","author":"Grifiths T.","year":"2004","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"e_1_2_2_28_1","volume-title":"Scheduling in the Z-Polyhedral Model. International Parallel and Distributed Processing Symposium.","author":"Gupta Gautam","year":"2007"},{"key":"e_1_2_2_29_1","volume-title":"Scheduling Reductions on Realistic Machines. In Symposium on Parallel Algorithms and Architectures.","author":"Gupta Gautam","year":"2002"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/57.1.97"},{"key":"e_1_2_2_31_1","doi-asserted-by":"crossref","unstructured":"Ian Holmes Keith Harris and Christopher Quince. 2012. Dirichlet Multinomial Mixtures: Generative Models for Microbial Metagenomics. PLOS ONE ( 2012 ).  Ian Holmes Keith Harris and Christopher Quince. 2012. Dirichlet Multinomial Mixtures: Generative Models for Microbial Metagenomics. PLOS ONE ( 2012 ).","DOI":"10.1371\/journal.pone.0030126"},{"key":"e_1_2_2_32_1","volume-title":"On Program Equivalence with Reductions. In International Static Analysis Symposium.","author":"Iooss Guillaume","year":"2014"},{"key":"e_1_2_2_33_1","doi-asserted-by":"crossref","DOI":"10.1109\/TPAMI.2003.1206509","article-title":"Stereo matching using belief propagation","volume":"25","author":"Sun Jian","year":"2003","journal-title":"Transactions on Pattern Analysis and Machine Intelligence"},{"key":"e_1_2_2_34_1","doi-asserted-by":"crossref","unstructured":"Ryoichi Kikuchi. 1951. A Theory of Cooperative Phenomena. Physical Review 81 (March 1951 ) 988-1003. Issue 6.  Ryoichi Kikuchi. 1951. A Theory of Cooperative Phenomena. Physical Review 81 (March 1951 ) 988-1003. Issue 6.","DOI":"10.1103\/PhysRev.81.988"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-47958-3_19"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1994.10476829"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1053468.1053471"},{"key":"e_1_2_2_38_1","volume-title":"Probabilistic Programming with Programmable Inference. In Conference on Programming Language Design and Implementation.","author":"Mansingkha Vikash","year":"2018"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1699114"},{"key":"e_1_2_2_40_1","volume-title":"Machine Learning: A Probabilistic Perspective","author":"Murphy Kevin P.","year":"2012"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-29604-3_5"},{"key":"e_1_2_2_42_1","volume-title":"Wolsey","author":"Nemhauser George L.","year":"1988"},{"key":"e_1_2_2_43_1","unstructured":"David Newman. 2008. Bag of Words Dataset. In UCI Machine Learning Respository.  David Newman. 2008. Bag of Words Dataset. In UCI Machine Learning Respository."},{"key":"e_1_2_2_44_1","volume-title":"Eficient Synthesis of Probabilistic Programs. In Conference on Programming Language Design and Implementation.","author":"Nori Aditya V.","year":"2015"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-09766-4_2303"},{"key":"e_1_2_2_46_1","unstructured":"Martyn Plummer. 2015. JAGS Version 4.0.0 user manual. Addison-Wesley Reading Massachusetts.  Martyn Plummer. 2015. JAGS Version 4.0.0 user manual. Addison-Wesley Reading Massachusetts."},{"key":"e_1_2_2_47_1","doi-asserted-by":"crossref","unstructured":"Louis-No\u00ebl Pouchet C\u00e9dric Bastoul Albert Cohen and John Cavazos. 2008. Iterative optimization in the polyhedral model: Part II multidimensional time.  Louis-No\u00ebl Pouchet C\u00e9dric Bastoul Albert Cohen and John Cavazos. 2008. Iterative optimization in the polyhedral model: Part II multidimensional time.","DOI":"10.1145\/1375581.1375594"},{"key":"e_1_2_2_48_1","volume-title":"International Symposium on Code Generation and Optimization.","author":"Pouchet Louis-No\u00ebl","year":"2007"},{"key":"e_1_2_2_49_1","volume-title":"Pruning and Optimization. In Symposium on Principles of Programming Languages.","author":"Pouchet Louis-No\u00ebl","year":"2011"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.752782"},{"key":"e_1_2_2_51_1","doi-asserted-by":"crossref","unstructured":"C. Reddy M. Kruse and A. Cohen. 2016. Reduction drawing: Language constructs and polyhedral compilation for reductions on GPUs.  C. Reddy M. Kruse and A. Cohen. 2016. Reduction drawing: Language constructs and polyhedral compilation for reductions on GPUs.","DOI":"10.1145\/2967938.2967950"},{"key":"e_1_2_2_52_1","volume-title":"Scheduling Reductions. In International Conference on Supercomputing.","author":"Redon Xavier","year":"1994"},{"key":"e_1_2_2_54_1","volume-title":"International Conference on Artificial Intelligence and Statistics.","author":"Ritchie Daniel","year":"2016"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90326-O"},{"key":"e_1_2_2_57_1","volume-title":"Theory of Linear and Integer Programming","author":"Schrijver Alexander"},{"key":"e_1_2_2_58_1","article-title":"Machine Learning for Predictive Maintenance: A Multiple Classifier Approach","volume":"11","author":"Susto G. A.","year":"2015","journal-title":"Transactions on Industrial Informatics"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3294-8"},{"key":"e_1_2_2_60_1","volume-title":"International Conference on Learning Representations.","author":"Tran Dustin","year":"2017"},{"key":"e_1_2_2_61_1","doi-asserted-by":"crossref","unstructured":"Peter Turnbaugh Micah Hamady Tanya Yatsunenko Brandi Cantarel Alexis Duncan Ruth Ley Mitchell Sogin Joe Jones Bruce A Roe Jason Afourtit Michael Egholm Bernard Henrissat Andrew C Heath Rob Knight and Jefrey I Gordon. 2008. A core gut microbiome in obese and lean twins. Nature 457 (12 2008 ) 480-4.  Peter Turnbaugh Micah Hamady Tanya Yatsunenko Brandi Cantarel Alexis Duncan Ruth Ley Mitchell Sogin Joe Jones Bruce A Roe Jason Afourtit Michael Egholm Bernard Henrissat Andrew C Heath Rob Knight and Jefrey I Gordon. 2008. A core gut microbiome in obese and lean twins. Nature 457 (12 2008 ) 480-4.","DOI":"10.1038\/nature07540"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15582-6_49"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.13140\/RG.2.1.1174.6323"},{"key":"e_1_2_2_64_1","volume-title":"On Demand Parametric Array Dataflow Analysis. In International Workshop on Polyhedral Compilation Techniques.","author":"Verdoolaege Sven","year":"2013"},{"key":"e_1_2_2_65_1","doi-asserted-by":"crossref","unstructured":"Sven Verdoolaege Rachid Seghir Kristof Beyls Vincent Loechner and Maurice Bruynooghe. 2007. Counting Integer Points in Parametric Polytopes Using Barvinok's Rational Functions. (May 2007 ).  Sven Verdoolaege Rachid Seghir Kristof Beyls Vincent Loechner and Maurice Bruynooghe. 2007. Counting Integer Points in Parametric Polytopes Using Barvinok's Rational Functions. (May 2007 ).","DOI":"10.1007\/s00453-006-1231-0"},{"key":"e_1_2_2_66_1","volume-title":"International Conference on Functional Programming.","author":"Walia Rajan","year":"2019"},{"key":"e_1_2_2_67_1","doi-asserted-by":"crossref","unstructured":"Nicola White Fiona Reid Adam Harris Priscilla Harries and Patrick Stone. 2016. A Systematic Review of Predictions of Survival in Palliative Care: How Accurate Are Clinicians and Who Are the Experts? PLOS ONE ( 08 2016 ).  Nicola White Fiona Reid Adam Harris Priscilla Harries and Patrick Stone. 2016. A Systematic Review of Predictions of Survival in Palliative Care: How Accurate Are Clinicians and Who Are the Experts? PLOS ONE ( 08 2016 ).","DOI":"10.1371\/journal.pone.0161407"},{"key":"e_1_2_2_68_1","volume-title":"In International Joint Conferences on Artificial Intelligence.","author":"Wu Yi","year":"2016"},{"key":"e_1_2_2_69_1","volume-title":"International Conference on Artificial Intelligence and Statistics.","author":"Yang Lingfeng","year":"2014"},{"key":"e_1_2_2_70_1","volume-title":"AlphaZ: A System for Design Space Exploration in the Polyhedral Model. In Workshop on Languages and Compilers for Parallel Computing.","author":"Yuki Tomofumi","year":"2013"},{"key":"e_1_2_2_71_1","volume-title":"Incremental Precision-Preserving Symbolic Inference for Probabilistic Programs. In Conference on Programming Language Design and Implementation.","author":"Zhang Jieyuan","year":"2019"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434301","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3434301","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3434301","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:35Z","timestamp":1750195475000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434301"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,4]]},"references-count":69,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2021,1,4]]}},"alternative-id":["10.1145\/3434301"],"URL":"https:\/\/doi.org\/10.1145\/3434301","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,4]]},"assertion":[{"value":"2021-01-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}