高级检索

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

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

    • 摘要: 在科学计算中,稀疏矩阵向量乘(SpMV)是一个十分重要且经常被大量调用的计算内核.由于SpMV一般实现算法的浮点计算和存储访问次数比率非常低,且其存储访问模式极为不规则,其实际运行性能往往很低.通过采用寄存器分块算法和启发式分块大小选择算法,将稀疏矩阵分成小的稠密分块,重用保存在寄存器中向量x元素,可以提高该计算内核的性能.剖析和总结了OSKI软件包所采用的若干关键优化技术,并进行了实际应用性能测试.测试表明,在实际应用这些优化技术的过程中,应用程序对SpMV的调用次数要达到上百次的量级,才能抵消由于应用这些性能优化技术所带来的额外时间开销,取得性能加速效果.在Pentium 4和AMD Athlon平台上,测试了10个矩阵,其平均加速比分别达到了1.69和1.48.

       

      Abstract: 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.

       

    /

    返回文章
    返回