{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,20]],"date-time":"2026-06-20T16:22:43Z","timestamp":1781972563302,"version":"3.54.5"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2018,10,24]],"date-time":"2018-10-24T00:00:00Z","timestamp":1540339200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100011030","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-SC0008923,DE-SC0018121"],"award-info":[{"award-number":["DE-SC0008923,DE-SC0018121"]}],"id":[{"id":"10.13039\/100011030","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100015599","name":"Toyota Research Institute","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100015599","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1533753"],"award-info":[{"award-number":["CCF-1533753"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"crossref","award":["HR0011-18-3-0007"],"award-info":[{"award-number":["HR0011-18-3-0007"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Application Driving Architectures Research Center"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2018,10,24]]},"abstract":"<jats:p>This paper shows how to build a sparse tensor algebra compiler that is agnostic to tensor formats (data layouts). We develop an interface that describes formats in terms of their capabilities and properties, and show how to build a modular code generator where new formats can be added as plugins. We then describe six implementations of the interface that compose to form the dense, CSR\/CSF, COO, DIA, ELL, and HASH tensor formats and countless variants thereof. With these implementations at hand, our code generator can generate code to compute any tensor algebra expression on any combination of the aforementioned formats.<\/jats:p><jats:p>To demonstrate our technique, we have implemented it in the taco tensor algebra compiler. Our modular code generator design makes it simple to add support for new tensor formats, and the performance of the generated code is competitive with hand-optimized implementations. Furthermore, by extending taco to support a wider range of formats specialized for different application and data characteristics, we can improve end-user application performance. For example, if input data is provided in the COO format, our technique allows computing a single matrix-vector multiplication directly with the data in COO, which is up to 3.6\u00d7 faster than by first converting the data to CSR.<\/jats:p>","DOI":"10.1145\/3276493","type":"journal-article","created":{"date-parts":[[2018,10,24]],"date-time":"2018-10-24T11:57:18Z","timestamp":1540382238000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":108,"title":["Format abstraction for sparse tensor algebra compilers"],"prefix":"10.1145","volume":"2","author":[{"given":"Stephen","family":"Chou","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fredrik","family":"Kjolstad","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saman","family":"Amarasinghe","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,10,24]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Karin A. Remington. 1996. NIST Sparse BLAS User\u2019s Guide. (08 1996). Karin A. Remington. 1996. NIST Sparse BLAS User\u2019s Guide. (08 1996)."},{"key":"e_1_2_2_2_1","article-title":"Tensor Decompositions for Learning Latent Variable Models","author":"Anandkumar Animashree","year":"2014","journal-title":"J. Mach. Learn. Res. 15, Article 1"},{"key":"e_1_2_2_3_1","unstructured":"Gilad Arnold. 2011. Data-Parallel Language for Correct and Efficient Sparse Matrix Codes. Ph.D. Dissertation. University of California Berkeley. Gilad Arnold. 2011. Data-Parallel Language for Correct and Efficient Sparse Matrix Codes. Ph.D. Dissertation. University of California Berkeley."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1863543.1863581"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/00268970500275780"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/060676489"},{"key":"e_1_2_2_7_1","volume-title":"2012 IEEE Conference on High Performance Extreme Computing. 1\u20136.","author":"Baskaran M."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/165939.166023"},{"key":"e_1_2_2_10_1","volume-title":"Languages and Compilers for Parallel Computing","author":"Bik Aart JC"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584053"},{"key":"e_1_2_2_12_1","volume-title":"IEEE International Symposium on Parallel and Distributed Processing, (IPDPS). 1\u201311","author":"Bulu\u00e7 Aydin"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSSC.2017.2749425"},{"key":"e_1_2_2_14_1","doi-asserted-by":"crossref","unstructured":"Timothy A Davis. 2006. Direct methods for sparse linear systems. SIAM. Timothy A Davis. 2006. Direct methods for sparse linear systems. SIAM.","DOI":"10.1137\/1.9780898718881"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11428831_13"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/jcc.23377"},{"key":"e_1_2_2_18_1","unstructured":"Richard Feynman Robert B. Leighton and Matthew L. Sands. 1963. The Feynman Lectures on Physics. Vol. 3. Addison-Wesley. Richard Feynman Robert B. Leighton and Matthew L. Sands. 1963. The Feynman Lectures on Physics. Vol. 3. Addison-Wesley."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1274971.1274989"},{"key":"e_1_2_2_20_1","volume-title":"Model-Based Memory Hierarchy Optimizations for Sparse Matrices. In In Workshop on Profile and Feedback-Directed Compilation.","author":"Katherine Yelick Im","year":"1998"},{"key":"e_1_2_2_22_1","unstructured":"Eric Jones Travis Oliphant Pearu Peterson etal 2001. SciPy: Open source scientific tools for Python. http:\/\/www.scipy.org\/ {Online; accessed &lt;today&gt;}. Eric Jones Travis Oliphant Pearu Peterson et al. 2001. SciPy: Open source scientific tools for Python. http:\/\/www.scipy.org\/ {Online; accessed &lt;today&gt;}."},{"key":"e_1_2_2_23_1","doi-asserted-by":"crossref","unstructured":"David R. Kincaid Thomas C. Oppe and David M. Young. 1989. ITPACKV 2D User\u2019s Guide. David R. Kincaid Thomas C. Oppe and David M. Young. 1989. ITPACKV 2D User\u2019s Guide.","DOI":"10.2172\/7093021"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133901"},{"key":"e_1_2_2_25_1","unstructured":"Donald Ervin Knuth. 1973. The art of computer programming: sorting and searching. Vol. 3. Pearson Education. Donald Ervin Knuth. 1973. The art of computer programming: sorting and searching. Vol. 3. Pearson Education."},{"key":"e_1_2_2_26_1","volume-title":"Communication-Avoiding Parallel Sparse-Dense Matrix-Matrix Multiplication. In 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 842\u2013853","author":"Koanantakool P."},{"key":"e_1_2_2_27_1","first-page":"29","article-title":"An Introduction to Tensors for Students of Physics and Engineering","author":"Kolecki Joseph C","year":"2002","journal-title":"Unixenguaedu 7"},{"key":"e_1_2_2_28_1","unstructured":"Vladimir Kotlyar. 1999. Relational Algebraic Techniques for the Synthesis of Sparse Matrix Programs. Ph.D. Dissertation. Cornell. Vladimir Kotlyar. 1999. Relational Algebraic Techniques for the Synthesis of Sparse Matrix Programs. Ph.D. Dissertation. Cornell."},{"key":"e_1_2_2_29_1","volume-title":"Euro-Par\u201997 Parallel Processing","author":"Kotlyar Vladimir"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807671"},{"key":"e_1_2_2_31_1","volume-title":"2017 IEEE International Conference on Cluster Computing (CLUSTER). 47\u201357","author":"Liu B."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/233561.233564"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/362575.362584"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11515-8_10"},{"key":"e_1_2_2_36_1","volume-title":"Matrix Market: File Formats","author":"National Institute of Standards and Technology.","year":"2013"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629698"},{"key":"e_1_2_2_38_1","volume-title":"SIPR: A new framework for generating efficient code for sparse matrix computations. In Languages and Compilers for Parallel Computing","author":"Pugh William","year":"1999"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2967938.2967943"},{"key":"e_1_2_2_40_1","doi-asserted-by":"crossref","unstructured":"Yousef Saad. 2003. Iterative methods for sparse linear systems. SIAM. Yousef Saad. 2003. Iterative methods for sparse linear systems. SIAM.","DOI":"10.1137\/1.9780898718003"},{"key":"e_1_2_2_41_1","unstructured":"Shaden Smith Jee W. Choi Jiajia Li Richard Vuduc Jongsoo Park Xing Liu and George Karypis. 2017a. FROSTT file formats. http:\/\/frostt.io\/tensors\/file-formats.html Shaden Smith Jee W. Choi Jiajia Li Richard Vuduc Jongsoo Park Xing Liu and George Karypis. 2017a. FROSTT file formats. http:\/\/frostt.io\/tensors\/file-formats.html"},{"key":"e_1_2_2_42_1","volume-title":"FROSTT: The Formidable Repository of Open Sparse Tensors and Tools","author":"Smith Shaden","year":"2017"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2833179.2833183"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2015.27"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2014.06.002"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2581122.2544155"},{"key":"e_1_2_2_47_1","unstructured":"Paul Springer and Paolo Bientinesi. 2016. Design of a high-performance GEMM-like Tensor-Tensor Multiplication. arXiv preprint arXiv:1607.00145 (2016). Paul Springer and Paolo Bientinesi. 2016. Design of a high-performance GEMM-like Tensor-Tensor Multiplication. arXiv preprint arXiv:1607.00145 (2016)."},{"key":"e_1_2_2_48_1","unstructured":"Paul Stodghill. 1997. A Relational Approach to the Automatic Generation of Sequential Sparse Matrix Codes. Ph.D. Dissertation. Cornell. Paul Stodghill. 1997. A Relational Approach to the Automatic Generation of Sequential Sparse Matrix Codes. Ph.D. Dissertation. Cornell."},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2304576.2304624"},{"key":"e_1_2_2_50_1","unstructured":"The SciPy community. 2018a. scipy.sparse.dok_matrix \u2013 SciPy v1.1.0 Reference Guide. https:\/\/docs.scipy.org\/doc\/scipy\/ reference\/generated\/scipy.sparse.dok_matrix.html . The SciPy community. 2018a. scipy.sparse.dok_matrix \u2013 SciPy v1.1.0 Reference Guide. https:\/\/docs.scipy.org\/doc\/scipy\/ reference\/generated\/scipy.sparse.dok_matrix.html ."},{"key":"e_1_2_2_51_1","unstructured":"The SciPy community. 2018b. scipy.sparse.lil_matrix \u2013 SciPy v1.1.0 Reference Guide. https:\/\/docs.scipy.org\/doc\/scipy\/ reference\/generated\/scipy.sparse.lil_matrix.html . The SciPy community. 2018b. scipy.sparse.lil_matrix \u2013 SciPy v1.1.0 Reference Guide. https:\/\/docs.scipy.org\/doc\/scipy\/ reference\/generated\/scipy.sparse.lil_matrix.html ."},{"key":"e_1_2_2_52_1","unstructured":"Scott Thibault Lenore Mullin and Matt Insall. 1994. Generating Indexing Functions of Regularly Sparse Arrays for Array Compilers. Scott Thibault Lenore Mullin and Matt Insall. 1994. Generating Indexing Functions of Regularly Sparse Arrays for Array Compilers."},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1967.6011"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2738003"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/113446.113449"},{"key":"e_1_2_2_56_1","unstructured":"Michael Joseph Wolfe. 1982. Optimizing Supercompilers for Supercomputers. Ph.D. Dissertation. University of Illinois at Urbana-Champaign Champaign IL USA. AAI8303027. Michael Joseph Wolfe. 1982. Optimizing Supercompilers for Supercomputers. Ph.D. Dissertation. University of Illinois at Urbana-Champaign Champaign IL USA. AAI8303027."},{"key":"e_1_2_2_57_1","doi-asserted-by":"crossref","unstructured":"Albert-Jan N. Yzelman and Rob H. Bisseling. 2012. A Cache-Oblivious Sparse Matrix\u2013Vector Multiplication Scheme Based on the Hilbert Curve. In Progress in Industrial Mathematics at ECMI 2010 Michael G\u00fcnther Andreas Bartel Markus Brunk Sebastian Sch\u00f6ps and Michael Striebel (Eds.). Springer Berlin Heidelberg Berlin Heidelberg 627\u2013633. Albert-Jan N. Yzelman and Rob H. Bisseling. 2012. A Cache-Oblivious Sparse Matrix\u2013Vector Multiplication Scheme Based on the Hilbert Curve. In Progress in Industrial Mathematics at ECMI 2010 Michael G\u00fcnther Andreas Bartel Markus Brunk Sebastian Sch\u00f6ps and Michael Striebel (Eds.). Springer Berlin Heidelberg Berlin Heidelberg 627\u2013633.","DOI":"10.1007\/978-3-642-25100-9_73"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3276493","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3276493","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3276493","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:01:59Z","timestamp":1750208519000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3276493"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,24]]},"references-count":54,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2018,10,24]]}},"alternative-id":["10.1145\/3276493"],"URL":"https:\/\/doi.org\/10.1145\/3276493","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,24]]},"assertion":[{"value":"2018-10-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}