Swift: High-Performance Sparse Tensor Contraction for Scientific Applications
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916437630648320 |
|---|---|
| author | Ensinger, Andrew Kulp, Gabriel Agostinelli, Victor Lyakhov, Dennis Chen, Lizhong |
| author_facet | Ensinger, Andrew Kulp, Gabriel Agostinelli, Victor Lyakhov, Dennis Chen, Lizhong |
| contents | In scientific fields such as quantum computing, physics, chemistry, and machine learning, high dimensional data are typically represented using sparse tensors. Tensor contraction is a popular operation on tensors to exploit meaning or alter the input tensors. Tensor contraction is, however, computationally expensive and grows quadratically with the number of elements. For this reason, specialized algorithms have been created to only operate on the nonzero elements. Current sparse tensor contraction algorithms utilize sub-optimal data structures that perform unnecessary computations which increase execution time and the overall time complexity. We propose Swift, a novel algorithm for sparse tensor contraction that replaces the costly sorting with more efficient grouping, utilizes better data structures to represent tensors, and employs more memory-friendly hash table implementation. Swift is evaluated against the state-of-the-art sparse tensor contraction algorithm, demonstrating up to 20x speedup in various test cases and being able to handle imbalanced input tensors significantly better. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_10094 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Swift: High-Performance Sparse Tensor Contraction for Scientific Applications Ensinger, Andrew Kulp, Gabriel Agostinelli, Victor Lyakhov, Dennis Chen, Lizhong Data Structures and Algorithms In scientific fields such as quantum computing, physics, chemistry, and machine learning, high dimensional data are typically represented using sparse tensors. Tensor contraction is a popular operation on tensors to exploit meaning or alter the input tensors. Tensor contraction is, however, computationally expensive and grows quadratically with the number of elements. For this reason, specialized algorithms have been created to only operate on the nonzero elements. Current sparse tensor contraction algorithms utilize sub-optimal data structures that perform unnecessary computations which increase execution time and the overall time complexity. We propose Swift, a novel algorithm for sparse tensor contraction that replaces the costly sorting with more efficient grouping, utilizes better data structures to represent tensors, and employs more memory-friendly hash table implementation. Swift is evaluated against the state-of-the-art sparse tensor contraction algorithm, demonstrating up to 20x speedup in various test cases and being able to handle imbalanced input tensors significantly better. |
| title | Swift: High-Performance Sparse Tensor Contraction for Scientific Applications |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.10094 |