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

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

项目编号： No.61272134

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 自动化技术、计算机技术

项目作者： 谭光明

作者单位： 中国科学院计算技术研究所

项目金额： 80万元

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

中文关键词： 并行效率；稀疏矩阵；图；自适应；动态优化

英文摘要： 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 rese

英文关键词： parallel efficiency；sparse matrices；graph；self-adaptive；dynamic optimization