{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T18:55:17Z","timestamp":1771959317440,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":52,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,11]],"date-time":"2020-06-11T00:00:00Z","timestamp":1591833600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["1645514, 1645599, 1750399, 1816793"],"award-info":[{"award-number":["1645514, 1645599, 1750399, 1816793"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,11]]},"DOI":"10.1145\/3385412.3385989","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:40:10Z","timestamp":1591494010000},"page":"808-822","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["Automated derivation of parametric data movement lower bounds for affine programs"],"prefix":"10.1145","author":[{"given":"Auguste","family":"Olivry","sequence":"first","affiliation":[{"name":"Grenoble Alps University, France \/ CNRS, France \/ Inria, France \/ Grenoble INP, France \/ LIG, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julien","family":"Langou","sequence":"additional","affiliation":[{"name":"University of Colorado at Denver, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Louis-No\u00ebl","family":"Pouchet","sequence":"additional","affiliation":[{"name":"Colorado State University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Sadayappan","sequence":"additional","affiliation":[{"name":"University of Utah, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabrice","family":"Rastello","sequence":"additional","affiliation":[{"name":"Grenoble Alps University, France \/ Inria, France \/ CNRS, France \/ Grenoble INP, France \/ LIG, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Tallent","author":"Adhianto Laksono","year":"2010","unstructured":"Laksono Adhianto, S. Banerjee, Michael W. Fagan, Mark Krentel, Gabriel Marin, John M. Mellor-Crummey, and Nathan R. Tallent. 2010."},{"key":"e_1_3_2_1_2_1","volume-title":"tools for performance analysis of optimized parallel programs. Concurrency and Computation: Practice and Experience 22, 6","author":"HPCTOOLKIT","year":"2010","unstructured":"HPCTOOLKIT: tools for performance analysis of optimized parallel programs. Concurrency and Computation: Practice and Experience 22, 6 (2010), 685\u2013701."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_3_2_1_4_1","unstructured":"Issue 9."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492914000038"},{"key":"e_1_3_2_1_6_1","unstructured":"Grey Ballard James Demmel Olga Holtz and Oded Schwartz. 2011."},{"key":"e_1_3_2_1_7_1","volume-title":"Matrix Analysis Applications 32, 3","author":"Numerical Linear Algebra Minimizing Communication","year":"2011","unstructured":"Minimizing Communication in Numerical Linear Algebra. SIAM J. Matrix Analysis Applications 32, 3 (2011), 866\u2013901."},{"key":"e_1_3_2_1_8_1","unstructured":"Grey Ballard James Demmel Olga Holtz and Oded Schwartz. 2012."},{"key":"e_1_3_2_1_9_1","volume-title":"32","author":"Graph","year":"2012","unstructured":"Graph expansion and communication costs of fast matrix multiplication. J. ACM 59, 6 (2012), 32."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.19.4.769"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.2001.0494"},{"key":"e_1_3_2_1_12_1","unstructured":"Gianfranco Bilardi and Enoch Peserico. 2001."},{"key":"e_1_3_2_1_13_1","volume-title":"Automata, Languages and Programming","author":"A","year":"2001","unstructured":"A characterization of temporal locality and its portability across memory hierarchies. Automata, Languages and Programming (2001), 128\u2013139."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32820-6_67"},{"key":"e_1_3_2_1_15_1","unstructured":"Michael Christ James Demmel Nicholas Knight Thomas Scanlon and Katherine Yelick. 2013."},{"key":"e_1_3_2_1_17_1","unstructured":"James Demmel Laura Grigori Mark Hoemmen and Julien Langou. 2012."},{"key":"e_1_3_2_1_18_1","volume-title":"Scientific Computing 34, 1","author":"Factorizations Parallel","year":"2012","unstructured":"Communication-optimal Parallel and Sequential QR and LU Factorizations. SIAM J. Scientific Computing 34, 1 (2012), A206\u2013A239."},{"key":"e_1_3_2_1_19_1","unstructured":"Venmugil Elango Fabrice Rastello Louis-No\u00ebl Pouchet J. Ramanujam and P. Sadayappan. 2014."},{"key":"e_1_3_2_1_20_1","volume-title":"Proc. of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA \u201914","author":"On","year":"2014","unstructured":"On characterizing the data movement complexity of computational DAGs for parallel execution. In Proc. of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA \u201914, Prague, Czech Republic - June 23 - 25, 2014. 296\u2013306."},{"key":"e_1_3_2_1_21_1","unstructured":"Venmugil Elango Fabrice Rastello Louis-No\u00ebl Pouchet J. Ramanujam and P. Sadayappan. 2015."},{"key":"e_1_3_2_1_22_1","volume-title":"Characterizing the Data Access Complexity of Programs. In Proc. of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2015","author":"On","year":"2015","unstructured":"On Characterizing the Data Access Complexity of Programs. In Proc. of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2015, Mumbai, India, January 15-17, 2015. 567\u2013580."},{"key":"e_1_3_2_1_23_1","unstructured":"Paul Feautrier. 1988."},{"key":"e_1_3_2_1_24_1","volume-title":"RAIRO Recherche Op\u00e9rationnelle 22, 3","author":"Parametric","year":"1988","unstructured":"Parametric integer programming. RAIRO Recherche Op\u00e9rationnelle 22, 3 (1988), 243\u2013268."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407835"},{"key":"e_1_3_2_1_26_1","volume-title":"Encyclopedia of Parallel Computing. 1581\u20131592.","author":"Feautrier Paul","unstructured":"Paul Feautrier and Christian Lengauer. 2011. Polyhedron model. In Encyclopedia of Parallel Computing. 1581\u20131592."},{"key":"e_1_3_2_1_27_1","volume-title":"Cache-Oblivious Algorithms. In Proc. of the 40th Annual Symposium on Foundations of Computer Science, FOCS \u201999","author":"Frigo Matteo","year":"1999","unstructured":"Matteo Frigo, Charles E. Leiserson, Harald Prokop, and Sridhar Ramachandran. 1999. Cache-Oblivious Algorithms. In Proc. of the 40th Annual Symposium on Foundations of Computer Science, FOCS \u201999, 17-18 October, 1999, New York, NY, USA. 285\u2013298."},{"key":"e_1_3_2_1_28_1","volume-title":"Proc. of the 13th Annual ACM Symposium on Theory of Computing (STOC \u201981)","author":"Hong Jia-Wei","year":"1981","unstructured":"Jia-Wei Hong and H. T. Kung. 1981. I\/O complexity: The red-blue pebble game. In Proc. of the 13th Annual ACM Symposium on Theory of Computing (STOC \u201981), May 11-13, 1981, Milwaukee, Wisconsin, USA. 326\u2013333."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.03.021"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3295500.3356181"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1949-09320-5"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Auguste Olivry Julien Langou Louis-No\u00ebl Pouchet P. Sadayappan and Fabrice Rastello. 2019. Automated Derivation of Parametric Data Movement Lower Bounds for Affine Programs. arXiv: cs.CC\/1911.06664","DOI":"10.1145\/3385412.3385989"},{"key":"e_1_3_2_1_33_1","unstructured":"Louis-No\u00ebl Pouchet and Tomofumi Yuki. 2015."},{"key":"e_1_3_2_1_34_1","unstructured":"PolyBench\/C 4.2. http:\/\/polybench.sf.net\/."},{"key":"e_1_3_2_1_35_1","unstructured":"J. Ramanujam and P. Sadayappan. 1992."},{"key":"e_1_3_2_1_36_1","volume-title":"108\u2013230","author":"Parallel Tiling","year":"1992","unstructured":"Tiling multidimensional iteration spaces for multicomputers. J. Parallel and Distrib. Comput. 16, 2 (1992), 108\u2013230."},{"key":"e_1_3_2_1_37_1","unstructured":"Desh Ranjan John E. Savage and Mohammad Zubair. 2010."},{"key":"e_1_3_2_1_38_1","volume-title":"IWOCA 2010","author":"Pyramids Upper","year":"2010","unstructured":"Upper and Lower I\/O Bounds for Pebbling r-Pyramids. In Combinatorial Algorithms - 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers. 107\u2013120."},{"key":"e_1_3_2_1_39_1","unstructured":"Desh Ranjan John E. Savage and Mohammad Zubair. 2011."},{"key":"e_1_3_2_1_40_1","volume-title":"LNCS","volume":"6842","author":"Lower Strong","unstructured":"Strong I\/O Lower Bounds for Binomial and FFT Computation Graphs. In Computing and Combinatorics. LNCS, Vol. 6842. 134\u2013145."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2011.12.005"},{"key":"e_1_3_2_1_42_1","unstructured":"John E. Savage. 1995."},{"key":"e_1_3_2_1_43_1","volume-title":"Computing and Combinatorics. LNCS","author":"Extending","unstructured":"Extending the Hong-Kung model to memory hierarchies. In Computing and Combinatorics. LNCS, Vol. 959. 270\u2013281."},{"key":"e_1_3_2_1_44_1","volume-title":"Savage and Mohammad Zubair","author":"John","year":"2008","unstructured":"John E. Savage and Mohammad Zubair. 2008."},{"key":"e_1_3_2_1_45_1","volume-title":"Proc. of the 1st international forum on Next-generation multicore\/manycore technologies, IFMT 2008","author":"A","year":"2008","unstructured":"A unified model for multicore architectures. In Proc. of the 1st international forum on Next-generation multicore\/manycore technologies, IFMT 2008, Cairo, Egypt, November 24-25, 2008. 9."},{"key":"e_1_3_2_1_46_1","volume-title":"van de Geijn","author":"Smith Tyler Michael","year":"2019","unstructured":"Tyler Michael Smith, Bradley Lowery, Julien Langou, and Robert A. van de Geijn. 2019. A Tight I\/O Lower Bound for Matrix Multiplication. arXiv: 1702.02017v2"},{"key":"e_1_3_2_1_47_1","volume-title":"Gaussian elimination is not optimal. Numerische mathematik 13, 4","author":"Strassen Volker","year":"1969","unstructured":"Volker Strassen. 1969. Gaussian elimination is not optimal. Numerische mathematik 13, 4 (1969), 354\u2013356."},{"key":"e_1_3_2_1_48_1","volume-title":"ISL: An integer set library for the polyhedral model. In Mathematical Software\u2013ICMS","author":"Verdoolaege Sven","year":"2010","unstructured":"Sven Verdoolaege. 2010. ISL: An integer set library for the polyhedral model. In Mathematical Software\u2013ICMS 2010. 299\u2013302."},{"key":"e_1_3_2_1_49_1","unstructured":"Sven Verdoolaege. 2018."},{"key":"e_1_3_2_1_50_1","unstructured":"Integer Set Library: Manual. http:\/\/isl.gforge.inria.fr\/manual.pdf."},{"key":"e_1_3_2_1_51_1","unstructured":"Sven Verdoolaege and Tobias Grosser. 2012."},{"key":"e_1_3_2_1_52_1","volume-title":"Extraction Tool. In Second International Workshop on Polyhedral Compilation Techniques (IMPACT\u201912)","author":"Polyhedral","unstructured":"Polyhedral Extraction Tool. In Second International Workshop on Polyhedral Compilation Techniques (IMPACT\u201912)."},{"key":"e_1_3_2_1_53_1","unstructured":"Samuel Williams Andrew Waterman and David Patterson. 2009."}],"event":{"name":"PLDI '20: 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation","location":"London UK","acronym":"PLDI '20","sponsor":["SIGPLAN ACM Special Interest Group on Programming Languages"]},"container-title":["Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3385412.3385989","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3385412.3385989","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3385412.3385989","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:14Z","timestamp":1750200074000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3385412.3385989"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,11]]},"references-count":52,"alternative-id":["10.1145\/3385412.3385989","10.1145\/3385412"],"URL":"https:\/\/doi.org\/10.1145\/3385412.3385989","relation":{},"subject":[],"published":{"date-parts":[[2020,6,11]]},"assertion":[{"value":"2020-06-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}