异构并行系统上负载感知的新型稀疏算法性能优化研究

Emerging sparse algorithms (ESP algorithms) are the core components in big data and machine learning. Recently, implementing ESP algorithms based on core sparse matrix primitives (like SpMV and SpGEMM) is proposed. This method has high flexibility as a large number of ESP algorithms can be built by using a few core primitives. However, we point out that the method has limitations on performance (there is a ninja performance gap compared to the hand-optimized implementation) and hardware support (there are no implementations that support many-core processors and heterogeneous systems at present). Thus, it is hard to efficiently support future scenarios where a large spectrum of ESP algorithms running on various heterogeneous systems. Therefore, this work aims to devise efficient performance optimization methods for ESP algorithms on heterogeneous systems. Based on a workload-aware approach, we divide the research work into application, algorithm, and hardware layers to explore key research questions, which are workload characterization, optimization model design, and workload balancing on heterogeneous systems. By following such a top-down approach, we are able to distill key performance optimization techniques for ESP algorithms. Our work will overcome the limitation of primitive-based ESP algorithms, and provide a solid computing building block for big data and machine learning.

新型稀疏算法（ESP算法）是大数据与机器学习应用的核心组成部分。近年来研究人员提出基于核心稀疏矩阵算子（SpMV、SpGEMM等）实现ESP算法的方法。这种方法具有很高的灵活性，通过调用少量核心算子就可以构建大量ESP算法，然而我们指出这种方法目前在性能上（与手工优化存在差距）和硬件支持上（尚没有支持异构并行系统的实现）存在局限性，不能有效支持未来大量不同类型ESP算法在不同层次异构并行系统上运行的应用场景。因此本课题以面向异构并行系统的ESP算法高效性能优化为目标，将研究内容划分为应用层、算法层、硬件层三个层次，基于负载感知抽象出关键性的研究问题，即ESP算法负载特征分析、算法优化模型和面向异构并行系统的负载均衡模型，通过这样自顶向下层次式的研究，提炼出针对ESP算法的性能优化关键技术。本课题的研究成果将有效解决当前基于算子实现ESP算法的局限性，为大数据和机器学习提供有力的计算支持。

随着大数据与机器学习的兴起，面向图处理与智能计算的新型稀疏算法优化成为集算法、并行计算和体系结构交叉融合的新兴研究领域。本项目面向异构并行系统研究新型稀疏算法性能优化关键技术，主要包括：（1）构建了一套面向异构并行系统的新型稀疏算法测试程序集，提出了一套运行时算法负载描述和剖析技术，根据运行时获取的算法负载特征，综合运用一系列先进优化方法提高了算法性能；（2）针对新型稀疏应用对超越函数性能需求的提高，分段量化评估了当前超越函数的性能和精度，利用国产异构处理器向量部件，提出了基于操作数特征的向量化优化技术；（3）研究了新型稀疏算法中典型超越函数的软硬件协同优化技术，从软件层面抽象出影响性能的核心计算和访存片段，指导硬件定制专用加速指令并进行指令级优化，为新型稀疏算法充分发挥处理器计算性能提供了有力支持。本项目的研究成果将对下一代国产异构处理器的性能优化研究起到技术探索和预先研究的作用。