.png){kind=icon}
.png){kind=icon}
Return
Accelerating Sparse Algebra with Program Synthesis
.png){kind=icon}
PRE
AI
DOI：10.1145/3771775.3786281.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Linear algebra libraries and tensor domain-specific languages are able to deliver high performance for modern scientific and machine learning workloads. While there has been recent work in automatically translating legacy software to use these libraries/DSLs using pattern matching and program lifting, this has been largely limited to dense linear algebra. This paper tackles the more challenging problem of porting legacy sparse linear algebra code to libraries and DSLs. It exploits the power of large language models to predict a sketch of the solution and then uses type-based program synthesis to search the space of possible code to target parameter bindings. We implement this in a tool named SLEB (Sparse LiftEr with Binding) and evaluate it on a large set of benchmarks and real-world datasets, comparing against two state-of-the-art compiler techniques, LiLAC and SpEQ; and GPT 4.o. Overall, we lift 94% of programs compared to 11%, 17%, and 48% for LiLAC, SpEQ, and GPT 4.o respectively. This delivers a geomean speedup of 2.6 Chi and 7.2 Chi on a CPU and GPU platform, respectively.
Keywords:
Sparse
Program Lifting
Synthesis
TACO
Tensor Algebra
Journal
P
IF:
0
Papers:
18
Citations:
0