{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,14]],"date-time":"2026-09-14T23:03:44Z","timestamp":1789427024517,"version":"build-2803163510"},"reference-count":57,"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":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"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>\n                  <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-24T07:57:18Z","timestamp":1540367838000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":111,"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","volume-title":"NIST Sparse BLAS User\u2019s Guide. (08","author":"Remington Karin A.","year":"1996","unstructured":"Karin A. Remington. 1996. NIST Sparse BLAS User\u2019s Guide. (08 1996)."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2697055"},{"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."},{"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.","unstructured":"M. Baskaran, B. Meister, N. Vasilache, and R. Lethin. 2012. Efficient and scalable computations with sparse tensors. In 2012 IEEE Conference on High Performance Extreme Computing. 1\u20136."},{"key":"e_1_2_2_8_1","unstructured":"Nathan Bell and Michael Garland. 2008. Efficient Sparse Matrix-Vector Multiplication on CUDA. NVIDIA Technical Report NVR-2008-004. NVIDIA Corporation."},{"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","unstructured":"Aart JC Bik and Harry AG Wijshoff. 1994. On automatic data structure selection and code generation for sparse computations. In Languages and Compilers for Parallel Computing. Springer, 57\u201375."},{"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","unstructured":"Aydin Bulu\u00e7 and John R. Gilbert. 2008. On the representation and multiplication of hypersparse matrices. In IEEE International Symposium on Parallel and Distributed Processing, (IPDPS). 1\u201311."},{"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":"publisher","unstructured":"Timothy A Davis. 2006. Direct methods for sparse linear systems. SIAM.","DOI":"10.5555\/1196434"},{"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","volume-title":"Sands","author":"Feynman Richard","year":"1963","unstructured":"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","unstructured":"Eun-jin Im and Katherine Yelick. 1998. Model-Based Memory Hierarchy Optimizations for Sparse Matrices. In In Workshop on Profile and Feedback-Directed Compilation."},{"key":"e_1_2_2_21_1","unstructured":"Intel. 2012. Intel math kernel library reference manual. Technical Report. 630813-051US 2012. http:\/\/software.intel.com\/ sites\/products\/documentation\/hpc\/mkl\/mklman\/mklman.pdf ."},{"key":"e_1_2_2_22_1","unstructured":"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","volume-title":"Young","author":"Kincaid David R.","year":"1989","unstructured":"David R. Kincaid, Thomas C. Oppe, and David M. Young. 1989. ITPACKV 2D User\u2019s Guide."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133901"},{"key":"e_1_2_2_25_1","volume-title":"The art of computer programming: sorting and searching","author":"Knuth Donald Ervin","unstructured":"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.","unstructured":"P. Koanantakool, A. Azad, A. Bulu\u00c3\u011f, D. Morozov, S. Y. Oh, L. Oliker, and K. Yelick. 2016. Communication-Avoiding Parallel Sparse-Dense Matrix-Matrix Multiplication. In 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 842\u2013853."},{"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","unstructured":"Joseph C Kolecki. 2002. An Introduction to Tensors for Students of Physics and Engineering. Unixenguaedu 7, September (2002), 29.","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."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/646662.699553"},{"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.","unstructured":"B. Liu, C. Wen, A. D. Sarwate, and M. M. Dehnavi. 2017. A Unified Optimization Approach for Sparse Tensor Operations on GPUs. In 2017 IEEE International Conference on Cluster Computing (CLUSTER). 47\u201357."},{"key":"e_1_2_2_32_1","unstructured":"Devin Matthews. 2017. High-Performance Tensor Contraction without Transposition. Technical Report."},{"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","unstructured":"National Institute of Standards and Technology. 2013. Matrix Market: File Formats. http:\/\/math.nist.gov\/MatrixMarket\/ formats.html"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629698"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/645676.663645"},{"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":"publisher","unstructured":"Yousef Saad. 2003. Iterative methods for sparse linear systems. SIAM.","DOI":"10.5555\/829576"},{"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"},{"key":"e_1_2_2_42_1","volume-title":"FROSTT: The Formidable Repository of Open Sparse Tensors and Tools","author":"Smith Shaden","year":"2017","unstructured":"Shaden Smith, Jee W. Choi, Jiajia Li, Richard Vuduc, Jongsoo Park, Xing Liu, and George Karypis. 2017b. FROSTT: The Formidable Repository of Open Sparse Tensors and Tools. http:\/\/frostt.io\/"},{"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","volume-title":"Design of a high-performance GEMM-like Tensor-Tensor Multiplication. arXiv preprint arXiv:1607.00145","author":"Springer Paul","year":"2016","unstructured":"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."},{"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 ."},{"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 ."},{"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."},{"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."},{"key":"e_1_2_2_57_1","volume-title":"Bisseling","author":"Yzelman Albert-Jan N.","year":"2012","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."}],"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":[[2026,9,10]],"date-time":"2026-09-10T16:06:03Z","timestamp":1789056363000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3276493"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,24]]},"references-count":57,"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":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}