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

Autor: Akbudak, Kadir
Přispěvatelé: Aykanat, Cevdet, Bilgisayar Mühendisliği Anabilim Dalı
Jazyk: angličtina
Rok vydání: 2009
Předmět:
Popis: 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. The sparse matrix-vector multiplication (SpMxV) is an important kernel operationwidely used in linear solvers. The same sparse matrix is multiplied by a dense vec-tor repeatedly in these solvers to solve a system of linear equations. High performancegains can be obtained if we can take the advantage of today?s deep cache hierarchyin SpMxV operations. Matrices with irregular sparsity patterns make it difficult toutilize data locality effectively in SpMxV computations. Different techniques are pro-posed in the literature to utilize cache hierarchy effectively via exploiting data local-ity during SpMxV. In this work, we investigate two distinct frameworks for cache-aware/oblivious SpMxV: single matrix-vector multiply and multiple submatrix-vectormultiplies. For the single matrix-vector multiply framework, we propose a cache-sizeaware top-down row/column-reordering approach based on 1D sparse matrix parti-tioning by utilizing the recently proposed appropriate hypergraph models of sparsematrices, and a cache oblivious bottom-up approach based on hierarchical clusteringof rows/columns with similar sparsity patterns. We also propose a column compres-sion scheme as a preprocessing step which makes these two approaches cache-line-sizeaware. The multiple submatrix-vector multiplies framework depends on the partition-ing the matrix into multiple nonzero-disjoint submatrices. For an effective matrix-to-submatrix partitioning required in this framework, we propose a cache-size awaretop-down approach based on 2D sparse matrix partitioning by utilizing the recentlyproposed fine-grain hypergraph model. For this framework, we also propose a trav-eling salesman formulation for an effective ordering of individual submatrix-vectormultiply operations. We evaluate the validity of our models and methods on a widerange of sparse matrices. Experimental results show that proposed methods and mod-els outperforms state-of-the-art schemes. 70
Databáze: OpenAIRE
Externí odkaz: