面向稀疏矩阵和图计算的自适应优化方法研究

As multi-core becomes the mainstream of computer architecture, the factors influencing the efficiency of parallel programs increase in count and complexity. Moreover, the more and more highlighted power problem demands energy efficiency improvement the same important as parallel efficiency increasing. Considering the importance of sparse matrix and graph operations in emerging high performance computational applications and the increasing influence of self-adaptive method in performance portability, the project focuses on self-adaptive methods of parallel sparse matrices and graph programs on multi-core computer system. Three major items of the project are shown as follows. Firstly, due to the poor parallel scalability of graph algorithms, we study large-scale graph algorithms of good scalability based on sparse matrix primitives, to lay the foundation for realizing integrated optimization framework of sparse matrix and graph algorithms. Additionally, to improve the performance of sparse matrix operations on multi-core architecture, we investigate auto-tuning methods which combine algorithm characteristics with architecture features, pursuing the best performance as well as portability. Finally, in the light of the problems of parallelism and energy consumption during program runtime on parallel systems, we research into self-adaptive dynamic optimization strategy, making it possible to achieve high parallel efficiency and power efficiency on diverse multi-core systems. Through the project we will be able to provide portable high performance library and optimization methods for applications with the core of sparse matrix and graph operations.

随着多核成为计算机体系结构的主流，影响并行程序执行效率的因素愈加复杂多样，而日益突出的能耗问题迫使多核系统上优化并行程序需要同时提高并行效率和能耗效率。考虑到稀疏矩阵和图计算在传统和新兴高性能计算应用中的重要性，同时自适应优化技术在获得性能可移植性方面将发挥日益重要的作用。本项目拟研究多核系统上稀疏矩阵和图计算并行程序自适应优化方法的三个重要内容：1）针对图算法并行扩展性差的问题，研究基于稀疏矩阵原语操作的高可扩展大规模图算法，为实现稀疏矩阵和图算法优化的统一框架提供基础；2）针对稀疏矩阵操作在多核上性能低的问题，研究算法和体系结构特征相结合的自动调优技术，获得可移植性的最优性能；3）针对程序在并行系统上运行时的并行和能耗效率问题，研究自适应的动态优化策略，使得应用程序在不同多核系统上同时获得高并行效率和高能耗效率。通过本项目的研究，为以稀疏矩阵和图为核心的应用提供可移植性的高性能库。

随着多核成为计算机体系结构的主流，影响并行程序执行效率的因素愈加复杂 多样，而日益突出的能耗问题迫使多核系统上优化并行程序需要同时提高并行效率和能耗效 率。考虑到稀疏矩阵和图计算在传统和新兴高性能计算应用中的重要性，同时自适应优化技 术在获得性能可移植性方面将发挥日益重要的作用。本项目研究多核系统上稀疏矩阵和图计算并行程序自适应优化方法的三个重要内容:1)针对图算法并行扩展性差的问题，研究基于稀疏矩阵原语操作的高可扩展大规模图算法，为实现稀疏矩阵和图算法优化的统一框架提供基础;2)针对稀疏矩阵操作在多核上性能低的问题，研究算法和体系结构特征相结合的自动调优技术，获得可移植性的最优性能;3)针对程序在并行系统上运行时的并行和能 耗效率问题，研究自适应的动态优化策略，使得应用程序在不同多核系统上同时获得高并行 效率和高能耗效率。通过本项目的研究，为以稀疏矩阵和图为核心的应用提供可移植性的高性能库，发表了13篇高水平学术论文，包括CCF A类论文4篇。