SpMV的自动性能优化实现技术及其应用研究  

Automatic Performance Tuning of Sparse Matrix-Vector Multiplication:Implementation Techniques and Its Application Research

作　　者：袁娥[1,2,3] 张云泉[1,3] 刘芳芳[1] 孙相征[1,2,3] 

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

出　　处：《计算机研究与发展》2009年第7期1117-1126,共10页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60303020);国家自然科学基金重点项目(60533020);国家"八六三"高技术研究发展计划基金项目(2006AA01A102;2006AA01A125)~~

摘　　要：在科学计算中,稀疏矩阵向量乘(SpMV)是一个十分重要且经常被大量调用的计算内核.由于SpMV一般实现算法的浮点计算和存储访问次数比率非常低,且其存储访问模式极为不规则,其实际运行性能往往很低.通过采用寄存器分块算法和启发式分块大小选择算法,将稀疏矩阵分成小的稠密分块,重用保存在寄存器中向量x元素,可以提高该计算内核的性能.剖析和总结了OSKI软件包所采用的若干关键优化技术,并进行了实际应用性能测试.测试表明,在实际应用这些优化技术的过程中,应用程序对SpMV的调用次数要达到上百次的量级,才能抵消由于应用这些性能优化技术所带来的额外时间开销,取得性能加速效果.在Pentium4和AMD Athlon平台上,测试了10个矩阵,其平均加速比分别达到了1.69和1.48.Sparse matrix-vector multiplication （SpMV） is an important computational kernel in scientific computing applications that tends to perform poorly on modern processors with deep memory hierarchy due to its low ratio of the number of floating point operations to the number of memory accesses, and its irregular memory access patterns. Register-level blocking algorithm and heuristic block-size selection algorithm store a sparse matrix as a sequence of small dense blocks and re-organize the computation sequence to compute each block before moving on to the next, thus reuse the elements of vector x to optimize the performance of SpMV. Several key optimization techniques adopted in OSKI software package are analyzed and summarized, and real matrix data performance testing on them is performed. The performance testing indicates that to realize the performance speedup goal of these optimization techniques, the calling times of SpMV kernel must be around 100 times to amortize the overhead of performance optimization. Ten real matrices are tested to compare the performance of the heuristic-register blocking algorithm with the general algorithm. The average speedups are 1.69 on Pentium 4 platform and 1.48 on AMD Athlon platform.

关 键 词：稀疏矩阵向量乘 启发式算法 自适应性能优化 存储访问模式 寄存器分块 

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