{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:19:53Z","timestamp":1750220393598,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T00:00:00Z","timestamp":1634256000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2021,10,20]]},"abstract":"<jats:p>This paper presents a novel optimization for differentiable programming named coarsening optimization. It offers a systematic way to synergize symbolic differentiation and algorithmic differentiation (AD). Through it, the granularity of the computations differentiated by each step in AD can become much larger than a single operation, and hence lead to much reduced runtime computations and data allocations in AD. To circumvent the difficulties that control flow creates to symbolic differentiation in coarsening, this work introduces phi-calculus, a novel method to allow symbolic reasoning and differentiation of computations that involve branches and loops. It further avoids \"expression swell\" in symbolic differentiation and balance reuse and coarsening through the design of reuse-centric segment of interest identification. Experiments on a collection of real-world applications show that coarsening optimization is effective in speeding up AD, producing several times to two orders of magnitude speedups.<\/jats:p>","DOI":"10.1145\/3485507","type":"journal-article","created":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T19:18:28Z","timestamp":1634325508000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Coarsening optimization for differentiable programming"],"prefix":"10.1145","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3599-8010","authenticated-orcid":false,"given":"Xipeng","family":"Shen","sequence":"first","affiliation":[{"name":"North Carolina State University, USA \/ Facebook, USA"}]},{"given":"Guoqiang","family":"Zhang","sequence":"additional","affiliation":[{"name":"North Carolina State University, USA \/ Facebook, USA"}]},{"given":"Irene","family":"Dea","sequence":"additional","affiliation":[{"name":"Facebook, USA"}]},{"given":"Samantha","family":"Andow","sequence":"additional","affiliation":[{"name":"Facebook, USA"}]},{"given":"Emilio","family":"Arroyo-Fang","sequence":"additional","affiliation":[{"name":"Facebook, USA"}]},{"given":"Neal","family":"Gafter","sequence":"additional","affiliation":[{"name":"Facebook, USA"}]},{"given":"Johann","family":"George","sequence":"additional","affiliation":[{"name":"Facebook, USA"}]},{"given":"Melissa","family":"Grueter","sequence":"additional","affiliation":[{"name":"Facebook, USA"}]},{"given":"Erik","family":"Meijer","sequence":"additional","affiliation":[{"name":"Facebook, USA"}]},{"given":"Olin Grigsby","family":"Shivers","sequence":"additional","affiliation":[{"name":"Facebook, USA"}]},{"given":"Steffi","family":"Stumpos","sequence":"additional","affiliation":[{"name":"Facebook, USA"}]},{"given":"Alanna","family":"Tempest","sequence":"additional","affiliation":[{"name":"Facebook, USA"}]},{"given":"Christy","family":"Warden","sequence":"additional","affiliation":[{"name":"Facebook, USA"}]},{"given":"Shannon","family":"Yang","sequence":"additional","affiliation":[{"name":"Facebook, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,10,15]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"[n.d.]. Calculus package for Julia. Available at https:\/\/github.com\/JuliaMath\/Calculus.jl  [n.d.]. Calculus package for Julia. Available at https:\/\/github.com\/JuliaMath\/Calculus.jl"},{"key":"e_1_2_2_2_1","unstructured":"[n.d.]. HMC Explained. Available at https:\/\/arogozhnikov.github.io\/2016\/12\/19\/markov_chain_monte_carlo.html  [n.d.]. HMC Explained. Available at https:\/\/arogozhnikov.github.io\/2016\/12\/19\/markov_chain_monte_carlo.html"},{"key":"e_1_2_2_3_1","unstructured":"[n.d.]. SageMath. Available at https:\/\/www.sagemath.org\/  [n.d.]. SageMath. Available at https:\/\/www.sagemath.org\/"},{"key":"e_1_2_2_4_1","unstructured":"[n.d.]. Sympy software. https:\/\/www.sympy.org\/en\/index.html.  [n.d.]. Sympy software. https:\/\/www.sympy.org\/en\/index.html."},{"volume-title":"Fast reverse-mode automatic differentiation using expression templates in C++. Perspectives in Computing, 19","year":"1988","key":"e_1_2_2_5_1","unstructured":"1988. Fast reverse-mode automatic differentiation using expression templates in C++. Perspectives in Computing, 19 ( 1988 ), Source of expression swell. 1988. Fast reverse-mode automatic differentiation using expression templates in C++. Perspectives in Computing, 19 (1988), Source of expression swell."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1201\/b10905"},{"key":"e_1_2_2_7_1","doi-asserted-by":"crossref","unstructured":"Trans. Math. Software 2014 40 Fast reverse-mode automatic differentiation using expression templates in C++","DOI":"10.1145\/2560359"},{"volume-title":"High-Performance Derivative Computations using CoDiPack. Trans. Math. Software, 45","year":"2017","key":"e_1_2_2_8_1","unstructured":"2017. High-Performance Derivative Computations using CoDiPack. Trans. Math. Software, 45 ( 2017 ), CoDiPack . 2017. High-Performance Derivative Computations using CoDiPack. Trans. Math. Software, 45 (2017), CoDiPack."},{"key":"e_1_2_2_9_1","volume-title":"Compilers: Principles, Techniques, and Tools","author":"Aho A. V.","year":"2006","unstructured":"A. V. Aho , M. S. Lam , R. Sethi , and J. D. Ullman . 2006 . Compilers: Principles, Techniques, and Tools ( 2 nd ed.). Addison Wesley . A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman. 2006. Compilers: Principles, Techniques, and Tools (2nd ed.). Addison Wesley.","edition":"2"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007910000048"},{"key":"e_1_2_2_11_1","article-title":"Automatic differentiation in machine learning: a survey","volume":"18","author":"Baydin At\u0131l\u0131m G\u00fcnes","year":"2018","unstructured":"At\u0131l\u0131m G\u00fcnes Baydin , Barak A. Pearlmutter , Alexey Andreyevich Radul , and Jeffrey Mark Siskind . 2018 . Automatic differentiation in machine learning: a survey . The Journal of Machine Learning Research , 18 , 1 (2018). At\u0131l\u0131m G\u00fcnes Baydin, Barak A. Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind. 2018. Automatic differentiation in machine learning: a survey. The Journal of Machine Learning Research, 18, 1 (2018).","journal-title":"The Journal of Machine Learning Research"},{"key":"e_1_2_2_12_1","volume-title":"Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang.","author":"Bradbury James","year":"2018","unstructured":"James Bradbury , Roy Frostig , Peter Hawkins , Matthew James Johnson , Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. 2018 . JAX: composable transformations of Python +NumPy programs. https:\/\/jax.readthedocs.io\/. James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. 2018. JAX: composable transformations of Python+NumPy programs. https:\/\/jax.readthedocs.io\/."},{"key":"e_1_2_2_13_1","unstructured":"Breandan Considine Michalis Famelis and Liam Paull. 2019. Kotlin\u2207 : A Shape-Safe eDSL for Differentiable Programming. https:\/\/github.com\/breandan\/kotlingrad.  Breandan Considine Michalis Famelis and Liam Paull. 2019. Kotlin\u2207 : A Shape-Safe eDSL for Differentiable Programming. https:\/\/github.com\/breandan\/kotlingrad."},{"volume-title":"Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. 25\u201335","author":"Cytron Ron","key":"e_1_2_2_14_1","unstructured":"Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , and F. Kenneth Zadeck . 1989. An efficient method of computing static single assignment form . In Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. 25\u201335 . Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. 1989. An efficient method of computing static single assignment form. In Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. 25\u201335."},{"key":"e_1_2_2_15_1","doi-asserted-by":"crossref","unstructured":"B. Dauvergne and L. Hascoet. 2006. The Data-Flow Equations of Checkpointing in Reverse Automatic Differentiation. Lecture Notes in Computer Science 3994 (2006).  B. Dauvergne and L. Hascoet. 2006. The Data-Flow Equations of Checkpointing in Reverse Automatic Differentiation. Lecture Notes in Computer Science 3994 (2006).","DOI":"10.1007\/11758549_78"},{"volume-title":"Proceedings of OOPSLA at The ACM SIGPLAN conference on Systems, Programming, Languages and Applications: Software for Humanity (SPLASH).","author":"Ding Y.","key":"e_1_2_2_16_1","unstructured":"Y. Ding and X. Shen . 2017. GLORE: Generalized Loop Redundancy Elimination upon LER-Notation . In Proceedings of OOPSLA at The ACM SIGPLAN conference on Systems, Programming, Languages and Applications: Software for Humanity (SPLASH). Y. Ding and X. Shen. 2017. GLORE: Generalized Loop Redundancy Elimination upon LER-Notation. In Proceedings of OOPSLA at The ACM SIGPLAN conference on Systems, Programming, Languages and Applications: Software for Humanity (SPLASH)."},{"key":"e_1_2_2_17_1","unstructured":"L. C. Dixon. 1991. Use of automatic differentiation for calculating Hessians and Newton steps. Automatic Differentiation of Algorithms: Theory Implementation and Application 114\u2013125.  L. C. Dixon. 1991. Use of automatic differentiation for calculating Hessians and Newton steps. Automatic Differentiation of Algorithms: Theory Implementation and Application 114\u2013125."},{"key":"e_1_2_2_18_1","volume-title":"Don\u2019t Unroll Adjoint: Differentiating SSA-Form Programs. CoRR, abs\/1810.07951","author":"Innes Michael","year":"2018","unstructured":"Michael Innes . 2018. Don\u2019t Unroll Adjoint: Differentiating SSA-Form Programs. CoRR, abs\/1810.07951 ( 2018 ), arXiv:1810.07951. arxiv:1810.07951 Michael Innes. 2018. Don\u2019t Unroll Adjoint: Differentiating SSA-Form Programs. CoRR, abs\/1810.07951 (2018), arXiv:1810.07951. arxiv:1810.07951"},{"key":"e_1_2_2_19_1","volume-title":"Proceedings of the 3rd MLSys Conference. https:\/\/fluxml.ai\/Zygote.jl\/latest\/.","author":"Innes Michael J","year":"2020","unstructured":"Michael J Innes . 2020 . Sense & Sensitivities: The Path to General-Purpose Algorithmic Differentiation . In Proceedings of the 3rd MLSys Conference. https:\/\/fluxml.ai\/Zygote.jl\/latest\/. Michael J Innes. 2020. Sense & Sensitivities: The Path to General-Purpose Algorithmic Differentiation. In Proceedings of the 3rd MLSys Conference. https:\/\/fluxml.ai\/Zygote.jl\/latest\/."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/268946.268956"},{"key":"e_1_2_2_21_1","volume-title":"On the Equivalence of Forward Mode Automatic Differentiation and Symbolic Differentiation. CoRR, abs\/1904.02990","author":"Laue S\u00f6ren","year":"2019","unstructured":"S\u00f6ren Laue . 2019. On the Equivalence of Forward Mode Automatic Differentiation and Symbolic Differentiation. CoRR, abs\/1904.02990 ( 2019 ), arXiv:1904.02990. arxiv:1904.02990 S\u00f6ren Laue. 2019. On the Equivalence of Forward Mode Automatic Differentiation and Symbolic Differentiation. CoRR, abs\/1904.02990 (2019), arXiv:1904.02990. arxiv:1904.02990"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/widm.1305"},{"volume-title":"ACM SIGPLAN 1990 conference on Programming language design and implementation. 257\u2013271","author":"Ottenstein Karl J.","key":"e_1_2_2_24_1","unstructured":"Karl J. Ottenstein , Robert A. Ballance , and Arthur B . MacCabe. 1990. The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages . In ACM SIGPLAN 1990 conference on Programming language design and implementation. 257\u2013271 . Karl J. Ottenstein, Robert A. Ballance, and Arthur B. MacCabe. 1990. The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages. In ACM SIGPLAN 1990 conference on Programming language design and implementation. 257\u2013271."},{"key":"e_1_2_2_25_1","volume-title":"Proceedings of NIPS 2017 Workshop Autodiff.","author":"Paszke Adam","year":"2017","unstructured":"Adam Paszke , Sam Gross , Soumith Chintala , Gregory Chanan , Edward Yang , Zachary DeVito , Zeming Lin , Alban Desmaison , Luca Antiga , and Adam Lerer . 2017 . Automatic differentiation in PyTorch . In Proceedings of NIPS 2017 Workshop Autodiff. Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. 2017. Automatic differentiation in PyTorch. In Proceedings of NIPS 2017 Workshop Autodiff."},{"volume-title":"Recent Advances in Algorithmic Differentiation","author":"Phipps Eric","key":"e_1_2_2_26_1","unstructured":"Eric Phipps and Roger Pawlowski . 2012. Efficient Expression Templates for Operator Overloading-BasedAutomatic Differentiation . In Recent Advances in Algorithmic Differentiation , Shaun Forth, Paul Hovland, Eric Phipps, Jean Utke, and Andrea Walther (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg . 309\u2013319. isbn:978-3-642-30023-3 Eric Phipps and Roger Pawlowski. 2012. Efficient Expression Templates for Operator Overloading-BasedAutomatic Differentiation. In Recent Advances in Algorithmic Differentiation, Shaun Forth, Paul Hovland, Eric Phipps, Jean Utke, and Andrea Walther (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 309\u2013319. isbn:978-3-642-30023-3"},{"key":"e_1_2_2_27_1","volume-title":"NeurIPS Workshop on Machine Learning for Creativity and Design 3.0.","author":"Rojas Junior","year":"2019","unstructured":"Junior Rojas , Stelian Coros , and Ladislav Kavan . 2019 . Deep reinforcement learning for 2D soft body locomotion . In NeurIPS Workshop on Machine Learning for Creativity and Design 3.0. Junior Rojas, Stelian Coros, and Ladislav Kavan. 2019. Deep reinforcement learning for 2D soft body locomotion. In NeurIPS Workshop on Machine Learning for Creativity and Design 3.0."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341701"},{"key":"e_1_2_2_29_1","volume-title":"Proceedings of the ACM SIGPLAN-SIGACT symposium on Principles of programming languages.","author":"Sherman Benjamin","year":"2021","unstructured":"Benjamin Sherman , Jesse Michel , and Michael Carbin . 2021 . Computable Semantics for Differentiable Programming with Higher-Order Functions and Datatypes . In Proceedings of the ACM SIGPLAN-SIGACT symposium on Principles of programming languages. Benjamin Sherman, Jesse Michel, and Michael Carbin. 2021. Computable Semantics for Differentiable Programming with Higher-Order Functions and Datatypes. In Proceedings of the ACM SIGPLAN-SIGACT symposium on Principles of programming languages."},{"key":"e_1_2_2_30_1","volume-title":"Proceedings of the 10th International Conference on Probabilistic Graphical Models.","author":"Tehrani Nazanin","year":"2020","unstructured":"Nazanin Tehrani , Nimar S. Arora , Yucen Lily Li , Kinjal Divesh Shah , David Noursi , Michael Tingley , Narjes Torabi , Sepehr Masouleh , Eric Lippert , and Erik Meijer . 2020 . Bean Machine: A Declarative Probabilistic Programming Language For Efficient Programmable Inference . In Proceedings of the 10th International Conference on Probabilistic Graphical Models. Nazanin Tehrani, Nimar S. Arora, Yucen Lily Li, Kinjal Divesh Shah, David Noursi, Michael Tingley, Narjes Torabi, Sepehr Masouleh, Eric Lippert, and Erik Meijer. 2020. Bean Machine: A Declarative Probabilistic Programming Language For Efficient Programmable Inference. In Proceedings of the 10th International Conference on Probabilistic Graphical Models."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/224538.224648"},{"key":"e_1_2_2_32_1","volume-title":"Proceedings of the International Conference on Compiler Constructions.","author":"van Engelen Robert A.","year":"2001","unstructured":"Robert A. van Engelen . 2001 . A method for recognizing and substitutions of generalized inductive variables through Chains of recurrences (CRs) . In Proceedings of the International Conference on Compiler Constructions. Robert A. van Engelen. 2001. A method for recognizing and substitutions of generalized inductive variables through Chains of recurrences (CRs). In Proceedings of the International Conference on Compiler Constructions."},{"volume-title":"Proceedings of the International Conference on Supercomputing.","author":"van Engelen Robert A.","key":"e_1_2_2_33_1","unstructured":"Robert A. van Engelen , J. Birch , Y. Shou , B. Walsh , and Kyle A. Gallivan . 2004. A Unified Framework for Nonlinear Dependence Testing and Symbolic Analysis . In Proceedings of the International Conference on Supercomputing. Robert A. van Engelen, J. Birch, Y. Shou, B. Walsh, and Kyle A. Gallivan. 2004. A Unified Framework for Nonlinear Dependence Testing and Symbolic Analysis. In Proceedings of the International Conference on Supercomputing."},{"key":"e_1_2_2_34_1","volume-title":"Automatic differentiation in ML: Where we are and where we should be going. CoRR, abs\/1810.11530","author":"van Merri\u00ebnboer Bart","year":"2018","unstructured":"Bart van Merri\u00ebnboer , Olivier Breuleux , Arnaud Bergeron , and Pascal Lamblin . 2018. Automatic differentiation in ML: Where we are and where we should be going. CoRR, abs\/1810.11530 ( 2018 ), arXiv:1810.11530. arxiv:1810.11530 Bart van Merri\u00ebnboer, Olivier Breuleux, Arnaud Bergeron, and Pascal Lamblin. 2018. Automatic differentiation in ML: Where we are and where we should be going. CoRR, abs\/1810.11530 (2018), arXiv:1810.11530. arxiv:1810.11530"},{"key":"e_1_2_2_35_1","volume-title":"Demystifying Differentiable Programming: Shift\/Reset the Penultimate Backpropagator. CoRR, abs\/1803.10228","author":"Wang Fei","year":"2018","unstructured":"Fei Wang , Xilun Wu , Gr\u00e9gory M. Essertel , James M. Decker , and Tiark Rompf . 2018. Demystifying Differentiable Programming: Shift\/Reset the Penultimate Backpropagator. CoRR, abs\/1803.10228 ( 2018 ), arXiv:1803.10228. arxiv:1803.10228 Fei Wang, Xilun Wu, Gr\u00e9gory M. Essertel, James M. Decker, and Tiark Rompf. 2018. Demystifying Differentiable Programming: Shift\/Reset the Penultimate Backpropagator. CoRR, abs\/1803.10228 (2018), arXiv:1803.10228. arxiv:1803.10228"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1795194.1795196"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485507","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485507","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:40Z","timestamp":1750191520000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485507"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,15]]},"references-count":35,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2021,10,20]]}},"alternative-id":["10.1145\/3485507"],"URL":"https:\/\/doi.org\/10.1145\/3485507","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2021,10,15]]},"assertion":[{"value":"2021-10-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}