论文标题
自动生成有效的稀疏张量格式转换例程
Automatic Generation of Efficient Sparse Tensor Format Conversion Routines
论文作者
论文摘要
本文展示了如何生成有效转换不同量的稀疏张量的代码（数据布局），例如CSR，DIA，ELL等。我们将稀疏张量转换分解为三个逻辑阶段：坐标重新映射，分析和组装。然后，我们开发了一种语言，可以精确地描述不同格式如何组合在一起并在内存中订购张量的nonzeros。这使得编译器发射代码在格式之间转换时会进行复杂的非Zeros的复杂删除。我们还开发了一种可以提取有关稀疏张量的统计信息的查询语言，并展示了如何发出计算此类查询的有效分析代码。最后，我们定义了一个抽象接口，该界面捕获了如何有效地组装用于张张量的特定统计信息的数据结构。不同的格式可以实现此通用界面，从而使编译器发射优化的稀疏张量转换代码，以适用于许多格式的任意组合，而无需对任何特定组合进行硬编码。 我们的评估表明，该技术生成了稀疏的张量转换例程，其性能在1.00至2.01 $ \ times $ \ times $ $ \ times $ $ $ $ $ $ $ $ $ $ $ $ $ $ $的Sparskit和Intel MKL中，这是两个流行的稀疏线性代数库。通过发出避免实现临时性的代码，这两个库都需要许多源和目标格式组合，我们的技术将这些库的表现优于1.78至4.01 $ \ times $ \ times $ \ times $ csc/coo to dia/ell conversion。
This paper shows how to generate code that efficiently converts sparse tensors between disparate storage formats (data layouts) such as CSR, DIA, ELL, and many others. We decompose sparse tensor conversion into three logical phases: coordinate remapping, analysis, and assembly. We then develop a language that precisely describes how different formats group together and order a tensor's nonzeros in memory. This lets a compiler emit code that performs complex remappings of nonzeros when converting between formats. We also develop a query language that can extract statistics about sparse tensors, and we show how to emit efficient analysis code that computes such queries. Finally, we define an abstract interface that captures how data structures for storing a tensor can be efficiently assembled given specific statistics about the tensor. Disparate formats can implement this common interface, thus letting a compiler emit optimized sparse tensor conversion code for arbitrary combinations of many formats without hard-coding for any specific combination. Our evaluation shows that the technique generates sparse tensor conversion routines with performance between 1.00 and 2.01$\times$ that of hand-optimized versions in SPARSKIT and Intel MKL, two popular sparse linear algebra libraries. And by emitting code that avoids materializing temporaries, which both libraries need for many combinations of source and target formats, our technique outperforms those libraries by 1.78 to 4.01$\times$ for CSC/COO to DIA/ELL conversion.
