Spatula: A Hardware Accelerator for Sparse Matrix Factorization
Solving sparse systems of linear equations is a crucial component in many science and engineering problems, like simulating physical systems. Sparse matrix factorization dominates a large class of these solvers. Efficient factorization algorithms have two key properties that make them challenging fo...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
ACM|56th Annual IEEE/ACM International Symposium on Microarchitecture
2024
|
| Online Access: | https://hdl.handle.net/1721.1/153276 |
| _version_ | 1811071864855855104 |
|---|---|
| author | Feldmann, Axel Sanchez, Daniel |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Feldmann, Axel Sanchez, Daniel |
| author_sort | Feldmann, Axel |
| collection | MIT |
| description | Solving sparse systems of linear equations is a crucial component in many science and engineering problems, like simulating physical systems. Sparse matrix factorization dominates a large class of these solvers. Efficient factorization algorithms have two key properties that make them challenging for existing architectures: they consist of small tasks that are structured and compute-intensive, and sparsity induces long chains of data dependences among these tasks. Data dependences make GPUs struggle, while CPUs and prior sparse linear algebra accelerators also suffer from low compute throughput.
We present Spatula, an architecture for accelerating sparse matrix factorization algorithms. Spatula hardware combines systolic processing elements that execute structured tasks at high throughput with a flexible scheduler that handles challenging data dependences. Spatula enables a novel scheduling algorithm that avoids stalls and load imbalance while reducing data movement, achieving high compute utilization. As a result, Spatula outperforms a GPU running the state-of-the-art sparse Cholesky and LU factorization implementations by gmean 47 × across a wide range of matrices, and by up to thousands of times on some challenging matrices. |
| first_indexed | 2024-09-23T08:57:15Z |
| format | Article |
| id | mit-1721.1/153276 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:57:15Z |
| publishDate | 2024 |
| publisher | ACM|56th Annual IEEE/ACM International Symposium on Microarchitecture |
| record_format | dspace |
| spelling | mit-1721.1/1532762024-07-11T18:55:55Z Spatula: A Hardware Accelerator for Sparse Matrix Factorization Feldmann, Axel Sanchez, Daniel Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Solving sparse systems of linear equations is a crucial component in many science and engineering problems, like simulating physical systems. Sparse matrix factorization dominates a large class of these solvers. Efficient factorization algorithms have two key properties that make them challenging for existing architectures: they consist of small tasks that are structured and compute-intensive, and sparsity induces long chains of data dependences among these tasks. Data dependences make GPUs struggle, while CPUs and prior sparse linear algebra accelerators also suffer from low compute throughput. We present Spatula, an architecture for accelerating sparse matrix factorization algorithms. Spatula hardware combines systolic processing elements that execute structured tasks at high throughput with a flexible scheduler that handles challenging data dependences. Spatula enables a novel scheduling algorithm that avoids stalls and load imbalance while reducing data movement, achieving high compute utilization. As a result, Spatula outperforms a GPU running the state-of-the-art sparse Cholesky and LU factorization implementations by gmean 47 × across a wide range of matrices, and by up to thousands of times on some challenging matrices. 2024-01-03T20:32:13Z 2024-01-03T20:32:13Z 2023-10-28 2024-01-01T08:48:22Z Article http://purl.org/eprint/type/ConferencePaper 979-8-4007-0329-4 https://hdl.handle.net/1721.1/153276 Feldmann, Axel and Sanchez, Daniel. 2023. "Spatula: A Hardware Accelerator for Sparse Matrix Factorization." PUBLISHER_CC PUBLISHER_CC en https://doi.org/10.1145/3613424.3623783 Creative Commons Attribution-Share Alike https://creativecommons.org/licenses/by-sa/4.0/ The author(s) application/pdf ACM|56th Annual IEEE/ACM International Symposium on Microarchitecture |
| spellingShingle | Feldmann, Axel Sanchez, Daniel Spatula: A Hardware Accelerator for Sparse Matrix Factorization |
| title | Spatula: A Hardware Accelerator for Sparse Matrix Factorization |
| title_full | Spatula: A Hardware Accelerator for Sparse Matrix Factorization |
| title_fullStr | Spatula: A Hardware Accelerator for Sparse Matrix Factorization |
| title_full_unstemmed | Spatula: A Hardware Accelerator for Sparse Matrix Factorization |
| title_short | Spatula: A Hardware Accelerator for Sparse Matrix Factorization |
| title_sort | spatula a hardware accelerator for sparse matrix factorization |
| url | https://hdl.handle.net/1721.1/153276 |
| work_keys_str_mv | AT feldmannaxel spatulaahardwareacceleratorforsparsematrixfactorization AT sanchezdaniel spatulaahardwareacceleratorforsparsematrixfactorization |