Journals / Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen ve Mühendislik Dergisi / 2020 / Cilt: 22 Sayı: 65
Sparse Matrix-Vector Multiplication Based on Duff’s Device
- Pages
- 315–324
- DOI
- —
Abstract
Sparse matrix-vector multiplication (SpMV) is used frequently in several engineering problems and scientific computation. Optimizing SpMV positively impacts a wide range of applications. In this paper, we investigate the effect of a loop-unrolling method known as Duff’s device on the performance of SpMV. The Duff’s device-based SpMV implementation that we propose can be used after a low-cost preprocessing of the CSR representation – the most common sparse matrix storage format – of a matrix. We have evaluated the approach on a dataset consisting of matrices from real-world problems, and observed that substantial speedup can be achieved.
Özet
Seyrek matris-vektör çarpımı (SpMV) pek çok mühendislik probleminde ve bilimsel hesaplamada sıklıkla kullanılan bir işlemdir. SpMV’nin hızlandırılması geniş bir yelpazedeki uygulamaları olumlu etkiler. Bu makalede Duff aygıtı olarak bilinen döngü açılımının SpMV’nin başarımına etkisini irdeliyoruz. Önerdiğimiz Duff aygıtı tabanlı SpMV gerçeklemesi, en geçerli seyrek matris saklama formatı olan CSR formatının düşük maliyetli bir ön işlemesi sonrası kullanılabilmektedir. Gerçek problemlerde kullanılan matrislerden oluşan veri kümesi ile deneysel bir değerlendirme yaptık ve önemli derecede hızlanma kaydedilebileceğini gözlemledik.