面向异构计算平台的SpMV划分优化算法研究  

An SpMV partitioning and optimization algorithm on heterogeneous computing platforms

作　　者：谈兆年 计卫星[1] Akrem Benatia 高建花 李安民 王一拙[1] TAN Zhao-nian;JI Wei-xing;AKREM Benatia;GAO Jian-hua;LI An-min;WANG Yi-zhuo(School of Computer Science and Technology,Beijing Institute of Technology,Beijing 100081,China)

机构地区：[1]北京理工大学计算机学院,北京100081

出　　处：《计算机工程与科学》2019年第4期590-597,共8页Computer Engineering & Science

摘　　要：稀疏矩阵向量乘SpMV在科学计算和工程问题中有着广泛的应用。稀疏矩阵的非零元素分布会极大地影响SpMV的计算效率,针对不同的数据分布模式使用特定算法进行加速可以获得显著的性能提升。CPU的控制能力强,适用于通用计算,而GPU的计算核心多,并行度高,适用于数据密集型计算。根据CPU和GPU的不同特点,充分发挥二者的优势,可以使SpMV获得更大的性能提升。研究CPU-GPU混合架构上SpMV的任务划分与优化方法,针对2种主要的稀疏矩阵数据分布模式:Quasi-diagonal和Tetris,提出了一种基于SVR的任务二次分配算法。研究的2种稀疏矩阵模式具有很好的代表性,在实际科学工程应用中占比达到66%。实验评测结果表明,采用本文的算法之后,与GPU相比,异构平台上Quasi-diagonal和Tetris的加速比平均值分别达到1.74×和2.15×。Sparse matrix vector multiplication SpMV is widely used in solving scientific computing and engineering problems. The distribution of non-zero elements of the sparse matrix can greatly affect the computational efficiency of SpMV, and significant performance improvements can be achieved by using specific algorithms for different data distribution patterns. CPU has strong controllability which enables its application in general-purpose computing while GPU has high degree of parallelism and many cores, thus suitable for data-intensive computing. Taking advantage of the two can gain greater performance for SpMV. We study the task partitioning and optimization methods of SpMV on CPU-GPU hybrid architecture and propose a task-based rescheduling algorithm based on SVR for two main data distribution patterns: Quasi-diagonal and Tetris. The two representative sparse matrix patterns account for 66% of the data in practical scientific and engineering applications. Experimental results show that our approach can achieve an average speedup of 1.74x and 2.15x for Quasi-diagonal and Tetris on heterogeneous platforms over on GPU respectively.

关 键 词：异构计算 矩阵划分 协同优化 SVR SpMV 

分 类 号：O246[理学—计算数学]