Indexed Streams: A Formal Intermediate Representation for Fused Contraction Programs
Indexed Streams: A Formal Intermediate Representation for Fused Contraction Programs
复制标题
DOI：
10.1145/3591268
复制
发表时间：
2023-06
影响因子：
--
通讯作者：
S. Kovach;Praneeth Kolichala;Tiancheng Gu;Fredrik Kjolstad
中科院分区：
文献类型：
--
作者：
S. Kovach;Praneeth Kolichala;Tiancheng Gu;Fredrik Kjolstad
我们介绍了索引流，这是一种正式的操作模型和中间表示，描述了融合的收缩语言的执行，该融合既包含稀疏张量代数和关系代数。我们证明，索引流模型相对于功能语义是正确的。我们还为使用索引流作为中间表示的收缩表达式开发了一个编译器。编译器仅是540行代码，但我们表明其性能可以匹配稀疏张量代数的炸玉米饼编译器，以及用于关系代数的Sqlite和Sqlite和DuckDB查询处理库。
We introduce indexed streams, a formal operational model and intermediate representation that describes the fused execution of a contraction language that encompasses both sparse tensor algebra and relational algebra. We prove that the indexed stream model is correct with respect to a functional semantics. We also develop a compiler for contraction expressions that uses indexed streams as an intermediate representation. The compiler is only 540 lines of code, but we show that its performance can match both the TACO compiler for sparse tensor algebra and the SQLite and DuckDB query processing libraries for relational algebra.