Designing Hardware Accelerators for Solving Sparse Linear Systems

Solving sparse linear systems is a key primitive that sits at the heart of many important numeric algorithms. Because of this primitive’s importance, algorithm designers have spent many decades optimizing linear solvers for high performance hardware. However, despite their efforts, existing hardware has let them down. State-of-the-art linear solvers often utilize < 1% of available compute throughput on existing architectures such as CPUs and GPUs. There are many different algorithms used to solve sparse linear systems. These algorithms are diverse and often have very different computational bottlenecks. These include low arithmetic intensity, fine-grained parallellism, tight dependences, and sparsity-induced load imbalance. This thesis studies the problem of designing hardware accelerators for sparse linear solvers. We propose three novel architectures that explore different parts of the design space. The accelerators exploit static sparsity as the basis of novel hardware-software co-designed scheduling approaches. First, we introduce Spatula, an architecture designed to accelerate direct solvers. Then, we propose Azul, a hardware accelerator targeted at iterative solvers. Taken together, Spatula and Azul demonstrate significant speedups on both of the main classes of sparse linear solver algorithms. Finally, to show that our techniques are useful for end-to-end applications, we present Ōmeteōtl, an accelerator targeted at applications that use iterative solvers in their inner loop. Ōmeteōtl also shows that the techniques in this thesis generalize to sparse matrix computations beyond linear solvers. These accelerators deliver order-of-magnitude speedups over state-of-the-art GPU baselines, achieving > 100× speedups on many inputs.

Name thesis:degree_name

Doctoral

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2025

Author dc:creator

• Feldmann, Axel

Advisor dc:contributor.advisor

• Sanchez, Daniel

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright retained by author(s)

Licence dc:rights.uri

• https://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/164057

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/164057