对角线稀疏矩阵的SpMV自适应性能优化  

Auto-Tuning of SpMV for Diagonal Sparse Matrices

作　　者：孙相征[1,2,3] 张云泉[1,2] 王婷[1,2] 李焱[1,2,3] 袁良[1,2,3] 

机构地区：[1]中国科学院软件所并行软件与计算科学实验室,北京100190 [2]计算机科学国家重点实验室(中国科学院软件研究所),北京100190 [3]中国科学院大学,北京100190

出　　处：《计算机研究与发展》2013年第3期648-656,共9页Journal of Computer Research and Development

基　　金：国家"八六三"高技术研究发展计划基金项目(2009AA01A129;2009AA01A134);国家"核高基"重大科技专项基金项目(2009ZX01036-001-002);中国科学院知识创新工程重大项目课题(KGCX1-YW-13);国家重大科研装备研制项目(ZDYZ2008-2);国家自然科学基金项目(61100073;61133005;61100066);中国科学院研究生科技创新与社会实践资助专项

摘　　要：稀疏矩阵向量乘(SpMV)是科学计算中常用的内核之一,其运行速率跟非零元分布相关.针对对角线稀疏矩阵,提出了压缩行片段对角(compressed row segment diagonal,CRSD)存储格式.它利用"对角线格式"有效描述矩阵的对角线分布,区别于以往通用的计算方法,CRSD通过对给定应用的对角线稀疏矩阵采样再进行特定的优化.并且在软件安装阶段,通过自适应的方法选取适合具体运行平台的最优SpMV实现.在CPU端进行多线程并行化实现时,自适应调优过程中收集的信息还被用于线程间任务划分,以实现负载平衡.同时完成CRSD存储格式在GPU端的实现,并根据GPU端计算与访存的特点进行优化.实验结果表明:在Intel和AMD的多核平台使用相同线程数的情况下,与DIA相比,使用CRSD的加速比可以达到2.37X(平均1.7X);与CSR相比,可以达到4.6X(平均2.1X).SpMV （sparse matrix-vector multiplication） is an important computational kernel in scientific applications. Its performance is mainly affected by the nonzero distribution of sparse matrices. In this paper, we propose a new storage format for diagonal sparse matrices, called CRSD （compressed row segmented with diagonal-pattern）. We design a diagonal pattern to represent the diagonal distribution. Unlike general purpose methods, our CRSD based SpMV implementation is application specific since it needs to sample the sparse matrix of one given application. The optimal implementation is selected automatically for a given hardware platform during the software installation phase. The information collected during auto-tuning process is also utilized for parallel implementation to maintain load-balance. The implementation is also tuned on GPU platform. Experimental results demonstrate that the speedup reaches up to 2.37X（1.7X on average） in comparison with DIA and 4. 6X（2.1X on average） in comparison with CSR under the same number of threads on Intel and AMD platforms.

关 键 词：CRSD 自适应性能优化SpMV 对角线格式 对角线稀疏矩阵 GPU 科学应用 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]