Cache locality exploiting methods and models for sparse matrix-vector multiplication

Seyrek matrix-vektör çarpımı doğrusal denklem sistemi çözen yazılımlarda çok önemli bir çekirdek işlemdir.Aynı seyrek matris, seyrek olmayan bir vektörle çok defa çarpılır.Şu anki teknolojinin sunduğu çok seviyeli önbellekler etkin kullanılırsa, bu çarpma işlemi sırasında önemli performans kazançları olabilmektedir.Lakin düzensiz veri erişimine neden olan matrisler önbellekteki veri yerelliğinin kullanımını olumsuz etkilemektedir.Bu problemi çözmek için önbellek yerelliğini kullanan pek çok yöntem şu zamana kadar sunulmuştur.Bu çalışmada, biz de iki farklı çerçeve sunuyoruz: tek matris-vektor çarpımı ve çoklu matris-vektor çarpımı.Tek matris-vektör çarpımı çerçevesinde, önbelleğin boyutunu dikkate alarak matrisin satır ve sütunlarını yeniden sıralayan ve bu sıralam işlemini hiperçizge bölümleme ile yapan bir yöntem sunuyoruz.Ve bu yöntemlere ek olarak önbelleğin boyutunu dikkate almadan yerelliği sağlayacak bir yöntem öneriyoruz.Bir de sutunları sıkıştırıp alansal yerelliği sağlayan önişleme yöntemi sunuyoruz.Çoklu matris-vektör çarpımı çerçevesinde, matrisi alt matrislere ayırarak veri yerelliğini sağlamaya çalışmayı hedefliyoruz.Yine bu ayırma işleminde de hiperçizge kullanılıyor.Alt matrislerin çarpma sırası da önem taşıdığından veri yerelliğini arttıran bir sıralamayı bulma problemini de seyyar satıcı problemi olarak çözülebileceğini açıklıyoruz.Deneysel sonuçlar bu önerilen çerçeve ve yöntemlerin şu anda kullanılan yöntemlerden daha hızlı çalıştığını göstermektedir.