Reordering methods for exploiting spatial and temporal localities in parallel sparse matrix-vector multiplication

Seyrek matris-vektör çarpımı (SyMV), bilimsel uygulamalarda yaygın olarak kullanılan önemli bir çekirdek işlemdir. Düzensiz seyrek matrislerde SyMV işlemi, girdi vektör elemanlarına düzensiz erişim gerçekleştirdiği için önbellek başarımının düşük olmasına neden olmaktadır. Bu çalışmada, SyMv işleminde yüksek başarım elde etmek amacıyla, girdi-vektör elemanlarının erişiminde uzaysal ve zamansal yerellikten yararlanmak için, çizge ve hiper çizge bölümleme yöntemlerine dayanan matris satır ve sütun sıralama yöntemleri önerilmektedir. Bu yon temler, seyreklik örüntüsü benzer olan matris satır ve sütunlarını gruplayarak birbirlerine yakın sıralamaktadırlar. Önerilen çizge ve hiper çizge bölümleme tabanlı uzaysal ve zamansal yerellik sağlama yöntemleri, tek a ̧samada ayrı ayrı kullanılabileceği gibi, tek veya iki aşamada birlikte de kullanılabilmektedirler. Önerilen yöntemlerin başarımı, 60 ̧cekirdekli Xeon-Phi işlemcide, çeşitli uygulamalarda ortaya çıkan geniş bir matris kümesi kullanılarak denenmiştir. Deney sonuçları, önerilen yöntemlerin geçerlilik ve etkinliğini doğrulamaktadırlar.