Cited By
View all- Gladshtein VZhao QAhrens WAmarasinghe SSergey I(2024)Mechanised Hypersafety Proofs about Structured DataProceedings of the ACM on Programming Languages10.1145/36564038:PLDI(647-670)Online publication date: 20-Jun-2024
Code Synthesis for Sparse Tensor Format Conversion and Optimization
Authors: 
Tobi Popoola, Tuowen Zhao, Aaron St. George, Kalyan Bhetwal, 
Michelle Mills Strout, Mary Hall, Catherine OlschanowskyAuthors Info & Claims
Pages 28 - 40
Abstract
Many scientific applications compute using sparse data and store that data in a variety of sparse formats because each format has unique space and performance benefits. Optimizing applications that use sparse data involves translating the sparse data into the chosen format and transforming the computation to iterate over that format. This paper presents a formal definition of sparse tensor formats and an automated approach to synthesize the transformation between formats. This approach is unique in that it supports ordering constraints not supported by other approaches and synthesizes the transformation code in a high-level intermediate representation suitable for applying composable transformations such as loop fusion and temporary storage reduction. We demonstrate that the synthesized code for COO to CSR with optimizations is 2.85x faster than TACO, Intel MKL, and SPARSKIT while the more complex COO to DIA is 1.4x slower than TACO but faster than SPARSKIT and Intel MKL using the geometric average of execution time.
References
[1]
Khalid Ahmad, Hari Sundar, and Mary Hall. 2019. Data-Driven Mixed Precision Sparse Matrix Vector Multiplication for GPUs. ACM Trans. Archit. Code Optim., 16, 4 (2019), Article 51, Dec., 24 pages. issn:1544-3566 https://doi.org/10.1145/3371275
[2]
Aart J. C. Bik and Harry A. G. Wijshoff. 1993. On Automatic Data Structure Selection and Code Generation for Sparse Computations. In Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing. Springer-Verlag, Berlin, Heidelberg. 57–75. isbn:3540576592
[3]
James Bornholt, Emina Torlak, Dan Grossman, and Luis Ceze. 2016. Optimizing Synthesis with Metasketches. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’16). Association for Computing Machinery, New York, NY, USA. 775–788. isbn:9781450335492 https://doi.org/10.1145/2837614.2837666
[4]
Chun Chen. 2012. Polyhedra Scanning Revisited. SIGPLAN Not., 47, 6 (2012), jun, 499–508. issn:0362-1340 https://doi.org/10.1145/2345156.2254123
[5]
Chun Chen, Jacqueline Chame, and Mary Hall. 2008. CHiLL: A Framework for Composing High-Level Loop Transformations. University of Southern California.
[6]
Stephen Chou, Fredrik Kjolstad, and Saman Amarasinghe. 2018. Format Abstraction for Sparse Tensor Algebra Compilers. Proc. ACM Program. Lang., 2, OOPSLA (2018), Oct., 123:1–123:30.
[7]
Stephen Chou, Fredrik Kjolstad, and Saman Amarasinghe. 2020. Automatic Generation of Efficient Sparse Tensor Format Conversion Routines. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2020). Association for Computing Machinery, New York, NY, USA. 823–838. isbn:9781450376136 https://doi.org/10.1145/3385412.3385963
[8]
Timothy A. Davis and Yifan Hu. 2011. The University of Florida Sparse Matrix Collection. ACM Trans. Math. Softw., 38, 1 (2011), Article 1, dec, 25 pages. issn:0098-3500 https://doi.org/10.1145/2049662.2049663
[9]
Timothy A. Davis and Yifan Hu. 2011. The University of Florida Sparse Matrix Collection. ACM Trans. Math. Softw., 38, 1 (2011), Article 1, dec, 25 pages. issn:0098-3500 https://doi.org/10.1145/2049662.2049663
[10]
Ahmed E. Helal, Jan Laukemann, Fabio Checconi, Jesmin Jahan Tithi, Teresa Ranadive, Fabrizio Petrini, and Jeewhan Choi. 2021. ALTO: Adaptive Linearized Storage of Sparse Tensors. In Proceedings of the ACM International Conference on Supercomputing (ICS ’21). Association for Computing Machinery, New York, NY, USA. 404–416. isbn:9781450383356 https://doi.org/10.1145/3447818.3461703
[11]
Wayne Kelly, Vadim Maslov, William Pugh, Evan Rosser, Tatiana Shpeisman, and David Wonnacott. 1995. The Omega Library Interface Guide. University of Maryland at College Park.
[12]
Fredrik Kjolstad, Shoaib Kamil, Stephen Chou, David Lugato, and Saman Amarasinghe. 2017. The Tensor Algebra Compiler. Proc. ACM Program. Lang., 1, OOPSLA (2017), Oct., 77:1–77:29.
[13]
Tristan Knoth, Di Wang, Nadia Polikarpova, and Jan Hoffmann. 2019. Resource-Guided Program Synthesis. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2019). Association for Computing Machinery, New York, NY, USA. 253–268. isbn:9781450367127 https://doi.org/10.1145/3314221.3314602
[14]
Jiajia Li, Jimeng Sun, and Richard Vuduc. 2018. HiCOO: Hierarchical Storage of Sparse Tensors. In Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis (SC ’18). IEEE Press, Piscataway, NJ, USA. 19:1–19:15.
[15]
Jiajia Li, Bora Uçar, Ümit V. Çatalyürek, Jimeng Sun, Kevin Barker, and Richard Vuduc. 2019. Efficient and Effective Sparse Tensor Reordering. In Proceedings of the ACM International Conference on Supercomputing (ICS ’19). Association for Computing Machinery, New York, NY, USA. 227–237. isbn:9781450360791 https://doi.org/10.1145/3330345.3330366
[16]
Mahdi Soltan Mohammadi, Kazem Cheshmi, Maryam Mehri Dehnavi, Anand Venkat, Tomofumi Yuki, and Michelle Mills Strout. 2019. Extending Index-Array Properties for Data Dependence Analysis. In Languages and Compilers for Parallel Computing, Mary Hall and Hari Sundar (Eds.). Springer International Publishing, Cham. 78–93. isbn:978-3-030-34627-0
[17]
Payal Nandy, Mary W. Hall, Eddie C. Davis, Catherine Mills Olschanowsky, Mahdi Soltan Mohammadi, Wei He, and Michelle Mills Strout. 2018. Abstractions for Specifying Sparse Matrix Data Transformations.
[18]
Tobi Popoola, Ravi Shankar, Anna Rift, Shivani Singh, Eddie C. Davis, Michelle Mills Strout, and Catherine Olschanowsky. 2021. An Object-Oriented Interface to The Sparse Polyhedral Library. In 2021 IEEE 45th Annual Computers, Software, and Applications Conference (COMPSAC). 1825–1831. https://doi.org/10.1109/COMPSAC51774.2021.00275
[19]
Tobi Popoola, Tuowen Zhao, Aaron St. George, Kalyan Bhetwal, Michelle Mills Strout, Mary Hall, and Catherine Olschanowsky. 2023. Reproduction Package for Code Synthesis for Sparse Tensor Format Conversion and Optimization. March, https://doi.org/10.1145/3554347
[20]
William Pugh and Tatiana Shpeisman. 1998. SIPR: A New Framework for Generating Efficient Code for Sparse Matrix Computations. In Proceedings of the Eleventh International Workshop on Languages and Compilers for Parallel Computing. Chapel Hill, North Carolina.
[21]
Hongbo Rong, Jongsoo Park, Lingxiang Xiang, Todd A. Anderson, and Mikhail Smelyanskiy. 2016. Sparso: Context-driven optimizations of sparse linear algebra. In 2016 International Conference on Parallel Architecture and Compilation Techniques (PACT). 247–259. https://doi.org/10.1145/2967938.2967943
[22]
Yousef Saad. 1994. SPARSKIT: a basic tool kit for sparse matrix computations.
[23]
Xujie Si, Woosuk Lee, Richard Zhang, Aws Albarghouthi, Paraschos Koutris, and Mayur Naik. 2018. Syntax-Guided Synthesis of Datalog Programs. In Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE 2018). Association for Computing Machinery, New York, NY, USA. 515–527. isbn:9781450355735 https://doi.org/10.1145/3236024.3236034
[24]
Armando Solar-Lezama. 2009. The Sketching Approach to Program Synthesis. In Proceedings of the 7th Asian Symposium on Programming Languages and Systems (APLAS ’09). Springer-Verlag, Berlin, Heidelberg. 4–13. isbn:9783642106712 https://doi.org/10.1007/978-3-642-10672-9_3
[25]
Armando Solar-Lezama, Liviu Tancau, Rastislav Bodik, Sanjit Seshia, and Vijay Saraswat. 2006. Combinatorial Sketching for Finite Programs. In Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS XII). Association for Computing Machinery, New York, NY, USA. 404–415. isbn:1595934510 https://doi.org/10.1145/1168857.1168907
[26]
Michelle Mills Strout, Geri Georg, and Catherine Olschanowsky. 2013. Set and relation manipulation for the Sparse Polyhedral Framework. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7760 LNCS (2013), 61–75. isbn:9783642376573 issn:03029743 https://doi.org/10.1007/978-3-642-37658-0_5
[27]
Anand Venkat, Mary Hall, and Michelle Strout. 2015. Loop and Data Transformations for Sparse Matrix Code. SIGPLAN Not., 50, 6 (2015), jun, 521–532. issn:0362-1340 https://doi.org/10.1145/2813885.2738003
[28]
Anand Venkat, Manu Shantharam, Mary Hall, and Michelle Mills Strout. 2014. Non-affine Extensions to Polyhedral Code Generation. In Proceedings of Annual IEEE/ACM International Symposium on Code Generation and Optimization (CGO ’14).
[29]
Endong Wang, Qing Zhang, Bo Shen, Guangyong Zhang, Xiaowei Lu, Qing Wu, and Yajuan Wang. 2014. Intel math kernel library. In High-Performance Computing on the Intel® Xeon Phi. Springer, 167–188.
Index Terms
- Code Synthesis for Sparse Tensor Format Conversion and Optimization
Recommendations
Polyhedral Specification and Code Generation of Sparse Tensor Contraction with Co-iteration
This article presents a code generator for sparse tensor contraction computations. It leverages a mathematical representation of loop nest computations in the sparse polyhedral framework (SPF), which extends the polyhedral model to support non-affine ...
Automatic generation of efficient sparse tensor format conversion routines
PLDI 2020: Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and ImplementationThis paper shows how to generate code that efficiently converts sparse tensors between disparate storage formats (data layouts) such as CSR, DIA, ELL, and many others. We decompose sparse tensor conversion into three logical phases: coordinate remapping,...
Format abstraction for sparse tensor algebra compilers
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 ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
February 2023
262 pages
ISBN:9798400701016
DOI:10.1145/3579990
- General Chair:
- Christophe Dubach,
- Program Chairs:
- Derek Bruening,
- Ben Hardekopf
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 22 February 2023
Check for updates
Badges
Author Tags
Qualifiers
- Research-article
Conference
CGO '23: 21st ACM/IEEE International Symposium on Code Generation and Optimization
February 25 - March 1, 2023
QC, Montréal, Canada
Acceptance Rates
Overall Acceptance Rate 312 of 1,061 submissions, 29%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 347Total Downloads
- Downloads (Last 12 months)126
- Downloads (Last 6 weeks)12
Reflects downloads up to 18 Nov 2024
Other Metrics
Citations
Cited By
View all- Gladshtein VZhao QAhrens WAmarasinghe SSergey I(2024)Mechanised Hypersafety Proofs about Structured DataProceedings of the ACM on Programming Languages10.1145/36564038:PLDI(647-670)Online publication date: 20-Jun-2024
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in