Accelerating Sparse Algebra with Program Synthesis

doi:10.1145/3771775.3786281

2026-01-01

PRE

José Wesley de Souza Magalhães *

Michael F. P. O’Boyle

DOI：10.1145/3771775.3786281

原文链接

原文求助

摘要

En 中文

线性代数库和张量领域专用语言能够为现代科学和机器学习工作负载提供高性能。尽管近期已有工作通过模式匹配和程序提升自动将遗留软件翻译为使用这些库/DSL，但这在很大程度上仅限于稠密线性代数。本文解决了更困难的遗留稀疏线性代数代码移植到库和DSL的问题。它利用大语言模型预测解决方案的草图，然后使用基于类型的程序合成搜索可能的代码空间以针对参数绑定。我们实现了一个名为SLEB（带绑定的稀疏提升器）的工具，并在大量基准测试和真实数据集上对其进行评估，将其与两种最先进的编译器技术LiLAC和SpEQ以及GPT 4.o进行比较。总体而言，我们提升了94%的程序，而LiLAC、SpEQ和GPT 4.o分别提升了11%、17%和48%。这分别在CPU和GPU平台上实现了2.6倍和7.2倍的平均加速。

Keyword:

Sparse

Program Lifting

Synthesis

TACO

Tensor Algebra

期刊

PROCEEDINGS OF THE 35TH ACM SIGPLAN INTERNATIONAL CONFERENCE ON COMPILER CONSTRUCTION, CC 2026

IF:

论文数:

被引数:

机构

University of Edinburgh

学者数:

5.2W

论文数: 4.6W

被引数: 71

引用论文

Automatic Matching of Legacy Code to Heterogeneous APIs

Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems

IF0

2018-03-19

OAAI

Philip Ginsbach; Toomas Remmelg; Michel Steuwer; Bruno Bodin; Christophe Dubach; Michael F. P. O'Boyle

SpEQ: Translation of Sparse Codes using Equivalences

Proceedings of the ACM on Programming Languages

IF0

2024-06-20

PREAI

Laird,Avery; Liu,Bangtian; Bjørner,Nikolaj; Dehnavi,Maryam Mehri

IF0

PREAI

KernelFaRer

ACM Transactions on Architecture and Code Optimization

IF0

2021-06-28

OAAI

João P. L. De Carvalho; Braedy Kuzma; Ivan Korostelev; José Nelson Amaral; Christopher Barton; José Moreira; Guido Araujo

PASTA: a parallel sparse tensor algorithm benchmark suite

CCF Transactions on High Performance Computing

IF0

2019-08-05

PREAI

Jiajia Li; Yuchen Ma; Xiaolong Wu; Ang Li; Kevin Barker

WACO: Learning Workload-Aware Co-optimization of the Format and Schedule of a Sparse Tensor Program WACO：学习工作负载感知的稀疏张量程序格式和调度协同优化

Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2

IF0

2023-01-30

OAAI

Jaeyeon Won; Charith Mendis; Joel S. Emer; Saman Amarasinghe

Ginkgo: A Modern Linear Operator Algebra Framework for High Performance Computing

ACM Transactions on Mathematical Software

IF0

2022-02-16

OAAI

Hartwig Anzt; Terry Cojean; Goran Flegar; Fritz Göbel; Thomas Grützmacher; Pratik Nayak; Tobias Ribizel; Yuhsiang Mike Tsai; Enrique S. Quintana-Ortí

The tensor algebra compiler 张量代数编译器

Proceedings of the ACM on Programming Languages

IF0

2017-10-12

OAAI

Fredrik Kjolstad; Shoaib Kamil; Stephen Chou; David Lugato; Saman Amarasinghe

The NAS Parallel Benchmarks for evaluating C plus plus parallel programming frameworks on shared-memory architectures 用于评估共享内存架构上的C plus plus并行编程框架的NAS并行基准

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE

IF6.1

2021-12-01

PREAI

Loff, Junior; Griebler, Dalvan; Mencagli, Gabriele; Araujo, Gabriell; Torquati, Massimo; Danelutto, Marco; Fernandes, Luiz Gustavo

SuperLU

Encyclopedia of Parallel Computing

IF0

2011-01-01

PREAI

Dongarra,Jack; Luszczek,Piotr; Wolf,Felix; Träff,Jesper Larsson; Quinton,Patrice; Hellwagner,Hermann; Fränzle,Martin; Lengauer,Christian; Ceze,Luis H; Hiraki,Kei; Riesen,Rolf; Maccabe,Arthur B.; Feo,John; Madduri,Kamesh; Risset,Tanguy; Khan,Maleq; Kumar,V. S. Anil; Marathe,Madha V.; Stretz,Paula E.; Dwarkadas,Sandhya; Kalé,Laxmikant V.; Solomonik,Edgar; Bader,Michael; Bungartz,Hans-Joachim; Mehl,Miriam; Huckle,Thomas; Sedlacek,Matous; Bader,David A; Cong,Guojing; Gupta,Anshul; Müller,Matthias; Whitney,Brian; Henschel,Robert; Kumaran,Kalyan; Torrellas,Josep; Rauchwerger,Lawrence; Polizzi,Eric; Püschel,Markus; Franchetti,Franz; Voronenko,Yevgen; Darema,Frederica; Newton,Ryan; Ghoting,Amol; Makarychev,Konstantin; Li,Xiaoye Sherry; Demmel,James; Gilbert,John; Grigori,Laura; Shao,Meiyue; Hwu,Wen mei; Bader,David A.; Cong,Guojing; Flich,José; Yalamanchili,Sudhakar; Scott,Michael L.; Zola,Jaroslaw; Aluru,Srinivas; Aluru,Srinivas; Reinders,James R.

查看更多内容