Geri Dön

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

Paralel seyrek matris vektör çarpımında uzaysal ve zamansal yerelliği kullanmak için sıralma yöntemleri

PDF İndir

  1. Tez No: 436336
  2. Yazar: NABIL F. T. ABUBAKER
  3. Danışmanlar: PROF. DR. CEVDET AYKANAT
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Seyrek matrisler, Sparse matrixes
  7. Yıl: 2016
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: Belirtilmemiş.

Özet

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.

Özet (Çeviri)

Sparse Matrix-Vector multiplication (SpMV) is a very important kernel opera- tion for many scientific applications. For irregular sparse matrices, the SpMV operation suffers from poor cache performance due to the irregular accesses of the input vector entries. In this work, we propose row and column reordering methods based on Graph partitioning (GP) and Hypergraph partitioning (HP) in order to exploit spatial and temporal localities in accessing input vector entries by clustering rows/columns with a similar sparsity pattern close to each other. The proposed methods exploit spatial and temporal localities separately (using either rows or columns of the matrix in a GP or HP method), simultaneously (using both rows and column) and in a two-phased manner(using either rows or columns in each phase). We evaluate the validity of the proposed models on a 60- core Xeon Phi co-processor for a large set of sparse matrices arising from different applications. The performance results confirm the validity and the effectiveness of the proposed methods and models.

Geri Dön