A System to Exploit Symmetry in Common Tensor Kernels
Symmetric tensors arise naturally in many domains including linear algebra, statistics, physics, chemistry, and graph theory. Symmetry arises through both mathematical properties and scientific phenomena. Taking advantage of symmetry in matrices saves a factor of two, but taking advantage of symmetr...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2024
|
| Online Access: | https://hdl.handle.net/1721.1/156832 |
| _version_ | 1811092685729038336 |
|---|---|
| author | Patel, Radha |
| author2 | Amarasinghe, Saman |
| author_facet | Amarasinghe, Saman Patel, Radha |
| author_sort | Patel, Radha |
| collection | MIT |
| description | Symmetric tensors arise naturally in many domains including linear algebra, statistics, physics, chemistry, and graph theory. Symmetry arises through both mathematical properties and scientific phenomena. Taking advantage of symmetry in matrices saves a factor of two, but taking advantage of symmetry in a tensor of order n can save a factor of n! in memory accesses and operations. However, implementing this symmetry by hand significantly increases the complexity; for instance, leveraging symmetry in 2D BLAS nearly doubles the implementation burden, and this burden escalates further in the case of higher-dimensional tensors. Existing compilers to compute those kernels either do not take advantage of symmetry or do not take advantage of it to the extent possible. My thesis will identify and categorize methods to exploit symmetry in common and uncommon tensor kernels. We will depict a methodology to systematically generate and optimize symmetric code and will present a compiler in Julia that automates this process. Our symmetric implementation demonstrates significant speedups ranging from 1.36x for SSYMV to 7.95x for a 4-dimensional MTTKRP over the naive implementation of these kernels. |
| first_indexed | 2024-09-23T15:22:13Z |
| format | Thesis |
| id | mit-1721.1/156832 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T15:22:13Z |
| publishDate | 2024 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1568322024-09-17T03:10:02Z A System to Exploit Symmetry in Common Tensor Kernels Patel, Radha Amarasinghe, Saman Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Symmetric tensors arise naturally in many domains including linear algebra, statistics, physics, chemistry, and graph theory. Symmetry arises through both mathematical properties and scientific phenomena. Taking advantage of symmetry in matrices saves a factor of two, but taking advantage of symmetry in a tensor of order n can save a factor of n! in memory accesses and operations. However, implementing this symmetry by hand significantly increases the complexity; for instance, leveraging symmetry in 2D BLAS nearly doubles the implementation burden, and this burden escalates further in the case of higher-dimensional tensors. Existing compilers to compute those kernels either do not take advantage of symmetry or do not take advantage of it to the extent possible. My thesis will identify and categorize methods to exploit symmetry in common and uncommon tensor kernels. We will depict a methodology to systematically generate and optimize symmetric code and will present a compiler in Julia that automates this process. Our symmetric implementation demonstrates significant speedups ranging from 1.36x for SSYMV to 7.95x for a 4-dimensional MTTKRP over the naive implementation of these kernels. M.Eng. 2024-09-16T13:51:51Z 2024-09-16T13:51:51Z 2024-05 2024-07-11T14:37:23.465Z Thesis https://hdl.handle.net/1721.1/156832 Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) Copyright retained by author(s) https://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Patel, Radha A System to Exploit Symmetry in Common Tensor Kernels |
| title | A System to Exploit Symmetry in Common Tensor Kernels |
| title_full | A System to Exploit Symmetry in Common Tensor Kernels |
| title_fullStr | A System to Exploit Symmetry in Common Tensor Kernels |
| title_full_unstemmed | A System to Exploit Symmetry in Common Tensor Kernels |
| title_short | A System to Exploit Symmetry in Common Tensor Kernels |
| title_sort | system to exploit symmetry in common tensor kernels |
| url | https://hdl.handle.net/1721.1/156832 |
| work_keys_str_mv | AT patelradha asystemtoexploitsymmetryincommontensorkernels AT patelradha systemtoexploitsymmetryincommontensorkernels |