{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T07:23:27Z","timestamp":1777965807430,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,7,6]],"date-time":"2021-07-06T00:00:00Z","timestamp":1625529600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["678880"],"award-info":[{"award-number":["678880"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Swiss National Science Foundation","award":["185778"],"award-info":[{"award-number":["185778"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,7,6]]},"DOI":"10.1145\/3409964.3461796","type":"proceedings-article","created":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T23:07:02Z","timestamp":1625094422000},"page":"328-339","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Pebbles, Graphs, and a Pinch of Combinatorics"],"prefix":"10.1145","author":[{"given":"Grzegorz","family":"Kwasniewski","sequence":"first","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tal","family":"Ben-Nun","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lukas","family":"Gianinazzi","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexandru","family":"Calotoiu","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Timo","family":"Schneider","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexandros Nikolaos","family":"Ziogas","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maciej","family":"Besta","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Torsten","family":"Hoefler","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,7,6]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2703149"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2013.6704670"},{"key":"e_1_3_2_1_3_1","volume-title":"PADAL Workshop","author":"Tate A.","year":"2014","unstructured":"A. Tate , A. Kamil , A. Dubey , A. Gr\u00f6\u00dflinger , B. Chamberlain , B. Goglin , C. Edwards , C. J. Newburn , D. Padua , D. Unat \u201cProgramming abstractions for data locality.\u201dhskip 1em plus 0.5em minus 0.4emrelax PADAL Workshop 2014 . A. Tate, A. Kamil, A. Dubey, A. Gr\u00f6\u00dflinger, B. Chamberlain, B. Goglin, C. Edwards, C. J. Newburn, D. Padua, D. Unat et al., \u201cProgramming abstractions for data locality.\u201dhskip 1em plus 0.5em minus 0.4emrelax PADAL Workshop 2014."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2703149"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3126908.3126971"},{"issue":"1","key":"e_1_3_2_1_6_1","first-page":"1","article-title":"Trade-offs between synchronization, communication, and computation in parallel linear algebra computations","volume":"3","author":"Solomonik E.","year":"2017","unstructured":"E. Solomonik , E. Carson , N. Knight , and J. Demmel , \u201c Trade-offs between synchronization, communication, and computation in parallel linear algebra computations ,\u201d ACM Transactions on Parallel Computing (TOPC) , vol. 3 , no. 1 , pp. 1 -- 47 , 2017 . E. Solomonik, E. Carson, N. Knight, and J. Demmel, \u201cTrade-offs between synchronization, communication, and computation in parallel linear algebra computations,\u201d ACM Transactions on Parallel Computing (TOPC), vol. 3, no. 1, pp. 1--47, 2017.","journal-title":"ACM Transactions on Parallel Computing (TOPC)"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.21236\/ADA584726"},{"key":"e_1_3_2_1_8_1","first-page":"326","volume-title":"STOC","author":"Hong J.","year":"1981","unstructured":"J. Hong and H. Kung , \u201c I\/O complexity: The red-blue pebble game ,\u201d in STOC , 1981 , pp. 326 -- 333 . J. Hong and H. Kung, \u201cI\/O complexity: The red-blue pebble game,\u201d in STOC, 1981, pp. 326--333."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cpc.2014.10.021"},{"key":"e_1_3_2_1_10_1","volume-title":"CoRR","author":"Zheng Q.","year":"2016","unstructured":"Q. Zheng and J. D. Lafferty , \u201c Convergence analysis for rectangular matrix completion using burer-monteiro factorization and gradient descent ,\u201d CoRR , 2016 . Q. Zheng and J. D. Lafferty, \u201cConvergence analysis for rectangular matrix completion using burer-monteiro factorization and gradient descent,\u201d CoRR, 2016."},{"key":"e_1_3_2_1_11_1","volume-title":"ACM Comput. Surv.","author":"Ben-Nun T.","unstructured":"T. Ben-Nun and T. Hoefler , \u201c Demystifying parallel and distributed deep learning: An in-depth concurrency analysis ,\u201d ACM Comput. Surv. , vol. 52 , no. 4, 2019. T. Ben-Nun and T. Hoefler, \u201cDemystifying parallel and distributed deep learning: An in-depth concurrency analysis,\u201d ACM Comput. Surv., vol. 52, no. 4, 2019."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719512"},{"key":"e_1_3_2_1_13_1","first-page":"70","volume-title":"Matrix inversion using Cholesky decomposition","author":"Krishnamoorthy A.","year":"2013","unstructured":"A. Krishnamoorthy and D. Menon , \u201c Matrix inversion using Cholesky decomposition ,\u201d in 2013 signal processing: Algorithms, architectures, arrangements, and applications (SPA). hskip 1em plus 0.5em minus 0.4emrelax IEEE , 2013, pp. 70 -- 72 . A. Krishnamoorthy and D. Menon, \u201cMatrix inversion using Cholesky decomposition,\u201d in 2013 signal processing: Algorithms, architectures, arrangements, and applications (SPA). hskip 1em plus 0.5em minus 0.4emrelax IEEE, 2013, pp. 70--72."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2014.06.002"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2677010"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3295500.3356181"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210387"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385989"},{"key":"e_1_3_2_1_20_1","volume-title":"I\/O lower bounds for auto-tuning of convolutions in CNNs","author":"Zhang X.","year":"2020","unstructured":"X. Zhang , J. Xiao , and G. Tan , \u201c I\/O lower bounds for auto-tuning of convolutions in CNNs ,\u201d 2020 . X. Zhang, J. Xiao, and G. Tan, \u201cI\/O lower bounds for auto-tuning of convolutions in CNNs,\u201d 2020."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.21236\/ADA584726"},{"key":"e_1_3_2_1_22_1","volume-title":"Parallelepipeds obtaining HBL lower bounds","author":"Demmel J.","year":"2016","unstructured":"J. Demmel and A. Rusciano , \u201c Parallelepipeds obtaining HBL lower bounds ,\u201d arXiv preprint arXiv:1611.05944, 2016 . J. Demmel and A. Rusciano, \u201cParallelepipeds obtaining HBL lower bounds,\u201d arXiv preprint arXiv:1611.05944, 2016."},{"key":"e_1_3_2_1_23_1","volume-title":"Communication-optimal convolutional neural nets","author":"Demmel J.","year":"1802","unstructured":"J. Demmel and G. Dinh , \u201c Communication-optimal convolutional neural nets ,\u201d arXiv preprint arXiv: 1802 .06905, 2018. J. Demmel and G. Dinh, \u201cCommunication-optimal convolutional neural nets,\u201d arXiv preprint arXiv:1802.06905, 2018."},{"key":"e_1_3_2_1_24_1","volume-title":"Communication-optimal tilings for projective nested loops with arbitrary bounds","author":"Dinh G.","year":"2003","unstructured":"G. Dinh and J. Demmel , \u201c Communication-optimal tilings for projective nested loops with arbitrary bounds ,\u201d arXiv preprint arXiv: 2003 .00119, 2020. G. Dinh and J. Demmel, \u201cCommunication-optimal tilings for projective nested loops with arbitrary bounds,\u201d arXiv preprint arXiv:2003.00119, 2020."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0030842"},{"key":"e_1_3_2_1_26_1","volume-title":"Red-blue and standard pebble games : Complexity and applications in the sequential and parallel models","author":"Liu Q.","year":"2018","unstructured":"Q. Liu , \u201c Red-blue and standard pebble games : Complexity and applications in the sequential and parallel models ,\u201d 2018 . Q. Liu, \u201cRed-blue and standard pebble games : Complexity and applications in the sequential and parallel models,\u201d 2018."},{"key":"e_1_3_2_1_27_1","volume-title":"On the parallel I\/O optimality of linear algebra kernels: Near-optimal LU factorization","author":"Kwasniewski G.","year":"2020","unstructured":"G. Kwasniewski , T. Ben-Nun , A. N. Ziogas , T. Schneider , M. Besta , and T. Hoefler , \u201c On the parallel I\/O optimality of linear algebra kernels: Near-optimal LU factorization ,\u201d 2020 . G. Kwasniewski, T. Ben-Nun, A. N. Ziogas, T. Schneider, M. Besta, and T. Hoefler, \u201cOn the parallel I\/O optimality of linear algebra kernels: Near-optimal LU factorization,\u201d 2020."},{"key":"e_1_3_2_1_28_1","volume-title":"PolyBench: The Polyhedral Benchmark suite","author":"Pouchet L. N.","year":"2016","unstructured":"BIBentryALTinterwordspacing L. N. Pouchet , \u201c PolyBench: The Polyhedral Benchmark suite ,\u201d 2016 . [Online]. Available: https:\/\/sourceforge.net\/projects\/polybenchBIBentrySTDinterwordspacing BIBentryALTinterwordspacingL. N. Pouchet, \u201cPolyBench: The Polyhedral Benchmark suite,\u201d 2016. [Online]. Available: https:\/\/sourceforge.net\/projects\/polybenchBIBentrySTDinterwordspacing"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3295500.3356173"},{"key":"e_1_3_2_1_30_1","volume-title":"Livermore unstructured lagrange explicit shock hydrodynamics","author":"Keasler J.","year":"2010","unstructured":"BIBentryALTinterwordspacing J. Keasler and USDOE , \u201c Livermore unstructured lagrange explicit shock hydrodynamics ,\u201d 9 2010 . [Online]. Available: https:\/\/www.osti.gov\/\/servlets\/purl\/1231396BIBentrySTDinterwordspacing BIBentryALTinterwordspacingJ. Keasler and USDOE, \u201cLivermore unstructured lagrange explicit shock hydrodynamics,\u201d 9 2010. [Online]. Available: https:\/\/www.osti.gov\/\/servlets\/purl\/1231396BIBentrySTDinterwordspacing"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1175\/MWR-D-10-05013.1"},{"key":"e_1_3_2_1_32_1","volume-title":"Data movement is all you need: A case study on optimizing transformers","author":"Ivanov A.","year":"2020","unstructured":"A. Ivanov , N. Dryden , T. Ben-Nun , S. Li , and T. Hoefler , \u201c Data movement is all you need: A case study on optimizing transformers ,\u201d 2020 . A. Ivanov, N. Dryden, T. Ben-Nun, S. Li, and T. Hoefler, \u201cData movement is all you need: A case study on optimizing transformers,\u201d 2020."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.726791"},{"key":"e_1_3_2_1_34_1","volume-title":"Attention is all you need","author":"Vaswani A.","year":"2017","unstructured":"A. Vaswani , N. Shazeer , N. Parmar , J. Uszkoreit , L. Jones , A. N. Gomez , L. Kaiser , and I. Polosukhin , \u201c Attention is all you need ,\u201d 2017 . A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, \u201cAttention is all you need,\u201d 2017."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804049"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289150"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90011-X"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400278"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.03.021"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23397-5_10"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2013.80"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/090760969"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2019.00020"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492914000038"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA47549.2020.00050"},{"key":"e_1_3_2_1_47_1","first-page":"132","volume-title":"Automatic Transformations for Communication-Minimized Parallelization and Locality Optimization in the Polyhedral Model. hskip 1em plus 0.5em minus 0.4emrelax Berlin","author":"Bondhugula U.","year":"2008","unstructured":"BIBentryALTinterwordspacing U. Bondhugula , M. Baskaran , S. Krishnamoorthy , J. Ramanujam , A. Rountev , and P. Sadayappan , Automatic Transformations for Communication-Minimized Parallelization and Locality Optimization in the Polyhedral Model. hskip 1em plus 0.5em minus 0.4emrelax Berlin , Heidelberg : Springer Berlin Heidelberg , 2008 , pp. 132 -- 146 . [Online]. Available: https:\/\/doi.org\/10.1007\/978--3--540--78791--4_9BIBentrySTDinterwordspacing BIBentryALTinterwordspacingU. Bondhugula, M. Baskaran, S. Krishnamoorthy, J. Ramanujam, A. Rountev, and P. Sadayappan, Automatic Transformations for Communication-Minimized Parallelization and Locality Optimization in the Polyhedral Model. hskip 1em plus 0.5em minus 0.4emrelax Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 132--146. [Online]. Available: https:\/\/doi.org\/10.1007\/978--3--540--78791--4_9BIBentrySTDinterwordspacing"},{"key":"e_1_3_2_1_48_1","volume-title":"International Conference on Compiler Construction (ETAPS CC)","year":"2008","unstructured":"\u201c Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model ,\u201d in International Conference on Compiler Construction (ETAPS CC) , Apr. 2008 . \u201cAutomatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model,\u201d in International Conference on Compiler Construction (ETAPS CC), Apr. 2008."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626412500107"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612685"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.1999.807510"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612694"}],"event":{"name":"SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures","location":"Virtual Event USA","acronym":"SPAA '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"]},"container-title":["Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3409964.3461796","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3409964.3461796","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:08Z","timestamp":1750191428000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3409964.3461796"}},"subtitle":["Towards Tight I\/O Lower Bounds for Statically Analyzable Programs"],"short-title":[],"issued":{"date-parts":[[2021,7,6]]},"references-count":51,"alternative-id":["10.1145\/3409964.3461796","10.1145\/3409964"],"URL":"https:\/\/doi.org\/10.1145\/3409964.3461796","relation":{},"subject":[],"published":{"date-parts":[[2021,7,6]]},"assertion":[{"value":"2021-07-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}