Sparse Matrix-Vector multiplication (SpMV) is an essential computational kernel in many application scenarios. Tens of sparse matrix formats and implementations have been proposed to compress the memory storage and speed up SpMV performance. We develop AlphaSparse, a superset of all existing works that goes beyond the scope of human-designed format(s) and implementation(s). AlphaSparse automatically \emph{creates novel machine-designed formats and SpMV kernel implementations} entirely from the knowledge of input sparsity patterns and hardware architectures. Based on our proposed Operator Graph that expresses the path of SpMV format and kernel design, AlphaSparse consists of three main components: Designer, Format \& Kernel Generator, and Search Engine. It takes an arbitrary sparse matrix as input while outputs the performant machine-designed format and SpMV implementation. By extensively evaluating 843 matrices from SuiteSparse Matrix Collection, AlphaSparse achieves significant performance improvement by 3.2$\times$ on average compared to five state-of-the-art artificial formats and 1.5$\times$ on average (up to 2.7$\times$) over the up-to-date implementation of traditional auto-tuning philosophy.
翻译:在许多应用情景中,剖析矩阵- vector 倍增( SpMV) 是一个不可或缺的计算内核。 已经提出了十种稀薄的矩阵格式和实施模式, 以压缩存储存储存储存储和加速 SpMV 性能。 我们开发了阿尔法Sparse, 这是超出人类设计格式和执行范围的所有现有作品的超级集。 阿尔法Sparse 自动创建了新机器设计的格式和 SpMV内核实施 。 阿尔法Sparse 完全基于对输入空间模式和硬件结构的知识 。 根据我们提议的显示 SpMV 格式和内核设计路径的运算符图, 阿尔法Sparse 由三个主要组成部分组成: 设计器、 格式 ⁇ 核心生成器 和搜索引擎。 将任意的稀释矩阵作为输入, 输出性能机器设计格式和SpmV 执行。 通过对 ASomSparse 矩阵收集的843 矩阵进行广泛的评估, AlphaSparse 实现显著的性能改进。 320\ times 平均改进了3.2美元,, 而不是五个最先进的人造型格式和1.5\timeal- distimemetimetimetime- daltime- $)。