Performance evaluation of unfolded sparse matrix-vector multiplication

Abstract

Sparse matrix-vector multiplication (spMV) is a kernel operation in scientific com- putation. There exist problems where a matrix is repeatedly multiplied by many different vectors. For such problems, specializing the spMV code based on the matrix has the potential of producing significantly faster code. This, in fact, has been one of the motivational examples of program generation. Using program generation, spMV code can be unfolded fully to eliminate loop overheads as well as enable high-impact optimizations. In this work we focus on specialization of spMV by unfolding the code according to a given matrix. We provide an experimental evaluation of performance using 70 sparse matrices collected from real-world scientific computation domains. We present optimizations with which high-performant assembly code can be generated rapidly without having to generate source-level code and go through all the phases of a general-purpose compiler. We finally present how one of the optimizations we studied can be implemented as a code-transforming pass.

Seyrek matris-vektör çarpımı (spMV) bilimsel hesaplamalarda kullanılan, çok temel bir işlemdir. Kimi bilimsel problemlerde aynı matris farklı vektörlerle tekrar tekrar çarpılmaktadır. Bu problemlerde kullanılan spMV kodunu matrise göre özelleşmiş bir şekilde optimize edersek çok ciddi performans artışları sağlanabilir. Bunu gerçekleştirmek için program üretimi teknikleri uygundur. Program üretimi ile spMV kodundaki döngü u yükleri kaldırılabilir, ayrıca etkili eniyilemeler uygulanabilir. Bu çalışmada, spMV kodunun tam döngü açılımı vasıtasıyla çarpımı yapılmak istenen matrise göre özelleştirilmesini inceledik. Gerçek örneklerden oluşan 70 adet matris üzerinde deneysel performans çalışmaları yaptık. Ayrıca, kaynak kod üretimi ve sonrasında genel amaçlı derleyici kullanımına gerek bırakmayacak kadar yüksek kaliteli makine kodunu hızlı bir şekilde ¨üretmemizi sağlayacak eniyilemeler sunuyoruz. Son olarak da, tanımladığımız eniyilemelerden birinin kod dönüşümü şeklinde nasıl tanımlanabileceğini gösteriyoruz.