Spatula: A Hardware Accelerator for Sparse Matrix Factorization
Spatula: A Hardware Accelerator for Sparse Matrix Factorization
复制标题
DOI：
10.1145/3613424.3623783
复制
发表时间：
2023-10
期刊：
影响因子：
--
通讯作者：
Axel Feldmann;Daniel Sanchez
中科院分区：
文献类型：
--
作者：
Axel Feldmann;Daniel Sanchez
求解稀疏线性方程组是许多科学和工程问题的关键组成部分，如模拟物理系统。稀疏矩阵分解在这些求解器中占主导地位。高效的因式分解算法有两个关键特性，这使得它们对现有架构具有挑战性：它们由结构化和计算密集型的小任务组成，稀疏性导致这些任务之间的长数据依赖链。数据依赖性使得GPU变得困难，而CPU和先前的稀疏线性代数加速器也受到低计算吞吐量的影响。Spatula硬件将以高吞吐量执行结构化任务的脉动处理元件与处理具有挑战性的数据依赖性的灵活调度器相结合。Spatula实现了一种新颖的调度算法，避免了停顿和负载不平衡，同时减少了数据移动，实现了高计算利用率。因此，Spatula在各种矩阵上的性能比运行最先进的稀疏Cholesky和LU分解实现的GPU高出gmean 47倍，在一些具有挑战性的矩阵上高出数千倍。
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.