Volltext-Downloads (blau) und Frontdoor-Views (grau)

SpMV Runtime Improvements with Program Optimization Techniques on Different Abstraction Levels

  • The multiplication of a sparse matrix with a dense vector is a performance critical computational kernel in many applications, especially in natural and engineering sciences. To speed up this operation, many optimization techniques have been developed in the past, mainly focusing on the data layout for the sparse matrix. Strongly related to the data layout is the program code for the multiplication. But even for a fixed data layout with an accommodated kernel, there are several alternatives for program optimizations. This paper discusses a spectrum of program optimization techniques on different abstraction layers for six different sparse matrix data format and kernels. At the one end of the spectrum, compiler options can be used that hide from the programmer all optimizations done by the compiler internally. On the other end of the spectrum, a multiplication kernel can be programmed that use highly sophisticated intrinsics on an assembler level that ask for a programmer with a deep understanding of processor architectures. These special instructions can be used to efficiently utilize hardware features in processors like vector units that have the potential to speed up sparse matrix computations. The paper compares the programming effort and required knowledge level for certain program optimizations in relation to the gained runtime improvements.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Check availability


Show usage statistics
Document Type:Article
Author:Rudolf Berrendorf, Max Weierstall, Florian Mannuss
Parent Title (English):IntSys (International Journal On Advances in Intelligent Systems)
First Page:417
Last Page:429
Date of first publication:2016/12/31
Keyword:OpenMP; Single Instruction Multiple Data (SIMD); Sparse Matrix Vector multiply (SpMV); intrinsics; unrolling; vector units
Departments, institutes and facilities:Fachbereich Informatik
Dewey Decimal Classification (DDC):0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Entry in this database:2017/03/17